1
$\begingroup$

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
$\endgroup$
7
  • $\begingroup$ Side question: How is such a graph with vertices that have a position called? Is this and embedding in $\mathbb{R}^2$? $\endgroup$ Jun 25, 2018 at 5:24
  • 2
    $\begingroup$ What do you consider to be a "changed" edge, as opposed to one being removed and one added? $\endgroup$ Jun 25, 2018 at 5:38
  • 1
    $\begingroup$ Is the set of vertices the same for both $M_1,M_2$? If vertices can change position between the two maps, are they close enough that you can associate each vertex in $M_1$ with its corresponding vertex in $M_2$, and vice versa? Are there vertices in one map but not the other? $\endgroup$
    – D.W.
    Jun 25, 2018 at 5:47
  • 1
    $\begingroup$ Please edit the question to provide all that information in the question. Thank you! Also, what counts as a road that is the same, when the vertex has "moved"? If vertices $v_1,v_2$ move, but there's still a road between them, is that the same road or a change to the road? $\endgroup$
    – D.W.
    Jun 25, 2018 at 6:59
  • 1
    $\begingroup$ Is the map oriented the same, has the same dimensions, same scale, same vertex names? This could be either trivial or incredibly complex. Please add far more detail to your question. $\endgroup$
    – bukwyrm
    Jun 26, 2018 at 16:07

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.