擅长:python、mysql、java
<p>步骤:</p>
<ul>
<li>迭代多边形中的所有线段</li>
<li>检查它们是否与沿x递增方向的射线相交</li>
</ul>
<p>使用<a href="https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect">This SO Question</a>中的<code>intersect</code>函数</p>
<pre><code>def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)
# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def point_in_polygon(pt, poly, inf):
result = False
for i in range(len(poly.corners)-1):
if intersect((poly.corners[i].x, poly.corners[i].y), ( poly.corners[i+1].x, poly.corners[i+1].y), (pt.x, pt.y), (inf, pt.y)):
result = not result
if intersect((poly.corners[-1].x, poly.corners[-1].y), (poly.corners[0].x, poly.corners[0].y), (pt.x, pt.y), (inf, pt.y)):
result = not result
return result
</code></pre>
<p>请注意,<code>inf</code>参数应该是图形中x轴上的最大点。</p>