[geos-devel] RE: [Jts-topo-suite-user] JTS Topology error

Wed Feb 2 18:55:08 EST 2011

(Crossposting to GEOS list)

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?

This seems like an elegant solution to deal with the roundoff issues.

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?

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.

Cheers,
James Sewell
Developer
LISAsoft
________________________________
Ph: +61 3 8680 3250 Fax: +61 3 8680 3299
Level 9, 601 Bourke St, Melbourne Vic 3000
________________________________

LISAsoft is part of the A2end Group of Companies
http://www.ardec.com.au<http://www.ardec.com.au/>
http://www.lisasoft.com<http://www.lisasoft.com/>
http://www.terrapages.com<http://www.terrapages.com/>

From: Martin Davis [mailto:mtnclimb at telus.net]
Sent: Thursday, 3 February 2011 2:54 AM
Cc: jts-topo-suite-user at lists.sourceforge.net
Subject: Re: [Jts-topo-suite-user] JTS Topology error

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.

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.

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.

Martin

On 2/1/2011 11:55 PM, James.Sewell at lisasoft.com<mailto:James.Sewell at lisasoft.com> wrote:
I thought as much.
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).
As a sidenote the AffineTransformation worked in PostGIS / GEOS to fix my problem, as does using it in JTS (tranlate, union, polygonize, translate).
I'm not quite sure I understand what this is achiving though? Is it just a matter of more significant digits to use?
Cheers,
James Sewell
Developer
LISAsoft
________________________________
Ph: +61 3 8680 3250 Fax: +61 3 8680 3299
Level 9, 601 Bourke St, Melbourne Vic 3000
________________________________

LISAsoft is part of the A2end Group of Companies
http://www.ardec.com.au<http://www.ardec.com.au/>
http://www.lisasoft.com<http://www.lisasoft.com/>
http://www.terrapages.com<http://www.terrapages.com/>

From: Martin Davis [mailto:mtnclimb at telus.net]
Sent: Wednesday, 2 February 2011 3:34 PM
To: jts-topo-suite-user at lists.sourceforge.net<mailto:jts-topo-suite-user at lists.sourceforge.net>
Subject: Re: [Jts-topo-suite-user] JTS Topology error

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.

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.

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.

Here's the code inline:

  public static Geometry overlaySnapRounded(Geometry g1, Geometry g2, double precisionTol)
  {
    PrecisionModel pm = new PrecisionModel(precisionTol);
    GeometryFactory geomFact = g1.getFactory();

    List lines = LinearComponentExtracter.getLines(g1);
    // add second input's linework, if any
    if (g2 != null)
      LinearComponentExtracter.getLines(g2, lines);
    List nodedLinework = new GeometryNoder(pm).node(lines);
    // union the noded linework to remove duplicates
    Geometry nodedDedupedLinework = geomFact.buildGeometry(nodedLinework).union();

    // polygonize the result
    Polygonizer polygonizer = new Polygonizer();
    polygonizer.add(nodedDedupedLinework);
    Collection polys = polygonizer.getPolygons();

    // convert to collection for return
    Polygon[] polyArray = GeometryFactory.toPolygonArray(polys);
    return geomFact.createGeometryCollection(polyArray);
  }

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.

On 2/1/2011 7:14 PM, James.Sewell at lisasoft.com<mailto:James.Sewell at lisasoft.com> wrote:
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.

However now when I polygonize my unioned linework like this:

Polygonizer p = new Polygonizer();
p.add(uniongeom);
Collection polys = p.getPolygons();

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.

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?

Once again thanks so much for the help.

________________________________

No virus found in this message.
Checked by AVG - www.avg.com<http://www.avg.com>
Version: 10.0.1202 / Virus Database: 1435/3417 - Release Date: 02/01/11
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20110203/354505c0/attachment-0001.html