logoalt Hacker News

morishuz • today at 1:27 PM • 1 reply • view on HN

awesome. the performance improvements looks impressive!

i’m the author of Delaunay32, a constrained delaunay triangulator with polygon and hole support. it uses divide-and-conquer rather than incremental insertion, so im curious how it would compare with the delaunay baseline here.

https://github.com/morishuz/delaunay32

i havent benchmarked on your corpus yet, and our current polygon api requires simple rings with non-touching holes. thanks for publishing the datasets, they look useful for testing and comparison!

Replies

molind • today at 2:01 PM

Numbers without benchmarks are useless. :) During vector map generation we make sure that all data is valid. But our users can import custom GeoJSON layers and they could contain all sorts of self-intersections.

  == world.bin
  56472 polygons
  whole file, best of 7: earstrip 453.4 ms, delaunay32 1696.9 ms
  up to 4          14455 polygons: earstrip 0.3 ms, delaunay32 14.4 ms
  5-8               8328 polygons: earstrip 0.6 ms, delaunay32 14.5 ms
  9-32             18019 polygons: earstrip 6.8 ms, delaunay32 83.7 ms
  33-256           13511 polygons: earstrip 66.6 ms, delaunay32 366.9 ms
  257 and more      2159 polygons: earstrip 376.8 ms, delaunay32 1209.4 ms
  delaunay32: rejected 3039 (by class 0/28/365/1671/975), empty outer ring 0, area off on 0 covered, 1930016 triangles
  earstrip: exact 56338, constrained 134
➕ show 1 reply