I have a series of spatial polygons on a 2D plane (Fig a). These polygons can be represented as a graph where neighbouring polygons are linked and the location of the nodes is dictated by the centroid of the polygon (e.g. Fig b).

enter image description here

I want to map each node to a point on a grid (e.g. Fig c) whilst maintaining as much topological similarity as possible. I.e. to find the graph (which will have the same number of nodes) that is most topologically similar to the existing graph but under two constraints:

  • Each node must sit on its own unique point on the grid
  • Once assigned, all nodes must be contiguous on the grid

By topologically similar I mean having the same neighbours and ideally having as similar as possible spatial relationships (e.g. polygons remain on similar sides of another).

I am aware that certain graph similarity methods could be used (e.g. https://wadsashika.wordpress.com/2014/09/19/measuring-graph-similarity-using-neighbor-matching/ and graph kernels can be understood to measure the similarity of graphs.

Is there any way of calculating / generating the graph that is most similar (optimal) given certain constraints (i.e. moving the nodes to a grid). I see it as an optimisation problem but I’m not aware of any formal algorithms that identify optimally similar graphs (when using topology as a metric).

Should any solutions exist i will be looking to implement them in R and thanks in advance for any insight!


migrated from stackoverflow.com Aug 9 '17 at 15:06

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ There is a country in the example (on the south west end) that didn't get a node. This is not supposed to happen, right? $\endgroup$ – Hellen Aug 9 '17 at 15:19
  • $\begingroup$ Thanks for pointing this out - in this case i believe it's the river. As the river narrows it becomes indiscernible from a border. (Apologies for not providing a higher resolution image). $\endgroup$ – Hamley Aug 10 '17 at 9:37

I could see building an iterative solution following: https://gis.stackexchange.com/questions/121722/how-can-i-snap-one-set-of-points-to-another-in-r.

  1. Start with a seed

  2. For each point i, generate some candidate shortest distances to target grid.

  3. Test if any meet the topology criteria

  4. Reject any that don't

Would probably need to traverse the tree many times to avoid points where all candidates are rejected on the basis of invalid topology.


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.