I'm working on a piece of software that deals with several polygons, These polygons have far to many corners and I would like to reduce them such that the total area in the polygons and general shape don't change overly much (within a few percent). There is however one problem and that is that these polygons are not allowed to intersect.

These polygons can also be inside of each other or next to each other. So for example the following polygon polygon

should not be simplified into


Because now we have an intersection

but something like is ok

is ok. Do note how it's possible for one polygon to contain another.

This is also something I would (if possible) like to be somewhat efficient with, currently the program is bottlenecked by an O(n^3) calculation somewhat later so any solution that is faster then that is good but anything O(n³) or slower is a no go. Anybody know how to check this efficiently?

  • $\begingroup$ I hope I picked the right stack exchange for this, I also considered the computer science exchange. If this is OT here please don't be mad. $\endgroup$ – Thijser Mar 15 '17 at 21:17
  • $\begingroup$ You should consider Stack Overflow. $\endgroup$ – Bobson Dugnutt Mar 15 '17 at 21:25
  • $\begingroup$ It looks for me like collision detection with bounding areas that detects intersection between circles or polygons, particularly if the distance between the circles' centers is less than the circles' combined radii (length < || > r1 +r2). For more complicated scenarios, such as collisions between polygons of arbitrary size and shape you could use the Separating Axis Theorem - a mathematical equivalent of shining a light on two polygons from different angles. $\endgroup$ – usiro Mar 16 '17 at 1:15

You might start by computing the Hausdorff distance between the two polygons. It can easily be done in $O(n^2)$ time where $n$ is the total number of vertices. If the distance is $r$, then changes to both polygons by Hausdorff distances $< r/2$ will be safe.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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