复合多边形内的点

我已经看到很多点内多边形的算法。我的教训至今都来自这个网站：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个相邻的分段。对于一个正常的部分，这种情况下是通过避免如果(p1.Y < testY != p2.Y < testY)

我找不到的圆弧部分组成的配料多边形任何类似的实现。有人曾经做过类似的事情或有任何暗示吗？

来源

2016-01-19 Eric Biron

你有整数或浮点坐标吗？ –

浮点坐标（double） –

这一行

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

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

为此，可能希望将弧分割为单调部分（相对于y轴）。在你的例子中，较低的弧线已经是单调的了。上部弧线应分成两部分（沿着垂直线穿过其中心）。然后，你必须为每个分段minY和maxY并且可以应用上述公式：

minY < testY != maxY < testY

或者，也可以检查是否交点是在圆弧端（等于y坐标），并评估如果电弧继续向下基于角度和弧线方向。但取决于实施，这可能会有一些数值稳定性问题。第一个选项（分成单调部分）可能更容易实现。它推广到其他原语。

来源

2016-01-19 19:03:56

将弧分割成单调部分并不容易，因为在Y轴的同一侧可能有两个部分，但是一旦我找到它，它就解决了我的问题。坦克 –

复合多边形内的点

回答

相关问题