<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 "circumscribed circle"? 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 <<a href="mailto:geosanak@gmail.com" style="color: rgb(20, 125, 186); ">geosanak@gmail.com</a>><br>Subject: Re: [geos-devel] Computational Geometry Problem<br>
To: GEOS Development List <<a href="mailto:geos-devel@lists.osgeo.org" style="color: rgb(20, 125, 186); ">geos-devel@lists.osgeo.org</a>><br>Message-ID:<br> <<a href="mailto:5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com" style="color: rgb(20, 125, 186); ">5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="iso-8859-1"<br><br>Hi Jo,<br><br>Hmm.. I think that Voronoi Diagrams approach is usefull for computing<br>"circumscribed circle" but not "inscribed circle", 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"><<a href="mailto:geos-devel-request@lists.osgeo.org">geos-devel-request@lists.osgeo.org</a>></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 'help' 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 "Re: Contents of geos-devel digest..."<br>
<br>
<br>
Today'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 <<a href="mailto:mateusz@loskot.net">mateusz@loskot.net</a>><br>
Subject: Re: [geos-devel] Spatial Relationships<br>
To: GEOS Development List <<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a>><br>
Message-ID: <<a href="mailto:4A469BF4.40305@loskot.net">4A469BF4.40305@loskot.net</a>><br>
Content-Type: text/plain; charset=ISO-8859-1<br>
<br>
Jo wrote:<br>
> Hi,<br>
> Does anybody know a good website with clear examples and definitions of<br>
> spatial relationships, such as Touching, Crossing, etc?<br>
> (apart from the OGC spec, that didnt help me that much..)<br>
<br>
Jo,<br>
<br>
The JTS (GEOS' 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 <<a href="mailto:geosanak@gmail.com">geosanak@gmail.com</a>><br>
Subject: Re: [geos-devel] Computational Geometry Problem<br>
To: GEOS Development List <<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a>><br>
Message-ID:<br>
<<a href="mailto:5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com">5f9be0a0906271619g7accc690s9a4727865951984d@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="iso-8859-1"<br>
<br>
Hi Jo,<br>
<br>
Hmm.. I think that Voronoi Diagrams approach is usefull for computing<br>
"circumscribed circle" but not "inscribed circle", 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 <<a href="mailto:doublebyte@gmail.com">doublebyte@gmail.com</a>><br>
<br>
> I thought I would published my solution here, for all the ppl who are lazy<br>
> like me, and google for a solution before posting...<br>
> Dis problem is reduced to finding the InCirce of a polygon, which is<br>
> slightly different from the well-known geometry problem: largest empty<br>
> circle.<br>
><br>
><br>
> <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><<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>><br>
><br>
> In the "largest empty circle" we calculate the Voronoi Diagrams and test<br>
> each of its vertexes inside the convex-hull as a candidate for the center.<br>
> It all comes down<br>
> to a max-min optimization of the radius: the largest radius, that does not<br>
> contain any points inside (and therefore, the circle is "empty").<br>
> The Largest inscribed circle, is very similar except that here we look for<br>
> a circle that does not contain the *actual* polygon (rather than just its<br>
> vertexes).<br>
> The distance we wont to test here is the (minimum) distance of the<br>
> candidate centre to the polygon.<br>
> I struggled a little bit here to measure a distance from polygon to a point<br>
> that is located inside it, and ended up having to decompose the polygon to<br>
> its boundary<br>
> to get it done (Im using OGR)!<br>
> Here is the result:<br>
><br>
> <a href="http://ladybug.no-ip.org/files/inCircle.png" target="_blank">http://ladybug.no-ip.org/files/inCircle.png</a><br>
><br>
> Just as a final note: there are plenty (exact) implementations of the<br>
> incircle (or apotheom) of a triangle or a regular polygon, but it becomes a<br>
> bit complicated when we are dealing<br>
> with irregular geometries, which is my case... (and prob everyone else<br>
> workin in GIS)<br>
><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>"#define QUESTION ((bb) || !(bb))" (Shakespeare)<br><br>