How about creating a grid of centre candidates and refining search near the best match (in a sort of quadtree approach)?<div>Does anybody have any experience wid that? Would it be awfully slow?</div><div> cheers,</div>
<div> Jo<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>
</div>