Computational Geometry >

Minimum Square Covering

INPUT: A rectilinear polygon represented by a list of every other corner. Move the blue circles to change the polygon.

OUTPUT: A smallest set of squares whose union is the polygon.

TEST CASES:

• Rectangles: square fat thin
• U shapes: fat medium thin
• Pack of cards: two three four
• Thin roads: 2 legs 3 legs 4 legs (overlap)
• Fat roads: 2 legs 3 legs
• Halls and rooms: tight apart H-shape rectangular rooms
• Rooms and corridors: linear c-shaped

CONTROLS:

• Add a point
• Remove a point by dragging it over the left or top border.
• Save your configuration by copying the PermaLink.
• Export then right-click to save the image:
• Move all points randomly;
• Remove all points by clicking Clear.
• Interrupt the current calculation.
• Automatically find the minimum covering