Площадь пересечения в Python

У меня есть код, который принимает условие C в качестве входных данных и вычисляет решение моей проблемы как «разрешенную область» A в пространстве (x, y). Эта область состоит из нескольких «трубок», которые определяются двумя линиями, которые никогда не могут пересекаться.

Конечный результат, который я ищу, должен удовлетворять k условиям {C1, .., Ck} и поэтому является пересечением S между k областями {A1, .., Ak}.

Вот пример с 2 условиями (A1: зеленый, 3 пробирки. A2: фиолетовый, 1 пробирка); решение S в красном.

Как я могу найти S, когда я имею дело с 4 областями по 10 пробирок в каждой? (Финальный сюжет ужасен!)

Мне нужно было бы иметь возможность построить ее и найти среднюю координату и дисперсию точек в S (дисперсия каждой координаты). [Если есть эффективный способ узнать, принадлежит ли точка P к S или нет, я просто воспользуюсь методом Монте-Карло].

В идеале я также хотел бы иметь возможность реализовать «запрещенные трубки», которые я бы удалил из S [это может быть немного сложнее, чем пересечение S с внешней частью моей запрещенной области, поскольку две трубки из одной и той же области могут пересекаться (даже если линии, определяющие трубу, никогда не пересекаются).

Замечания:

Код также хранит длину дуги линий.

Линии хранятся в виде массивов точек (около 1000 точек на линию). Две линии, определяющие трубу, не обязательно имеют одинаковое количество точек, но Python может интерполировать ВСЕ из них как функцию их длины дуги за 1 секунду.

Линии являются параметрическими функциями (то есть мы не можем написать y = f (x), поскольку линии могут быть вертикальными).

Сюжет был отредактирован краской, чтобы получить правильный результат ... Не очень эффективно!

Редактировать:

Я не знаю, как я могу использовать plt.fill_between для многократного пересечения (я могу сделать это здесь для 2 условий, но мне нужен код, чтобы сделать это автоматически, когда слишком много строк для оценки зрения).

Пока я просто генерирую строки. Я ничего не написал для поиска окончательного решения, так как совершенно не знаю, какая структура наиболее приспособлена для этого. [Тем не менее, предыдущая версия кода смогла найти точки пересечения между линиями двух разных труб, и я планировал передать их в виде многоугольников, но это подразумевало несколько других проблем ...]

Я не думаю, что смогу сделать это сsets: сканирование всей (x, y) области с требуемой точностью представляет около 6e8 точек ... [Линии имеют только 1e3 точки благодаря переменному размеру шага (адаптируется к кривизне), но вся проблема довольно велика]

 Imanol Luengo01 июн. 2016 г., 11:49
Если вы можете параметризовать уравнения труб (например, труба 1 ->y = x + x^2 - 5) вы можете решить проблему, используя стандартные инструменты оптимизации. Если у вас есть линии, представленные точками, вы, вероятно, можете аппроксимировать линии полиномами, а затем использовать оптимизацию, чтобы найти область. Это неочень просто проблема, хотя, но выполнима.
 tfv01 июн. 2016 г., 11:14
Посмотрите наСтройная библиотека который помогает решить такие проблемы:pypi.python.org/pypi/Shapely
 Serenity01 июн. 2016 г., 10:52
Посмотрите на примеры наmatplotlib.org/examples/pylab_examples/fill_between_demo.html
 Phlya01 июн. 2016 г., 10:44
К вашему последнему замечанию - вы можете сделать это, используя plt.fill_between (или plt.fill)
 Dilettant01 июн. 2016 г., 10:44
Не могли бы вы добавить некоторый код к вопросу, который показывает, где вы находитесь в процессе реализации, чтобы те, кто хочет помочь, получили более конкретное представление, где вы можете застрять и что они знают лучше всего? Это было бы прекрасно. Благодарю.
 machine yearning01 июн. 2016 г., 10:50
Просто идея, не глядя слишком внимательно, если вы можете рассчитать каждую трубку какset очков, то вы могли бы сделатьset пересечение между каждой парой трубок, чтобы получить что-то полезное для желаемого результата.

Ответы на вопрос(1)

Решение Вопроса

Проблема решена с Shapely!

Я определил каждую трубку какPolygonи область А являетсяMultiPolygon Объект построен как союз его труб.

intersection Затем метод вычисляет решение, которое я искал (перекрытие между всеми областями).

Все это почти мгновенно. Я не знал, что форма была так хороша для больших объектов [около 2000 точек на трубу, 10 труб на область, 4 области].

Спасибо за помощь! :)

Редактировать:

Рабочий пример.

import matplotlib.pyplot as plt
import shapely
from shapely.geometry import Polygon
from descartes import PolygonPatch
import numpy as np

def create_tube(a,height):
    x_tube_up = np.linspace(-4,4,300)
    y_tube_up = a*x_tube_up**2 + height
    x_tube_down = np.flipud(x_tube_up)          #flip for correct definition of polygon
    y_tube_down = np.flipud(y_tube_up - 2)

    points_x = list(x_tube_up) + list(x_tube_down)
    points_y = list(y_tube_up) + list(y_tube_down)

    return Polygon([(points_x[i], points_y[i]) for i in range(600)])

def plot_coords(ax, ob):
    x, y = ob.xy
    ax.plot(x, y, '+', color='grey')


area_1 = Polygon()          #First area, a MultiPolygon object
for h in [-5, 0, 5]:
    area_1 = area_1.union(create_tube(2, h))

area_2 = Polygon()
for h in [8, 13, 18]:
    area_2 = area_2.union(create_tube(-1, h))

solution = area_1.intersection(area_2)      #What I was looking for

##########  PLOT  ##########

fig = plt.figure()
ax = fig.add_subplot(111)

for tube in area_1:
    plot_coords(ax, tube.exterior)
    patch = PolygonPatch(tube, facecolor='g', edgecolor='g', alpha=0.25)
    ax.add_patch(patch)

for tube in area_2:
    plot_coords(ax, tube.exterior)
    patch = PolygonPatch(tube, facecolor='m', edgecolor='m', alpha=0.25)
    ax.add_patch(patch)

for sol in solution:
    plot_coords(ax, sol.exterior)
    patch = PolygonPatch(sol, facecolor='r', edgecolor='r')
    ax.add_patch(patch)

plt.show()

И сюжет:

 nicoguaro02 июн. 2016 г., 06:05
Можете ли вы опубликовать рабочий пример вашего решения? Кстати, вы можете выбрать свой ответ в качестве решения.

Ваш ответ на вопрос