<span class="Apple-style-span" style="border-collapse: collapse; "><div>You are totally right, and I can see in some cases, the algorithm is unable to find the right candidate to centre, searching only among the Voronoi vertices.</div>
<div>Anybody has any suggestions for choosing the candidates of centres for the maximum &quot;circumscribed circle&quot;? It does not need to  touch all vertices, but it needs to be the largest circle</div><div>that fits inside the polygon.</div>
<div>And btw, is an irregular complex polygon...</div><div>                                                                      cheers,</div><div>                                                                                    Jo</div>
<div><br></div><div><br></div>Date: Sun, 28 Jun 2009 08:19:58 +0900<br>From: Sanak &lt;<a href="mailto:geosanak@gmail.com" style="color: rgb(20, 125, 186); ">geosanak@gmail.com</a>&gt;<br>Subject: Re: [geos-devel] Computational Geometry Problem<br>
To: GEOS Development List &lt;<a href="mailto:geos-devel@lists.osgeo.org" style="color: rgb(20, 125, 186); ">geos-devel@lists.osgeo.org</a>&gt;<br>Message-ID:<br>       &lt;<a href="mailto:5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com" style="color: rgb(20, 125, 186); ">5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com</a>&gt;<br>
Content-Type: text/plain; charset=&quot;iso-8859-1&quot;<br><br>Hi Jo,<br><br>Hmm.. I think that Voronoi Diagrams approach is usefull for computing<br>&quot;circumscribed circle&quot; but not &quot;inscribed circle&quot;, if the geometry is<br>
triangle.<br><br><a href="http://en.wikipedia.org/wiki/Circumscribed_circle" target="_blank" style="color: rgb(20, 125, 186); ">http://en.wikipedia.org/wiki/Circumscribed_circle</a><br><br>But your result image seems to be well computed and have no problem.<br>
<br>Thanks for your reply.<br><br>Regards,<br><br>Sanak.</span><br><br><div class="gmail_quote">2009/6/28  <span dir="ltr">&lt;<a href="mailto:geos-devel-request@lists.osgeo.org">geos-devel-request@lists.osgeo.org</a>&gt;</span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Send geos-devel mailing list submissions to<br>
        <a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
        <a href="http://lists.osgeo.org/mailman/listinfo/geos-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
or, via email, send a message with subject or body &#39;help&#39; to<br>
        <a href="mailto:geos-devel-request@lists.osgeo.org">geos-devel-request@lists.osgeo.org</a><br>
<br>
You can reach the person managing the list at<br>
        <a href="mailto:geos-devel-owner@lists.osgeo.org">geos-devel-owner@lists.osgeo.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than &quot;Re: Contents of geos-devel digest...&quot;<br>
<br>
<br>
Today&#39;s Topics:<br>
<br>
   1. Re: Spatial Relationships (Mateusz Loskot)<br>
   2. Re: Computational Geometry Problem (Sanak)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Sat, 27 Jun 2009 23:23:48 +0100<br>
From: Mateusz Loskot &lt;<a href="mailto:mateusz@loskot.net">mateusz@loskot.net</a>&gt;<br>
Subject: Re: [geos-devel] Spatial Relationships<br>
To: GEOS Development List &lt;<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a>&gt;<br>
Message-ID: &lt;<a href="mailto:4A469BF4.40305@loskot.net">4A469BF4.40305@loskot.net</a>&gt;<br>
Content-Type: text/plain; charset=ISO-8859-1<br>
<br>
Jo wrote:<br>
&gt; Hi,<br>
&gt; Does anybody know a good website with clear examples and definitions of<br>
&gt; spatial relationships, such as Touching, Crossing, etc?<br>
&gt; (apart from the OGC spec, that didnt help me that much..)<br>
<br>
Jo,<br>
<br>
The JTS (GEOS&#39; father) has a very good test suite with<br>
visual presentation of validated cases:<br>
<br>
<a href="http://www.vividsolutions.com/jts/tests/index.html" target="_blank">http://www.vividsolutions.com/jts/tests/index.html</a><br>
<br>
Best regards,<br>
--<br>
Mateusz Loskot, <a href="http://mateusz.loskot.net" target="_blank">http://mateusz.loskot.net</a><br>
Charter Member of OSGeo, <a href="http://osgeo.org" target="_blank">http://osgeo.org</a><br>
<br>
<br>
------------------------------<br>
<br>
Message: 2<br>
Date: Sun, 28 Jun 2009 08:19:58 +0900<br>
From: Sanak &lt;<a href="mailto:geosanak@gmail.com">geosanak@gmail.com</a>&gt;<br>
Subject: Re: [geos-devel] Computational Geometry Problem<br>
To: GEOS Development List &lt;<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a>&gt;<br>
Message-ID:<br>
        &lt;<a href="mailto:5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com">5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com</a>&gt;<br>
Content-Type: text/plain; charset=&quot;iso-8859-1&quot;<br>
<br>
Hi Jo,<br>
<br>
Hmm.. I think that Voronoi Diagrams approach is usefull for computing<br>
&quot;circumscribed circle&quot; but not &quot;inscribed circle&quot;, if the geometry is<br>
triangle.<br>
<br>
<a href="http://en.wikipedia.org/wiki/Circumscribed_circle" target="_blank">http://en.wikipedia.org/wiki/Circumscribed_circle</a><br>
<br>
But your result image seems to be well computed and have no problem.<br>
<br>
Thanks for your reply.<br>
<br>
Regards,<br>
<br>
Sanak.<br>
<br>
2009/6/28 Jo &lt;<a href="mailto:doublebyte@gmail.com">doublebyte@gmail.com</a>&gt;<br>
<br>
&gt; I thought I would published my solution here, for all the ppl who are lazy<br>
&gt; like me, and google for a solution before posting...<br>
&gt; Dis problem is reduced to finding the InCirce of a polygon, which is<br>
&gt; slightly different from the well-known geometry problem: largest empty<br>
&gt; circle.<br>
&gt;<br>
&gt;<br>
&gt; <a href="http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/LgEmptyCircle/lccli.htm" target="_blank">http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/LgEmptyCircle/lccli.htm</a>&lt;<a href="http://www.personal.kent.edu/%7Ermuhamma/Compgeometry/MyCG/CG-Applets/LgEmptyCircle/lccli.htm" target="_blank">http://www.personal.kent.edu/%7Ermuhamma/Compgeometry/MyCG/CG-Applets/LgEmptyCircle/lccli.htm</a>&gt;<br>

&gt;<br>
&gt; In the &quot;largest empty circle&quot; we calculate the Voronoi Diagrams and test<br>
&gt; each of its vertexes inside the convex-hull as a candidate for the center.<br>
&gt; It all comes down<br>
&gt; to a max-min optimization of the radius: the largest radius, that does not<br>
&gt; contain any points inside (and therefore, the circle is &quot;empty&quot;).<br>
&gt; The Largest inscribed circle, is very similar except that here we look for<br>
&gt; a circle that does not contain the *actual* polygon (rather than just its<br>
&gt; vertexes).<br>
&gt; The distance we wont to test here is the (minimum) distance of the<br>
&gt; candidate centre to the polygon.<br>
&gt; I struggled a little bit here to measure a distance from polygon to a point<br>
&gt; that is located inside it, and ended up having to decompose the polygon to<br>
&gt; its boundary<br>
&gt; to get it done (Im using OGR)!<br>
&gt; Here is the result:<br>
&gt;<br>
&gt; <a href="http://ladybug.no-ip.org/files/inCircle.png" target="_blank">http://ladybug.no-ip.org/files/inCircle.png</a><br>
&gt;<br>
&gt; Just as a final note: there are plenty (exact) implementations of the<br>
&gt; incircle (or apotheom) of a triangle or a regular polygon, but it becomes a<br>
&gt; bit complicated when we are dealing<br>
&gt; with irregular geometries, which is my case... (and prob everyone else<br>
&gt; workin in GIS)<br>
&gt;<br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <a href="http://lists.osgeo.org/pipermail/geos-devel/attachments/20090628/5844fbe0/attachment-0001.html" target="_blank">http://lists.osgeo.org/pipermail/geos-devel/attachments/20090628/5844fbe0/attachment-0001.html</a><br>

<br>
------------------------------<br>
<br>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/geos-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
<br>
End of geos-devel Digest, Vol 80, Issue 22<br>
******************************************<br>
</blockquote></div><br><br clear="all"><br>-- <br>&quot;#define QUESTION ((bb) || !(bb))&quot;  (Shakespeare)<br><br>