点随机形状的多边形？ [英] Point in random-shape polygon?

问题描述

我们可以很容易地确定一个点是在凸多边形著名的光线投射算法。

One can easily determine if a point is in a convex polygon with the famous Ray Casting Algorithm.

def point_inside_polygon(x, y, poly):
    """ Deciding if a point is inside (True, False otherwise) a polygon,
    where poly is a list of pairs (x,y) containing the polygon's vertices.
    The algorithm is called the 'Ray Casting Method' """
    n = len(poly)
    inside = False
    p1x, p1y = poly[0]
    for i in range(n):
        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) / (p2y-p1y) + p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x, p1y = p2x, p2y
    return inside

但是，如果多边形不是完全凸？

But what if the polygon is not completely convex?

我怎么可能确定一个点是否在随机形状多边形给出的边界点？

How may I determine whether a point is in a random-shape polygon given the boundary points?

说我有边界点的多边形像这样

Say I have a polygon of boundary points like so

我怎么可以这样做呢？

最好的，如果在Python，但任何通用的解决方案也受到了欢迎。

Best if in Python, but any generic solutions are also welcomed.

推荐答案

其实，光线投射方法将工作，如果你使用 非零绕数规则，而不是普通的奇偶规则

Actually the ray casting method will work if you use a nonzero winding number rule instead of the common even-odd rule.

这是它在解释的方式，Adobe公司的 PostScript语言参考的（这里所说的道是指多边形顶点定义多边形的列表）。

This is the way it's explained in the Adobe's Postscript Language Reference (where the word "path" means the list of polygon vertices defining the polygon).

非零绕数规则确定一个给定的点是否   通过概念上画一个线，从该点的路径内   无穷大在任何方向，然后检查地方一个   路径段穿过线。为0时，开始计数   规则增加了1每个路径段自左而越过线时间   权利，每个从右到左段跨越时间中减去1。   计数所有的交叉点，如果结果是0，则该点是后   外的路径;否则是内

The nonzero winding number rule determines whether a given point is inside a path by conceptually drawing a ray from that point to infinity in any direction and then examining the places where a segment of the path crosses the ray. Starting with a count of 0, the rule adds 1 each time a path segment crosses the ray from left to right and subtracts 1 each time a segment crosses from right to left. After counting all the crossings, if the result is 0 then the point is outside the path; otherwise it is inside.

这篇关于点随机形状的多边形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！