D 2012-08-29T19:50:28.807 L tesselations-4.0 U sandro W 11733 x

Tesselation-related SQL functions supported in version 4.0.0

Back to main page

Generalities about tessellations

Tessellation is the process of creating a two-dimensional plane using the repetition of a geometric shape with no overlaps and no gaps. read more

A tessellation could be eventually based on indentical cells, all of exactly the same shape and size. In this case we'll have a regular tessellation.
Just a quick recall of elementary geometry; there are simply 3 regular polygonal shapes we can use in order to get a regular tessellation: the equilateral triangle, the square and the regular hexagon.

On the other way many tessellations aren't regular at all, because each single cell has an individual size and shape of its own.
It's really interesting to note that many natural shapes closely resemble a tessellation: going from biology to cristallography since geology and landscapes it's not at all difficult to identify many natural tessellation examples on the wild. So it's not at all surprising to discover that tessellations are often useful in geography as well.

Setting up a testbed DB

In this short tutorial we'll use a very simple SpatiaLite DB, just containing the following Geometry tables:
Just to keep any example as simple as possible, both datasets have been referenced into the SRID=23032 - ED50 / UMT32 zone N

Creating regular tessellations in Spatial SQL

generic prototypes:
ST_xxxxGrid( input Geometry, size double precision ) : grid Geometry
ST_xxxxGrid( input Geometry, size double precision, edges_only boolean ) : grid Geometry
ST_xxxxGrid( input Geometry, size double precision, edges_only boolean, origin Geometry ) : grid Geometry
  • the input Geometry is always expected to be a Polygon or a MultiPolygon, and will be exactly covered by the return grid.
  • the size argument identifies the edge length of the grid cell.
  • the facultative edges_only argument will be interpreted as follows:
    • if FALSE (default value) a MultiPolygon will be returned.
    • if TRUE a MultiLinestring will be returned (simply representing the cells edges).
  • the facultative origin Geometry is always assumed to be a Point, and will identify the grid's origin.
    By default a (0, 0) origin will be assumed.

using Square cells

SELECT ST_SquareGrid(geometry, 10000)
FROM regions
WHERE cod_reg = 9;

This SQL query will return a regular grid (square cells) covering Tuscany (cod_reg=9).
Each grid's cell will have an edge length of exactly 10 Km 		square grid

using Triangular cells

SELECT ST_TriangularGrid(geometry, 10000)
FROM regions
WHERE cod_reg = 9;
triangular grid

using Hexagonal cells

SELECT ST_HexagonalGrid(geometry, 10000)
FROM regions
WHERE cod_reg = 9;
hexagonal grid

Delaunay Triangulations

Triangulations simply represent a special case of tessellations: in this case all cells are represented by generic triangles, not necessarily of the equilateral kind.
A Delaunay Triangulation is very peculiar, imposing a specific constraint.
All triangles in a Delaunay triangulation must satisfy the empty circle property: i.e. for each edge we can find a circle containing the edge's endpoints but not containing any other points. read more

Computing a Delaunay Triangulation representing many points is a very complex opeation, and one possibily imposing a huge computational load and may be requiring a long time. Happily enough many highly efficient alghorithms have been already developed for the Dalaunay problem.
The next-to-come GEOS 3.4.0 will support Delaunay Triangulations; this GEOS version is currently still under active development, but the experimental base-code (trunk) seems to be stable enough to be safely tested. SpatiaLite already relies on GEOS for many tasks, so integrating a smooth support for Delaunay Triangulation as well wasn't at all difficult.

prototype:
ST_DelaunayTriangulation( input Geometry ) : delaunay Geometry
ST_DelaunayTriangulation( input Geometry, edges_only boolean ) : delaunay Geometry
ST_DelaunayTriangulation( input Geometry, edges_only boolean, tolerance double precision ) : delaunay Geometry
SELECT ST_DelaunayTriangulation(ST_Collect(geometry))
FROM italy_populated_places;

This SQL query will return a Delaunay Triangulation based on Italy's populated places (about 8,000+ Points).
The visual example simply covers Tuscany, so the ensure an easy readibility. 		delaunay triangulation

Voronoj Diagrams

voronoj-dealaunay relationship The Voronoj Diagram simply is the dual graph of the Delaunay Triangulation. A Voronoj Diagram still is a tessellation, and cells in a Voronoj can have any arbitrary polygonal (irregular) shape.

This figure clearly shows the relation joining the Delaunay Triangulation and the corresponding Voronoj Diagram.

Each single Voronoj's cell is obtained by connecting all the circumcenters of adjacent Delaunay's triangles; consequently each Voronoj cell surely contains one (and only one) Delaunay's node.

The cell in the Voronoj Diagram presents an interesting property: all points falling within the same cell are ensured to be nearest to the Delaunay's node placed on the cell itself than to any other Delaunay's node placed in a different cell.
So the Voronoj Diagram is a very effective conceptual tool allowing to divide an arbitrary space region in many rational cells, and is thus widely usued on many applicative fields.
This including Geography, obviously.

read more
GEOS 3.4.0 will not support Voronoj; so the SpatiaLite own support is based on an original implementation (based in turn on the Delaunay support made available by GEOS).

prototype:
ST_VoronojDiagram( input Geometry ) : voronoj Geometry
ST_VoronojDiagram( input Geometry, edges_only boolean ) : voronoj Geometry
ST_VoronojDiagramn( input Geometry, edges_only boolean, extra_frame_size double precision ) : voronoj Geometry ST_VoronojDiagramn( input Geometry, edges_only boolean, extra_frame_size double precision, tolerance double precision ) : voronoj Geometry
SELECT ST_VoronojDiagma(ST_Collect(geometry))
FROM italy_populated_places;

This SQL query will return a Voronoj Diagram based on Italy's populated places (about 8,000+ Points).
The visual example simply covers Tuscany, so the ensure an easy readibility.
All populated places (aka cell's seeds) are explicitly represented. 		voronoj diagram

Back to main page Z 1ed9f4fb75eb13c6dd0f3c8dec01bd8c