algorithm - 定位边界2D实体

Question

给定一个点和一组任意的2D实体（圆、多边形、线、折线、弧等），有人知道现有的策略：
确定点是否由任何实体组合包围（包围）？我知道在封闭形状上做一个“内部”测试是很容易的，但这并不总是给我想要的东西，特别是嵌套或相交的形状。
找到最小的（最接近的？）围绕我的点形成闭合多边形的线/实体集？（想想洪水泛滥，但不依赖颜色）

Answer 1

我以前在一个商业产品中解决过这个问题。你问过解析曲线，但我将更一般地讨论至少两次可微的曲线。将多边形处理为一组独立的线段。不需要对曲线进行分段，但如果需要，可以稍微调整算法。
另外，您可能希望在Graphics Gems V中看到我的基于纸矩阵的椭圆几何图形，以找到椭圆之间的交点。
基本思想：
考虑从你的测试点在+x方向的射线。
现在考虑一只蚂蚁从测试点沿着你的光线行走。
当蚂蚁击中与其中一条曲线的第一个交叉点时，它会尽可能地向左转，并在该交叉点留下一个箭头，指示它选择的方向。（如果没有交点，则显然该点没有边界。）
如果它到了曲线的末端，它会自我加倍。
如果有多条曲线在该点相交，则选择最左侧的曲线。
如果一条或多条曲线实际上与相交处的光线相切，则可以使用更高的导数来决定选择哪条曲线和方向。（这只蚂蚁懂微积分。）
现在，当蚂蚁沿着弯道漫步时，它总是像上面那样，最大限度地左转。如果相交处的曲线之间存在相切，则使用更高的导数来确定“最左边”的曲线。（细节由蚂蚁决定）。
蚂蚁在行进过程中，可能会多次到达与光线的起始交点。但一旦它发现自己朝着箭头的方向前进（在第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-该点是有界的。射线等高线相交奇偶性。
以下是可能出现的问题：
由于各种数字原因，找不到轮廓。例如，可能会错过交点，例如两条曲线几乎在一条曲线上相切。您可能会将其视为单个交叉点，但当您执行光线交叉点奇偶校验测试时，您会看到单个交叉点，以便奇偶校验在不应该的时候翻转。
你可能无法计算出足够的导数来做出正确的转向决策。在解析几何的情况下，这不应该是这样。
光线击中轮廓的顶点（线段之间的连接）。（注意，在一个（x，y）点上可以有多个顶点。每个都必须单独处理。）
在这种情况下，必须确定顶点的传入和传出线段是否位于顶点处光线的同一侧。如果他们站在同一边，平价不受影响。否则奇偶性翻转。如果其中一条曲线与顶点处的光线相切，则可能需要使用更高的导数来确定。
线段与测试光线共线。这实际上是2的特例，但很容易处理：忽略它。
有很多细节，但你应该能够处理它们。一定要使用空间树来避免计算不必要的交叉点。
第二个问题的答案是从轮廓中删除任何双遍历的线段。这可能会产生多个子等高线。其中一个将包含你的观点。