walking an undirected cyclic graph with minimal jumps

[i-make-robots]

Hello! I hope you are well. I'm having a funny result and hoping one of you big brains can ELI5 to me. Apologies if this is not strictly a JTS question.. I don't know a better place to ask.

I'm using JTS in Makelangelo Software. Recently someone asked if this plotter software could be made to work for sand plotters. The biggest challenge I see right away is that the plotter can't jump from one place to another. Since I already have my JTS hammer I thought I'd use it to hit this nail. JTS should be perfect for finding intersections and building graphs, right?

The eventual goal is to walk a graph of connections with a stack to remember if I have unvisited neighbors in the past. if i hit a dead end and there are zero unvisited neighbors in the stack, stop. else, retrace the line until I get to the unvisited and explore that branch. I understand that there may be "islands" that are unreachable without a jump - the goal is only to minimize jumps by any means available.

Here's my input line set:

First I swizzle my lines into JTS and get the merged line set. I ran a test to draw all merged lines in alternating colors, which looked OK.

private void addLinesToJTS(Turtle turtle) {
    LineMerger lineMerger = new LineMerger();
    Coordinate previous = new Coordinate(0,0);
    for( var move : turtle.history ) {
        if(move.type == MovementType.DRAW_LINE) {  // other types are TOOL_CHANGE and TRAVEL.
            Coordinate current = new Coordinate(move.x,move.y);
            // Add a line to the set
            lineMerger.add( geometryFactory.createLineString( new Coordinate[]{
                            new Coordinate(previous),current
            }) );
        }
        previous.setX(move.x);
        previous.setY(move.y);
    }
    try {
        mergedLines.addAll(lineMerger.getMergedLineStrings());
    } catch (TopologyException e) {
        System.err.println("Error merging lines: " + e.getMessage());
    }
}

Then I build a graph of the start and end of each line. Note that every line is added at least twice.

private void mergeLinesAndBuildGraph() {
    // Step 3: Add vertices (endpoints/intersections) to the graph
    for (LineString line : mergedLines) {
        Coordinate start = line.getCoordinateSequence().getCoordinate(0);
        Coordinate end = line.getCoordinateSequence().getCoordinate(line.getNumPoints() - 1);
        graph.computeIfAbsent(start, k -> new ArrayList<>()).add(end);
        graph.computeIfAbsent(end, k -> new ArrayList<>()).add(start);
    }
}

I use getCoordinateSequence() to avoid allocating new instances AND I want to match by memory address. For example:

private LineString findLineInList(List<LineString> list, Coordinate p0, Coordinate p1) {
    for (LineString line : list) {
        Coordinate start = line.getCoordinateSequence().getCoordinate(0);
        Coordinate end = line.getCoordinateSequence().getCoordinate(line.getNumPoints() - 1);
        if((p0==start && p1==end) || (p0==end && p1==start)) {
            return line;
        }
    }
    return null;
}

To test the graph, I tried to draw every connection. Here's where I got my mystery.

private Turtle drawUndirectedGraph() {
    List<LineString> done = new ArrayList<>();
    Turtle newTurtle = new Turtle();
    int missing=0;
    for( var p : graph.keySet() ) {
        var neighbors = graph.get(p);
        for( var q : neighbors ) {
            var s = findLineInList(mergedLines, p, q);
            if (s != null) {
                drawLine(newTurtle, Color.RED, s);
                mergedLines.remove(s);
                done.add(s);
                continue;
            }
            // try the reverse, which shouldn't happen.
            s = findLineInList(mergedLines, q, p);
            if (s != null) {
                drawLine(newTurtle, Color.BLUE, s);
                mergedLines.remove(s);
                done.add(s);
                continue;
            }
            if(null==findLineInList(done,p,q)) ++missing;
        }
    }
    if(!mergedLines.isEmpty()) {  // shouldn't happen.
        System.out.println("There are "+mergedLines.size()+" lines left over and "+missing+" missing.");
        for( var q : mergedLines ) {
            drawLine(newTurtle, Color.GREEN, q);
        }
    }
    return newTurtle;
}

There are 3 lines left over and 18 missing.

Despite the fact that every LineString is in mergedLines and therefore MUST be in the graph, some LineStrings are never reached.

....how?! 🫠 Any hints or advice are greatly appreciated.

[micycle1]

I'd personally try turning the JTS linework into a JGraphT graph, then look at the various graph traversal methods, etc, offered by that library.

[i-make-robots]

I've neer heard of JGraphT. Interesting!

[i-make-robots]

I tried printing the memory address of every Coordinate as it was added to the graph and then again as the graph is queried for LineStrings.

Added line 356641328 to 201985188
Added line 201985188 to 356641328
Added line 1733872499 to 1429188403
Added line 1429188403 to 1733872499
Added line 1336266700 to 328631728
Added line 328631728 to 1336266700
Added line 842323938 to 449487008
Added line 449487008 to 842323938
Added line 2070992794 to 1550607937
Added line 1550607937 to 2070992794
Added line 1223897577 to 124995575
Added line 124995575 to 1223897577
Added line 2051185796 to 1168352227
Added line 1168352227 to 2051185796
Added line 344899271 to 165617502
Added line 165617502 to 344899271
Added line 1729565789 to 1064505319
Added line 1064505319 to 1729565789
Added line 1592456776 to 800991012
Added line 800991012 to 1592456776
Added line 1884584818 to 1476353704
Added line 1476353704 to 1884584818
Added line 1580120745 to 16195919
Added line 16195919 to 1580120745
Added line 1395348936 to 2123127579
Added line 2123127579 to 1395348936
Added line 1440505233 to 1813570364
Added line 1813570364 to 1440505233
Added line 1695837794 to 2036118872
Added line 2036118872 to 1695837794
Added line 1314610999 to 1701926083
Added line 1701926083 to 1314610999
Added line 600850801 to 1069209126
Added line 1069209126 to 600850801
Added line 730633217 to 1152654079
Added line 1152654079 to 730633217
Added line 1699610833 to 212656568
Added line 212656568 to 1699610833
Added line 1129267376 to 667470276
Added line 667470276 to 1129267376
Added line 848633188 to 1507822511
Added line 1507822511 to 848633188
Added line 1621887716 to 30108124
Added line 30108124 to 1621887716
Added line 464468668 to 1049122965
Added line 1049122965 to 464468668
Added line 1047760522 to 1680639249
Added line 1680639249 to 1047760522
Added line 112474610 to 2055505217
Added line 2055505217 to 112474610
Added line 1478579013 to 1487225181
Added line 1487225181 to 1478579013
Added line 2138675218 to 562668593
Added line 562668593 to 2138675218
Added line 1944088638 to 20805814
Added line 20805814 to 1944088638
Added line 850905483 to 1593002944
Added line 1593002944 to 850905483
Added line 786608544 to 1156617218
Added line 1156617218 to 786608544
Added line 1216870022 to 208537885
Added line 208537885 to 1216870022
Added line 934987393 to 1999246576
Added line 1999246576 to 934987393
Added line 15662933 to 2083797172
Added line 2083797172 to 15662933
Added line 492529533 to 980516274
Added line 980516274 to 492529533
Added line 1293036030 to 280910192
Added line 280910192 to 1293036030
Added line 1444455573 to 1739972361
Added line 1739972361 to 1444455573
Added line 1001674712 to 1503919111
Added line 1503919111 to 1001674712
Added line 1242351530 to 59245685
Added line 59245685 to 1242351530
Added line 438016331 to 1545473483
Added line 1545473483 to 438016331
Added line 1887678581 to 862697916
Added line 862697916 to 1887678581
Added line 1979494235 to 1503691898
Added line 1503691898 to 1979494235
Added line 885888803 to 1510305375
Added line 1510305375 to 885888803
Added line 1242797107 to 399333983
Added line 399333983 to 1242797107
Added line 1340191498 to 1055345471
Added line 1055345471 to 1340191498

Found line 1503691898 to 1979494235
Found line 1395348936 to 2123127579
Found line 934987393 to 1999246576
Found line 2138675218 to 562668593
Found line 1168352227 to 2051185796
Found line 15662933 to 2083797172
Found line 356641328 to 201985188
Found line 1216870022 to 208537885
Found line 1510305375 to 885888803
Found line 1550607937 to 2070992794
Found line 1242797107 to 399333983
Found line 16195919 to 1580120745
Found line 2036118872 to 1695837794
Found line 492529533 to 980516274
Missing line 492529533 to 59245685

line 492529533 to 59245685 was never added to the mix, so IDK how it appears in the graph. Both Coordinates were added...but not in that combination.

[i-make-robots]

So... I'm definitely going about it the wrong way. I see that LineMerger won't find intersections and add nodes. It also can't detect duplicate coordinates at the same location.

[dr-jts]

Correct. There are functions which will do that - e.g. union.

[i-make-robots]

Oh man, really? I just deleted what I thought was never going to work.... sigh.

[dr-jts]

Still working on this?

The first step is to check if your lines are actually noded and connected. The easiest way to do this is to dump them out as WKT and drop them into the JTS TestBuilder. Then you can enable MagnifyTopology to see if lines which look connected actually are. You can also easily see if lines are noded correctly.

Here's lines which look like they are connected:

But using Magnify Topology (the checkbox with distance 5) shows the endpoint is slightly off the line:

You can use the Noding.findInteriorNodes function to find places where an endpoint touches a line at a non-endpoint:

If you attach the WKT to this ticket I can have a look.