Map Simplification Program (version 2.1)- Documentation

Table of Contents

• Introduction
• What's new in this version ?
• Requirements
• Configuration
• How it Works
• FAQ
• Developers
• Credits

Generally, vectorial maps have a large number of points. The more accurate they are, the more they require time to be displayed. Moreover, when the zoom level is higher than the precision of the map - for instance, when you display a whole country with a map based on its city limits - it could be useful to simplify the map by deleting some points which are invisible due to the zoom factor.

From now, some algorithms already exist which simplify polylines such as the Douglas-Peucker algorithm. However, here comes two main problems with vectorial map simplification :

1. A polyline (a border in a common map language) is generally shared by at least two elements. For example, a border can separate towns, districts, countries.
2. Vectorial maps are often grouped in many layers, sharing their points. For instance : a group composed of a world map layer, a country map layer, a city limit map layer. The most accurate is obviously the last one but after every simplifications, each map should always be superimposable.

Our program solves these problems and we will explain how we did that in the How it Works section.

• We simplified the process with embedding the simplified geometry in a new column in the same table. We don't use inherited tables anymore.
• We use now a lex/yacc processor in order to decode geometry.
• We use 2 separate processes in order to create a vertex table and then to simplify.

• a Python interpreter.
• a Postgres Database and the Postgis extension.
• a Python API for Postgres : psycopg
• a lex/yacc Python module : PLY
• some vectorial maps to work on it ;)

Installation

1. Install the pl/sql function 'vertex' from func.sql
2. Check/Install psycopg and PLY modules

---

Files

• simplify.py
• vertex.py
• polyLex.py
• polyYacc.py
table
• func.sql
• ChangeLog
• Credits
• License
• ReadMe
• TODO
• css/style.css

This section will explain how the algorithm has been created and how it works.

Basis

Let's start explaining how your project should be before launching the algorithm. Your map data should be in a Postgres database with a Postgis geometry column.

Basically, you will have to choose the most detailed map as the basic map to create the vertex table. Then, all simplifications in your project will use this table to create new maps. One last important point is that there are as many vertex tables as there are different minimal distance values for the algorithm.

From now, every map should shared the same points. In other words, map must be superimposed and in addition, a map with a higher level should not have points which do not belong to the original map used to create the vertex map.

Creating a Vertex Table (vertex.py)

First, you have to choose the geometry table which contains the largest number of vertex. For example, if you have two tables in your database sharing their points : city limits and country limits, the one you will have to choose is the former one.

Now, the program will extract each polygon from your table and store each vertex found in a table named "vertex" concatenated with the minimal distance value - eg - vertex5000, vertex2500 etc ... Let's explain the columns of this table :

• id (integer) : the primary key
• x and y (integers) : the coordinates
• nref (integer) : the number of polygons sharing this vertex
• simplif (boolean) : true if the vertex is simplifiable

As a default value, every vertex from this table are simplifiable. Therefore, the algorithm will have to find which points are not simplifiable and update their simplif column.
Then, the program is inspired by the Douglas-Peucker algorithm on each polygon to find which vertex should not be simplifiable. The following picture explains briefly how our algorithm works out.

To explain shortly the way the algorithm simplifies each points : it creates a cylinder around a series of vertex of the polygon with the minimal distance value as the radius. Next, every vertex which do not belong are marked as non simplifiable and the cylinder moves every iterations. Due to this process, each polygon are well-simplified : a vertex is not simplified if it is required by at least one of the polygons. Here's an example :

Map Simplification

When a vertex table is created, we can run the map simplification process. For each table to be simplified a new geometry column (named the original name + the simplification distance) is created and filled with polygons composed of vertice that can be simplified in respect with the vertex table. Because all maps are sharing the same simplified vertex table, each simplified maps are superimposable. Here's an example :

Tricks

We add a few features in order to have maps more attractive. For instance, when a vertex is shared by at least three polygons - eg - its nref is greater than or equal to 3, we consider it as a non simplifiable vertex.

Moreover, a problem appears on every borders of each maps :

As you can see, if the vertex A is simplifiable and, as the vertex B does not belong to the country limits map, those two maps become non-superimposable. Therefore, we worked on it and every points which are at the same position as vertex A are automatically set as non simplifiable vertex.

Known Problems

In some cases, especially when the distance entered for simplification is of the same order than the dimension of the polygons to be simplified, weird geometries can be generated.

Let's resolve your frequently asked questions ? ;)

---

- My maps are currently in shapefile format, how could I put them into my Postgres database ?

You just have to use the shp2pgsql and psql function on your favorite shell console.

• shp2pgsql name_shapefile name_table name_database > ~/name_table.sql
• psql -d name_database -f ~/name_table.sql

Map Simplification Algorithm is Open Source, so feel free to contribute to it. If you are planning to continue this program, please read the following information :

• try to keep the code as simple as possible in order to be easily reusable.
• do not forget to update the ChangeLog file if you write or rewrite anything

How did this project start ?

• Laurent PIERRE <laurent.pierre@edf.fr>
  • creator of the map simplification project
  • wrote the original script
• Damien GARZILLI <garzilld@esiee.fr>
  • rewrote and optimized the script
  • bugfixes and improvements