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.
should not be simplified into
Because now we have an intersection
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?