在Boost :: Geometry :: Polygon中找到一个点

Question

我有一个Polygon对象，我正在寻找一种有效的方法来找到它内部的任何点（不在它的边界上）。这样做的最佳方法是什么？

我有以下想法，我不喜欢：

1. 对多边形进行三角测量并在其中一个三角测量边缘上报告一个点（太昂贵）。
2. 检查多边形的缠绕方向并报告位于距多边形边缘之一的epsilon距离内的点（在边缘情况下不起作用）。

Answer 1

给定多边形，您可以找到多边形与x轴平行的线的前两个点，它位于多边形的yMin和yMax之间（下图中的0和1）。

这些点之间的任何点都将位于多边形内。基本思想来自扫描转换多边形-i.e.这些是你要填的点。第二个点之后的线条部分的绕组为0或2，具体取决于您的多边形。

必须采用前两个交叉点（或最后一个），因为交叉点沿x轴排序。

一些极端情况：

1. 如果省略刚触及直线的多边形的所有点，在某些情况下，这可能会失败（下图）。
2. 如果多边形中有重叠的线条，则必须解决这些问题。

为了避免第一个问题，请确保将第一个点作为明确的交叉点，并且下一个点可以是交叉点或多边形刚刚接触线的点。

这可以在不使用大多数语言的任何特殊功能的情况下轻松实现。由于我不熟悉Boost方法，我在javascript中发布了基本思想的草图。

绘图是使用paper.js完成的 - 尽管这里概述的算法代码本身是自包含的。

只要您可以枚举Boost :: polygon中的所有点，就可以将其转换为C ++

这是demo。