[geos-devel] Re: [Jts-topo-suite-user] JTS Topology error
Martin Davis
mtnclimb at telus.net
Wed Feb 2 20:58:23 EST 2011
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).
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.
Martin
On 2/2/2011 3:55 PM, James.Sewell at lisasoft.com wrote:
>
> (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
>
> ------------------------------------------------------------------------
>
> No virus found in this message.
> Checked by AVG - www.avg.com <http://www.avg.com>
> Version: 10.0.1202 / Virus Database: 1435/3418 - Release Date: 02/02/11
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20110202/dae3595f/attachment-0001.html
More information about the geos-devel
mailing list