Python выражает набор в виде суммы / разности других наборов - PullRequest
Новая
       36

Python выражает набор в виде суммы / разности других наборов

0 голосов
/ 07 июня 2018

Я использую python для реализации решения геометрических задач, таких как: [геометрическая задача, где требуется выразить заштрихованную область как сумму / разницу форм на рисунке]

В этой задаче необходимо выразить заштрихованную область как сумму / разность форм и соответственно рассчитать площадь.

Например,

Заштрихованная область = субрегион A + C+ E

Большой полукруг = A + B + C

Малый полукруг = C + D + E

Треугольник = B + C + D

Отсюда, заштрихованная область = A + B + C + (C + D + E) - (B + C + D)

Следовательно, для решения таких задач мне нужен алгоритм, который может выразить набор запросов, состоящий изсубрегионов (A, C, E ....) как сумма или разность (не требуется объединение или пересечение) ряда shape наборов в словаре (например, B, C, D)

Я намерен сделать это методом грубой силы (пробуя все комбинации всех обнаруженных фигур), однако, когда фигура усложняетсяЭд, как здесь, Рисунок с множеством маленьких фигур , сложность может выйти из-под контроля.

Есть ли эффективный способ решения этой проблемы?

Большое спасибо

1 Ответ

0 голосов
/ 07 июня 2018

Вы просто должны решить это уравнение: 

A + C + E = x(A + B + C) + y(C + D + E) + z(B + C + D)

Примерно так:

A + C + E = A * (x) + B * (x + z) + C* (y + z) + D * (z + y) + E * (y)

A * (x - 1) + B * (x + z) + C * (x + y + z- 1) + D * (z + y) + E * (y - 1) = 0

Поскольку A, B, C, D и E всегда не равны нулю, поэтому имеем: 

x - 1 = 0
x + z = 0
x + y + z - 1 = 0
z + y = 0
y - 1 = 0

Что дает y = 1, z = -1 и x = 1 или

A + C + E = (A + B + C) + (C + D + E) - (B + C + D).

Так что теперь мы просто должны сделать то же самое в Python. 

import numpy as np

shadow = [1,0,1,0,1]
big_circle = [1,1,1,0,0]
small_circle = [0,0,1,1,1]
triangle = [0,1,1,1,0]
universe = [big_circle, small_circle, triangle]
print("shadow : " + str(shadow) )
print("universe : " + str(universe) )
variables = [0] * len(universe)
equations = []
for key in zip(*universe):
    equations.append(list(key))
print("equations : " + str(equations) )
a = np.array(equations)
b = np.array(shadow)
x = np.linalg.lstsq(a,b)
print("Result: \n" )
print( str(x[0]) )

Вот что вы получите: 

shadow : [1, 0, 1, 0, 1]
universe : [[1, 1, 1, 0, 0], [0, 0, 1, 1, 1], [0, 1, 1, 1, 0]]
equations : [[1, 0, 0], [1, 0, 1], [1, 1, 1], [0, 1, 1], [0, 1, 0]]
Result: 

[ 1.  1. -1.]

Если вы сделаете это для других настроек и получите нецелочисленный результат, то заштрихованную область невозможно будет создать как комбинацию фигур, предоставленных программой.

...