计算给定矩形中直线范围的最佳算法是什么？

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 条组成线中的每一条，并找到所有线段交点，以将线过滤到仅与它们真正相交的矩形。然后，您可以使用与给定相交

(line, rect)

元组列表来计算每个相交面积的相同方法。

获取所有线交点在相关的 SE.stackexchange 问题和其他地方进行了讨论，我将考虑一种超出此处范围的精确算法（其中一个算法是Bentley-Ottmann）。下面是如何将此问题转换为交集一和反向的草图。

def get_all_rect_lines(rects):
  # For each rect in rects, get the 4 lines that make up rect.
  # Return all lines in one list.
  # You should also keep track of which line corresponds to which rect.

# Convert to dict of lists: { line: rects_containing_line }
# This can rely on the correspondence from the above method.
def rect_lines_to_rect_dict(rect_lines):
  rect_dict = {}
  for (rect, line) in rect_lines:
    if line not in rect_dict:
      rect_dict[line] = [rect]
    else:
      rect_dict[line].append(rect)
  return rect_dict

def rect_line_intersections(rects, lines):
  rect_lines = get_all_rect_lines(rects)
  rect_dict = rect_lines_to_rect_dict(rect_lines)
  
  # Use line intersections algorithm of choice
  all_intersections = get_all_intersections(lines + [line for _, line in rect_lines])

  # Finally, filter all the intersections to line-rect intersections.
  line_set = set(lines)
  real_intersections = []
  for a, b in all_intersections:
    if a in line_set and b in rect_dict:
      real_intersections += [(a, r) for r in rect_dict[b]]
    if b in line_set and a in rect_dict:
      real_intersections += [(b, r) for r in rect_dict[a]]

  # This will give you pairs of rect-line intersections.
  # Then use your current approach to find the total intersection length.
  return real_intersections

可能有更好的算法来专门查找两个列表之间的交集，而不需要合并和拆分步骤，但我不知道有什么。