CODEWITHSUNDEEP
algorithmgeometrypolygoncomputational-geometry
Josh C.
Josh C.

Reputation: 4363

Rectilinearize a non-intersecting polygon

I have some non-intersecting polygon, and I need to "square" it up so that all angles are 90 degree angles.

Is there a good algorithm to do this?

EDIT

Allowing self-intersections in the resultant polygon, I'm looking for the "best" method of tesselating rectangular shaped tiles in the original polygon. The rectangles can span the original edges of the polygon, and the goal is to fit the most rectangles squarely into the polygon.

Upvotes: 0

Views: 483

Answers (2)

Geom
Geom

Reputation: 57

It is not guaranteed that you can avoid self-intersections if you allow just one new segment per original segment.

You can use a quadtree to subdivide the line segments until each line segment is alone in its quadtree cell (alternatively you can subdivide further until some approximation ratio is reached). Then replace each line-segment by two line segments of its bounding box.

hth

Upvotes: 0

Kevin
Kevin

Reputation: 76194

You can replace each side of the polygon with a "staircase" which resembles the original side, like so:

sawtooth algorithm output

the more "steps" you add to each staircase, the closer it resembles the original shape.

Upvotes: 0

Related Questions