sandify
sandify copied to clipboard
jeffeb3
voronoi effect
Adds a "uniformity" slider to Voronoi patterns that applies Lloyd relaxation, making cells more evenly distributed. Also improves path-finding performance.
New option:
- Uniformity (0-20) - applies Lloyd relaxation iterations to make Voronoi cells more regular/uniform
- Available on both Voronoi shape and Voronoi effect
Performance improvements:
- Binary heap PriorityQueue - O(log n) enqueue/dequeue (was O(n))
- Dijkstra restored with proper PriorityQueue - O((V+E) log V)
- BFS for unweighted shortest path - O(V+E)
- KDBush spatial index for densityWeight - O(n log n) (was O(n²))
- Removed redundant
clearCachedPaths()calls on addNode/addEdge
| Optimization | Before | After | Speedup |
|---|---|---|---|
| PriorityQueue enqueue/dequeue | O(n) | O(log n) | ~10x for 100 items |
| Dijkstra (overall) | O(V² + VE) | O((V+E) log V) | ~5-10x typical |
| densityWeight | O(n²) | O(n log n) | ~37x for 300 points |
| BFS for unweighted | O((V+E) log V) | O(V+E) | ~2-3x |
Test plan
- [ ] Verify Voronoi shape renders with uniformity = 0 (unchanged behavior)
- [ ] Test uniformity slider at various values (5, 10, 20)
- [ ] Verify Voronoi effect also has uniformity option
- [ ] Check performance on complex patterns (BFS should be faster)
