# Triangulating a 2D point cloud?

I have an algorithm that creates a randomly-generated 2D road network. I would like to fill in the spaces between roads with terrain data from a height map.

Unpaved areas are essentially polygons, so I’m planning to automatically triangulate them, using as input all the points on the perimeter of the polygon, as well as all points on the heightmap that fall into its interior. Adding extra points is OK, if it ever comes to that. And the operation is 2D-constrained because I don’t plan on adding any tunnels or bridges for now.

Is this something Panda’s Triangulator class can handle? Or if not, what about poly2tri?

As far as I know neither of the two takes your heightfield points on the interior of your polygon into account.

Since you probably don’t want to drop this requirement (terrain would loose height information) you probably have to roll your own tesselator/triangulator mix. You can tesselate on the inside (e. g. two triangles per cell) and only triangulate the strips between roads and the inside cells.

OK, good, that’s what I suspected. I got both the Triangulator class and the python script from poly2tri to work, although poly2tri is slightly easier to deal with because of dynamic typing (it’s 100% Python). I have a couple ideas:

1. Your idea: find the orthogonal or convex hull of the heightmap points. Flag this region as a hole to the triangulator and triangulate the polygon. Then go back into the hole area and tessellate it with the standard 2 polys/square.

2. Do my own triangulation vertex-by-vertex with Fortune’s method or something. I don’t really care how long it takes, since it only needs to happen once during level generation.

Nice. but looking at your image I have concerns that the “long” triangles won’t follow the heightfield. In order to get a terrain which follows the heightfield you have to split it into smaller chunks.

Hmm… I think that separating each polygon into exactly two areas (“inner” area which gets tesselated, “outer” area which gets triangulated) which get handles by different and independent algorithms is probably not a wise idea. Because the triangulated and the tesselated areas have common egdes, and these edges have to match with respect to the heightfield, or there will be crack in beween the two areas.

Maybe it is better to
(1) Start distinguishing between squares which can be tesselated, and squares which can not be tesselated because the intersect with a road.
(2) Make one huge geom
(3) Add triangles by tesselating the no-intersection squares.
(4) Now triangulate each has-contact square seperatedly, and add to the geom. Triangulation should by relative easy, since it is basically a cracker where someone has bitten away a chunk. The no-contact squera and the have-contact squares should have no cracks in between now.

Yeah, I noticed that. Also, because of the way I make my levels, I would have to account for the case where no heightmap points fall into the unpaved regions. I would either interpolate the rough road heightmap over the terrain, or subsample the fine terrain heightmap to make the roads.

I’ll take a shot at triangulating the point cloud incrementally. Aside from being the more elegant solution, it will probably look better, because there won’t be a discontinuity between the blocky tessellated region and the surrounding triangulated region. I may be able to modify or cannibalize the poly2tri code.

OK, I figured out that one can generate a triangulation for an arbitrary collection of points by:

1. Projecting them onto the surface of a 3d parabola
2. Finding the 3d convex hull of the parabola
3. Projecting the points in the hull back into two dimensions.

There are still a few hiccups, but I think this method is more robust, and I’m more confident in my ability to debug it than I would be with Fortune’s algorithm, the Bowyer-Watson algorithm, or the other alternatives.