Qual é a maneira mais eficiente de encontrar a interseção de uma linha e um círculo em python?
Eu tenho um polígono consiste em muitos pontos. Quero encontrar a interseção do polígono e um círculo. Fornecendo o centro do círculo de [x0, y0] e o raio de r0, escrevi uma função aproximada para simplesmente resolver a equação quadrática do círculo e uma linha. Mas e quanto à eficiência de encontrar a interseção de cada segmento de linha do polígono, um por um?Existe maneira mais eficiente?
Eu sei que o sympy já fornece o recurso para obter as interseções de geometria diferente. Mas tambéme quanto à eficiência da biblioteca externa, como o sympy, em comparação com o cálculo por minha própria função, se eu quiser lidar com muitos polígonos?
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