[geos-devel] Computational Geometry Problem
Jo
doublebyte at gmail.com
Sat Jun 27 13:23:46 EDT 2009
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
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)
2009/6/27 <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. [GEOS] #272: Incorrect mapping to
> BufferParameters::EndCapStyle in deprecated BufferOp enum (GEOS)
> 2. Re: [GEOS] #272: Incorrect mapping to
> BufferParameters::EndCapStyle in deprecated BufferOp enum (GEOS)
> 3. Spatial Relationships (Jo)
> 4. Re: Computational Geometry Problem (Sanak)
> 5. Re: trying to compile on MinGW (Sanak)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Fri, 26 Jun 2009 21:15:44 -0000
> From: "GEOS" <geos-trac at osgeo.org>
> Subject: [geos-devel] [GEOS] #272: Incorrect mapping to
> BufferParameters::EndCapStyle in deprecated BufferOp enum
> To: undisclosed-recipients:;
> Message-ID: <048.b9f8e1877047e745bbcba46a3b42c4ad at osgeo.org>
> Content-Type: text/plain; charset="utf-8"
>
> #272: Incorrect mapping to BufferParameters::EndCapStyle in deprecated
> BufferOp
> enum
>
> ------------------------+---------------------------------------------------
> Reporter: cscrimge | Owner: geos-devel at lists.osgeo.org
> Type: defect | Status: new
> Priority: minor | Milestone: 3.2.0
> Component: Core | Version: svn-trunk
> Severity: Unassigned | Keywords:
>
> ------------------------+---------------------------------------------------
> The deprecated enum in BufferOp that maps to BufferParameters::EndCapStyle
> has the following incorrect mapping:
>
> CAP_ROUND = BufferParameters::CAP_ROUND,
> CAP_BUTT = BufferParameters::CAP_FLAT,
> CAP_SQUARE = BufferParameters::CAP_FLAT
>
> --
> Ticket URL: <http://trac.osgeo.org/geos/ticket/272>
> GEOS <http://geos.refractions.net/>
> GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology
> Suite (JTS).
>
> ------------------------------
>
> Message: 2
> Date: Fri, 26 Jun 2009 21:59:51 -0000
> From: "GEOS" <geos-trac at osgeo.org>
> Subject: [geos-devel] Re: [GEOS] #272: Incorrect mapping to
> BufferParameters::EndCapStyle in deprecated BufferOp enum
> To: undisclosed-recipients:;
> Message-ID: <057.7809cb1e3e569205aee2e9211228ac49 at osgeo.org>
> Content-Type: text/plain; charset="utf-8"
>
> #272: Incorrect mapping to BufferParameters::EndCapStyle in deprecated
> BufferOp
> enum
>
> ------------------------+---------------------------------------------------
> Reporter: cscrimge | Owner: geos-devel at lists.osgeo.org
> Type: defect | Status: closed
> Priority: minor | Milestone: 3.2.0
> Component: Core | Version: svn-trunk
> Severity: Unassigned | Resolution: fixed
> Keywords: |
>
> ------------------------+---------------------------------------------------
> Changes (by strk):
>
> * status: new => closed
> * resolution: => fixed
>
> Comment:
>
> Thanks for finding this out. Fixed as r2605.
>
> --
> Ticket URL: <http://trac.osgeo.org/geos/ticket/272#comment:1>
> GEOS <http://geos.refractions.net/>
> GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology
> Suite (JTS).
>
> ------------------------------
>
> Message: 3
> Date: Sat, 27 Jun 2009 12:12:55 +0100
> From: Jo <doublebyte at gmail.com>
> Subject: [geos-devel] Spatial Relationships
> To: geos-devel at lists.osgeo.org
> Message-ID:
> <23ab5f0a0906270412o152ba61ag29fbc80c26305eab at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
> 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..)
> Thanks in advance for ur help,
> Jo
>
> --
> "Law 1: Every program can be optimised to be smaller. Law 2: There's always
> one more bug. Corollary: Every program can be reduced to a one-line bug."
>
> (Lubarsky's Laws of Cybernetic Entomology)
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
> http://lists.osgeo.org/pipermail/geos-devel/attachments/20090627/03cbfd43/attachment-0001.html
>
> ------------------------------
>
> Message: 4
> Date: Sat, 27 Jun 2009 21:31:45 +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:
> <5f9be0a0906270531t3b28212et1c6903157337e4dd at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
> Hi Jo,
>
> You mean you want to know about "Incircle of an irregular polygon"?
>
> I don't know that GEOS(or JTS) had already implement it,
> but if not, you might google the word above. (and I hope GEOS(or JTS)
> implement it)
>
> The following site is written in Japanese, but the images may be helpful.
> http://izumi-math.jp/K_Katou/tatamu/tatamu.htm
>
> Regards,
>
> Sanak.
>
> 2009/6/27 Jo <doublebyte at gmail.com>
>
> > Hi,First of all, I apologize if this post is unrelated to the scope of
> the
> > mailing list (I hope not).
> > I have to find an algorithm to draw the maximum enclosed circle in a
> > polygon, which is slightly different from the "well-known" geometry
> problem:
> > "maximum empty circle"; in this case, not only all the vertices need to
> be
> > outside the circle but also the entire perimeter of the polygon must
> *not*
> > be inside the circle.
> > I can get the center of the polygon using Voronoi Diagrams: anybody has
> any
> > suggestions or recomendations of how to calculate its radius?
> > Also, I would like to avoid as much as possible iterative processes (as
> > they can be slow when dealing with a high number of polygons, that have
> > complex frontiers)...
> > It would be really appreciated any ideas on this, or even references to
> > libraries that could help me... Im not finding a lot of stuff about this
> on
> > the web :-/ Im using C/C++ but all ideas are welcome, really...
> >
> > Thanks in advance for your time!
> > cheers,
> > Jo
> >
> >
> > --
> > "Law 1: Every program can be optimised to be smaller. Law 2: There's
> always
> > one more bug. Corollary: Every program can be reduced to a one-line bug."
> >
> > (Lubarsky's Laws of Cybernetic Entomology)
> >
> > _______________________________________________
> > geos-devel mailing list
> > geos-devel at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
> http://lists.osgeo.org/pipermail/geos-devel/attachments/20090627/f84e6dbf/attachment-0001.html
>
> ------------------------------
>
> Message: 5
> Date: Sat, 27 Jun 2009 22:04:58 +0900
> From: Sanak <geosanak at gmail.com>
> Subject: Re: [geos-devel] trying to compile on MinGW
> To: GEOS Development List <geos-devel at lists.osgeo.org>
> Message-ID:
> <5f9be0a0906270604p3320f742r34b2eeefb50e04e at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
> Hi Allegri,
>
> I encountered the same problem today.
> (I am using gcc-3.4.5, referring to
> http://trac.osgeo.org/postgis/wiki/UsersWikiWinCompile)
>
> The cause seems to be the latest MinGW bug, and Mark has already report
> MinGW tracker.
>
> [Latest MingW download breaks g++ -ansi option - ID: 2373234]
>
> http://sourceforge.net/tracker/index.php?func=detail&aid=2373234&group_id=2435&atid=102435
>
>
> I had modified "cwchar" file referring to the following site,
> and I could "make" geos-3.0.4 successfully with the latest MinGW.
>
> [g++ compilation error within vim]
> http://www.nabble.com/g%2B%2B-compilation-error-within-vim-td22764394.html
>
> Regards,
>
> Sanak.
>
> 2009/3/19 G. Allegri <giohappy at gmail.com>
>
> > Hello list,
> > this is my very first post. I'm trying to build GEOS 3.0.0 with MSYS
> 1.0.11
> > + MinGW 5.1.4 environment and Windows Vista SP1.
> > make aborts with the following traceback:
> >
> > g++ -DHAVE_CONFIG_H -I. -I. -I../../source/headers
> > -I../../source/headers/geos -I../../source/headers -g -O2 -DGEOS_INLINE
> > -Wall -ansi -pedantic -Wno-long-long -MT CGAlgorithms.lo -MD -MP -MF
> > .deps/CGAlgorithms.Tpo -c CGAlgorithms.cpp -DDLL_EXPORT -DPIC -o
> > .libs/CGAlgorithms.o
> > In file included from
> >
> C:/msys/mingw/bin/../lib/gcc/mingw32/3.4.5/../../../../include/c++/3.4.5/bits/postypes.h:46,
> > from
> >
> C:/msys/mingw/bin/../lib/gcc/mingw32/3.4.5/../../../../include/c++/3.4.5/iosfwd:50,
> > from
> >
> C:/msys/mingw/bin/../lib/gcc/mingw32/3.4.5/../../../../include/c++/3.4.5/bits/stl_algobase.h:70,
> > from
> >
> C:/msys/mingw/bin/../lib/gcc/mingw32/3.4.5/../../../../include/c++/3.4.5/vector:67,
> > from
> > ../../source/headers/geos/algorithm/CGAlgorithms.h:24,
> > from CGAlgorithms.cpp:21:
> >
> C:/msys/mingw/bin/../lib/gcc/mingw32/3.4.5/../../../../include/c++/3.4.5/cwchar:161:
> > error: `::swprintf' has not been declared
> >
> C:/msys/mingw/bin/../lib/gcc/mingw32/3.4.5/../../../../include/c++/3.4.5/cwchar:168:
> > error: `::vswprintf' has not been declared
> > make[2]: *** [CGAlgorithms.lo] Error 1
> > make[2]: Leaving directory `/usr/local/src/geos-3.0.0/source/algorithm'
> > make[1]: *** [all-recursive] Error 1
> > make[1]: Leaving directory `/usr/local/src/geos-3.0.0/source'
> > make: *** [all-recursive] Error 1
> >
> > I don't know how to solve the "error: `::swprintf' has not been declared"
> > error. Any idea? What could cause it?
> > Thanks,
> > Giovanni
> >
> >
> > _______________________________________________
> > geos-devel mailing list
> > geos-devel at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
> http://lists.osgeo.org/pipermail/geos-devel/attachments/20090627/21197fe1/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 19
> ******************************************
>
--
"Law 1: Every program can be optimised to be smaller. Law 2: There's always
one more bug. Corollary: Every program can be reduced to a one-line bug."
(Lubarsky's Laws of Cybernetic Entomology)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20090627/43580892/attachment-0001.html
More information about the geos-devel
mailing list