确定点是否在多边形内

Question

目前我正在使用光线投射算法，但它有一些局限性，例如光线通过顶点时无法确定其是否在内部。

我可以使用哪种算法，它总能用于任何种类的多边形？

Answer 1

您可以根据多边形本身选择光线方向，使其不会穿过任何顶点。

对于整数坐标它就足以沿着(1,0.5/deltaX)，其中deltaX是多边形顶点的x坐标之间的最大差值投下射线。射线上的整数坐标的第一个点将成为它的开始。下一个将有多边形之外的x坐标startX+2*deltaX，并且不能是其顶点。通过精确的算术，您可以稳健地确定点内外的点。

对于浮点数精确算术是一个问题，所以您希望射线尽可能远离多边形顶点。为此，您可以计算每个多边形顶点的方向，并按顶点排序。然后选择此排序序列中相邻顶点之间的最大差异，并在它们之间投射光线。