寻找描述曲线的点集之间的交点 [英] 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.

一种可能的替代方案，实现起来更简单，是使用分层边界:取每个段的边界框，两两(连续的段)合并框，然后四四，依此类推.从 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屋！