# First stab at line data simplification

Until FlightGear has a proper Level-of-Detail-implementation it will be necessary to simplify the basic data so that also boxes with lower graphic performance can enjoy the more detailed and more accurate scenery.

Based on Michael Garland's algorithm for surface simplification using quadric error metrics, I created a tool which can read ASCII files in standard GRASS format and simplify the lines.

In contrast to the standard Douglas-Peucker line-simplification-algorithm Garland's method not only removes points but also moves points in order to minimise the error described by the error quadrics. As the error quadrics capture the curvature of the lines, Garland's method seems to be a good choice for polyline simplification, when the polylines actually represent curves, which is the case with roads, rivers and railroads.

The following pictures show the original data (red) and the simplified data (black) of two major freeway intersections and the very curved mainstreet of the town of Hochheim in the Frankfurt/Main area in Midwestern Germany. The intersections were modelled including the typical clover-leaf forms of the driveways, which make such intersections important landmarks for VFR navigation.

The original dataset represents the major roads and freeways of an areal of about 480 square-kilometers in the western part of Frankfurt, including the infrastructure around EDDF (Frankfurt/Main Intl). The data was digitised including as much curvature as possible and then simplified to 50% edge count, i.e., the simplified version uses only half as much edges as the original.

The first picture shows the Frankfurter Kreuz, a freeway intersection located directly north-east of EDDF, the second shows the Nordwestkreuz Frankfurt and the third shows the mainstreet of Hochheim, west of Frankfurt towards Wiesbaden.

From the pictures it can be seen that the algorithm tries to preserve the curvature as far as possible with the given budget by moving remaining vertices to appropriate places. Intersections of lines are kept in place, so that the exact placement of the actual freeway intersection remains.