<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#ffffff">
Yes, GeometryNoder uses true snap-rounding, whereas ST_Snaptogrid
just does vertex rounding. Snap-rounding is more complex and
slower, but is much more powerful in terms of increasing
robustness. (In fact, as far as I am aware, it's the only real
solution to provide fully robust noding using finite-precision
arithmetic).<br>
<br>
Your suggestion of ST_Node makes reasonable sense to me. The only
caveat is that it would have to execute entirely in memory, so would
not scale to really big datasets. And it might be more precise to
call it ST_SnapRound.<br>
<br>
Martin<br>
<br>
On 2/2/2011 3:55 PM, <a class="moz-txt-link-abbreviated" href="mailto:James.Sewell@lisasoft.com">James.Sewell@lisasoft.com</a> wrote:
<blockquote
cite="mid:CB506E813C77E9498F043F1F951BB2768E3B9827EE@optimus.ms.a2end.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
<meta name="Generator" content="Microsoft Word 12 (filtered
medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
..shape {behavior:url(#default#VML);}
</style><![endif]-->
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Verdana;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle20
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
p.avgcert, li.avgcert, div.avgcert
{mso-style-name:avgcert;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
span.EmailStyle22
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
..MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);">(Crossposting to GEOS list)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);">I see. So the difference between the
GeometryNoder with a PrecisionModel and using ST_Snaptogrid
from PostGIS on the input geometries is that the
GeometryNoder snaps all nodes which are created by the
noding process as it works?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);">This seems like an elegant solution to deal with
the roundoff issues.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);">I gather GEOS doesn’t expose noding functionality
in this way? Is this something that could possibly be added?
From PostGIS would a command like ST_Node(geometry, 10E-10)
make sense / be plausible? Or would a better solution be to
define the precision for each geometry column?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);">It is possible I will be able to commit some time
to this problem, so I am keen to hear what the GEOS list
people think.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color: rgb(31,
73, 125);">Cheers,<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">James Sewell </span><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">Developer </span><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">LISAsoft </span><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);"><o:p></o:p></span></p>
<div>
<div>
<div>
<div class="MsoNormal"><span style="font-size: 9pt;
font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">
<hr style="width: 315pt;" width="420" align="left"
size="2"></span></div>
</div>
</div>
</div>
<p class="MsoNormal"><b><span style="font-size: 9pt;
font-family: "Verdana","sans-serif";
color: rgb(153, 153, 153);">Ph: </span></b><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">+61 3 8680 3250 <b>Fax: </b>+61 3
8680 3299 </span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">Level 9, 601 Bourke St, Melbourne Vic
3000<o:p></o:p></span></p>
<div>
<div>
<div>
<div class="MsoNormal"><span style="font-size: 9pt;
font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">
<hr style="width: 315pt;" width="420" align="left"
size="2"></span></div>
</div>
</div>
</div>
<p class="MsoNormal"><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">LISAsoft is part of the A2end Group
of Companies</span><span style="font-size: 9pt;
font-family: "Verdana","sans-serif";
color: rgb(153, 153, 153);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color: rgb(79,
129, 189);"><a moz-do-not-send="true"
href="http://www.ardec.com.au/"><span style="color:
rgb(79, 129, 189); text-decoration: none;">http://www.ardec.com.au</span></a></span><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color: rgb(79,
129, 189);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color: rgb(79,
129, 189);"><a moz-do-not-send="true"
href="http://www.lisasoft.com/"><span style="color:
rgb(79, 129, 189); text-decoration: none;">http://www.lisasoft.com</span></a></span><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color: rgb(79,
129, 189);"><br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color: rgb(79,
129, 189);"><a moz-do-not-send="true"
href="http://www.terrapages.com/"><span style="color:
rgb(79, 129, 189); text-decoration: none;">http://www.terrapages..com</span></a></span><span
style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif"; color: rgb(31,
73, 125);"><o:p> </o:p></span></p>
<div>
<div style="border-right: medium none; border-width: 1pt
medium medium; border-style: solid none none; border-color:
rgb(181, 196, 223) -moz-use-text-color -moz-use-text-color;
padding: 3pt 0cm 0cm;">
<p class="MsoNormal"><b><span style="font-size: 10pt;
font-family:
"Tahoma","sans-serif"; color:
windowtext;" lang="EN-US">From:</span></b><span
style="font-size: 10pt; font-family:
"Tahoma","sans-serif"; color:
windowtext;" lang="EN-US"> Martin Davis
[<a class="moz-txt-link-freetext" href="mailto:mtnclimb@telus.net">mailto:mtnclimb@telus.net</a>] <br>
<b>Sent:</b> Thursday, 3 February 2011 2:54 AM<br>
<b>Cc:</b> <a class="moz-txt-link-abbreviated" href="mailto:jts-topo-suite-user@lists.sourceforge.net">jts-topo-suite-user@lists.sourceforge.net</a><br>
<b>Subject:</b> Re: [Jts-topo-suite-user] JTS Topology
error<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The key aspect of the code I provided is
the use of GeometryNoder. This performs a snap-rounded noding
using the supplied PrecisionModel. This is what allows the
noding to be performed correctly, and result in a set of line
segments which polygonize correctly. Are you using this in
GEOS too? If not, I would expect to see noding failures
occur.<br>
<br>
I'll be interested to hear your speed comparisons.
GeometryNoder is not all that optimized, and it's doing a lot
of extra work to implement the snap-rounding, so it may well
be slower. That's the price for robustness.. I do have a
much faster implementation in the lab, but it's not quite
ready for prime time yet.<br>
<br>
And yes, using an AffineTransformation to move the data closer
to the origin has the effect of reducing the number of
significant digits, which provides more numeric "room" for the
line segment intersection algorithm to operate correctly.
This isn't a panacea, though - it's possible for the data to
be too wide or have too many digits of precision and thus
still fail.<br>
<br>
Martin<br>
<br>
<br>
On 2/1/2011 11:55 PM, <a moz-do-not-send="true"
href="mailto:James.Sewell@lisasoft.com">James.Sewell@lisasoft.com</a>
wrote: <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif";">I thought as
much.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif";">The code you
provide is identical to the code I am using in PostGIS
land (without the pointonsuface intersection to map gids
through from the left and the right), I’ll test yours when
I get a chance for speed. In PostGIS it performs really
well so long as I use Union(Collect(geom),
EMPTYLINESTRING).</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif";">As a sidenote
the AffineTransformation worked in PostGIS / GEOS to fix
my problem, as does using it in JTS (tranlate, union,
polygonize, translate).</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif";">I’m not quite
sure I understand what this is achiving though? Is it just
a matter of more significant digits to use?</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif";">Cheers,</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">James Sewell <br>
Developer <br>
LISAsoft </span><o:p></o:p></p>
<div>
<div>
<div>
<div>
<div class="MsoNormal"><span style="font-size: 9pt;
font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">
<hr style="width: 315pt;" width="420" align="left"
size="2"></span></div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><b><span style="font-size: 9pt;
font-family: "Verdana","sans-serif";
color: rgb(153, 153, 153);">Ph: </span></b><span
style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">+61 3 8680 3250 <b>Fax: </b>+61 3
8680 3299 <br>
Level 9, 601 Bourke St, Melbourne Vic 3000</span><o:p></o:p></p>
<div>
<div>
<div>
<div>
<div class="MsoNormal"><span style="font-size: 9pt;
font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);">
<hr style="width: 315pt;" width="420" align="left"
size="2"></span></div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><span style="font-size: 9pt; font-family:
"Verdana","sans-serif"; color:
rgb(153, 153, 153);"><br>
LISAsoft is part of the A2end Group of Companies<br>
</span><span style="font-size: 9pt; font-family:
"Verdana","sans-serif";"><a
moz-do-not-send="true" href="http://www.ardec.com.au/"><span
style="color: rgb(79, 129, 189); text-decoration:
none;">http://www.ardec.com.au</span></a><br>
<a moz-do-not-send="true" href="http://www.lisasoft.com/"><span
style="color: rgb(79, 129, 189); text-decoration:
none;">http://www.lisasoft.com</span></a><br>
<a moz-do-not-send="true"
href="http://www.terrapages.com/"><span style="color:
rgb(79, 129, 189); text-decoration: none;">http://www.terrapages.com</span></a></span><o:p></o:p></p>
</div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<div>
<div style="border-right: medium none; border-width: 1pt
medium medium; border-style: solid none none; padding: 3pt
0cm 0cm; border-color: -moz-use-text-color;">
<p class="MsoNormal"><b><span style="font-size: 10pt;
font-family:
"Tahoma","sans-serif"; color:
windowtext;" lang="EN-US">From:</span></b><span
style="font-size: 10pt; font-family:
"Tahoma","sans-serif"; color:
windowtext;" lang="EN-US"> Martin Davis [<a
moz-do-not-send="true"
href="mailto:mtnclimb@telus.net">mailto:mtnclimb@telus.net</a>]
<br>
<b>Sent:</b> Wednesday, 2 February 2011 3:34 PM<br>
<b>To:</b> <a moz-do-not-send="true"
href="mailto:jts-topo-suite-user@lists.sourceforge.net">jts-topo-suite-user@lists.sourceforge.net</a><br>
<b>Subject:</b> Re: [Jts-topo-suite-user] JTS Topology
error</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">The reason you're seeing incorrect results
from the Polygonize operation is due to numerical roundoff
issues in the noding code. These result in linework which
isn't quite correctly noded, and thus which don't polygonize
correctly.<br>
<br>
The best way to handle this issue is to use snap-rounding with
a precision model, to limit the precision of the noding
process and provide correct output. This will also help to
reduce the number of slivers in the output.<br>
<br>
I have prototyped some code to do just this. It's in
com.vividsolutions.jtstest.function.PolygonOverlayFunctions in
SVN. You can try it directly in the TestBuilder, or just port
it to your environment. I'm not sure how well it will scale,
but I'd be interested to hear if it works for you. <br>
<br>
Here's the code inline:<br>
<br>
public static Geometry overlaySnapRounded(Geometry g1,
Geometry g2, double precisionTol)<br>
{<br>
PrecisionModel pm = new PrecisionModel(precisionTol);<br>
GeometryFactory geomFact = g1.getFactory();<br>
<br>
List lines = LinearComponentExtracter.getLines(g1);<br>
// add second input's linework, if any<br>
if (g2 != null)<br>
LinearComponentExtracter.getLines(g2, lines);<br>
List nodedLinework = new GeometryNoder(pm).node(lines);<br>
// union the noded linework to remove duplicates<br>
Geometry nodedDedupedLinework =
geomFact.buildGeometry(nodedLinework).union();<br>
<br>
// polygonize the result<br>
Polygonizer polygonizer = new Polygonizer();<br>
polygonizer.add(nodedDedupedLinework);<br>
Collection polys = polygonizer.getPolygons();<br>
<br>
// convert to collection for return<br>
Polygon[] polyArray =
GeometryFactory.toPolygonArray(polys);<br>
return geomFact.createGeometryCollection(polyArray);<br>
}<br>
<br>
<br>
Note that you need to use the right precisionTolerance. This
is the reciprocal of the desired grid size. For your data I
used 1000000, which rounds to a grid of size10^-6. I also
tried 10^8, which worked as well. <br>
<br>
On 2/1/2011 7:14 PM, <a moz-do-not-send="true"
href="mailto:James.Sewell@lisasoft.com">James.Sewell@lisasoft.com</a>
wrote: <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";">I have used
AffineTransformation to move closer to the origin which
seems to have worked brilliantly, thanks for that! I will
test this in GEOS with our problem geoms in GEOS (seem bug
report on the GEOS list) and see if this approach translates
well.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";">However now
when I polygonize my unioned linework like this:</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<p class="MsoNormal" style="text-indent: 36pt;"><span
style="font-size: 11pt; font-family:
"Calibri","sans-serif";">Polygonizer p =
new Polygonizer();</span><o:p></o:p></p>
<p class="MsoNormal" style="text-indent: 36pt;"><span
style="font-size: 11pt; font-family:
"Calibri","sans-serif";">p.add(uniongeom);</span><o:p></o:p></p>
<p class="MsoNormal" style="text-indent: 36pt;"><span
style="font-size: 11pt; font-family:
"Calibri","sans-serif";">Collection
polys = p..getPolygons();</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";">I run into the
same problem I was hoping to fix by porting from GEOS.
Perhaps the bug is in Polygonize? Or perhaps my
understanding of how it is meant to work is flawed. </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:
"Calibri","sans-serif";">I would have
thought the Polgonize of the unioned linework would produce
an upper and lower polygon (as well as many smaller
polygons along the inner edge where the lines cut each
other). Is there a reason this is not the output?</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";">Once again
thanks so much for the help.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family:
"Calibri","sans-serif";"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<div class="MsoNormal" style="text-align: center;"
align="center">
<hr style="color: rgb(160, 160, 160);" width="100%"
align="center" noshade="noshade" size="1"></div>
<p class="avgcert">No virus found in this message.<br>
Checked by AVG - <a moz-do-not-send="true"
href="http://www.avg.com">www.avg.com</a><br>
Version: 10.0.1202 / Virus Database: 1435/3417 - Release Date:
02/01/11<o:p></o:p></p>
</div>
<hr noshade="noshade" size="1">
<p class="avgcert" color="#000000" align="left">No virus found in
this message.<br>
Checked by AVG - <a moz-do-not-send="true"
href="http://www.avg.com">www.avg.com</a><br>
Version: 10.0.1202 / Virus Database: 1435/3418 - Release Date:
02/02/11</p>
</blockquote>
</body>
</html>