Hello StackOverflow community!
I am currently facing a challenge in detecting rotated rectangles that can be formed from a given set of line segments. With a total of approximately 5000 line segments, the performance becomes a significant concern.
To better illustrate the problem, consider the following example:
segments = [
[(0, 0), (10, 0)],
[(10, 0), (10, 10)],
[(10, 10), (0, 10)],
[(0, 10), (0, 0)],
]
From the above example, these line segments form a rectangle. However, this rectangle is not rotated. But in other cases, the segments might form a rotated rectangle, and I want to be able to detect that.
How can I efficiently determine if a given set of line segments can form a rotated rectangle? Is there any existing algorithm or Python library that can assist with this?
Thank you in advance for any guidance and suggestions!
import cv2
import numpy as np
import pandas as pd
from tqdm import tqdm
def find_rectangles(segments):
"""
Finds all rectangles in a list of segments.
Args:
segments: A list of segments.
Returns:
A list of rectangles.
"""
rectangles = []
segments = np.array(segments)
for i in tqdm(range(len(segments))):
l1 = segments[i]
l2 = None
l3 = None
l4 = None
for j in range(len(segments)):
if are_perpendicular(l1, segments[j]):
l2 = segments[j]
break
if l2 is None:
continue
for j in range(len(segments)):
# l3: Vuong goc voi l2, song song voi l1, ke voi l2
z = segments[j]
if are_parallel(l1, segments[j]) and are_perpendicular(l2, segments[j]):
l3 = segments[j]
break
if l3 is None:
continue
for j in range(len(segments)):
# l4: Vuong goc voi l1, song song voi l2, ke voi l3
if (
are_perpendicular(l1, segments[j])
and are_parallel(l2, segments[j])
and are_perpendicular(l3, segments[j])
):
l4 = segments[j]
break
if l4 is None:
continue
lines = np.array([l1, l2, l3, l4])
points = lines.reshape(-1, 2)
x = points[:, 0]
y = points[:, 1]
xmin, ymin, xmax, ymax = min(x), min(y), max(x), max(y)
rectangles.append(Rectangle(xmin, ymin, xmax, ymax))
print("Found rectangle: ", rectangles[-1])
return rectangles
def are_parallel(v1, v2):
"""
Determines if two segments are parallel.
Args:
segment1: A segment.
segment2: A segment.
Returns:
True if the segments are parallel, False otherwise.
"""
slope1 = compute_slope(v1)
slope2 = compute_slope(v2)
return slope1 == slope2
def are_adjacent(segment1, segment2):
"""
Determines if two segments are adjacent.
Args:
segment1: A segment.
segment2: A segment.
Returns:
True if the segments are adjacent, False otherwise.
"""
p1, p2 = segment1
p3, p4 = segment2
return (p1 == p3).all() or (p1 == p4).all() or (p2 == p3).all() or (p2 == p4).all()
def compute_slope(seg):
seg = seg[1] - seg[0]
angle = np.angle(complex(*(seg)), deg=True)
return angle
def are_perpendicular(v1, v2):
"""
Determines if two segments are perpendicular.
Args:
segment1: A segment.
segment2: A segment.
Returns:
True if the segments are perpendicular, False otherwise.
"""
# Không chùng nhau
# points = np array shape (-1, 2)
points = np.array([v1[0], v1[1], v2[0], v2[1]])
xmin, ymin, xmax, ymax = min(points[:, 0]), min(points[:, 1]), max(
points[:, 0]
), max(points[:, 1])
is_overlap = (xmin == xmax) or (ymin == ymax)
if is_overlap:
return False
# adjacent
cond2 = are_adjacent(v1, v2)
if not cond2:
return False
# Vuông góc
s1 = compute_slope(v1) # in degree
s2 = compute_slope(v2) # in degree
cond3 = np.abs(s1 - s2) == 90
return cond3
class Rectangle:
"""
Represents a rectangle.
Attributes:
top_left: The top left corner of the rectangle.
bottom_right: The bottom right corner of the rectangle.
"""
def __init__(self, xmin, ymin, xmax, ymax):
"""
Initializes a rectangle.
Args:
top_left: The top left corner of the rectangle.
bottom_right: The bottom right corner of the rectangle.
"""
self.top_left = (xmin, ymin)
self.bottom_right = (xmax, ymax)
def __str__(self):
"""
Returns a string representation of the rectangle.
Returns:
A string representation of the rectangle.
"""
return "Rectangle(top_left=({}, {}), bottom_right=({}, {}))".format(
self.top_left[0],
self.top_left[1],
self.bottom_right[0],
self.bottom_right[1],
)
def draw_line(df):
x = df["x0"].values.tolist() + df["x1"].values.tolist()
y = df["y0"].values.tolist() + df["y1"].values.tolist()
xmin, ymin, xmax, ymax = min(x), min(y), max(x), max(y)
w, h = xmax - xmin, ymax - ymin
mat = np.zeros((ymax - ymin + 1, xmax - xmin + 1, 3), dtype=np.uint8)
df[["x0", "x1"]] = df[["x0", "x1"]] - xmin
df[["y0", "y1"]] = df[["y0", "y1"]] - ymin
for x0, y0, x1, y1 in tqdm(df[["x0", "y0", "x1", "y1"]].values.tolist()):
cv2.line(mat, (x0, y0), (x1, y1), (255, 255, 255), 1)
# cv2.imshow("mat", mat)
cv2.imwrite("mat.png", mat)
print('write mat')
if __name__ == "__main__":
segments = [
[(0, 0), (10, 0)],
[(10, 0), (10, 10)],
[(10, 10), (0, 10)],
[(0, 10), (0, 0)],
]
# Find all rectangles in the list of segments.
rectangles = find_rectangles(segments)
# Print the rectangles.
rects = []
for rectangle in rectangles:
print(rectangle)
I would group the segments by their vector direction and size. Then in each group you will have segments that are parallel and of the same size. These are candidates for opposing sides of rectangles. When also the connecting sides are perpendicular we have a match.
Here is a way to do this:
from collections import defaultdict
from itertools import combinations
class Vector(tuple):
def __add__(self, other):
return Vector((self[0] + other[0], self[1] + other[1]))
def __sub__(self, other):
return Vector((self[0] - other[0], self[1] - other[1]))
def __mul__(self, other): # dot product
return self[0] * other[0] + self[1] * other[1]
def to_vector_pairs(segments):
# Normalise direction of each segment and turn tuples into Vectors
return [
list(map(Vector, sorted(segment)))
for segment in segments
]
def key_by_vector(segments):
d = defaultdict(list)
for a, b in segments:
d[b - a].append(a)
return d
def find_rectangles(segments):
vectors = key_by_vector(to_vector_pairs(segments))
for v, offsets in vectors.items():
if v[0] <= 0 or v[1] < 0: # only look at vectors in first quarter
continue
for a, b in combinations(sorted(offsets), 2):
side = b - a # third side connecting the two parallel segments
# check 3rd side is perpendicular and 3rd & 4th are segments
if v * side == 0 and side in vectors and a in vectors[side] and a + v in vectors[side]:
yield a, b, b + v, a + v
Here is an example use:
segments = [
[(3, 0), (6, 1)],
[(6, 1), (10, 1)],
[(10, 1), (10, 4)],
[(10, 4), (9, 6)],
[(9, 6), (7, 8)],
[(7, 8), (4, 7)],
[(4, 7), (3, 10)],
[(3, 10), (0, 9)],
[(0, 9), (1, 6)],
[(1, 6), (3, 0)],
[(6, 1), (6, 3)],
[(6, 3), (10, 4)],
[(9, 6), (6, 3)],
[(6, 3), (4, 5)],
[(4, 5), (7, 8)],
[(4, 5), (4, 7)],
[(4, 7), (1, 6)],
[(4, 7), (6, 1)],
[(6, 1), (5, 1)],
[(5, 1), (5, 3)],
[(5, 3), (6, 3)]
]
# Find all rectangles in the list of segments.
rectangles = find_rectangles(segments)
# Print the rectangles.
for rectangle in rectangles:
print(rectangle)
Output for this example:
((0, 9), (1, 6), (4, 7), (3, 10))
((1, 6), (3, 0), (6, 1), (4, 7))
((4, 5), (6, 3), (9, 6), (7, 8))
((5, 1), (5, 3), (6, 3), (6, 1))