复合多边形内的点 [英] Point inside compound polygon

问题描述

我见过很多关于多边形内点的算法.到目前为止我学到的东西来自这个网站:

我找不到圆弧部分的复合多边形的任何类似实现.是否有人不得不做类似的事情或有任何提示?

解决方案

With this line

p1.Y 

您只计算从底部(或穿过它)接近查询线的线段.而这正是您需要为圆弧做的事情.

为此，可能需要将弧分成单调部分(相对于 y 轴).在您的示例中，较低的弧线已经是单调的.上面的圆弧应该一分为二(沿着通过其中心的垂直线).然后你有每个段的 minY 和 maxY ，你可以应用上面的公式:

minY 

或者，您可以检查交点是否在圆弧末端(等于 y 坐标)，并根据角度和圆弧方向评估圆弧是否继续向下.但是根据实现，这可能会有一些数值稳定性问题.第一个选项(拆分为单调部分)可能更容易实现.并且可以推广到其他原语.

I have seen many algorithms for point inside polygon. What I learned so far came from this site: http://alienryderflex.com/polygon/

The best algorithm usually look like this:

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;
    }
}

But compound polygon segments can either be a straight line or an arc. Arc segments are defined by the normal 2 points and a bulge which is used to find the center and radius of the arc. The 2 points are used to find the start and end angle of the arc.

Using the test point Y and Math.Asin((testY - arc.Center.Y) / arc.Radius) I can find the angle at which the test line intersect the circle. When the test line intersects the circle, there are 2 intersection points. After that I test the angle to know if the intersections points are on the arc.

My result are pretty good so far except that when the test point happen have exactly the same y as a vertex. It will be counted for the 2 adjacent segments. For a normal segment, this case is avoided by the if (p1.Y < testY != p2.Y < testY)

I can't find any similar implementation for compound polygon for the arc part. Did someone ever had to do something similar or have any hint?

解决方案

With this line

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

you only count segments that approach the query line from the bottom (or cross it). And this is exactly what you need to do for the arcs.

For this, it may be desirable to split the arc into monotone parts (with respect to the y-axis). In your example, the lower arc already is monotone. The upper arc should be split into two (along a vertical line through the its center). Then you have minY and maxY for each segment and you can apply the above formula:

minY < testY != maxY < testY

Alternatively, you could check if the intersection is at the arc end (equal y-coordinate) and evaluate if the arc continues downwards based on the angle and arc direction. But depending on the implementation, this might have some numerical stability issues. The first option (with splitting into monotone parts) is probably easier to implement. And it generalizes to other primitives.

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