[PRO] Generalization - MDT26

Generalization

	Command to execute in the CAD
Vertical menu	MDT26 > Contour Lines/Mapping > Generalization
Ribbon menu
Command line	MDT26_cvgen

This command allows one to group together a series of known algorithms whose aim is to delete or keep the vertices of the polylines selected.

The program will execute the algorithm previously set in the program configuration. Consult the Contour Lines section in the Customization Manual.

Two algorithms (the Douglas-Peucker and the Visvalingam algorithms) are described below.

Douglas-peucker Algorithm

This is a simplification algorithm, in other words, it seeks to reduce the number of points existing on a polyline.

It is based on the search for critical points starting off from a linear tolerance. The critical points, which will form the simplified line, will be those which progressively attain a greater perpendicular distance with respect to the base line considered that is always greater than the tolerance imposed.

The first base line will be formed between the first (anchoring) and last (floating) points of the original line. Then the perpendicular distances from all intermediate points will be calculated:

• If none of these distances is greater than tolerance, the simplification will have come to an end with only the line's initial and final points being retained.

• Should tolerance be exceeded, the point furthest away will be retained as the critical point that will subdivide the original line into two sections. In each of those sections, the process will be repeated as if they were two independent lines and the process will continue thus until there is no need to further subdivide the line.

Scheme of operation of the Douglas- Peucker algorithm.

Once the command has been run, MDT will request the polylines that are to be modified. It will then request the scale of the drawing. In accordance with this scale, it will propose a value for tolerance, which users may later modify.

How the algorithm works by applying different tolerance values can be seen below.

Visvalingam Algorithm

The Visvalingam algorithm is a polyline simplification operator used in the process of generalization. In said process, it will progressively eliminate any points that are less significant for the shape of the line's definition.

It is therefore a very useful tool when the aim is to diminish the drawing's volume or to represent a specific linear object on a smaller scale than the one for which it was originally conceived.

The Visvalingam algorithm is based on effective area concept, defined as the triangle area formed by each the line's points and its two immediately neighboring points. The concept effectively signifies the adjustment the line suffers should that point be eliminated.

The algorithm's simplification process consists of establishing a specific tolerance which will correspond to the effective area parameter, below which any points will be eliminated whose corresponding triangles are smaller in area than said tolerance. Firstly, the areas of all the triangles are calculated and the point with least effective area is eliminated. Once this point has been eliminated, all the areas are calculated once more and the point with least effective area is eliminated once again. And so on until all areas are greater than the tolerance value set.

Scheme of operation of Visvalingam algorithm.

Once the command has been executed, MDT will request the polylines that are to be modified and the tolerance value. The program will then apply the entire calculation process.

How the algorithm works by applying different tolerance values can be seen below.