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

问题描述

给定一个点和一组任意 2D 实体(圆、多边形、线、折线、弧等)，有没有人知道现有的策略:

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

1. 确定点是否被任何实体组合包围(有界)?我知道对闭合形状进行内部"测试很容易，但这并不总是我想要的 - 特别是嵌套或相交的形状.

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.

找到围绕我的点形成闭合多边形的最小(最接近?)线/实体集?(想想洪水填充，但不依赖于颜色)

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.

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

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

基本思路:

1. 考虑来自测试点的 +x 方向的射线.
2. 现在考虑一只蚂蚁从测试点沿着射线行走.
3. 当蚂蚁碰到其中一条曲线的第一个交点时，它会尽可能地向左倾斜，并在该交点处留下一个箭头，指示它选择的方向.(如果没有交点，那么显然该点是无界的.)
4. 如果到了曲线的尽头，它会自行加倍.
5. 如果多条曲线在该点相交，则选择最靠左的曲线.
6. 如果一条或多条曲线实际上与相交处的光线相切，则可以使用更高的导数来决定选择哪条曲线和方向.(这只蚂蚁会微积分.)
7. 现在，当蚂蚁沿着曲线漫步​​时，它总是像上面一样做出最大的左转.如果在交点处的曲线之间存在相切，请使用更高的导数来确定最靠左"的那个.(细节留给蚂蚁).
8. 在它的旅行中，蚂蚁可能会多次到达与射线的起始交叉点.但是一旦它发现自己朝着箭头的方向(它在步骤 3 中留下的那个方向)前进，它的行程就完成了，并且已经穿过了一个轮廓".问题简化为确定点是否在该轮廓中.

轮廓"是一个拓扑实体.它是在顶点"处连接的段"的闭合环.

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.

顶点"是段之间的连接.顶点与平面上的 (x, y) 位置相关联，但同一位置可能有多个顶点，轮廓中每对在该点相交的线段对应一个顶点.每个曲线端点(一个支点)或蚂蚁遇到的曲线-曲线交点都有一个顶点.

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.

因此，即使您的一组曲线中只有一条从 A 到 B 的线(我假设您没有无限线)并且您的光线在 P 处击中它，您仍然有轮廓 V0(P)-V1(A)-V2(P)-V3(B)-V0 有 4 段 V0-V1、V1-V2、V2-V3、V3-V0.请注意，V0 和 V2 是不同的顶点，都位于 P 处.

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.

示例:

考虑这个曲线集.我使用线条，所以我不会太努力:

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

案例 1 - 点没有边界.轮廓对曲线段的使用由虚线箭头指示.射线-轮廓相交奇偶校验数为偶数.

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.

案例 2 - 该点是有界的.光线轮廓相交奇偶校验.

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

以下是可能出错的地方:

Here's what can go wrong:

1. 由于各种数字原因，您无法找到轮廓.例如，您可能会错过交叉路口，例如两条曲线在一条曲线上几乎相切.您可能会将其视为单个交叉点，但是当您进行光线交叉奇偶校验测试时，您会看到一个交叉点，因此奇偶校验在不应该翻转的时候翻转.

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.

您可能无法计算足够的导数来做出正确的转弯决策.在解析几何的情况下，情况绝不应该如此.

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.

您的光线击中轮廓的一个顶点(线段之间的连接).(请注意，单个 (x, y) 点可以有多个顶点.每个顶点都必须单独处理.)

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. 一条线段与您的测试光线共线.这实际上是 2 的特例，但很容易处理:忽略它.

有很多细节，但你应该能够处理它们.请务必使用空间树以避免计算不必要的交集.

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屋！