4

Given a series of interconnected rectangular bounding boxes, and a path that is a described by a polynomial (or a polynomial spline), how can I check whether the path is entirely inside the bounding boxes, precisely?

Nyaruko
  • 4,329
  • 9
  • 54
  • 105
  • 1
    The easiest way would be to rasterize the spline into points and check if each of the rasterized points lies in one of the bounding boxes. With a high enough point density, this should work for any spline, but I'm not sure if this is the solution you were looking for. – EvilTak Jul 17 '18 at 05:05
  • may be [OBB](https://stackoverflow.com/a/42997918/2521214) of intervals between control points of your curve would help you decide how and which control points to modify. (by comparing the OBBS of curve and input. – Spektre Jul 17 '18 at 07:17

1 Answers1

2

Dont know if this is precise enough, but one solution would iterate through the rectangles and use a polynomial solver to find out where the polynomial crosses one of the 4 lines in the rectangle (A-B, B-C, C-D, D-A). Then use these crossing points together with the polynomial evalution to find out for which xs the polynomial lies inside each rectangle. If the union of these intervals contains the definion area of the polynomial, the polynomial lies withing the rectangles.

Rough pseudo-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

For polynomial splines, this has to be repeated for each polynomial/definition area in the spline.

kuppern87
  • 1,125
  • 9
  • 14