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