Re: [geos-devel] RE: [Jts-topo-suite-user] JTS Topology error
On Thu, Feb 03, 2011 at 10:25:08AM +1030, james.sew...@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? Check the new ST_Snap() function in PostGIS and GEOS svn repository. --strk; () Free GIS Flash consultant/developer /\ http://strk.keybit.net/services.html ___ geos-devel mailing list geos-devel@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/geos-devel
[geos-devel] RE: [Jts-topo-suite-user] JTS Topology error
(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.auhttp://www.ardec.com.au/
http://www.lisasoft.comhttp://www.lisasoft.com/
http://www.terrapages.comhttp://www.terrapages.com/
From: Martin Davis [mailto:mtncl...@telus.net]
Sent: Thursday, 3 February 2011 2:54 AM
Cc: jts-topo-suite-u...@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.sew...@lisasoft.commailto:james.sew...@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.auhttp://www.ardec.com.au/
http://www.lisasoft.comhttp://www.lisasoft.com/
http://www.terrapages.comhttp://www.terrapages.com/
From: Martin Davis [mailto:mtncl...@telus.net]
Sent: Wednesday, 2 February 2011 3:34 PM
To:
jts-topo-suite-u...@lists.sourceforge.netmailto:jts-topo-suite-u...@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 =
[geos-devel] Re: [Jts-topo-suite-user] JTS Topology error
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.sew...@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:mtncl...@telus.net] *Sent:* Thursday, 3 February 2011 2:54 AM *Cc:* jts-topo-suite-u...@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.sew...@lisasoft.com mailto:james.sew...@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:mtncl...@telus.net] *Sent:* Wednesday, 2 February 2011 3:34 PM *To:* jts-topo-suite-u...@lists.sourceforge.net mailto:jts-topo-suite-u...@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
