Add support to rotate rings to avoid split

mattijn / topojson

Encode spatial data as topology in Python! 🌍 https://mattijn.github.io/topojson

BSD 3-Clause "New" or "Revised" License

178 stars 27 forks source link

Add support to rotate rings to avoid split #180

Closed theroggy closed 2 years ago

theroggy commented 2 years ago

Remark: depends on https://github.com/mattijn/topojson/pull/179 to be merged first!

Support rotating rings in cut to avoid unneeded splits happening.

I noticed that there is some logic in dedup that merges adjacent lines:

I'm not sure if this code is meant to do something similar but there are at least cases where it doesn't.
Performance-wise, rotating the rings is very efficiënt while mergine lines using shapely is rather "costly". I noticed a performance gain of 19.3 s to 18.1 s for my test file if the ring rotation is activated, so I guess (not sure) it might have to do with the linemerge logic having less work.

references #178

mattijn commented 2 years ago

First, thanks for this PR!

I like it how you rotate to the first junction part in the fast_split function.

I can imagine this reduce the workload in the Dedup class where it tries to merge arcs when possible.

As mentioned in the inline comme t, maybe we can track the type directly during extraction?

Also would be great if this PR only reflect the changes regarding the rotation.

theroggy commented 2 years ago

As mentioned in the inline comme t, maybe we can track the type directly during extraction?

It's possible, but I don't think there is an advantage in denormalizing this information in "permanent" structures as we only need access to it via linestring index in this specific code path? I might be wrong, but I also doubt it would give a measurable performance benefit?

Also would be great if this PR only reflect the changes regarding the rotation.

I made the changes independent of possible changes to the join logic.

mattijn commented 2 years ago

Thanks for making this PR more compact. All tests pass. Thanks for pushing!