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

我需要列出位于具有给定的坐标精度的特定多边形内的所有坐标，例如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;

我的方法几乎是一个蛮力的方法。有没有一种有效的算法来找出相同的？

来源

2017-05-25 Akeshwar Jha

我想你可以参考['this']（http://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/）。 –

问题不在于检查点是否在内部。我想减少这种检查的次数。 –

请参阅['这个']（http://codeforces.com/blog/entry/8515）这有一个解决方案，可以在任何点的'O（log n）'时间内回答查询。所以我认为这是我们能做的最好的事情。 –

最好的方法可能是使用在多边形上扫描扫描线的常用策略。将扫描线从最小的y值垂直移动到最大的y值;在每个y值，您可以通过计算扫描线与跨越y值的边界线的交点来计算x的区间列表。（由于扫描行是水平的，交叉点很容易计算。）

基本上，这个想法是：

创建活性边界线的阵列。这个数组最初是空的。
创建一个按y坐标排序的边界线端点数组。如果有两个端点具有相同的y坐标，则用x坐标对它们进行排序。每个端点出现两次（边界线每端一次）;根据该行的另一个端点对两个事件进行排序。
现在扫描扫描线从最小y到最大y。在出现在已排序的端点数组中的每个y值处，调整活动边界线的列表，从列表中添加或删除边界线。新添加的行按顺序插入到列表中，以便列表始终保持从左到右。这样，每个交叉点就是内部和外部之间的过渡点，所以交叉点列表将作为多边形内的一段点的起点和终点。

水平边界线是一个有点恼人，以及它们是如何处理取决于你是否要精确的边界线上的点到内部或外部的多边形考虑。如果边界被考虑在内，您应该可以完全忽略水平线段。但是请看下面。

尽管您已经说过多边形边界不是自相交，但您可能需要考虑量化导致的自相交。如果边界顶点非常接近边界线，则将所有端点四舍五入为整数值（量化）可能会消除微小的间隙，从而导致看起来像自交叉的情况。特别令人气愤的是近乎平行的近水平线：

    A  B       C 
        |___________________________________ 
          ___________________________ 
          |

如果这两条线被量化到相同的y坐标，你将最终

    A  B       C 
        | 
        .________._________________________. 
          |

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

上述算法对于凸和凹边界以及甚至是多边界都有同样的效果，但如果边界自相交，它将失败。为了处理自相交，您需要使用类似于Bentley-Ottmann algorithm的东西，它将线相交添加到扫描线扫描中的“事件”列表。（在交点处，必须颠倒线段的顺序，以便水平扫描是正确的，并且还必须为重新排序的线段计算新的交点。）另外，您还需要更改简单的偶奇交叉算法与匝数计算，这需要知道每个分段是顺时针还是逆时针。尽管理论上Bentley-Ottmann算法看起来很简单，但实际实现需要处理边缘情况，例如多条线在相同点处相交，或者甚至相互叠加（可能由于上述量化结果）。

来源

2017-05-26 15:24:25 rici

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

回答

相关问题