Friday, January 21, 2011

straight skeleton for polygon simplification

We can simplify shapes using the straight skeleton:

simplify_outlines

If we grow (offset) the polygon (a) we remove reflex corners(c), and if we shrink it we remove convex corners(b) (for lack of a better phrase). If we apply both offsets in sequence we have a fairly robust polygon simplification tool (d).

There are several drawbacks with the straight skeleton as a simplification tool. It does not introduce new edges to the polygon, so polygons that do not contain an edge with a good approximation for the local region are not simplified well. "Very" reflex corners have a disproportionate effect on the result. However this may be rectified using a variation of the linear axis. The computational complexity is also higher than that of existing algorithms.

If we view the process as 3d roofs, we get the following diagrams for interior-offset, exterior offset and a combination of both:
simplify

The advantages are that it is very conceptually simple, robust to any input shape and can effect genus change in the process of simplification. The weighted straight skeleton would also allow different weights to be applied to different edges. Perhaps this could be used to preserve particular features? The theory extends (easily?) into higher dimensions.



No comments:

Post a Comment