[OSGeo-UK] Computational Geometry Problem

Jo doublebyte at gmail.com
Fri Jun 26 11:33:05 EDT 2009


Hi,First of all, I apologize if this post is unrelated to the scope of the
mailing list (I hope not).
I have to find an algorithm to draw the maximum enclosed circle in a
polygon, which is slightly different from the "well-known" geometry problem:
"maximum empty circle"; in this case, not only all the vertices need to be
outside the circle but also the entire perimeter of the polygon must *not*
be inside the circle.
I can get the center of the polygon using Voronoi Diagrams: anybody has any
suggestions or recomendations of how to calculate its radius?
Also, I would like to avoid as much as possible iterative processes (as they
can be slow when dealing with a high number of polygons, that have
complex frontiers)...
It would be really appreciated any ideas on this, or even references to
libraries that could help me... Im not finding a lot of stuff about this on
the web :-/ Im using C/C++ but all ideas are welcome, really...

Thanks in advance for your time!
                                        cheers,
                                               Jo


-- 
"Law 1: Every program can be optimised to be smaller. Law 2: There's always
one more bug. Corollary: Every program can be reduced to a one-line bug."

        (Lubarsky's Laws of Cybernetic Entomology)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/uk/attachments/20090626/83184ad9/attachment.html


More information about the UK mailing list