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?

Answer 1

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.

Answer 2

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.

Answer 3

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.