Switched to map and contour generation from quad tree cells. Those are now correctly represent terrain transitions, not only passable regions.
The thing is more costly to construct, but the map filling is much faster than sampling each tile corner - less duplicate work and big chunks of uniform terrain are naturally aggregated and can be dispatched as one job.
Out of 1M tiles only ~75k are 1-tile transitions that are processed sequentially (presumably while some bigger jobs are chugging in background).