New node: Merge by Distance #2307

richard-uk1 · 2025-02-19T16:45:35Z

Here's a patch that adds a new node to collapse segments with chord shorter than a distance (parameter to the node). It's not finished but this version works - I tried it out by drawing freehand then watching the segments collapse as the distance increases.

Things still to do:

Also move bezier control points (I left this until after the first version because it is fairly orthogonal to finding and collapsing the short segments)
Updating faces if the end segments were removed
General tidy up (I've used petgraph for the clustering algo but unless you want to take the dep, I assume I'll need to figure it out myself and replace it with hand-written code.)
- If you did want to take the dep, I'd need to look at minimal features to get what is needed, to avoid bloating build time

I do think you should consider using a graph library though, because the relationship between points, segments and faces is inherantly graph-like, and one might as well take advantage of all the experties that's been developed for graphs.

EDIT I measured binary size before/after this PR:

with master size is 15.93M
with PR, size is 15.98M

node-graph/gcore/src/vector/vector_data/attributes.rs

node-graph/gcore/src/vector/vector_data/indexed.rs

richard-uk1 · 2025-02-19T16:52:37Z

node-graph/gcore/src/vector/vector_nodes.rs

+		Footprint -> VectorDataTable,
+	)]
+	source: impl Node<F, Output = VectorDataTable>,
+	#[default(10.)] distance: Length,


Perhaps a different default would be better.

Keavon · 2025-02-21T23:15:59Z

For the 0.05 MB I think we can accept the dependency. There's a chance we use it in the future for other graph data structures, too.

richard-uk1 · 2025-02-22T16:04:23Z

It's probably overkill for just this 1 problem, but I can see it being useful in a number of situations. It might even be the most efficient way to store path info.

Keavon · 2025-02-26T04:43:42Z

!build

github-actions · 2025-02-26T04:47:50Z

📦 Build Complete for `23a5e56`
https://281a17fb.graphite.pages.dev

richard-uk1 · 2025-02-27T16:33:46Z

I'll get back on this.

Keavon · 2025-03-01T21:51:09Z

Just a reminder since it's the weekend and you might have some time to fix this up for the merge.

TrueDoctor · 2025-03-05T22:31:22Z

node-graph/gcore/src/vector/merge_by_distance.rs

+
+		// Now group connected segments - all will be collapsed to a single point.
+		// Note: there are a few algos for this - perhaps test empirically to find fastest
+		let collapse: Vec<FxHashSet<PointId>> = petgraph::algo::tarjan_scc(&short_edges).into_iter().map(|connected| connected.into_iter().collect()).collect();


Tarjan will almost certainly be faster than Kosaraju because it only requires a single graph traversal

Keavon · 2025-03-09T08:54:50Z

Hi, just one more friendly reminder, it'd be awesome to get this landed. Thanks for your work so far on it!

richard-uk1 force-pushed the merge_by_distance branch 2 times, most recently from 7cd11f3 to 26c5460 Compare February 19, 2025 16:48