포인트가 다각형 파이썬 내부에 ​​있는지 확인

Question

주어진 포인트 (x, y)가 n * 2 배열의 폴리곤에 있는지 감지하려고합니다. 그러나 다각형의 테두리에있는 일부 지점은 포함하지 않는 것으로 보입니다.

def point_inside_polygon(x,y,poly): 

    n = len(poly) 
    inside =False 

    p1x,p1y = poly[0] 
    for i in range(n+1): 
     p2x,p2y = poly[i % n] 
     if y > min(p1y,p2y): 
      if y <= max(p1y,p2y): 
       if x <= max(p1x,p2x): 
        if p1y != p2y: 
         xinters = (y-p1y)*(p2x-p1x)/float((p2y-p1y))+p1x 
        if p1x == p2x or x <= xinters: 
         inside = not inside 
     p1x,p1y = p2x,p2y 

    return inside 

Answer 1

하면 작은 음성 및 양성 반경 (소 트릭)와 matplotlib.path에서 contains_point 함수를 사용할 수있다. 이런 식으로 뭔가 :

import matplotlib.path as mplPath 
import numpy as np 

crd = np.array([[0,0], [0,1], [1,1], [1,0]])# poly 
bbPath = mplPath.Path(crd) 
pnts = [[0.0, 0.0],[1,1],[0.0,0.5],[0.5,0.0]] # points on edges 
r = 0.001 # accuracy 
isIn = [ bbPath.contains_point(pnt,radius=r) or bbPath.contains_point(pnt,radius=-r) for pnt in pnts] 

결과는

[True, True, True, True] 

기본적으로

(또는 r=0)이다 국경에있는 모든 포인트는 포함되어 있지 않습니다, 그 결과는 다음

[False, False, False, False] 

Answer 2

인이다 가장자리가 포함 된 올바른 코드 :

def point_inside_polygon(x, y, poly, include_edges=True): 
    ''' 
    Test if point (x,y) is inside polygon poly. 

    poly is N-vertices polygon defined as 
    [(x1,y1),...,(xN,yN)] or [(x1,y1),...,(xN,yN),(x1,y1)] 
    (function works fine in both cases) 

    Geometrical idea: point is inside polygon if horisontal beam 
    to the right from point crosses polygon even number of times. 
    Works fine for non-convex polygons. 
    ''' 
    n = len(poly) 
    inside = False 

    p1x, p1y = poly[0] 
    for i in range(1, n + 1): 
     p2x, p2y = poly[i % n] 
     if p1y == p2y: 
      if y == p1y: 
       if min(p1x, p2x) <= x <= max(p1x, p2x): 
        # point is on horisontal edge 
        inside = include_edges 
        break 
       elif x < min(p1x, p2x): # point is to the left from current edge 
        inside = not inside 
     else: # p1y!= p2y 
      if min(p1y, p2y) <= y <= max(p1y, p2y): 
       xinters = (y - p1y) * (p2x - p1x)/float(p2y - p1y) + p1x 

       if x == xinters: # point is right on the edge 
        inside = include_edges 
        break 

       if x < xinters: # point is to the left from current edge 
        inside = not inside 

     p1x, p1y = p2x, p2y 

    return inside 

업데이트 : 버그 수정