Каков наиболее эффективный способ найти пересечение линии и круга в python?

У меня многоугольник состоит из множества точек. Я хочу найти пересечение многоугольника и круга. Предоставляя центр окружности [x0, y0] и радиус r0, я написал грубую функцию, чтобы просто решить квадратичное уравнение круга и прямой. Но как насчет эффективности найти пересечение каждого отрезка многоугольника один за другим? Есть ли более эффективный способ?

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

def LineIntersectCircle(p,lsp,lep):
# p is the circle parameter, lsp and lep is the two end of the line
  x0,y0,r0 = p
  x1,y1 = lsp
  x2,y2 = esp
  if x1 == x2:
    if abs(r0) >= abs(x1 - x0):
        p1 = x1, y0 - sqrt(r0**2 - (x1-x0)**2)
        p2 = x1, y0 + sqrt(r0**2 - (x1-x0)**2)
        inp = [p1,p2]
        # select the points lie on the line segment
        inp = [p for p in inp if p[1]>=min(y1,y2) and p[1]<=max(y1,y2)]
    else:
        inp = []
  else:
    k = (y1 - y2)/(x1 - x2)
    b0 = y1 - k*x1
    a = k**2 + 1
    b = 2*k*(b0 - y0) - 2*x0
    c = (b0 - y0)**2 + x0**2 - r0**2
    delta = b**2 - 4*a*c
    if delta >= 0:
        p1x = (-b - sqrt(delta))/(2*a)
        p2x = (-b + sqrt(delta))/(2*a)
        p1y = k*x1 + b0
        p2y = k*x2 + b0
        inp = [[p1x,p1y],[p2x,p2y]]
        # select the points lie on the line segment
        inp = [p for p in inp if p[0]>=min(x1,x2) and p[0]<=max(x1,x2)]
    else:
        inp = []
  return inp

Ответы

Ответ 1

Я думаю, может быть, ваш вопрос в том, как теоретически делать это самым быстрым образом. Но если вы хотите сделать это быстро, вы действительно должны использовать что-то, написанное на C/С++.

Я довольно привык к Shapely, поэтому я приведу пример того, как это сделать с этой библиотекой. Для python существует множество библиотек геометрии. Я перечислил их в конце этого ответа.

from shapely.geometry import LineString
from shapely.geometry import Point

p = Point(5,5)
c = p.buffer(3).boundary
l = LineString([(0,0), (10, 10)])
i = c.intersection(l)

print i.geoms[0].coords[0]
(2.8786796564403576, 2.8786796564403576)

print i.geoms[1].coords[0]
(7.121320343559642, 7.121320343559642)

Что является немного противоположным интуитивным в Shapely, так это то, что круги являются границами точек с буферными областями. Вот почему я делаю p.buffer(3).boundry

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

Существует fooobar.com/questions/78969/..., который подробно рассказывает об этих библиотеках для заинтересованных.

ИЗМЕНИТЬ, потому что комментарии:

Shapely основан на GEOS (trac.osgeo.org/geos), который построен на С++ и значительно быстрее, чем все, что вы пишете в python. SymPy, похоже, основан на mpmath (mpmath.org), который также кажется python, но, похоже, в него встроена довольно сложная математика. Реализация этого может потребовать много работы и, вероятно, будет не так быстро, как реализация GEOS С++.

Ответ 2

Низкозатратное пространственное разбиение может состоять в том, чтобы разделить плоскость на 9 частей

Вот дрянная диаграмма. Представьте, если вы хотите, что линии просто касаются круга.

  | |
__|_|__
__|O|__
  | |
  | |

8 интересующих нас областей окружают круг. Квадрат в центре не очень полезен для дешевого теста, но вы можете поместить квадрат r/sqrt(2) внутри круга, поэтому его углы просто касаются круга.

Давайте назовите области

A |B| C
__|_|__
D_|O|_E
  | |
F |G| H

И квадрат r/sqrt(2) в центре мы будем называть J

Назовем множество точек в центральном квадрате, показанных на диаграмме, которые не находятся в J, Z

Назовите каждую вершину многоугольника буквенным кодом.

Теперь мы можем быстро увидеть

AA => Outside
AB => Outside
AC => Outside
...
AJ => Intersects
BJ => Intersects
...
JJ => Inside

Это может превратиться в таблицу поиска

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

Ответ 3

Я думаю, что формулу, которую вы используете, чтобы найти координаты двух пересечений, не может быть оптимизирована дальше. Единственное улучшение (которое является численно важным) заключается в том, чтобы различать два случая: |x_2-x_1| >= |y_2-y_1| и |x_2-x1| < |y_2-y1|, так что величина k всегда находится между -1 и 1 (при вычислении вы можете получить очень большие числовые ошибки, если | x_2-x_1 | очень мало). Вы можете поменять местами x-s и y-s, чтобы уменьшить один случай до другого.

Вы также можете выполнить предварительную проверку: если обе оконечные точки являются внутренними по отношению к кругу, пересечение отсутствует. Вычисляя квадрат расстояния от точек до центра круга, это становится простой формулой, которая не использует функцию квадратного корня. Другая проверка: "ли линия вне круга" уже реализована в вашем коде и соответствует delta < 0. Если у вас много мелких сегментов, в большинстве случаев эти две проверки должны дать короткий ответ (без перекрестка).