Replace water inverse floodfill with scanline rasterization#753
Replace water inverse floodfill with scanline rasterization#753
Conversation
|
⏱️ Benchmark run finished in 0m 24s 📈 Compared against baseline: 30s ✅ This PR improves generation time. 📅 Last benchmark: 2026-02-14 18:50:14 UTC You can retrigger the benchmark by commenting |
There was a problem hiding this comment.
Pull request overview
This PR replaces the quadtree-based inverse floodfill algorithm for water area generation with a scanline rasterization approach. The change aims to dramatically improve performance for large or complex water bodies by reducing algorithmic complexity from O(A * V * P) to O(E * H + A), where A is the filled area, V is vertices per polygon, P is polygon count, E is total edges, and H is the height of the fill area.
Changes:
- Replaced recursive quadtree inverse floodfill with scanline rasterization algorithm
- Removed dependency on
geocrate functions (Orient, Contains, Intersects, Polygon types) - Implemented even-odd parity rule for polygon filling with edge crossing detection
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
There was a problem hiding this comment.
Pull request overview
Copilot reviewed 1 out of 1 changed files in this pull request and generated 1 comment.
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
No description provided.