Within polygon search on graph for shortest path calculation

[Ariel deGraaf]

Hello there,

In order to calculate the shortest route from point A to B on a graph which consists of a road network

(with roads as edges and crossings as vertices), I first need to find the nearest vertices to A and B.

I was thinking to do this with the help of so-called Voronoi regions, which for each vertex define the area

that is closest to that vertex. The idea is illustrated below. All points within a certain Voronoi polygon will 

by definition be closest to the vertex associated with that polygon. In the example shown below, the 

shortest route between the two star locations will therefore be calculated between the vertices within the

polygons of the indicated vertices. 

If I add the Voronoi polygons as property to every vertex, is there an efficient way to traverse the graph

and to determine whether a given location is within the vertex' polygon?

I know that JanusGraph offers the possibility to do a GEO search, but for infrastructural reasons I prefer 

to do it in Neptune.

Any ideas?

    

Thanks in advance!

Best regards,

Ariel de Graaf

Ariel de Graaf Algorithm Developer +972-53-255-8089 ariel....@wishtrip.com

[Philip Graff]

Shalom Ariel,

What I've done for similar problems - and maybe others have a better solution - is to make sure to also put the lat/lon on the vertices. You can then, for any given input lat/lon, use a rough bounding box approach to quickly filter to a small set of nearby vertices. The size of this box is up to you and can vary based on input latitude to account for unequal distances between longitudes at different latitudes. Amongst this small set of vertices, you can then query their polygon information and compute which the point should be associated with. At this point, you could also just compute actual distances from the lat/lon values on the vertices. The bounding box serves to filter the large set of vertices to a small set amongst which the closest will lie.

Good luck,

Phil

[Ariel deGraaf]

Thank you Phil!

The approach you suggest reminded me of an article on kd-tree search (https://blog.mapbox.com/a-dive-into-spatial-search-algorithms-ebd0c5e39d2a) which I believe is the way to go!

Best regards

Ariel

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/655fd9f6-3292-445a-9c73-accb498f8f00n%40googlegroups.com.

--