Algorithm to Find Overlapping Line Segments

Question

n4------------------n3--------------------n2--n1
|                    |                    |    |
|                    |                    | P1 |
|                    |                    |    |
|                    |                    n6--n5
|                    |                    |
|              n11--n10                   |
n17      P4     |    |         P2         |
|               | P3 |                    n7
|              n12---n9                   |
|               |                         n8
|               |                         |
n16------------n15---------n14------------n13

In the above ASCII art, there are four polygons (P1, P2, P3, P4) with exactly-overlapping line segments. For example, polygon P2 (formed by line segments between nodes n3, 10, 9, 12, 15, 14, 13, 8, 7, 6, and 2) and P1 (n1, 2, 5, and 6) overlap at the line segment between n2 and n6.

What is the fastest way to find line segments that overlap exactly?

Your example's description is wrong. P1 has nodes 1,2,5,6 and P2 has nodes 2,3,10,9,12,15,14,13,8,7,6. — perimosocordiae, Sep 15 '09 at 03:35
Before I answer, you should mention how your shapes are stored. That kind of influences the answer. — twolfe18, Sep 15 '09 at 03:45
are the line segments only straight lines? Do you want an algorithm that given two polygons finds what line segments they 'overlap' over? — Joshua, Sep 15 '09 at 03:46
@twolfe18 So far the data is stored as an ordered list of nodes. A polygon is actually a ring of nodes where the first and last nodes are the same (in Java: ==, not .equals()) — magneticMonster, Sep 15 '09 at 04:00
@Joshua Each node is a point in space, and the line segments are straight between the nodes. Since one "side" of a polygon can have multiple nodes (e.g. n7, 8, and 13) they don't necessarily have to be straight. Assume for this that the polygons wont overlap -- only their edges will. They will be adjacent, not overlapping — magneticMonster, Sep 15 '09 at 04:01

score 3 · Accepted Answer · answered Sep 15 '09 at 03:52

3

If each shape is a list of edges then:

initialize map<edge, list of shapes> map
for each Shape s
  for each Edge e in s
    list l = map.get(e)
    if(l == null) 
      l = new list()
    l.add(s)
    map.put(e, l)

for each <edge, list> in map.entries
  if(list.size > 1)
    do something with this common edge

its O(edges), and your not going to do better than that. this solution might not be satisfactory depending on what you want to do specifically though.

answered Sep 15 '09 at 03:52

twolfe18

2,228
4
24
25

1

+1. As an additional note, if the shape is stored as a list of points, you can just walk over the points pairwise and have the edge represented by a sorted pair (p1,p2) where p1 < p2 => p1.x < p2.x or p1.x = p2.x and p1.y <= p2.y. – Ants Aasma Sep 15 '09 at 20:21

score 0 · Answer 2 · answered Sep 15 '09 at 05:21

Given N line segments, in the worst case there can be O(n^2) intersections. Just think of the case where you have N polygons where each polygon shares the same edge. Unless there is an added constraint to prevent this situation from happening (that you omitted to add) then the best algorithm you can come up with will be O(N^2) in the worst case, since simply listing the intersections is O(N^2).

In practice, the most efficient algorithms in computational geometry for finding intersections of line segments are sweep line algorithms. Their worst case running time to find all intersections is O(k log n) where k is the number of interesections (this can be N^2, however it rarely is.)

You can find a description of exactly the algorithm you need in Introduction to algorithms by Thomas H Cormen in the section on computational geometry.

how do you get O(n^2)? if you had n shapes, each with m edges, it would be O(n*m). you clearly cannot do better than that because you have to inspect every edge. my algorithm is O(n*m). also, you didn't answer the question. — twolfe18, Sep 15 '09 at 14:37
I said *line segments*. The example I gave with polygons was just an illustration. The O(n^2) algorithm you gave is obvious and trivial. In practice, the sweepline algorithms out perform the trivial algorithms greatly. — ldog, Sep 15 '09 at 16:41

score 0 · Answer 3 · answered Oct 11 '09 at 03:41

twolfe18's algorithm looks good. There may be an added complication, however, if matching edges are not identically described. In your example, P1 and P2 both share the n2-n6 edge. But P2's edge might be described by the segment n2-n7 instead (if n2-n6 and n6-n7 are colinear). You'll then need a more complicated hashing method to determine if two edges overlap. You can tell whether two edges overlap by mapping segments onto lines, looking up the line in a hashtable, then testing whether two segments on a line intersect using an interval tree in parameter space on the line.

Algorithm to Find Overlapping Line Segments

3 Answers3