定位边界2D实体 [英] Locating Bounding 2D Entities

问题描述

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

1. 确定是否该点被封闭的（限定）由实体的任何组合？我知道这是很容易做到的封闭图形的内部的测试，但是这不会总是给我我想要的 - 尤其是嵌套或交叉形状

2. 查找最小的（最接近？）组形成围绕我的观点一个封闭的多边形线/实体？ （想起了洪水填充，但不依赖于颜色）

解决方案

我已经在过去的商业产品解决了这个问题。你问的分析曲线，但我会更普遍地解决这个问题的曲线是至少两次可微。处理的多边形作为一组独立的线段。有没有必要段的曲线，但如果你愿意，你可以稍调整算法。

此外，您可能希望看到我的文章的基于矩阵的椭圆几何的图形中的宝石V至找到你的椭圆之间的交叉点。

基本思路：

1. 从+ X方向的测试点考虑的曙光。
2. 现在，沿着从测试点的射线考虑蚂蚁行走。
3. 当蚂蚁击中的一条曲线的第一个十字路口，它使清晰的离开是可以的，留下一个箭头在那个路口指示它选择的方向。 （如果没有交点，则明显的点没有限制。）
4. 如果它涉及到一个曲线的末端，它的两倍自身向后
5. 如果有多个曲线相交在该点时，它选择所述曲线是最左边。
6. 如果一个曲线或多个是实际上相切的光线在交叉路口，更高衍生物可用于决定选择哪条曲线和方向。 （这蚂蚁知道演算。）
7. 现在，沿曲线蚂蚁散步，它总是让最大左转它可以如上。如果曲线之间相切的交集，用高阶导数来决定一个是最左侧。 （详细情况留待蚁）。
8. 在它的旅行，蚂蚁可能会与光线多次起动交集。但只要它发现自己继续在箭头（一个它留在步骤3）的方向上，它的行进完成和它已穿过一个轮廓。这个问题减少到决定如果点是在该轮廓。

一个轮廓是一个拓扑实体。它是连接在顶点。

段的闭环

一个段是在特定方向上所使用的轮廓的一块曲线的

一个顶点是段之间的连接。一个顶点与一个（X，Y）上的平面位置相关联，但有可能是多个顶点在相同的位置，一个用于每一对段，在这一点上达到了轮廓。这是一个每个曲线的端点顶点（一种鞭策顶点），或曲线曲线相交的蚂蚁遇到。

一个轮廓（在此上下文中）不是一个几何实体！不要认为它是在飞机上简单的闭合路径。蚂蚁可能沿段去，到达终点，并返回它来时的路 - 这就是所谓的鞭策，包括两个轮廓部分，一个用于两个方向。或者它可能沿曲线段的一个方向去，闲逛比特沿其它曲线，以及沿区段的另一方向返回。

因此​​，即使你组曲线中有只有一行从A到B（我假设你没有无限行）和您的射线撞击它为P，你仍然有轮廓V0（P） -V1（A）-V2（P）-V3（B）-V 0与4段V0-V1，V1-V2，V2，V3，V3-V0。注意，V0和V2分别不同的顶点，两者都位于以P

现在来测试，如果你的观点是在外形上

找到你的射线（任何射线起源于你的测试点都行）与轮廓的交点。我们只有真正想要交点与轮廓的数目的奇偶性（偶数或奇数）。如果奇偶是奇数，该点是曲线界，如果它甚至不是这样的。

由于双向穿越段毫无贡献奇偶校验，我们可以忽略它们。这是因为总有偶数上加倍遍历线段交点，因为他们是在外形上两次。

例如：

考虑这条曲线设置。我用的线，所以我不悠着点：

案例1 - 重点是无界的。轮廓的使用曲线段的由虚线的箭头表示。 ray-数量的轮廓的交集奇偶校验为偶数。

案例2 - 点为界。在光线轮廓的交叉校验为奇数。

下面是可能出现的错误：

1. 您不能找到一个轮廓各种数值的原因。例如，您可能会错过路口，如两条曲线几乎相切于一条曲线。您可能会看到它作为一个单一的交集，但是当你做光线交叉校验测试，你看到一个交叉，使奇偶翻转时，它不应该。

2. 您可能无法计算足够的衍生品做出正确的转弯决定。在解析几何的情况下，这不应该是这样的。

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

在这种情况下，必须决定是否是在射线的在顶点的同一侧的顶点的传入和传出段。如果他们是在同一侧，所述奇偶不受影响。否则，奇偶校验翻转。如果一条曲线相切的射线在顶点，你可能需要使用较高的衍生品来决定这一点。

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

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

回答你的第二个问题来自从轮廓删除任何双重穿越段。这可能会产生多个子轮廓。他们中的一个将包含您的观点。

Given a point and a set of arbitrary 2D entities (circles, polygons, lines, polylines, arcs, etc.), does anyone know of existing strategies to:

1. Determine if the point is enclosed (bounded) by any combination of entities? I know that it is easy enough to do an 'inside' test on the closed shapes, but this won't always give me what I want - particularly with nested or intersecting shapes.

2. Find the smallest (closest?) set of lines / entities that form a closed polygon around my point? (think of a flood-fill, but without relying on colour)

解决方案

I've addressed this problem in a commercial product in the past. You've asked about analytic curves, but I'll address it more generally for curves that are at least twice differentiable. Handle polygons as a set of separate line segments. There is no need to segment the curves, but if you want to you can and adapt the algorithm slightly.

Also, you might want to see my paper Matrix-Based Ellipse Geometry in Graphics Gems V to find the intersections between your ellipses.

Basic idea:

1. Consider a ray from your test point in the +x direction.
2. Now consider an ant walking along your ray from the test point.
3. When the ant hits the first intersection with one of the curves, it makes the sharpest left it can, and leaves an arrow at that intersection indicating the direction it's chosen. (If there is no intersection, then obviously the point isn't bounded.)
4. If it comes to the end of a curve, it doubles back on itself.
5. If there are multiple curves intersecting at that point, it chooses the curve that is most to the left.
6. If one or more of the curves is in fact tangent to the ray at the intersection, higher derivatives can be used decide which curve and direction to choose. (This ant knows calculus.)
7. Now as the ant strolls along the curves, it always makes the biggest left turn it can as above. If there is tangency between curves at the intersection, use higher derivatives to decide the one that is "most to the left". (Details are left to the ant).
8. In its travels, the ant may come to the starting intersection with the ray multiple times. But as soon as it finds itself proceeding in the direction of the arrow (the one it left in step 3), it's travels are done and it has traversed a "contour". The problem is reduced to deciding if the point is in that contour.

A "contour" is a topological entity. It's closed ring of "segments" connected at "vertices".

A "segment" is a piece of a curve used by the contour in a particular direction.

A "vertex" is a connection between segments. A vertex is associated with a (x, y) position on the plane, but there may be multiple vertices at the same position, one for each pair of segments in the contour that meet at that point. There is a vertex for each curve endpoint (a spur vertex), or curve-curve intersection encountered by the ant.

A contour (in this context) is not a geometric entity! Don't think of it as a simple closed path on the plane. The ant might go along a segment, get to the end, and go back the way it came--this is called a "spur" and includes two contour segments, one for either direction. Or it might go along one direction of a curve segment, wander around a bit along other curves, and return along the other direction of the segment.

So even if your set of curves has only one line in it from A to B (I'm assuming you don't have infinite lines) and your ray hits it at P, you still have the contour V0(P)-V1(A)-V2(P)-V3(B)-V0 with 4 segments V0-V1, V1-V2, V2-V3, V3-V0. Note that V0 and V2 are distinct vertices, both positioned at P.

Now to test if your point is in the contour.

Find the intersections of your ray (any ray originating at your test point will do) with the contour. We only really want the parity (even or odd) of the number of intersections with the contour. If the parity is odd, the point is bounded by the curves, if it's even it's not.

Because doubly traversed segments contribute nothing to the parity, we can ignore them. This is because there are always an even number of intersections on doubly traversed segments, since they're in the contour twice.

Examples:

Consider this curve set. I use lines so I don't work too hard:

Case 1 - The point is not bounded. The contour's use of the curve segments is indicated by the dotted arrows. The number of ray-contour intersection parity is even.

Case 2 - The point is bounded. The ray-contour intersection parity is odd.

Here's what can go wrong:

1. You can't find a contour for various numerical reasons. For example, you might miss intersections, e.g. two curves are almost tangent at a curve. You might see it as a single intersection, but when you do the ray intersection parity test you see a single crossing so that the parity flips when it shouldn't.

2. You might not be able to compute enough derivatives to make the correct turn decisions. In the case of analytic geometry this should never be the case.

3. Your ray hits a vertex (connections between segments) of your contour. (Note that there can be multiple vertices at a single (x, y) point. Each of these has to be handled separately.)

In this case, you have to decide if the incoming and outgoing segments of the vertex are on the same side of the ray at the vertex. If they're on the same side, the parity is not affected. Otherwise the parity flips. If one of the curves is tangent to the ray at the vertex, you may have to use higher derivatives to decide this.

1. A line segment is collinear with your test ray. This is actually a special case of 2, but easy to handle: Ignore it.

There are lots of details, but you should be able to handle them. Be sure to use spatial trees to avoid computing unnecessary intersections.

The answer to your second question comes from removing from the contour any doubly traversed segments. This may yield multiple sub-contours. One of them will contain your point.

这篇关于定位边界2D实体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！