ポイントがポリゴンの内部にあるかどうかを確認する

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 

更新：バグを修正しました