Search code examples
algorithm2dbounding-box

Smallest bounding box enclosing set of box on wraped 2D space

I have finite 2D space with wrapped coordinates both way (I mean going left will wrap around into right edge, the same going for up/down).

I also have a set of box aligned to axes. These boxes have float coordinates inside space.

Problem: find smallest bounding box aligned to axes enclosing all boxes. Bounding box CAN be wrapped around.

Samples:

Sample 1 Sample2

(Pink denotes space boundaries, red boxes needs to be enclosed, blue border denotes smallest possible bounding box)

Solution

  • A sweeping algorithm can be used to find the largest vertical gap, i.e. maximally distant two vertical lines that have no boxes between them.

    Similarly, a sweeping algorithm can be used to find the largest horizontal gap. Obviously, both gaps can wrap around edges.

    The shape left by removing the gaps from the 2D space is the smallest bounding box containing all boxes. I am not sure if it's guaranteed to have the smallest area of all the containing boxes, but there exists no bounding box that has both dimensions smaller than this one. If it existed, it would define two gaps (vertical & horizontal) both larger than the maximal ones.

    The sweeping to detect both gaps can be done in O(N * log N) where N is the number of boxes.