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

Question

My question is about the creation of visibility graphs in surfaces with multiple convex and concave polygons. My problem is that i am not able to classify whether the line segments connecting the nodes of the same polygon go through or don't go through this polygon. As seen in the picture below:

I'd need to separate the orange, invalid lines from the blue, valid lines. I hope somebody can provide me a solution to this problem with a suitable algorithm that can be implemented in python.

Or for even complexer polygons?: difficult polygon

Answer 1

This code accepts A and B as two vertices and checks if the line joining them lies completely inside , partially inside or completely outside the polygon. This is based on mathematical fact that for a line with eqn. F(X,y):Ax+By+C the point x1,y1 will lie on the line if F(x1,y1)=0 On one side of line if F(x1,y1)>0 On other side of line if 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')

I have written the code hope it works as required,but there maybe errors:o,the logic is correct,there may be syntax or other errors you have to take care of(I can help in that case) I have excluded one case if the two points chosen are consecutive,then it is obviously the side of the polygon(trivial to check).