在 Boost::Geometry::Polygon 内查找点
sna*_*ile 0 c++ boost computational-geometry boost-geometry
我有一个Polygon对象，我正在寻找一种有效的方法来找到严格位于其内部（而不是其边界上）的任何点。最好的方法是什么？
我有以下想法，但我不太喜欢：
- 对多边形进行三角测量并报告三角测量边之一上的点（太昂贵）。
- 检查多边形的缠绕方向并报告位于距多边形边缘之一 epsilon 距离的点（在边缘情况下不起作用）。
给定一个多边形，您可以找到多边形与平行于 x 轴的线交叉且位于多边形的 yMin 和 yMax 之间的前两个点（下图中的 0 和 1）。
\n\n这些点之间的任何点都将位于多边形内。基本思想来自扫描转换多边形 \xe2\x80\x94i.e. 这些是您需要填写的点。第二个点之后的线部分的缠绕程度为 0 或 2，具体取决于您的多边形。
\n\n必须采用前两个交叉点（或最后一个交叉点），因为交叉点沿 x 轴排序。
\n\n
一些极端情况：
\n\n- \n
- 如果您忽略了刚刚接触该线的多边形的所有点，在某些情况下这可能会失败（下图）。 \n
- 如果多边形中存在重叠线，则必须解决这些问题。 \n
为了避免第一个问题，请确保将第一个点作为明确的交叉点，下一个点可以是交叉点，也可以是多边形恰好与线相接触的点。
\n\n
在大多数语言中，这可以轻松实现，无需使用任何特殊函数。由于我不熟悉 Boost 方法，因此我发布了 javascript 基本思想的草图。
\n\n该绘图是使用paper.js \xe2\x80\x94 完成的，尽管此处概述的算法代码本身是独立的。
\n\n只要您可以枚举 Boost::polygon 中的所有点，您就可以将其转换为 C++
\n\n这是演示。
\n