[geos-devel] Re: Computational Geometry Problem

[Jo]

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.
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
that fits inside the polygon.
And btw, is an irregular complex polygon...

 cheers,

       Jo


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 <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/f32ec84f/attachment.html