폴리 라인을 파이썬을 사용하여 교차하는지 테스트하십시오.

Question

라이브러리를 사용하지 않고 두 폴리 라인이 교차하는지 테스트 할 간단한 솔루션이 있습니까?

같은

PL1 = ((-1, -1), (1, -1), (1, 2)), PL2 = ((0, 1), (2, 1)) 

PL1.intersect(PL2) 

나는 단지 2 점 라인에 대한 해결책을 찾을 수 있어요.

Answer 1

주석에서 언급했듯이 폴리곤의 모든 구성 요소 선 사이에 선 교차점 (this for example)의 전통적인 알고리즘을 적용 할 수 있습니다. 예 :

def line_intersection(line1, line2): 
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0]) 
    ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1]) 

    def det(a, b): 
     return a[0] * b[1] - a[1] * b[0] 

    div = det(xdiff, ydiff) 
    if div == 0: 
     return None 

    d = (det(*line1), det(*line2)) 
    x = det(d, xdiff)/div 
    y = det(d, ydiff)/div 
    return x, y 

def poly_intersection(poly1, poly2): 

    for i, p1_first_point in enumerate(poly1[:-1]): 
     p1_second_point = poly1[i + 1] 

     for j, p2_first_point in enumerate(poly2[:-1]): 
      p2_second_point = poly2[j + 1] 

      if line_intersection((p1_first_point, p1_second_point), (p2_first_point, p2_second_point)): 
       return True 

    return False 

PL1 = ((-1, -1), (1, -1), (1, 2)) 
PL2 = ((0, 1), (2, 1)) 

print poly_intersection(PL1, PL2)