StackOverflow 社区您好！
我目前面临着检测可以由给定线段集形成的旋转矩形的挑战。总共有大约 5000 条线段，性能成为一个重要问题。
为了更好地说明问题，请考虑以下示例：
segments = [
[(0, 0), (10, 0)],
[(10, 0), (10, 10)],
[(10, 10), (0, 10)],
[(0, 10), (0, 0)],
]
从上面的例子来看，这些线段形成了一个矩形。但是，该矩形并未旋转。但在其他情况下，这些线段可能会形成一个旋转的矩形，我希望能够检测到这一点。
如何有效地确定给定的一组线段是否可以形成旋转的矩形？是否有任何现有的算法或 Python 库可以帮助解决这个问题？
提前感谢您的指导和建议！
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 或 IV， arctan 将为您提供 -90° .. 90° 范围内的角度 θ。 按这些角度进行索引/排序，可能使用 关系数据库管理系统。
选择几度的 theta_tolerance，或者理想情况下为零。
现在迭代所有段，按角度排序。 遇到新的 θ 时，抓取所有后续线段 在它的承受范围之内。 现在生成角度 θ ± 90°， 将它们映射回象限 I 和 IV。 抓住与那些角度匹配的所有线段。 看看这些线段是否相交，从而可以形成一个矩形。 （IDK，你的问题规范在这个细节上有点含糊。 也许要求是段 1 的 (x, y) 必须与段 2 的 (x, y) 完全匹配， 在这种情况下，你的问题会容易得多。）
确定了一个矩形后， 将其四个部分标记为“完成” 所以你不要重复计算它 当你再转过 90° 时。