D 2012-08-29T19:50:28.807
L tesselations-4.0
U sandro
W 11733
x<h2>Tesselation-related SQL functions supported in version 4.0.0</h2>
Back to <a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=switching-to-4.0#tessellation">main page</a>
<h3>Generalities about tessellations</h3>
<i>Tessellation is the process of creating a two-dimensional plane using the repetition of a geometric shape with no overlaps and no gaps.</i>
<a href="http://en.wikipedia.org/wiki/Tessellation">read more</a><br><br>
A tessellation could be eventually based on indentical <i>cells</i>, all of exactly the same shape and size.
In this case we'll have a <i>regular tessellation</i>.<br>
Just a quick recall of elementary geometry; there are simply <b>3</b> regular polygonal shapes we can use in order to get a regular tessellation: the <b>equilateral triangle</b>, the <b>square</b> and the <b>regular hexagon</b>.<br><br>
On the other way many tessellations aren't regular at all, because each single cell has an individual size and shape of its own.<br>
It's really interesting to note that many <i>natural shapes</i> 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 <i>on the wild</i>.
So it's not at all surprising to discover that tessellations are often useful in geography as well.
<h3>Setting up a testbed DB</h3>
In this short tutorial we'll use a very simple SpatiaLite DB, just containing the following Geometry tables:<ul>
<li>Administrative boundaries for Italy regions: you can <a href="http://www.istat.it/it/files/2011/04/reg2011.zip">download</a> this dataset from ISTAT (released on CC-BY license terms).<br></li>
<li>Main Italian populated places (namely, Local Councils): you can <a href="http://download.geonames.org/export/dump/allCountries.zip">download</a> this dataset from GeoNames (released on CC-BY license terms).<br>
Please note: this one is a worldwide dataset; italian populated places have then been extracted imposing the SQL clause<br>
<b>WHERE county_code = 'IT' AND population > 0</b></li>
</ul><br>
Just to keep any example as simple as possible, both datasets have been referenced into the <b>SRID=23032 - ED50 / UMT32 zone N</b>
<br><br><hr>
<h3>Creating regular tessellations in Spatial SQL</h3>
<table cellspacing="4" cellpadding="4">
<tr><td colspan="2">
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<i>generic prototypes</i>:<hr>
ST_xxxxGrid( input <i>Geometry</i>, size <i>double precision</i> ) : grid <i>Geometry</i><br>
ST_xxxxGrid( input <i>Geometry</i>, size <i>double precision</i>, edges_only <i>boolean</i> ) : grid <i>Geometry</i><br>
ST_xxxxGrid( input <i>Geometry</i>, size <i>double precision</i>, edges_only <i>boolean</i>, origin <i>Geometry</i> ) : grid <i>Geometry</i>
</td></tr></table>
<ul>
<li>the <b>input</b> Geometry is always expected to be a Polygon or a MultiPolygon, and will be exactly covered by the return grid.</li>
<li>the <b>size</b> argument identifies the edge length of the grid cell.</li>
<li>the facultative <b>edges_only</b> argument will be interpreted as follows:<ul>
<li>if <b>FALSE</b> (<i>default value</i>) a MultiPolygon will be returned.</li>
<li>if <b>TRUE</b> a MultiLinestring will be returned (simply representing the cells edges).</li>
</ul></li>
<li>the facultative <b>origin</b> Geometry is always assumed to be a Point, and will identify the grid's origin.<br>
By default a <b>(0, 0)</b> origin will be assumed.</li>
</ul></td></tr>
<tr><td>
<h4>using Square cells</h4>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<b>SELECT ST_SquareGrid(geometry, 10000)<br>
FROM regions<br>WHERE cod_reg = 9;</b>
</td></tr>
</table><br>
This SQL query will return a regular grid (square cells) covering Tuscany (<b>cod_reg=9</b>).<br>
Each grid's cell will have an edge length of exactly <b>10 Km</b>
</td>
<td><img border="1" src="http://www.gaia-gis.it/gaia-sins/write-view-pics/square-grid.png" alt="square grid"></td></tr>
<tr><td>
<h4>using Triangular cells</h4>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<b>SELECT ST_TriangularGrid(geometry, 10000)<br>
FROM regions<br>WHERE cod_reg = 9;</b>
</td></tr>
</table></td>
<td><img border="1" src="http://www.gaia-gis.it/gaia-sins/write-view-pics/tri-grid.png" alt="triangular grid"></td></tr>
<tr><td>
<h4>using Hexagonal cells</h4>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<b>SELECT ST_HexagonalGrid(geometry, 10000)<br>
FROM regions<br>WHERE cod_reg = 9;</b>
</td></tr>
</table></td>
<td><img border="1" src="http://www.gaia-gis.it/gaia-sins/write-view-pics/hex-grid.png" alt="hexagonal grid"></td></tr>
</table>
<br><hr>
<h3>Delaunay Triangulations</h3>
Triangulations simply represent a special case of tessellations: in this case all cells are represented by generic <b>triangles</b>, not necessarily of the equilateral kind.<br>
A <b>Delaunay Triangulation</b> is very peculiar, imposing a specific constraint.<br>
All triangles in a Delaunay triangulation must satisfy the <u><i>empty circle</i></u> property: i.e. for each edge we can find a circle containing the edge's endpoints but not containing any other points.
<a href="http://en.wikipedia.org/wiki/Delaunay_triangulation">read more</a><br><br>
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.<br>
The next-to-come <a href="http://trac.osgeo.org/geos/">GEOS 3.4.0</a> will support Delaunay Triangulations; this GEOS version is currently still under active development, but the <i>experimental</i> base-code (<i>trunk</i>) 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.<br><br>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<i>prototype</i>:<hr>
ST_DelaunayTriangulation( input <i>Geometry</i> ) : delaunay <i>Geometry</i><br>
ST_DelaunayTriangulation( input <i>Geometry</i>, edges_only <i>boolean</i> ) : delaunay <i>Geometry</i><br>
ST_DelaunayTriangulation( input <i>Geometry</i>, edges_only <i>boolean</i>, tolerance <i>double precision</i> ) : delaunay <i>Geometry</i>
</td></tr></table>
<ul>
<li>the <b>input</b> Geometry can be of absolutely arbitrary type; all Linestrings and / or Polygowns will eventually be dissolved into Points corresponding to vertices.<br>
So after all ST_DelaunayTriangulation() will always process a MultiPoint.</li>
<li>the facultative <b>edges_only</b> argument will be interpreted as follows:<ul>
<li>if <b>FALSE</b> (<i>default value</i>) a MultiPolygon will be returned.</li>
<li>if <b>TRUE</b> a MultiLinestring will be returned (simply representing the triangles edges).</li>
</ul></li>
<li>the facultative <b>tolerance</b> argument is intended to normalize the input point-set, suppressing repeated (or too much close) points.<br>
By default a <b>0.0</b> tolerance will be assumed.</li>
</ul></td></tr></table>
<table cellspacing="4" cellpadding="4">
<tr><td>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<b>SELECT ST_DelaunayTriangulation(ST_Collect(geometry))<br>
FROM italy_populated_places;</b>
</td></tr>
</table><br>
This SQL query will return a Delaunay Triangulation based on Italy's populated places (about 8,000+ Points).<br>
The visual example simply covers Tuscany, so the ensure an easy readibility.
</td>
<td><img border="1" src="http://www.gaia-gis.it/gaia-sins/write-view-pics/delaunay.png" alt="delaunay triangulation"></td></tr>
</table>
<br><hr>
<h3>Voronoj Diagrams</h3>
<table cellspacing="4" cellpadding="4">
<tr><td><img border="1" src="http://www.gaia-gis.it/gaia-sins/write-view-pics/voronoj-1.png" alt="voronoj-dealaunay relationship">
</td><td>
The <b>Voronoj Diagram</b> simply is the <i><u>dual graph</u></i> of the <b>Delaunay Triangulation</b>.
A Voronoj Diagram still is a tessellation, and cells in a Voronoj can have any arbitrary polygonal (irregular) shape.<br><br>
This figure clearly shows the relation joining the Delaunay Triangulation and the corresponding Voronoj Diagram.<br><br>
Each single Voronoj's cell is obtained by connecting all the <i>circumcenters</i> of adjacent Delaunay's triangles; consequently each Voronoj cell surely contains one (and only one) Delaunay's node.<br><br>
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.<br>
So the Voronoj Diagram is a very effective conceptual tool allowing to divide an arbitrary space region in many <i>rational</i> cells, and is thus widely usued on many applicative fields.<br>
This including Geography, obviously.<br><br>
<a href="http://en.wikipedia.org/wiki/Voronoi_tessellation">read more</a>
<br></td></tr></table>
<a href="http://trac.osgeo.org/geos/">GEOS 3.4.0</a> 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).<br><br>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<i>prototype</i>:<hr>
ST_VoronojDiagram( input <i>Geometry</i> ) : voronoj <i>Geometry</i><br>
ST_VoronojDiagram( input <i>Geometry</i>, edges_only <i>boolean</i> ) : voronoj <i>Geometry</i><br>
ST_VoronojDiagramn( input <i>Geometry</i>, edges_only <i>boolean</i>, extra_frame_size <i>double precision</i> ) : voronoj <i>Geometry</i>
ST_VoronojDiagramn( input <i>Geometry</i>, edges_only <i>boolean</i>, extra_frame_size <i>double precision</i>, tolerance <i>double precision</i> ) : voronoj <i>Geometry</i>
</td></tr></table>
<ul>
<li>the <b>input</b> Geometry can be of absolutely arbitrary type; all Linestrings and / or Polygowns will eventually be dissolved into Points corresponding to vertices.<br>
So after all ST_VoronojDiagram() (exactly as ST_DelaunayTriangulation) will always process a MultiPoint.</li>
<li>the facultative <b>edges_only</b> argument will be interpreted as follows:<ul>
<li>if <b>FALSE</b> (<i>default value</i>) a MultiPolygon will be returned.</li>
<li>if <b>TRUE</b> a MultiLinestring will be returned (simply representing the triangles edges).</li>
</ul></li>
<li>the facultative <b>extra_frame_size</b> xxxxxx
<li>the facultative <b>tolerance</b> argument is intended to normalize the input point-set, suppressing repeated points (simply used when internally computing the Delaunay Triangulation).<br>
By default a <b>0.0</b> tolerance will be assumed.</li>
</ul></td></tr></table>
<table cellspacing="4" cellpadding="4">
<tr><td>
<table bgcolor="#f0f0f0" cellspacing="4" cellpadding="8">
<tr><td>
<b>SELECT ST_VoronojDiagma(ST_Collect(geometry))<br>
FROM italy_populated_places;</b>
</td></tr>
</table><br>
This SQL query will return a Voronoj Diagram based on Italy's populated places (about 8,000+ Points).<br>
The visual example simply covers Tuscany, so the ensure an easy readibility.<br>
All <i>populated places</i> (aka cell's seeds) are explicitly represented.
</td>
<td><img border="1" src="http://www.gaia-gis.it/gaia-sins/write-view-pics/voronoj-2.png" alt="voronoj diagram"></td></tr>
</table>
<br><hr>
Back to <a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=switching-to-4.0#tesselation">main page</a>
Z 1ed9f4fb75eb13c6dd0f3c8dec01bd8c