复合多边形内的点

Question

我见过很多点在多边形内的算法。到目前为止我所学到的来自这个网站：http://alienryderflex.com/polygon/

最好的算法通常是这样的：

var inside = false;
for (int i = poly.Count - 1, j = 0; j < poly.Count; i = j++)
{
    var p1 = poly.Vertices[i];
    var p2 = poly.Vertices[j];

    if ((p1.Y < testY != p2.Y < testY) && //at least one point is below the Y threshold and the other is above or equal
        (p1.X >= testX || p2.X >= testX)) //optimisation: at least one point must be to the right of the test point
    {
        if (p1.X + (testY - p1.Y) / (p2.Y - p1.Y) * (p2.X - p1.X) > testX)
            inside = !inside;
    }
}

但是复合多边形线段可以是直线也可以是圆弧。弧段由法线 2 点和用于查找弧的中心和半径的凸起定义。 2个点用于求圆弧的起点和终点角度。

使用测试点 Y 和 Math.Asin((testY - arc.Center.Y) / arc.Radius) 我可以找到测试线与圆相交的角度。当测试线与圆相交时，有2个交点。之后我测试角度以了解交点是否在弧上。

到目前为止，我的结果还不错，只是当测试点发生时与顶点完全相同 y。它将被计算在 2 个相邻的段中。对于普通段，if (p1.Y < testY != p2.Y < testY)
可以避免这种情况

对于圆弧部分的复合多边形，我找不到任何类似的实现。有人曾经做过类似的事情或有任何提示吗？

Answer 1

用这条线

p1.Y < testY != p2.Y < testY

您只计算从底部接近查询线（或穿过它）的线段。这正是您需要为弧线做的。

为此，可能需要将弧分成单调部分（相对于 y-axis）。在您的示例中，下弧已经是单调的。上弧应一分为二（沿着穿过其中心的垂直线）。然后每个段都有 minY 和 maxY，您可以应用上面的公式：

minY < testY != maxY < testY

或者，您可以检查交点是否在圆弧末端（等于y-coordinate），并根据角度和圆弧方向评估圆弧是否继续向下。但是根据实施情况，这可能会出现一些数值稳定性问题。第一个选项（拆分成单调部分）可能更容易实现。并且它推广到其他原语。

复合多边形内的点

Point inside compound polygon

c#

point

polygons

point-in-polygon