Minimal rectangle containing all intersections of

问题:

I'm trying to find an algorithm that will find all the intersections of a set of lines and compute the minimal rectangle that contains all the intersections in O(n log n) time. So far I'm guessing it has to do with duality and convex hulls, but I'm kinda stuck on how it would actually help me solve this problem.

If anyone has an idea on this, please let me know. Thanks :)

回答1:

Let's start from a box B[0] that minimally bounds three intersection points in a triangle.

If no triangle can be found, then we have a one of the following special cases which can be handled separately:

1. All lines are parallel.
2. All intersections are along one line. This could happen if all lines but one are parallel.
3. All lines intersect at a single point.

So let's ignore these cases as details and assume a triangle can be found and that finding it doesn't add too much time to the algorithm.

Phase 1 - Grow the box to include one intersection from each line:

1. Tag the three lines forming the initial triangle.
2. Choose one untagged line, and find an intersection P with a tagged line. This is always possible since there are at least three tagged lines that aren't mutually parallel.
3. Grow the box to include P.
4. Repeat from 2 until all the lines are tagged, i.e. they all have at least one intersection in the box.

Call the resulting box B[0].

Phase 2 - Detect if lines have an intersection outside of the box:

Here's the key observation: for two lines A and B that intersect WITHIN the box, walking around the box clockwise we encounter the lines alternating: e.g. A B A B. For two lines that intersect OUTSIDE the box, a clockwise walk does NOT alternate: e.g. A B B A. Of course there is the possibility that the lines intersect on the box boundary, or are concurrent, but that will be treated as a detail after describing the main algorithm.

1. Choose an orientation of the lines: Let the lines be directed toward the +y direction if the lines aren't horizontal, and let horizontal lines be oriented in the +x direct. One things of the lines as arrows, then the arrows are all chosen to point up as much as they can, or to the right if they're horizontal. With this orientation, each line has a point of entry into the box (where the oriented line points into the box, and a point of exit. These may be the same point.
2. Create an "exit sequence" of the lines by walking the EXITING intersections clockwise around the boundary, starting at, say, the upper right corner.
3. Create an "enter sequence" of the lines by walking the ENTERING intersections clockwise starting at the upper right corner of the box as well.
4. If all intersections are interior to the box, the enter and exit sequences will be cyclic with each other, and B[i] is the minimum bounding box of the intersections.
5. Otherwise, align the two sequences to an arbitrary element (by cyclic rotation).
6. Find the elements in the sequences where they first differ. Those two lines must have an intersection P outside of the box, so form B[i+1] by growing B[i] to include P.
7. Repeat from 2.

This isn't complete because the entering and exiting sequences aren't well defined if a group lines have a common entering or exiting point on the boundary. For each group of lines L with a common entering or exiting point, use a slightly larger box for ordering L.

Note that this algorithm doesn't emit all the intersections, but it does guarantee (I hope) that the box contains them all.

回答2:

In O(n log n) time? Wow. I'd not have guessed that this were possible.

I don't see any other answers here, yet, so here is one idea -- a shot in the dark, admittedly. You can make of it what you will.

Idea: Begin by sorting the lines by bearing or slope. Other things being equal, nearly parallel lines would seem likely to intersect at outlying points; and, of course, it is the outlying points that interest you.

Your convex-hull idea sounds as though it should be right, but consider that the hull may have nearly parallel sides whose tangents or extensions intersect far from the area of interest. All in all, it sounds like a major programming job. Good luck.