Thread: [Jts-topo-suite-user] Problem computing line intersections
Brought to you by:
dr_jts
From: Mark C. <mco...@gm...> - 2012-11-19 17:06:45
|
I'm writing documentation showing two different ways of computing line intersections. Unfortunately I'm getting two different results. One method uses union() and the other uses a noder. The union() approach returns proper results whereas the noder doesn't. Maybe I'm using the noder incorrectly? The two code snippets and their respective run results are given below: GeometryFactory geometryFactory = new GeometryFactory(); WKTReader reader = new WKTReader(geometryFactory); ArrayList<LineString> rawlines = new ArrayList<LineString>(); rawlines.add((LineString) reader.read("LINESTRING (0 1, 1 1)")); rawlines.add((LineString) reader.read("LINESTRING (1 0, 1 3)")); MultiLineString newLines = new MultiLineString(rawlines.toArray(new LineString[0]), geometryFactory); System.out.println("Before computing intersections:\n" + newLines); Geometry brokenUpLines = newLines.union(); System.out.println("Broken up by intersection:\n" + brokenUpLines); Before computing intersections: MULTILINESTRING ((0 1, 1 1), (1 0, 1 3)) Broken up by intersection: MULTILINESTRING ((0 1, 1 1), (1 0, 1 1), (1 1, 1 3)) The original lines describe a 'T', so naturally they'd split into three lines, as shown here. GeometryFactory geometryFactory = new GeometryFactory(); WKTReader reader = new WKTReader(geometryFactory); ArrayList<LineString> rawlines = new ArrayList<LineString>(); rawlines.add((LineString) reader.read("LINESTRING (0 1, 1 1)")); rawlines.add((LineString) reader.read("LINESTRING (1 0, 1 3)")); System.out.println("Before computing intersections: " + rawlines); GeometryNoder noder = new GeometryNoder(geometryFactory.getPrecisionModel()); List nodedLines = noder.node(rawlines); System.out.println("Noded lines: " + nodedLines); Before computing intersections: [LINESTRING (0 1, 1 1), LINESTRING (1 0, 1 3)] Noded lines: [LINESTRING (0 1, 1 0), LINESTRING (1 0, 1 1), LINESTRING (1 0, 0 1), LINESTRING (0 1, 1 1), LINESTRING (1 1, 1 3)] So we have the same 'T' configuration, but clearly we're getting something extra. We now have a diagonal line, (0 1, 1 0); worse yet it shows up another time in the reverse direction as (1 0, 0 1). The GeometryNoder mentions duplicate linestrings; that's all well and good, but adding *extra* lines that were not in the original configuration is not cool. Note I'm using JTS 1.12 from subversion. Am I using GeometryNoder correctly? Is there a bug in GeometryNoder? Should I be using a different noder class? Cheers! Mark -- mco...@gm... |
From: Martin D. <mtn...@gm...> - 2012-11-19 23:19:56
|
This is occurring because of a unanticipated usage of GeometryNoder! GeometryNoder was design mainly to support noding using snap-rounding. Snap-Rounding uses a fixed-precision grid, so GeometryNoder expects to be called with a FIXED precision model with a scale factor appropriate to the data being targetted. If you use the following code snippet in the second test case you should see it working: PrecisionModel pm = new PrecisionModel(10000); GeometryNoder noder = new GeometryNoder(pm); The value of 10000 is completely arbitrary - it's really up to you and your data. At some point it would be nice to add some heuristics to determine a reasonable grid size based on the input data. Obviously it would also be good to add a sensible default behaviour for FLOATING precision models - or at least throw an exception! Mark, I'm curious about the documentation you are writing. Is it something of interest to the general JTS community? On Mon, Nov 19, 2012 at 9:06 AM, Mark Coletti <mco...@gm...> wrote: > I'm writing documentation showing two different ways of computing line > intersections. Unfortunately I'm getting two different results. One > method uses union() and the other uses a noder. The union() approach > returns proper results whereas the noder doesn't. Maybe I'm using the > noder incorrectly? > > The two code snippets and their respective run results are given below: > > GeometryFactory geometryFactory = new GeometryFactory(); > WKTReader reader = new WKTReader(geometryFactory); > > ArrayList<LineString> rawlines = new ArrayList<LineString>(); > > rawlines.add((LineString) reader.read("LINESTRING (0 1, 1 > 1)")); > rawlines.add((LineString) reader.read("LINESTRING (1 0, 1 > 3)")); > > MultiLineString newLines = new > MultiLineString(rawlines.toArray(new LineString[0]), geometryFactory); > > System.out.println("Before computing intersections:\n" + > newLines); > > Geometry brokenUpLines = newLines.union(); > > System.out.println("Broken up by intersection:\n" + > brokenUpLines); > > Before computing intersections: > MULTILINESTRING ((0 1, 1 1), (1 0, 1 3)) > Broken up by intersection: > MULTILINESTRING ((0 1, 1 1), (1 0, 1 1), (1 1, 1 3)) > > The original lines describe a 'T', so naturally they'd split into three > lines, as shown here. > > > GeometryFactory geometryFactory = new GeometryFactory(); > WKTReader reader = new WKTReader(geometryFactory); > > ArrayList<LineString> rawlines = new ArrayList<LineString>(); > > rawlines.add((LineString) reader.read("LINESTRING (0 1, 1 > 1)")); > rawlines.add((LineString) reader.read("LINESTRING (1 0, 1 > 3)")); > > System.out.println("Before computing intersections: " + > rawlines); > > GeometryNoder noder = new > GeometryNoder(geometryFactory.getPrecisionModel()); > > List nodedLines = noder.node(rawlines); > > System.out.println("Noded lines: " + nodedLines); > > > Before computing intersections: [LINESTRING (0 1, 1 1), LINESTRING (1 0, 1 > 3)] > Noded lines: [LINESTRING (0 1, 1 0), LINESTRING (1 0, 1 1), LINESTRING (1 > 0, 0 1), LINESTRING (0 1, 1 1), LINESTRING (1 1, 1 3)] > > So we have the same 'T' configuration, but clearly we're getting something > extra. We now have a diagonal line, (0 1, 1 0); worse yet it shows up > another time in the reverse direction as (1 0, 0 1). The GeometryNoder > mentions duplicate linestrings; that's all well and good, but adding > *extra* lines that were not in the original configuration is not cool. > > Note I'm using JTS 1.12 from subversion. Am I using GeometryNoder > correctly? Is there a bug in GeometryNoder? Should I be using a different > noder class? > > Cheers! > > Mark > -- > mco...@gm... > > > > > ------------------------------------------------------------------------------ > Monitor your physical, virtual and cloud infrastructure from a single > web console. Get in-depth insight into apps, servers, databases, vmware, > SAP, cloud infrastructure, etc. Download 30-day Free Trial. > Pricing starts from $795 for 25 servers or applications! > http://p.sf.net/sfu/zoho_dev2dev_nov > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |
From: Mark C. <mco...@gm...> - 2012-11-19 23:26:06
|
On Mon, Nov 19, 2012 at 12:06 PM, Mark Coletti <mco...@gm...> wrote: > I'm writing documentation showing two different ways of computing line > intersections. Unfortunately I'm getting two different results. One > method uses union() and the other uses a noder. The union() approach > returns proper results whereas the noder doesn't. Maybe I'm using the > noder incorrectly? > > I've resolved the problem. Based on old JTS mailing list traffic, I observed someone use the MCIndexNoder, so I cribbed from them. I now know that the GeometryNoder is for int-based, fixed grids! D'oh! Naturally I first reached for it because it was the only Noder that used native Geometry objects. In any case my noder code now is: GeometryFactory geometryFactory = new GeometryFactory(); WKTReader reader = new WKTReader(geometryFactory); MultiLineString multiLine = (MultiLineString) reader.read("MULTILINESTRING ((0 1, 1 1),(1 3, 1 0))"); System.out.println("Before computing intersections: " + multiLine); List lines = SegmentStringUtil.extractSegmentStrings(multiLine); System.out.println("Converted to segmented lines: " + lines); RobustLineIntersector RLI = new RobustLineIntersector(); IntersectionAdder SI = new IntersectionAdder(RLI); MCIndexNoder noder = new MCIndexNoder(); noder.setSegmentIntersector(SI); noder.computeNodes(lines); System.out.println("Noded Noded Substrings: " + noder.getNodedSubstrings()); This produces the following expected output: Before computing intersections: MULTILINESTRING ((0 1, 1 1), (1 3, 1 0)) Converted to segmented lines: [LINESTRING (0.0 1.0, 1.0 1.0), LINESTRING (1.0 3.0, 1.0 0.0)] Noded Noded Substrings: [LINESTRING (0.0 1.0, 1.0 1.0), LINESTRING (1.0 3.0, 1.0 1.0), LINESTRING (1.0 1.0, 1.0 0.0)] Phew! Might I second the motion for a Noder FAQ? I'm sure I won't be the first nor last person to reach for GeometryNoder merely because it uses Geometry objects! Now on to your follow-on e-mail, which I received while writing this. Talk about good timing! :) Cheers! Mark |
From: Martin D. <mtn...@gm...> - 2012-11-19 23:34:13
|
On Mon, Nov 19, 2012 at 3:26 PM, Mark Coletti <mco...@gm...> wrote: > > Might I second the motion for a Noder FAQ? I'm sure I won't be the first > nor last person to reach for GeometryNoder merely because it uses Geometry > objects! > > > Noding is a bit of a wide-ranging topic in JTS, so yes, some better documentation would be nice. And actually that applies to a lot of other things in JTS... 8^) In the meantime, improving the Javadoc for GeometryNoder will have to suffice! And I think adding an exception in the case of FLOATING precision model inputs. |
From: Martin D. <mtn...@gm...> - 2012-11-19 23:44:00
|
On Mon, Nov 19, 2012 at 3:26 PM, Mark Coletti <mco...@gm...> wrote: > > I've resolved the problem. Based on old JTS mailing list traffic, I > observed someone use the MCIndexNoder, so I cribbed from them. > Another option is to simply using Geometry.union() (Unary union). When executed on a collection of LineStrings, this has the effect of noding them and dissolving any common linework. Be aware however that currently JTS overlay operations have a small robustness issue, so that if the input linework contains line segments that are almost coincident they may not in fact be noded quite correctly. That about covers the noding options currently in JTS. And it does seem like a good addition to the FAQ! |