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