<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><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]--></head><body bgcolor=white lang=EN-AU link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>(Crossposting to GEOS list)<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><div><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#1F497D'>Cheers,<o:p></o:p></span></p><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>James Sewell </span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>Developer </span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>LISAsoft </span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><o:p></o:p></span></p><div><div><div><div class=MsoNormal><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><hr size=2 width=420 style='width:315.0pt' align=left></span></div></div></div></div><p class=MsoNormal><b><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>Ph: </span></b><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>+61 3 8680 3250 <b>Fax: </b>+61 3 8680 3299 </span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>Level 9, 601 Bourke St, Melbourne Vic 3000<o:p></o:p></span></p><div><div><div><div class=MsoNormal><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><hr size=2 width=420 style='width:315.0pt' align=left></span></div></div></div></div><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>LISAsoft is part of the A2end Group of Companies</span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#4F81BD'><a href="http://www.ardec.com.au/"><span style='color:#4F81BD;text-decoration:none'>http://www.ardec.com.au</span></a></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#4F81BD'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#4F81BD'><a href="http://www.lisasoft.com/"><span style='color:#4F81BD;text-decoration:none'>http://www.lisasoft.com</span></a></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#4F81BD'><br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#4F81BD'><a href="http://www.terrapages.com/"><span style='color:#4F81BD;text-decoration:none'>http://www.terrapages.com</span></a></span><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p></o:p></span></p></div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'><p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'>From:</span></b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'> Martin Davis [mailto:mtnclimb@telus.net] <br><b>Sent:</b> Thursday, 3 February 2011 2:54 AM<br><b>Cc:</b> jts-topo-suite-user@lists.sourceforge.net<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 href="mailto:James.Sewell@lisasoft.com">James.Sewell@lisasoft.com</a> wrote: <o:p></o:p></p><div><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:9.0pt;font-family:"Verdana","sans-serif"'>I thought as much.</span><o:p></o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:9.0pt;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:12.0pt'><span style='font-size:9.0pt;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:12.0pt'><span style='font-size:9.0pt;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:12.0pt'><span style='font-size:9.0pt;font-family:"Verdana","sans-serif"'>Cheers,</span><o:p></o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>James Sewell <br>Developer <br>LISAsoft </span><o:p></o:p></p><div><div><div><div><div class=MsoNormal><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><hr size=2 width=420 style='width:315.0pt' align=left></span></div></div></div></div></div><p class=MsoNormal><b><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>Ph: </span></b><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'>+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:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><hr size=2 width=420 style='width:315.0pt' align=left></span></div></div></div></div></div><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Verdana","sans-serif";color:#999999'><br>LISAsoft is part of the A2end Group of Companies<br></span><span style='font-size:9.0pt;font-family:"Verdana","sans-serif"'><a href="http://www.ardec.com.au/"><span style='color:#4F81BD;text-decoration:none'>http://www.ardec.com.au</span></a><br><a href="http://www.lisasoft.com/"><span style='color:#4F81BD;text-decoration:none'>http://www.lisasoft.com</span></a><br><a href="http://www.terrapages.com/"><span style='color:#4F81BD;text-decoration:none'>http://www.terrapages.com</span></a></span><o:p></o:p></p></div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><div><div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0cm 0cm 0cm;border-color:-moz-use-text-color -moz-use-text-color'><p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'>From:</span></b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'> Martin Davis [<a 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 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 href="mailto:James.Sewell@lisasoft.com">James.Sewell@lisasoft.com</a> wrote: <o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;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:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;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:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt;font-family:"Calibri","sans-serif"'>Polygonizer p = new Polygonizer();</span><o:p></o:p></p><p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt;font-family:"Calibri","sans-serif"'>p.add(uniongeom);</span><o:p></o:p></p><p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt;font-family:"Calibri","sans-serif"'>Collection polys = p.getPolygons();</span><o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;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:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;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:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;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:11.0pt;font-family:"Calibri","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal> <o:p></o:p></p><div class=MsoNormal align=center style='text-align:center'><hr size=1 width="100%" noshade style='color:#A0A0A0' align=center></div><p class=avgcert>No virus found in this message.<br>Checked by AVG - <a 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></body></html>