Given a list of paths(with start and end coordinates) that are only horizontal and vertical, how can I find all the rectangles that they form?
Details:
- The end points of the rectangle must be end-points of their constituent edges. i.e rectangles formed from the intersections of lines are not needed.
- The x,y of start and end, represented as complex numbers of each line is given.
- The output should be four lines representing each edge of the rectangle
This is my naive implementation which is too slow. Are there any other approaches?
def find_rectangles(paths):
vertical_paths = filter(lambda path: is_vertical(path), paths)
horizontal_paths = filter(lambda path: is_horizontal(path), paths)
vertical_paths.sort(key=lambda path: path.start.imag, reverse=True)
horizontal_paths.sort(key=lambda path: path.start.real)
h_pairs = []
for i in range(0, len(horizontal_paths) - 1):
for j in range(1, len(horizontal_paths)):
if horizontal_paths[i].start.real == horizontal_paths[j].start.real and horizontal_paths[i].end.real == horizontal_paths[j].end.real:
h_pairs.append((horizontal_paths[i], horizontal_paths[j]))
v_pairs = []
for i in range(0, len(vertical_paths) - 1):
for j in range(1, len(vertical_paths)):
if vertical_paths[i].start.imag == vertical_paths[j].start.imag and vertical_paths[i].end.imag == vertical_paths[j].end.imag:
v_pairs.append((vertical_paths[i], vertical_paths[j]))
rects = []
for h1, h2 in h_pairs:
for v1, v2 in v_pairs:
if h1.start == v1.start and v1.end == h2.start and h1.end == v2.start and h2.end == v2.end:
rects.append(Rect(h1.start, h1.end, h2.end, h2.start))
return rects
Edit:(Improvements from all suggestions)
Main difference is I am storing all horizontal edges' end-points in a set so look up for them is O(1):
def find_rectangles(paths):
vertical_paths = [path for path in paths if is_vertical(path)]
horizontal_paths_set = set([(path.start, path.end) for path in paths if is_horizontal(path)])
vertical_paths.sort(key=lambda pair: path.start.imag, reverse=True)
v_pairs = [pair for pair in list(itertools.combinations(vertical_paths, 2)) if pair[0].start.imag == pair[1].start.imag and pair[0].end.imag == pair[1].end.imag]
rects = []
for v1,v2 in v_pairs:
h1 = (v1.start, v2.start)
h2 = (v1.end, v2.end)
if(h1 in horizontal_paths_set and h2 in horizontal_paths_set):
rects.append(Rect(h1[0], h1[1], h2[1], h2[0 ]))
return rects
My new code runs much much faster, but it still is on the order of O(n2). Any suggestion to improve upon it is welcome.
==
within a for loop can be replaced by boolean indexing to filter the results. – Joefilter
. Something likevertical_paths = [path for path in paths if is_vertical(path)]
. – Mike Borkland