java - 凸/凹多边形内的所有点 - 更好的方法？

Question

我需要列出位于给定坐标精度(比如 1)的特定多边形内部的所有坐标。这意味着，多边形边界的所有坐标都将是整数。多边形可以是凸面或凹面。

我有边界的所有坐标，coords[n][2]

这是我解决问题的方法:

为简单起见，假设多边形的第一个坐标为 [0,0]

for (i = 1;; i++)

    for all points that lie on the lines: y = ±i, x = ±i, 

        check if the point lies inside the polygon.

    if no point lies on the polygon

        break;

我的方法几乎是一种蛮力方法。有没有一种有效的算法来解决这个问题？

Answer 1

最好的方法可能是使用在多边形上扫描扫描线的常用策略。将扫描线从最小的y值垂直移动到最大的y值；在每个 y 值处，您可以通过计算扫描线与穿过该 y 值的边界线的交点来计算 x 的间隔列表。 (由于扫描线是水平的，交点很容易计算。)

基本上，这个想法是:

1. 创建一个 Activity 边界线数组。这个数组最初是空的。

2. 创建一个按 y 坐标排序的边界线端点数组。如果有两个端点具有相同的 y 坐标，则按 x 坐标对它们进行排序。每个端点出现两次(边界线的每一端各一次)；根据线的另一个端点对两个事件进行排序。

3. 现在扫描扫描线从最小 y 到最大 y。在排序的端点数组中出现的每个 y 值处，调整 Activity 边界线列表，从列表中添加或删除边界线。新添加的行按 x 坐标顺序插入到列表中，以便列表始终从左到右。这样，每个交点都是内部和外部之间的过渡，因此成对的交点列表将成为多边形内一段点的起点和终点。

水平边界线有点烦人，如何处理它们取决于您是否希望精确地位于边界线上的点被视为多边形内部或外部。如果边界被认为是在里面，你应该能够完全忽略水平线段。但见下文。

虽然您已经说过多边形边界不是自相交的，但您可能需要担心量化导致的自相交。如果边界顶点非常靠近边界线，则将所有端点四舍五入为整数值(量化)可能会消除微小的间隙，从而导致看起来像自相交。特别令人恼火的是几乎平行的近水平线:

                   A        B                         C
                   |___________________________________
                            ___________________________
                            |

如果将这两条线量化到同一个 y 坐标上，您将得到

                   A        B                         C
                   |  
                   .________._________________________.
                            |

然后，如果忽略水平边界线，线段 BC 将不会被报告为多边形的一部分。

上述算法将同样适用于凸边界和凹边界，甚至是多个边界，但如果边界自相交则失败。要处理自交，您需要使用类似于 Bentley-Ottmann algorithm 的东西, 它将线交点添加到扫描线扫描中的“事件”列表中。 (在交点处，您必须反转线段的顺序以便水平扫描正确，并且您还必须为重新排序的线段计算新的交点。)此外，您还需要更改简单的奇偶交叉点具有绕数计算的算法，这需要知道每个段是顺时针还是逆时针。虽然 Bentley-Ottmann 算法在理论上看起来很简单，但实际实现需要处理边缘情况，例如多条线在同一点相交，甚至相互重叠(可能是量化的结果，如上所述)。