У меня многоугольник состоит из множества точек. Я хочу найти пересечение многоугольника и круга. Предоставляя центр окружности [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
