Finding intersection between sets of points descri

问题:

Say I have two sets of points

p1, p2, p3,... ,pn 

and

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)

and

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

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.

回答1:

You can preprocess each polyline (chain of segments) and find a minimal bounding rectangle for each of them. Also you can build a hierarchical data structure for each polyline - a rectangle for the whole one, then a rectangle for each half and so on. You can use other geometrical forms instead of rectangle - circle or ellipse, for instance.

Then you can use Clipping and Culling to accelerate intersections search.

回答2:

You can calculate bounding box around a set of points, say every 100 pair of points and intersect only those in a n x n manner. Bounding box intersections can be done very efficiently. If two bounding boxes (one from each curve) intersect, you can test for intersection just the edges involved inside of those boxes.

This will handle the case when there's more than one intersection between the curves. Just mind the boundary cases, when the point of intersection is actually one of the vertices defining an edge.

回答3:

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.

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.