How can two maps be compared? The scenario is the creation of street maps. For example, two people at Open Street map edit the same part of the map at the same time. Now the one that submits the data later should see a diff. Assume they both started with no vertex, but they had the same aerial image as a basis to create the digital map.

Let's define a street map $M$ as a set of vertices and edges $M := (V, E)$ with

\begin{align}
V &amp;\subseteq \mathbb{R}^2\\
E &amp;\subseteq V \times V
\end{align}

I want to compare two maps $M_1$ and $M_2$, where $M_1$ was there first. Think of two teams creatings a map from satellite images on Open Street Maps (OSM).

What I want to understand is:


How many roads (edges) are new?
How many roads (edges) were removed?
How many roads (edges) were changed?


I only could think of Dynamic Time Warping to get a score how much things have changed. But very likely no single vertex will be exactly the same, but most will be close.

What is a change?

A "change" is fuzzy in this context. If it is only about a single vertex, I would say if the geo-positions of that vertex only changed by &lt; 10cm, it is for sure only a change. Likely also if it is less than 1m due to the lack of precision in GPS (and likely also the aerial image).

It is more complicated for streets which consist of multiple line segments and not necessarily the same number of line segments. If one knows which line segments should belong together, I would use the Douglas-Peucker algorithm to reduce the street with more line segments to have an equal amount of line segments as the second street. Then one can check if a single vertex is over the threshold to determine if a segment is different. In this case different would mean there is a "removed" and "new" segment.

But when we cannot have such a mapping I only see the possibility to check everything for change. And this does not cover the case of a change in between.

For example, obviously street (a) and street (b) have quite a bit in common, besides only point (a). They have the whole line segment AY in common.

a: A---------------------------------X

b: A---------------------Y
                          \
                           \---------Z
As a map is a geometric object, you can use from the concept of map matching in computational geometry. Also, some measures like Frechet Distance could help you to compare two maps on the plane.