algorithm - 如何有效地检查路径是否在一系列边界框内？

Question

给定一系列相互连接的矩形边界框，以及由多项式(或多项式样条)描述的路径，如何检查路径是否完全在边界框内，准确地？

Answer 1

不知道这是否足够精确，但一种解决方案是遍历矩形并使用多项式求解器找出多项​​式的位置穿过矩形中的 4 条线之一(A-B、B-C、C-D、D-A)。然后将这些交叉点与多项式求值一起使用，以找出多项式位于每个矩形内的 xs。如果这些区间的并集包含多项式的定义区域，多项式位于矩形内。

粗糙的伪python:

def get_covering_intervals(rectangle, polynomial):
    crossing_points = []

    # Find crossing points
    for line, x_range in get_lines_from_rectangle(rectangle):
        roots = solve_polynomial(polynomial-line)
        for root in roots:
            if x_range.min < root < x_range.max:
                crossing_points.append(root)
    crossing_points.extend(rectangle.x_range)
    crossing_points.sort()

    # Find covered areas
    covered_intervals = []
    prev_x = crossing_points[0]
    for x in crossing_points[1:]:
        if polynomial((x+prev_x)/2) in rectangle:
            covered_intervals.append(Interval(prev_x, x))
        prev_x = x

    return covered_intervals

polynomial = Polynomial([10, 2, 4])  # 10x^2+2x+4
definition_area = Interval(-1.5, 2.5)
rectangles = [Rectangle((-1.25, -1), (1, 1.25), (1.25, 1), (-1, -1.25)), ...]

covered_intervals = []
for rectangle in rectangles:
    covered_intervals.extend(get_covering_intervals(rectangle, polynomial))

covered = union(covered_intervals)
return definition_area in covered

对于多项式样条，必须对样条中的每个多项式/定义区域重复此操作。