How can two maps be compared?

Question

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 &\subseteq \mathbb{R}^2\\ E &\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 < 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

Answer 1

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.

Answer 2

It seems the idea you are floating is some variation of graph edit distance. The concept is general, and you need to decide a couple of things to fit your application:

1. Representation of your type of graph (which I see you already described in OP)
2. Set of graph operations allowed to be performed. (you listed rather informally)
3. The cost of performing each operation (may be dependent on input graph on top of being dependent which operation is used.)
4. editing path --- description how each elementary operations can be composed together and how composing them effects the cost. Do the cost just add up? or just take the maximum cost of the two operations being composed? In simpler case this might be just a string of editing operations $$(e_1,e_2,\ldots,e_n)$$ and the cost might simply be inductive as $$cost(e_1,e_2,\ldots,e_n) = cost(e_1) +cost(e_2,\ldots,e_n)$$

My description might be a bit too general. Maybe take a look at the basic example in the page I linked above first.

Editing cost also could reflects the idea of metric space, in particular: $$cost(e_1) + cost(e_2) \geq cost(e_1,e_2)$$ and $$0 = cost(id)$$ where $id$ stands for identity operation of doing nothing.

These two condition is the most important out of the standard four as pointed out by Lawvere's generalised metric space

---

For an advanced example, the algebraic description of tree-width, clique-width and rank-width can be thought of as instances of the more general view on graph edit distance I just mentioned.

_{This answer is relevant to my current research work.}