peterstace / simplefeatures

Simple Features is a pure Go Implementation of the OpenGIS Simple Feature Access Specification
MIT License
125 stars 19 forks source link

Separate point/line and line/line renoding in DCEL #571

Closed peterstace closed 8 months ago

peterstace commented 8 months ago

Description

Previously, the point/line and line/line renoding steps were intertwined during DCEL geometry renoding. This caused bad DCEL structures to be produced in some real-world inputs.

Logically, point/line renoding should occur before line/line renoding. This is because point/line renoding can snap together overlapping line segments. When line segments completely overlap, they are skipped by the line/line renoding step. If they are not snapped together, then numeric precision issues in the line/line renoding stage can cause DCEL points that are very close together. By doing point/line renoding first, the entire problem is avoided.

Check List

Have you:

Related Issue

Benchmark Results

There are some 10% to 40% perf degradations for DCEL operations. Unfortunate, but in the name of a bug fix I don't think there's much choice.

bench.txt

peterstace commented 8 months ago

Thanks for looking @albertteoh 😁