Use Euclidean MST For Ghost Lines - Githubissues

peterstace / simplefeatures

Simple Features is a pure Go Implementation of the OpenGIS Simple Feature Access Specification

MIT License

133 stars 19 forks source link

Use Euclidean MST For Ghost Lines #336

Closed peterstace closed 3 years ago

peterstace commented 3 years ago

Right now, we construct ghosts lines by just naively connecting all unconnected components. If there are a large amount of unconnected components, this results in a large number of cutting ghost lines.

A better approach would be to use a Euclidean Minimum Spanning Tree (with each point in the tree being an arbitrary point on each component, e.g. the first/last point in a ring).

For this we would need to follow this approach:

Calculate the Delaunay triangulation.
Use a regular MST algorithm on the triangulation (e.g. Prim's algorithm).

peterstace commented 3 years ago

This was fixed via https://github.com/peterstace/simplefeatures/pull/339