[geos-devel] Re: Computational Geometry Problem

[Jo]

How about creating a grid of centre candidates and refining search near the
best match (in a sort of quadtree approach)?Does anybody have any experience
wid that? Would it be awfully slow?
                                                                cheers,

Jo

2009/6/28 <geos-devel-request at lists.osgeo.org>

> Send geos-devel mailing list submissions to
>        geos-devel at lists.osgeo.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>        http://lists.osgeo.org/mailman/listinfo/geos-devel
> or, via email, send a message with subject or body 'help' to
>        geos-devel-request at lists.osgeo.org
>
> You can reach the person managing the list at
>        geos-devel-owner at lists.osgeo.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of geos-devel digest..."
>
>
> Today's Topics:
>
>   1. Re: Spatial Relationships (Mateusz Loskot)
>   2. Re: Computational Geometry Problem (Sanak)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sat, 27 Jun 2009 23:23:48 +0100
> From: Mateusz Loskot <mateusz at loskot.net>
> Subject: Re: [geos-devel] Spatial Relationships
> To: GEOS Development List <geos-devel at lists.osgeo.org>
> Message-ID: <4A469BF4.40305 at loskot.net>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Jo wrote:
> > Hi,
> > Does anybody know a good website with clear examples and definitions of
> > spatial relationships, such as Touching, Crossing, etc?
> > (apart from the OGC spec, that didnt help me that much..)
>
> Jo,
>
> The JTS (GEOS' father) has a very good test suite with
> visual presentation of validated cases:
>
> http://www.vividsolutions.com/jts/tests/index.html
>
> Best regards,
> --
> Mateusz Loskot, http://mateusz.loskot.net
> Charter Member of OSGeo, http://osgeo.org
>
>
> ------------------------------
>
> Message: 2
> Date: Sun, 28 Jun 2009 08:19:58 +0900
> From: Sanak <geosanak at gmail.com>
> Subject: Re: [geos-devel] Computational Geometry Problem
> To: GEOS Development List <geos-devel at lists.osgeo.org>
> Message-ID:
>        <5f9be0a0906271619g7accc690s9a4727865951984d at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
> 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-0001.html
>
> ------------------------------
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
> End of geos-devel Digest, Vol 80, Issue 22
> ******************************************
>



-- 
"#define QUESTION ((bb) || !(bb))"  (Shakespeare)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20090629/9dc90003/attachment-0001.html