[geos-devel] Computational Geometry Problem

[Sanak]

Hi Jo,

Hmm.. I think that Voronoi Diagrams approach is usefull for computing
"circumscribed circle" but not "inscribed circle", if the geometry is
triangle.

http://en.wikipedia.org/wiki/Circumscribed_circle

But your result image seems to be well computed and have no problem.

Thanks for your reply.

Regards,

Sanak.

2009/6/28 Jo <doublebyte at gmail.com>

> I thought I would published my solution here, for all the ppl who are lazy
> like me, and google for a solution before posting...
> Dis problem is reduced to finding the InCirce of a polygon, which is
> slightly different from the well-known geometry problem: largest empty
> circle.
>
>
> http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/LgEmptyCircle/lccli.htm<http://www.personal.kent.edu/%7Ermuhamma/Compgeometry/MyCG/CG-Applets/LgEmptyCircle/lccli.htm>
>
> In the "largest empty circle" we calculate the Voronoi Diagrams and test
> each of its vertexes inside the convex-hull as a candidate for the center.
> It all comes down
> to a max-min optimization of the radius: the largest radius, that does not
> contain any points inside (and therefore, the circle is "empty").
> The Largest inscribed circle, is very similar except that here we look for
> a circle that does not contain the *actual* polygon (rather than just its
> vertexes).
> The distance we wont to test here is the (minimum) distance of the
> candidate centre to the polygon.
> I struggled a little bit here to measure a distance from polygon to a point
> that is located inside it, and ended up having to decompose the polygon to
> its boundary
> to get it done (Im using OGR)!
> Here is the result:
>
> http://ladybug.no-ip.org/files/inCircle.png
>
> Just as a final note: there are plenty (exact) implementations of the
> incircle (or apotheom) of a triangle or a regular polygon, but it becomes a
> bit complicated when we are dealing
> with irregular geometries, which is my case... (and prob everyone else
> workin in GIS)
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20090628/5844fbe0/attachment.html