查找描述曲线的点集之间的交点 [英] Finding intersection between sets of points describing a curve

问题描述

说我有两组点

p1, p2, p3,... ,pn 

和

q1, q2, q3,..., qn

，它们描述了飞机上的两条路径（曲线）。这些点可能不是从曲线上均匀采样的，而是按顺序（关于曲线的参数化）。找出这两条曲线在哪里相交的好方法是什么？

which describe two paths (curves) in a plane. The points may not be evenly sampled from the curve, but they are "in order" (with regard to parameterizations of the curves). What is a good way to find out where these two curves intersect?

因此，例如，我可能只有两个点

So for example, I may have just two points each

(0,0) (1,0)

和

(-5,1) (-4,-1)

在这种情况下，它们的交点是（-4.5,0）。

in which case their intersection is (-4.5,0).

进行此操作的基本方法是在每两个点之间绘制一条边，将它们延伸，然后查看是否有两对边在合适的土地上相交。我很好奇是否有更好的方法。

The most rudimentary way to do this would be to draw the edges between every two points, extend them, and see whether any two pairs of edges intersect in a suitable patch of land. I'm curious if there's a better way.

推荐答案

找到这种交点的最有效方法是借助扫掠线算法，通过详尽的比较，可以达到O（n log n + k）的运行时间（n个具有k个交点的线段），优于O（n²）。参见 http：//www.ti.inf.ethz。 ch / ew / lehre / CG09 / materials / v9.pdf 。不幸的是，这样的解决方案相当复杂。

The most efficient way to find such intersection is by means of sweepline algorithms, that can achieve O(n log n + k) running time (n line segments having k intersections), better than the O(n²) by exhaustive comparisons. See http://www.ti.inf.ethz.ch/ew/lehre/CG09/materials/v9.pdf. Unfortunately, such solutions are rather sophisticated.

一个可能更容易实现的替代方法是使用层次边界：将每个段的边界框合并，将两个框合并乘以2（连续段），然后乘以4，以此类推。从N个段开始，您将形成N-1个边界框的层次结构。

A possible alternative, much simpler to implement, is to use hierarchichal bounding: take the bounding box of every segment, merge the boxes two by two (consecutive segments), then four by four and so on. starting from N segments, you'll form hierarchy of N-1 bounding boxes.

然后，要与两条曲线相交，请检查其顶级边界框的干扰。如果确实重叠，则递归检查子框的干扰，等等。

Then, to intersect two curves, check interference of their top-level bounding boxes. If the do overlap, check interference of the sub-boxes, and so on recursively.

除非您的曲线紧密缠绕在一起，否则您可以节省大量的线段比较。

Unless your curves are closely intertwined, you can spare a large number of segment comparisons.

这篇关于查找描述曲线的点集之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！