定位边界2D实体

Question

给定一个点，并且将任意2D实体（圆，多边形，直线，折线，弧等），没有人知道现有的战略到：

1. 确定是否点是由任何实体组合包围（界定）？我知道在封闭的形状上进行'内部'测试是很容易的，但这并不总是给我想要的东西 - 特别是嵌套或相交的形状。

2. 找到围绕我的点形成闭合多边形的最小（最接近？）线/实体集合？ （想想一个洪水填充，但不依靠颜色）

Answer 1

我已经解决了过去在商业产品中的这个问题。你已经问过关于分析曲线的问题，但是我会更一般性地讨论至少两次可微的曲线。将多边形作为一组单独的线段处理。不需要对曲线进行分割，但是如果您想要，可以稍微调整算法。

此外，您可能希望在Graphics Gems V中查看我的论文10基于矩阵的椭圆几何以找到您的省略号之间的交点。

基本思想：

1. 考虑从+ X方向测试点的射线。
2. 现在考虑一个蚂蚁从测试点沿射线行走。
3. 当蚂蚁碰到其中一条曲线的第一个交叉点时，它会使其最大限度地离开它，并在该交叉点留下一个箭头指示其选择的方向。 （如果没有交点，那么显然这个点是没有界限的。）
4. 如果涉及到曲线的末端，它会自己翻倍。
5. 如果在该点处有多条曲线相交，则会选择最左边的曲线。
6. 如果一条或多条曲线实际上与交叉处的射线相切，则可以使用更高的导数来决定选择哪条曲线和方向。 （这只蚂蚁知道微积分）
7. 现在，当蚂蚁沿着曲线漫步​​时，它总是会像上面那样产生最大的左转。如果在交叉点处曲线之间存在相切，请使用更高的导数来确定“最左边”的曲线。 （细节留给蚂蚁）。
8. 在旅途中，蚂蚁可能会多次与光线出发。但是一旦它发现自己沿箭头方向行进（它在步骤3中留下的箭头），就会完成行程并穿过“轮廓”。问题被减少到决定点是否在该轮廓中。

“轮廓”是一个拓扑实体。它是在“顶点”连接的“分段”的闭环。

“段”是轮廓在特定方向中使用的一段曲线。

“顶点”是段之间的连接。顶点与平面上的（x，y）位置相关联，但在同一位置可能有多个顶点，对于在该点处相交的轮廓中的每对分段，都有一个顶点。每个曲线终点（尖刺顶点）或蚂蚁遇到的曲线曲线交点都有一个顶点。

轮廓（在此上下文中）不是几何实体！不要把它看作是飞机上的简单封闭的道路。蚂蚁可能沿着一段，走到最后，并回到它来的方向 - 这被称为“刺激”，包括两个轮廓段，一个用于任一方向。或者它可能沿着曲线段的一个方向，沿着其他曲线漫游，并沿着该段的另一个方向返回。因此，即使你的曲线组中只有一行从A到B（假设你没有无限长线），并且你的光线在P点击了它，你仍然有轮廓V0（P ）-V1（A）-V2（P）-V3（B）-V0具有4段V0-V1，V1-V2，V2-V3，V3-V0。请注意，V0和V2是不同的顶点，都位于P.

现在测试您的点是否在轮廓中。

找到你的射线（任何射线源于你的测试点将与）轮廓的交点。我们只需要与轮廓交点的奇偶数（偶数或奇数）。如果奇偶校验是奇数的，则该点由曲线限定，如果它甚至不是。

因为双重穿越的部分对平价没有贡献，我们可以忽略它们。这是因为在双线段上总是有偶数个交点，因为它们在轮廓中是两次。

示例：

考虑这个曲线集。我用的线，所以我不工作太辛苦：

案例1 - 点是无界。虚线箭头表示轮廓对曲线段的使用。交叉口奇偶校验的数量是偶数。

案例2 - 该点为界。射线轮廓相交奇偶校验是奇数。

下面是可能出现的错误：

1. 你不能找到各种数值原因的轮廓。例如，您可能会错过交叉点，例如两条曲线在曲线上几乎相切。您可能会将其视为单个交叉点，但是当您执行射线交叉点奇偶校验测试时，您会看到单个交叉点，以便在奇偶校验不应该时翻转。

2. 您可能无法计算出足够的衍生产品以作出正确的转折决策。在解析几何的情况下，情况决不应该如此。

3. 你的射线击中轮廓的顶点（段之间的连接）。 （请注意，有可在单个（X，Y）点是多个顶点。每个这些必须被单独处理。）

在这种情况下，必须决定是否的传入和传出段顶点位于顶点射线的同一侧。如果他们在同一方面，平价不受影响。否则，奇偶校验翻转。如果其中一条曲线与顶点处的射线相切，则可能需要使用更高的导数来决定。

1. 线段与测试射线共线。这实际上是2的特例，但容易处理：忽略它。

有很多细节，但你应该能够处理它们。确保使用空间树来避免计算不必要的交点。

第二个问题的答案来自于从轮廓中删除任何双向遍历的段。这可能会产生多个子轮廓。其中之一将包含你的观点。