All geek questions in one place

Landscape Triangulation Algorithm

I have a relief represented by a large set of points in 3D-space . What is the best way to triangulate it?

I can just project all the points on 2D-space than create a Delaney triangulation in O(n * log(n)) and raise it back to the previous vertex. But is it good enough? I heard about Delaunay triangulation in time O(n * log(log(n)) ) in some special cases. Is this possible in my case? Or maybe I should use the approximation algorithm?

+4
source share
2 answers

Projecting and triangulating Delaunay in 2D is certainly a good solution that will generate right triangles. For terrain, you may also need to force certain edges to be executed, so find limited Delaunay triangulation.

Regarding runtime: for real-world data, you can assume linear runtime . If performance is important, make sure your input is not degenerate: scanners often return points on the grid. You can improve the situation by adding some noise.

+2
source

In fact, you did your homework. Well, Delaunay triangulation is a very good solution to your problem.

-1
source

Source: https://habr.com/ru/post/1441068/

More articles:


All Articles