如何创建计算给定矩形中线条范围的最佳算法

Question

正如标题所示，我正在尝试找到一种算法来计算给定矩形中存在的线段的所有距离的总和。

您已获得输入中矩形的对边坐标以及每个线段的起始和结束坐标。

输入如下所示：

1 (number of test cases)
1 (number of rectangles)
1 1 2 2 (each rectangle with the opposite side coordinates [1, 1], [2, 2])
2 (number of line segments)
0 0 3 3 (each line segment with the start and end coordinates [0, 0], [3, 3])
1 0 1 3 ...

此输入的预期输出是

2.41...

我创建了一个可行的解决方案，但对于大型输入案例来说还不够。

在我的实现中，我检查直线与矩形的交点并计算这两点之间的距离：

from shapely.geometry import LineString, Polygon
import math


def check_intersection(rect, line):
    polygon = Polygon(rect)
    line_segment = LineString(line)
    if polygon.intersects(line_segment):
        return polygon.intersection(line_segment).coords

def main(rects, lines):
    calc = 0
    for rect in rects:
        for segment in lines:
            inter = check_intersection(rect, segment)
            if inter:
                try:
                    calc += math.sqrt(math.pow((inter[1][0] - inter[0][0]), 2) + math.pow((inter[1][1] - inter[0][1]), 2))
                # when there is only one intersection, there isnt any area of the segment in the rect (I think)
                except IndexError:
                    pass

    return round(calc, 2)

with open("input", "r") as f:
    n = int(next(f).strip())
    rectangles = []
    lines = []
    for i in range(n):
        rect_count = int(next(f).strip())
        for _ in range(rect_count):
            rectangle_coords = list(map(int, next(f).strip().split(" ")))
            x1, y1, x2, y2 = rectangle_coords
            x3, y3 = x1, y2
            x4, y4 = x2, y1
            rectangles.append([(x1, y1), (x3, y3), (x2, y2), (x4, y4)])
        line_count = int(next(f).strip())
        for _ in range(line_count):
            line_coords = list(map(int, next(f).strip().split(" ")))
            line_coords = [
                (line_coords[i], line_coords[i + 1]) for i in range(0, len(line_coords), 2)
            ]
            lines.append(line_coords)

        print(main(rectangles, lines))

Answer 1

尚不清楚输入的确切属性是什么，或者它们将达到多大。但一种解决方案是将矩形分成 4 条组成线中的每一条，并找到所有线段交点，以仅将线过滤到它们真正相交的矩形。然后您可以使用与计算面积相同的方法。

加速这条线相交的一种方法，取自ratchet Freak's Answer对相关问题的回答，是按最左边的X坐标对所有

lines

和

rect_lines

进行排序。然后，您可以迭代所有

rect_lines

，直到它们最左边的 X 坐标大于

line

最右边的 Y 坐标。然后，当它们匹配时，您可以更仔细地检查交叉点。

一旦获得了

[(line, rect_line)]

交叉路口列表，您就可以遍历并获取每个真实交叉路口的准确交叉路口长度。