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

Question

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

我需要将橙色的无效行与蓝色的有效行分开。我希望有人可以为我提供一个可以在 python.

中实现的合适算法来解决这个问题

或者更复杂的多边形？： difficult polygon

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')

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

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

What is the difference between a line segment inside and outside of a concave polygon?

python

graph

geometry

polygon

concave