我需要列出具有给定坐标精度的特定多边形内部的所有坐标，例如 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;
我的方法几乎是蛮力的。有没有一种有效的算法来弄清楚同样的事情？
最好的方法可能是使用在多边形上扫描扫描线的常见策略。将扫描线从最小的y值垂直移动到最大的y值;在每个 Y 值处，您可以通过计算扫描线与穿过该 Y 值的边界线的交点来计算 X 的间隔列表。(由于扫描线是水平的，因此交点易于计算。
基本上，这个想法是：
-
创建活动边界线数组。此数组最初为空。
-
创建按 y 坐标排序的边界线端点数组。如果有两个端点具有相同的 y 坐标，请按 x 坐标对它们进行排序。每个端点出现两次(边界线的每一端出现一次);根据行的另一个端点对两个匹配项进行排序。
-
现在将扫描线从最小 y 扫描到最大 y。在端点排序数组中显示的每个 y 值处，调整活动边界线列表，在列表中添加或删除边界线。新添加的行按 x 坐标的顺序插入到列表中，以便列表始终从左到右。这样，每个交点都是内部和外部之间的过渡，因此成对的交点列表将是面内一段点的起点和终点。
水平边界线有点烦人，如何处理它们取决于您是希望将边界线上的点精确考虑在多边形内部还是外部。如果考虑内部边界，您应该能够完全忽略水平线段。但见下文。
尽管您说过多边形边界不是自相交的，但您可能需要担心量化导致的自相交。如果边界顶点非常靠近边界线，则将所有端点舍入为整数值(量化)可能会消除微小的间隙，从而产生看起来像自相交的情况。特别令人恼火的是几乎平行的近水平线：
A B C
|___________________________________
___________________________
|
如果将这两条线量化到相同的 y 坐标上，则最终会得到
A B C
|
.________._________________________.
|
然后，如果忽略水平边界线，则不会将线段 BC 报告为多边形的一部分。
上述算法同样适用于凸边界和凹边界，甚至多个边界，但如果边界自相交，则算法会失败。要处理自交集，您需要使用类似于 Bentley-Ottmann 算法的东西，该算法将线交点添加到扫描线扫描中的"事件"列表中。(在交点处，必须反转线段的顺序，以便水平扫描正确，并且还必须为重新排序的线段计算新的交点。此外，您将希望使用绕组数计算来更改简单的偶奇交叉算法，这需要知道每个段是顺时针还是逆时针。虽然 Bentley-Ottmann 算法在理论上看起来很简单，但实际实现需要处理边缘情况，例如多条线在同一点相交，甚至彼此重叠(可能是量化的结果，如上所述)。