4 
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?

Improve this question
6
  • 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. Commented Sep 15, 2009 at 3:35
  • @perimosocordiae Thanks. I believe I fixed the description. Commented Sep 15, 2009 at 3:39
  • Before I answer, you should mention how your shapes are stored. That kind of influences the answer. Commented Sep 15, 2009 at 3:45
  • are the line segments only straight lines? Do you want an algorithm that given two polygons finds what line segments they 'overlap' over? Commented Sep 15, 2009 at 3: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()) Commented Sep 15, 2009 at 4:00

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

+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.
0

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.

Improve this answer

2 Comments

how do you get O(n^2)? if you had n shapes, each with m edges, it would be O(nm). you clearly cannot do better than that because you have to inspect every edge. my algorithm is O(nm). also, you didn't answer the question.
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.
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.