Problem Definition:

Please consider join the mailing list to directly receive updates related to the competition.

Geometry generalization is a well known concept in the field of cartography (http://en.wikipedia.org/wiki/Cartographic_generalization). This concept is used in producing maps with less detail according to map scale. The algorithms used for geometry generalization usually concentrate on the techniques for simplifying individual geometry objects. When these algorithms are applied to a map, the result might not be what the user expects.

Consider a map that displays a set of state boundaries at a very detailed level. Some states share boundaries with other states and the areas of the states do not overlap with each other. In addition, let’s add a set of cities to the map. Some of these cities might be very close to the state boundaries. Now let us consider a simplified version of the same map. If geometry generalization algorithms are applied to each state boundary independently, the resulting map might not be accurate. For example, the simplified state boundaries might not align with each other exactly as they did before the simplification. Some of the cities that are very close to the state boundaries might now be in a different state if the simplified state boundary now falls on the other side of the point used to represent the city.

To facilitate this type of map simplification, it is often desirable to break the state boundaries into different line geometries so that all shared boundaries are represented as unique line geometries. These lines are then simplified and connected back together to form the state boundaries. With this approach, the state boundaries will still preserve the non-overlapping property they had before the boundary is simplified. But this itself does not guarantee that the cities still maintain their relative position with respect to their state boundaries.

This year’s SIG Spatial competition explores this map generalization problem and challenges the students to come up with novel solutions for this very useful problem. The scope of the problem is limited to allow the students to develop a meaningful solution in a short amount of time.

Problem Definition

INPUT: A set of linear geometries that bound polygonal regions and a set of constraining points.

OBJECTIVE: Simplify the linear geometries such that the relationship between the constraining points and linear geometries before and after the simplification does not change. In addition, the topological relationships between the original set of input linear geometries does not change after the simplification.

Description: Geometry generalization is a well known area and there are two main algorithms ((i) Peucker Algorithm and (ii) Visvalingam_Whyatt Algorithm). These techniques can be applied to linear and polygonal geometries to produce generalized geometries. The same techniques can also be applied to produce generalized maps. In map generalization one of the difficult problems is to maintain the topological consistency between adjacent polygonal regions during the simplification process. This is explained with the help of the following figures.


Consider a set of 6 lines: L1 .. L6 arranged as in Figure 1.

Figure 2 shows a valid simplification of these 6 lines. Note that the end points of each of the lines do not move. Only some of the intermediate points of the lines are deleted.


Image 2

Next, Figure 3 shows an invalid simplification of these lines.


Image 3

Next example in Figure 4 shows input of 6 lines with 5 control points.


Image 4

A valid simplification for this input is shown in Figure 5.


Image 5

Note that, P1 forces line L1 not to be simplified further and P5 forces L4 not to be simplified further. Figure 6 shows an invalid simplification of the input shown in Figure 4.


Image 6

P1 changes position with respect to line L1, so it is not a valid simplification. Similarly, point P5 changes position with respect to line L4.

Assumptions about the data and simplification process

  1. Data is assumed to be in Cartesian space.
  2. Linear geometries do not have self-intersections.
  3. Linear geometries do not intersect with other linear geometries except at end points.
  4. The constraining points do not intersect any of the linear geometries. 
  5. Number of lines will vary for each test. 
  6. Number of points will vary for each test. 
  7. The line generalization algorithm is expected to delete some of the input points to generalize the lines. It is not expected to add vertices that are not part of the input.
  8. The number of vertices in the generalized line are less than or equal to the number of vertices in the original line geometry. 
  9. The line generalization algorithm should not change the end points of the input line geometries. That is, it can remove any intermediate vertices except the end points. This preserves the original end point coincidences of the input line geometries. 

Evaluation Rules

  1. The time to process all the input data will be the main criterion for the evaluation of the solution. So the solution with the best rate (points reduced per minute) is the winner. 
  2. Each line will be assigned a score that is equal to the number of points reduced compared to the original geometry for that line.
  3. The accuracy of the result is also considered. If a line is simplified, but it violates the topological constraints of the input, the simplification for that line will not be considered. That is, even if x number of vertices are deleted from that line, the score for that line will be zero. 
  4. The program should be able to take a parameter that specifies the number of points to be removed from the input. 
  5. We will evaluate the input program with different values for this parameter. Final score will be averaged over all the different runs.

Input Data Format 

The first section of the input will describe the input line geometries in GML 2.1.1 format. The format will be an ID, followed by the GML for the line. The second section of the input will describe the input point geometries in GML 2.1.1. format. The format will be an ID, followed by the GML for the point.

Output Data Format

Output should be the set of simplified line geometries along with their IDs. The point geometries do not appear in the output.