Creating a Graph from a Voronoi Tessellation

[mkemeter]

In this blog post I will (very briefly) highlight one use case for Voronoi tessellations - a feature that has been introduced with SAP HANA 2 SPS05 and SAP HANA Cloud. A Voronoi polygon around a given point covers the area that is closer to this point than to any other point on a plane. You can watch a demo video here.

 

Find a path that avoids obstacles by using a Voronoi tessellation

 

If you have worked with Voronoi tessellations in SAP HANA before, you may think of it as being a tessellation of a plane by Voronoi polygons. So essentially the result is a set of polygons covering a plane without gaps and without overlap.

However, a Voronoi tessellation can also be interpreted as a graph, where each point of a polygon corresponds to a node of the graph and each line of a polygon corresponds to an edge. This is not to be confused with the dual graph and the associated Delaunay triangulation of the Voronoi tessellation, which you will also commonly find in literature.

So, why would you like to create that graph? Is there any use case behind?

One possible use case is path finding in open terrain, while avoiding hazards. Think for example about game development. Our hero wants to bypass several enemies, while keeping maximum distance to them. Obviously, the optimal path for this undertaking would be along the edges of the Voronoi polygons of the enemy locations. In this case, you would assign a path weight, that correlates with the distance to enemies and possibly the length of the path.

How is this done technically with SAP HANA?

Out of curiosity I wrote a little SQLScript, which creates a graph (i.e. its vertices and edges) out of a set of Voronoi polygons and would like to share it with you. I hope that you will find this useful.

Parameter (Input/Output)	Description
geomtable	A table variable containing identifiers and geometries (i.e. polygons that tessellate the plane)
bbox	The bounding box to apply to the tessellation. This is useful to eliminate out edges, which occur due to geometrical bounding boxes. Can be NULL if full polygons (i.e. all edges) should be considered.
vertices	Output vertices
edges	Output edges

CREATE OR REPLACE PROCEDURE GraphFromPolygons(

	IN geomtable TABLE (ID INTEGER, SHAPE ST_GEOMETRY), 

	IN bbox ST_GEOMETRY, 

	OUT vertices TABLE (ID Integer, GEOM ST_GEOMETRY),

	OUT edges TABLE (ID INTEGER, SRC_ID Integer, SRC_GEOM ST_GEOMETRY, SNK_ID Integer, SNK_GEOM ST_GEOMETRY, DISTANCE DOUBLE)

) AS

BEGIN



	-- assumptions: 

	-- * input is a table with polygons exclusively

	-- * plane is tessalated by given polygons

	-- * uncertainties are covered by the grid snapping of the srs

	-- * no new points will be introduced (e.g. overlap of polygons)

	

	DECLARE i INTEGER;

	DECLARE n INTEGER := 0;	



	exteriorrings = SELECT id, shape.st_exteriorring() AS extring FROM :geomtable;

	-- max iterations = max number of points per polygon

	SELECT MAX(extring.st_numpoints()) INTO n FROM :exteriorrings;



	-- gather all edges

	FOR i IN 2..n DO

		-- select all edges from i-1 to i, if existent

		edges_forth = 

			SELECT 

				-1 AS ID,

				-1 AS SRC_ID,

				extring.st_pointn(:i-1) AS SRC_GEOM, 

				-1 AS SNK_ID,

				extring.st_pointn(:i) AS SNK_GEOM,

				-1 AS DISTANCE

			FROM :exteriorrings

			WHERE extring.st_pointn(:i) IS NOT NULL;



		-- select the reverse edges, since we want to construct an undirected graph

		edges_back = 

			SELECT 

				-1 AS ID,

				-1 AS SRC_ID,

				extring.st_pointn(:i) AS SRC_GEOM, 

				-1 AS SNK_ID,

				extring.st_pointn(:i-1) AS SNK_GEOM,

				-1 AS DISTANCE

			FROM :exteriorrings

			WHERE extring.st_pointn(:i) IS NOT NULL;

		

		-- note that union will make the edges distinct

		edges = 

			(SELECT * FROM :edges) 

			UNION 

			(SELECT * FROM :edges_back)

			UNION

			(SELECT * FROM :edges_forth); 

	END FOR;



	IF bbox IS NOT NULL

	THEN

		edges = SELECT * FROM :edges WHERE src_geom.st_within(:bbox) > 0 or snk_geom.st_within(:bbox) > 0;

	END IF;

	

	vertices = SELECT ROW_NUMBER() OVER () AS id, geom FROM (SELECT DISTINCT src_geom AS geom FROM :edges);



	edges =

		SELECT ROW_NUMBER() OVER () AS id, v_src.id AS src_id, e.src_geom AS src_geom, v_snk.id AS snk_id, e.snk_geom AS snk_geom, e.src_geom.st_distance(e.snk_geom) AS distance

		FROM :edges e

		LEFT JOIN :vertices v_src ON v_src.geom = e.src_geom

		LEFT JOIN :vertices v_snk ON v_snk.geom = e.snk_geom;

END;

 

Example Usage

You can now call this procedure in SQLScript to retrieve the vertices and edges based on some base data:

CALL GRAPHFROMPOLYGONS(:somedata, NULL, geomvertices, geomedges);



vertices = SELECT ID FROM :geomvertices;

edges = SELECT ID, SRC_ID, SNK_ID, DISTANCE FROM :geomedges;

In GraphScript you can build a graph workspace and apply custom graph algorithms, such as the shortest path:

GRAPH g = Graph(:edges, "SRC_ID", "SNK_ID", "ID", :vertices, "ID");

	

VERTEX v_src = Vertex(:g, :src);

VERTEX v_snk = Vertex(:g, :snk);



WeightedPath<DOUBLE> p = Shortest_Path(:g, :v_src, :v_snk, (Edge e) => DOUBLE{ RETURN :e.DISTANCE; });

	

distance = WEIGHT(:p);

To learn more about GraphScript and its usage, I recommend checking rawatu's blog on SAP HANA Graph:

Find Your Path – With SAP HANA Graph

Summary

Did you realize, that the Stored Procedure outlined above does not explicitly make use of Voronoi polygons, which I used as a motivation? In fact the procedure does not only work with Voronoi tessellations but any tessellation of a plane by polygons. It will iterate along the edges of all polygons and create the corresponding vertices and edges for the output graph.

As always, there is no warranty for this script. Nevertheless I hope it enables you to build some interesting use cases involving SAP HANA Spatial and SAP HANA Graph. I am looking forward learning about your use cases in the comments section of this blog!