代码之家  ›  专栏  ›  技术社区  ›  Nyaruko

如何有效地检查路径是否在一系列边界框中?

  •  4
  • Nyaruko  · 技术社区  · 6 年前

    给定一系列 互连矩形边界框 , 以及一条由 多项式的 (或多项式样条曲线) 我怎么检查这条路 完全在里面 边界框, 准确地说 ?

    1 回复  |  直到 5 年前
        1
  •  2
  •   kuppern87    6 年前

    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