如何测试一个点是否在2D整数坐标中的凸多边形内？ [英] How to test if a point is inside of a convex polygon in 2D integer coordinates?

问题描述

多边形以Vector2I对象（2维，整数坐标）的列表形式给出。我如何测试给定的点是否在里面？我在网上找到的所有实现都会因为一些微不足道的反例而失败。这似乎很难写出正确的实现。这个语言并不重要，因为我将自己移植它。

解决方案

如果它是凸的，检查它的一个微不足道的方法是这个点位于所有分段的同一侧（如果以相同的顺序遍历）。

您可以使用交叉产品轻松检查它（因为它是成比例的到区段和点之间形成的角度的余弦，那些带有正号的将位于右侧，而在左侧则为负号）。

这里是Python中的代码：

  RIGHT =RIGHT
 LEFT =LEFT
 
 def inside_convex_polygon（point，vertices）：
 previous_side = None 
 n_vertices = len（vertices）
 for n in xrange（n_vertices）：
a，b = vertices [n ]，顶点[（n + 1）％n_vertices] 
 affine_segment = v_sub（b，a）
 affine_point = v_sub（point，a）
 current_side = get_side（affine_segment，affine_point）
如果current_side是None：
 return False #outside or over a edge 
 elif previous_side is None：#first segment 
 previous_side = current_side 
 elif previous_side！= current_side：
返回False 
返回True 
 $ b $ def get_side（a，b）：
x = x_product（a，b）
 if x < 0：
 return LEFT 
 elif x> 0：
 return RIGHT 
 else：
 return None 
 
 def v_sub（a，b）：
 return（a [0] -b [0 （a，b）：
返回a [0] * b [1] -a [1] * b [1] -b [1]）$ ​​b 
 $ b def x_product 0] 
  

The polygon is given as a list of Vector2I objects (2 dimensional, integer coordinates). How can i test if a given point is inside? All implementations i found on the web fail for some trivial counter-example. It really seems to be hard to write a correct implementation. The language does not matter as i will port it myself.

解决方案

If it is convex, a trivial way to check it is that the point is laying on the same side of all the segments (if traversed in the same order).

You can check that easily with the cross product (as it is proportional to the cosine of the angle formed between the segment and the point, those with positive sign would lay on the right side and those with negative sign on the left side).

Here is the code in Python:

RIGHT = "RIGHT"
LEFT = "LEFT"

def inside_convex_polygon(point, vertices):
    previous_side = None
    n_vertices = len(vertices)
    for n in xrange(n_vertices):
        a, b = vertices[n], vertices[(n+1)%n_vertices]
        affine_segment = v_sub(b, a)
        affine_point = v_sub(point, a)
        current_side = get_side(affine_segment, affine_point)
        if current_side is None:
            return False #outside or over an edge
        elif previous_side is None: #first segment
            previous_side = current_side
        elif previous_side != current_side:
            return False
    return True

def get_side(a, b):
    x = x_product(a, b)
    if x < 0:
        return LEFT
    elif x > 0: 
        return RIGHT
    else:
        return None

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

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

这篇关于如何测试一个点是否在2D整数坐标中的凸多边形内？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！