В чем разница между отрезком внутри и снаружи вогнутого многоугольника? - PullRequest
Новая
       64

В чем разница между отрезком внутри и снаружи вогнутого многоугольника?

2 голосов
/ 24 марта 2019

Мой вопрос касается создания графов видимости на поверхностях с несколькими выпуклыми и вогнутыми многоугольниками. Моя проблема в том, что я не могу классифицировать, проходят ли отрезки, соединяющие узлы одного и того же многоугольника, или нет через этот многоугольник. Как видно на рисунке ниже:

example

Мне нужно отделить оранжевые недействительные строки от синих допустимых строк. Я надеюсь, что кто-нибудь может дать мне решение этой проблемы с помощью подходящего алгоритма, который может быть реализован на python.

Или для еще более сложных полигонов ?: сложный многоугольник

1 Ответ

0 голосов
/ 24 марта 2019

this image explains the three cases Этот код принимает A и B как две вершины и проверяет, лежит ли соединяющая их линия полностью внутри, частично внутри или полностью вне многоугольника.Это основано на математическом факте, что для строки с уравнением.F (X, y): Ax + By + C точка x1, y1 будет лежать на прямой, если F (x1, y1) = 0 на одной стороне линии, если F (x1, y1)> 0 на другой стороне линииесли F (x1, y1) <0 </p> 

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 логика верна, возможно, у вас есть синтаксис или другие ошибкичтобы позаботиться (я могу помочь в этом случае) Я исключил один случай, если две выбранные точки являются последовательными, то это, очевидно, сторона многоугольника (тривиально проверить).

...