[makevalid] Cutout ring has extra point, causing extra line to be drawn:

[gdey]

This is using the natural_earth water dataset.
Location of error:
http://localhost:8080/?debug=true#13.13/52.75645/173.95104

Polygon In Question
ClipArea: slippy.NewTile(13,8054,2677).Extent3857().ExpandBy(64.0)

The issue is that one of the "bridges" is remaining in the cutout sliver.

This is an issue in the PolygonForRing function

[gdey]

The way we determine rings currently is a bit complicated:

geom/planar/makevalid/walker/walker.go

Lines 335 to 371 in fc18549

	// do a quick check to see if b is on ac
	removeB := planar.IsPointOnLine(rng[i], rng[pidx], rng[nidx])
	// ab … bc The sliver is going to be from b … just before b. So, the ring will be …abc… or …ac… depending on removeB
	if debug {
	log.Printf("bubble type ab…bc: (% 5v)(% 5v) … (% 5v)(% 5v) == %t", pidx, idx, i, nidx, removeB)
	log.Printf("ab..bc: [%v][%v]..[%v][%v]",
	wkt.MustEncode(geom.Point(rng[pidx])),
	wkt.MustEncode(geom.Point(rng[idx])),
	wkt.MustEncode(geom.Point(rng[i])),
	wkt.MustEncode(geom.Point(rng[nidx])),
	)
	log.Printf("%v , %v",
	wkt.MustEncode(geom.Point(rng[i])),
	wkt.MustEncode(geom.Line{rng[pidx], rng[nidx]}),
	)
	}
	// Quick hack to remove extra bridges that are geting left over.
	sliver := removeBridge(cut(&rng, idx, i))
	if len(sliver) >= 3 {
	cmp.RotateToLeftMostPoint(sliver)
	if debug {
	log.Printf("ring: %v", wkt.MustEncode(rng))
	log.Printf("sliver: %v", wkt.MustEncode(sliver))
	}
	plyg = append(plyg, sliver)
	}
	i = idx
	if removeB {
	cut(&rng, idx, idx+1)
	if idx == 0 {
	break
	}
	i = idx - 1

However, if we were to change to a different data structure we can find the bridges easier, remove them and have the rings fall out.

The new data structure is made up of three elements.

1. the smallest point found in the linestring (geom.Point)
2. a map of a point to node
3. a graph of nodes

type Node struct {
    Point          geom.Point
    Inbound     []*Node
    Outbound  []*Node
}

var (
  index map[geom.Point] struct {
         Node *Node
         Seen bool
  }
  smallest geom.Point
)

First step is to build out the node graph. This is done by traversing the linestring one point at a time. As we move from point to point we add the point to the map, updating the new point's inbound values and the prior points outbound value.

The second step is to iterate through all the nodes, looking at the inbound and outbound to see if there is a common point in both arrays. If there are, these are the bridges. Delete these points.

Finally, iterate through all the nodes, starting with the smallest point (this will be the outer ring), Follow the outbound links (there should only be one after eliminating all the bridges). till you get to and end node (a node without any outbound links.). Then follow all the inbound links till you get to a start node (a node without any inbound links). As you walk the nodes mark them as seen in the index.