python - 凹多边形内部和外部的线段有什么区别？

Question

我的问题是关于在具有多个凸面和凹面多边形的表面中创建可见性图。我的问题是我无法分类连接同一多边形节点的线段是通过还是不通过该多边形。如下图所示：

我需要将橙色的无效行与蓝色的有效行分开。我希望有人可以使用可以在 python 中实现的合适算法为我提供解决此问题的方法。

或者更复杂的多边形？： 困难的多边形

Answer 1

此代码接受 A 和 B 作为两个顶点，并检查连接它们的线是否完全位于多边形内部、部分内部或完全外部。这是基于数学事实，即与 eqn 的一条线。F(X,y):Ax+By+C 如果 F(x1,y1)=0 点 x1,y1 将位于直线上 如果 F(x1,y1)>0 在直线的一侧如果 F(x1,y1)<0

L=[] #list of all the vertices of the polygon as (x,y) tuples in order
A=() 
B=()
# A and B are tuples of coordinates of points joking diagonal to check
def eqn(A,B):
    X1=A[0];Y1=A[1]
    X2=B[0];Y2=B[1]
return(X2-X1,Y1-Y2,X1*Y2-X2*Y1)
def check(Y,X,C,y,x):
    if(Y*y+X*X+C>0):
          return 1
    elif(Y*y+X*X+C<0):
          return -1
    else:
          return 0

Y,X,C=eqn(A,B)
#get parameters of diagonal joining A and B
a=L.index(A)
b=L.index(B)
L1=[]
L2=[]
if(a>b):
     L1=L[b+1:a]
     L2=L[a+1:]+L[:b]
elif(b>a):
     L1=L[a+1:b]
     L2=L[b+1:]+L[:a]
#so I have split the list into two lists L1 and L2 containing vertices in cyclic order on either side of the diagonal
k=1
m=0
val1=check(Y,X,C,L1[0][1],L1[0][0])
val2=check(Y,X,C,L2[0][1],L2[0][0])
if(val1==val2):
    k=0
    m=1
else:
# I have to check F(x,y) for each point in list L1 and L2 it should be of one sign for all elements in L1 and of other sign for all elements in L2 for line to lie completely inside polygon
    for t in L1:
        if(check(Y,X,C,t[1],t[0])!=val1):
          k=0
          m=0
    for s in L2:
        if(check(Y,X,C,s[1],s[0])!=val2):
           k=0
           m=0
if(k==0):
     print('the diagonal passes outside')
else:
     print('the diagonal lies completely inside the polygon')
if(m==1):
     print('the diagonal lies completely outside the polygon')

我已经编写了代码，希望它能按要求工作，但可能存在错误：o，逻辑是正确的，可能有语法或其他错误你必须注意（我可以在这种情况下提供帮助）我已经排除了一种情况，如果选择的两个点是连续的，那么它显然是多边形的边（检查起来很简单）。