c++ - 在 Boost::Geometry::Polygon 中找到一个点

Question

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

我有以下想法，但我不太喜欢:

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

Answer 1

给定一个多边形，您可以找到第一个两个点，多边形穿过一条平行于 x 轴的线并位于多边形的 yMin 和 yMax 之间(0 & 1 在下图中)。

这些点之间的任何点都将在您的多边形内。基本思想来自扫描转换多边形——即这些是您要填写的要点。第二点之后的线段的缠绕度为 0 或 2，具体取决于您的多边形。

必须取前两个交叉点(或最后一个)，因为交叉点是沿 x 轴排序的。

一些角落案例:

1. 如果您省略多边形的所有 点，但在某些情况下，这可能会失败(下图)。
2. 如果您的多边形中有重叠线，您必须解决这些问题。

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

在大多数语言中，无需使用任何特殊函数即可轻松实现这一点。由于我不熟悉 Boost 方法，因此我在 javascript 中发布了基本思想的草图。

绘图是使用 paper.js 完成的——尽管此处概述的算法代码本身是独立的。

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

这是 demo .