4

给定一个点和一组任意 2D 实体（圆、多边形、线、折线、圆弧等），是否有人知道现有的策略：

  1. 确定该点是否被任何实体组合包围（有界）？我知道对封闭的形状进行“内部”测试很容易，但这并不总是能给我想要的东西——尤其是嵌套或相交的形状。

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

4

1 回答 1

7

我过去曾在商业产品中解决过这个问题。你问过解析曲线，但我会更一般地解决至少两次可微的曲线。将多边形作为一组单独的线段处理。不需要分割曲线，但如果你愿意，你可以稍微调整算法。

此外，您可能希望在 Graphics Gems V 中查看我的论文Matrix-Based Ellipse Geometry以找到椭圆之间的交点。

基本思路：

  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的一个特例，但是好处理：忽略它。

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

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

于 2012-12-12T23:18:46.490 回答