# Given a list of surveyor points, what is the algorithm used to simplify the points and retain the terrain characteristics?

Given a terrain and surveyor points sampled from from it or from its contours, is there any algorithm that one can use to simplify the points ( i.e., reduce the surveyor points number) and at the same time retaining the terrain characteristics?

The reason I ask this is because the surveyors may take too much redundant points at flat terrain, and these points serve nothing but to slow down my volume calculation process, so I want them to get filtered out.

## 4 Answers

Seems like the picking key points portion of generating a TIN could suit your purposes.

Here's a nice discussion on TINs, with three algorithms for picking key points.

Survey of Polygonal Surface Simplification Algorithms would also be a good place to start.

• Great! This is what I want, any open source code that implement this? Feb 23 '11 at 4:06

There are some extensions of the douglas-peucker filtering algorithm to 3D surfaces. See for example this paper.

Building on wwnick's answer, you can generate a TIN by using the `txt2las` tool provided with LAStools, then use `las2tin` (docs) to convert the LAS data into a TIN. Alternatively, you could import your data into GRASS following their instructions on creating a triangle mesh. There's also a simple library tinlib that be worth taking a look at.

• I am not too sure how can simplify the surveyor points so that I can create minimum number of triangles. Feb 23 '11 at 7:14

i agree with @scw and have some Windows code for you to play with:

http://www.cs.unc.edu/~isenburg/sd/download/lidar2iso_demo.zip

the TIN simplification happens in smsimp.exe in your case you would then need to strip the point out of that TIN as your reduce set of surveyor points.

Cheers,

Martin