Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm using the Douglas peucker (DP) algorithm to simplify some (2d) closed paths forming a shape. This works pretty good, but not so much for closed paths that have some symmetry. Take for example a pyramid like shape, with the slopes essentially being staircases. Depending where you define the start for DP it will (obviously) result in different simplified shapes.

Does anyone know of some sort of generic symmetry preserving simplification algorithm? In the case of (a top up) pyramid you could force this manually by having DP run from the end vertice of the top line to the first vertice of the bottom line, and another run from the end vertice of the bottom line to the first vertice of the top line. but this is of course very specific to the symmetry of this particular pyramid.

share|improve this question
up vote 1 down vote accepted

Break your closed shape into open paths, some of which are related by known symmetry transformations. For example, depending on your needs and where control points are located, a circle (to be simplified into a polygon) can be divided into two halves or four quarters related by rotation or reflection, or a rhombus into its four sides.

Then you can compute the simplification of one of parts of the original curve and replace all its copies with transformed copies of the simplified curve.

share|improve this answer
Yes that sounds like the logical thing to do.. Do you know of any methods to find line segments that could be candidates (exposing certain symmetry like features), or would this be too domain specific and implemented per case? – Martijnh Aug 9 '13 at 17:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.