Artifact
5233d7fdaca430825f1a3cd83bc2c489d37b6890:
Wiki page
[tesselations-4.0] by
sandro
2012-08-29 19:50:28.
0000: 44 20 32 30 31 32 2d 30 38 2d 32 39 54 31 39 3a D 2012-08-29T19:
0010: 35 30 3a 32 38 2e 38 30 37 0a 4c 20 74 65 73 73 50:28.807.L tess
0020: 65 6c 61 74 69 6f 6e 73 2d 34 2e 30 0a 55 20 73 elations-4.0.U s
0030: 61 6e 64 72 6f 0a 57 20 31 31 37 33 33 0a 78 3c andro.W 11733.x<
0040: 68 32 3e 54 65 73 73 65 6c 61 74 69 6f 6e 2d 72 h2>Tesselation-r
0050: 65 6c 61 74 65 64 20 53 51 4c 20 66 75 6e 63 74 elated SQL funct
0060: 69 6f 6e 73 20 73 75 70 70 6f 72 74 65 64 20 69 ions supported i
0070: 6e 20 76 65 72 73 69 6f 6e 20 34 2e 30 2e 30 3c n version 4.0.0<
0080: 2f 68 32 3e 0d 0a 42 61 63 6b 20 74 6f 20 3c 61 /h2>..Back to <a
0090: 20 68 72 65 66 3d 22 68 74 74 70 73 3a 2f 2f 77 href="https://w
00a0: 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 66 ww.gaia-gis.it/f
00b0: 6f 73 73 69 6c 2f 6c 69 62 73 70 61 74 69 61 6c ossil/libspatial
00c0: 69 74 65 2f 77 69 6b 69 3f 6e 61 6d 65 3d 73 77 ite/wiki?name=sw
00d0: 69 74 63 68 69 6e 67 2d 74 6f 2d 34 2e 30 23 74 itching-to-4.0#t
00e0: 65 73 73 65 6c 6c 61 74 69 6f 6e 22 3e 6d 61 69 essellation">mai
00f0: 6e 20 70 61 67 65 3c 2f 61 3e 0d 0a 3c 68 33 3e n page</a>..<h3>
0100: 47 65 6e 65 72 61 6c 69 74 69 65 73 20 61 62 6f Generalities abo
0110: 75 74 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 73 ut tessellations
0120: 3c 2f 68 33 3e 0d 0a 3c 69 3e 54 65 73 73 65 6c </h3>..<i>Tessel
0130: 6c 61 74 69 6f 6e 20 69 73 20 74 68 65 20 70 72 lation is the pr
0140: 6f 63 65 73 73 20 6f 66 20 63 72 65 61 74 69 6e ocess of creatin
0150: 67 20 61 20 74 77 6f 2d 64 69 6d 65 6e 73 69 6f g a two-dimensio
0160: 6e 61 6c 20 70 6c 61 6e 65 20 75 73 69 6e 67 20 nal plane using
0170: 74 68 65 20 72 65 70 65 74 69 74 69 6f 6e 20 6f the repetition o
0180: 66 20 61 20 67 65 6f 6d 65 74 72 69 63 20 73 68 f a geometric sh
0190: 61 70 65 20 77 69 74 68 20 6e 6f 20 6f 76 65 72 ape with no over
01a0: 6c 61 70 73 20 61 6e 64 20 6e 6f 20 67 61 70 73 laps and no gaps
01b0: 2e 3c 2f 69 3e 0d 0a 3c 61 20 68 72 65 66 3d 22 .</i>..<a href="
01c0: 68 74 74 70 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 http://en.wikipe
01d0: 64 69 61 2e 6f 72 67 2f 77 69 6b 69 2f 54 65 73 dia.org/wiki/Tes
01e0: 73 65 6c 6c 61 74 69 6f 6e 22 3e 72 65 61 64 20 sellation">read
01f0: 6d 6f 72 65 3c 2f 61 3e 3c 62 72 3e 3c 62 72 3e more</a><br><br>
0200: 0d 0a 41 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e ..A tessellation
0210: 20 63 6f 75 6c 64 20 62 65 20 65 76 65 6e 74 75 could be eventu
0220: 61 6c 6c 79 20 62 61 73 65 64 20 6f 6e 20 69 6e ally based on in
0230: 64 65 6e 74 69 63 61 6c 20 3c 69 3e 63 65 6c 6c dentical <i>cell
0240: 73 3c 2f 69 3e 2c 20 61 6c 6c 20 6f 66 20 65 78 s</i>, all of ex
0250: 61 63 74 6c 79 20 74 68 65 20 73 61 6d 65 20 73 actly the same s
0260: 68 61 70 65 20 61 6e 64 20 73 69 7a 65 2e 0d 0a hape and size...
0270: 49 6e 20 74 68 69 73 20 63 61 73 65 20 77 65 27 In this case we'
0280: 6c 6c 20 68 61 76 65 20 61 20 3c 69 3e 72 65 67 ll have a <i>reg
0290: 75 6c 61 72 20 74 65 73 73 65 6c 6c 61 74 69 6f ular tessellatio
02a0: 6e 3c 2f 69 3e 2e 3c 62 72 3e 0d 0a 4a 75 73 74 n</i>.<br>..Just
02b0: 20 61 20 71 75 69 63 6b 20 72 65 63 61 6c 6c 20 a quick recall
02c0: 6f 66 20 65 6c 65 6d 65 6e 74 61 72 79 20 67 65 of elementary ge
02d0: 6f 6d 65 74 72 79 3b 20 74 68 65 72 65 20 61 72 ometry; there ar
02e0: 65 20 73 69 6d 70 6c 79 20 3c 62 3e 33 3c 2f 62 e simply <b>3</b
02f0: 3e 20 72 65 67 75 6c 61 72 20 70 6f 6c 79 67 6f > regular polygo
0300: 6e 61 6c 20 73 68 61 70 65 73 20 77 65 20 63 61 nal shapes we ca
0310: 6e 20 75 73 65 20 69 6e 20 6f 72 64 65 72 20 74 n use in order t
0320: 6f 20 67 65 74 20 61 20 72 65 67 75 6c 61 72 20 o get a regular
0330: 74 65 73 73 65 6c 6c 61 74 69 6f 6e 3a 20 74 68 tessellation: th
0340: 65 20 3c 62 3e 65 71 75 69 6c 61 74 65 72 61 6c e <b>equilateral
0350: 20 74 72 69 61 6e 67 6c 65 3c 2f 62 3e 2c 20 74 triangle</b>, t
0360: 68 65 20 3c 62 3e 73 71 75 61 72 65 3c 2f 62 3e he <b>square</b>
0370: 20 61 6e 64 20 74 68 65 20 3c 62 3e 72 65 67 75 and the <b>regu
0380: 6c 61 72 20 68 65 78 61 67 6f 6e 3c 2f 62 3e 2e lar hexagon</b>.
0390: 3c 62 72 3e 3c 62 72 3e 0d 0a 4f 6e 20 74 68 65 <br><br>..On the
03a0: 20 6f 74 68 65 72 20 77 61 79 20 6d 61 6e 79 20 other way many
03b0: 74 65 73 73 65 6c 6c 61 74 69 6f 6e 73 20 61 72 tessellations ar
03c0: 65 6e 27 74 20 72 65 67 75 6c 61 72 20 61 74 20 en't regular at
03d0: 61 6c 6c 2c 20 62 65 63 61 75 73 65 20 65 61 63 all, because eac
03e0: 68 20 73 69 6e 67 6c 65 20 63 65 6c 6c 20 68 61 h single cell ha
03f0: 73 20 61 6e 20 69 6e 64 69 76 69 64 75 61 6c 20 s an individual
0400: 73 69 7a 65 20 61 6e 64 20 73 68 61 70 65 20 6f size and shape o
0410: 66 20 69 74 73 20 6f 77 6e 2e 3c 62 72 3e 0d 0a f its own.<br>..
0420: 49 74 27 73 20 72 65 61 6c 6c 79 20 69 6e 74 65 It's really inte
0430: 72 65 73 74 69 6e 67 20 74 6f 20 6e 6f 74 65 20 resting to note
0440: 74 68 61 74 20 6d 61 6e 79 20 3c 69 3e 6e 61 74 that many <i>nat
0450: 75 72 61 6c 20 73 68 61 70 65 73 3c 2f 69 3e 20 ural shapes</i>
0460: 63 6c 6f 73 65 6c 79 20 72 65 73 65 6d 62 6c 65 closely resemble
0470: 20 61 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 3a a tessellation:
0480: 20 67 6f 69 6e 67 20 66 72 6f 6d 20 62 69 6f 6c going from biol
0490: 6f 67 79 20 74 6f 20 63 72 69 73 74 61 6c 6c 6f ogy to cristallo
04a0: 67 72 61 70 68 79 20 73 69 6e 63 65 20 67 65 6f graphy since geo
04b0: 6c 6f 67 79 20 61 6e 64 20 6c 61 6e 64 73 63 61 logy and landsca
04c0: 70 65 73 20 69 74 27 73 20 6e 6f 74 20 61 74 20 pes it's not at
04d0: 61 6c 6c 20 64 69 66 66 69 63 75 6c 74 20 74 6f all difficult to
04e0: 20 69 64 65 6e 74 69 66 79 20 6d 61 6e 79 20 6e identify many n
04f0: 61 74 75 72 61 6c 20 74 65 73 73 65 6c 6c 61 74 atural tessellat
0500: 69 6f 6e 20 65 78 61 6d 70 6c 65 73 20 3c 69 3e ion examples <i>
0510: 6f 6e 20 74 68 65 20 77 69 6c 64 3c 2f 69 3e 2e on the wild</i>.
0520: 0d 0a 53 6f 20 69 74 27 73 20 6e 6f 74 20 61 74 ..So it's not at
0530: 20 61 6c 6c 20 73 75 72 70 72 69 73 69 6e 67 20 all surprising
0540: 74 6f 20 64 69 73 63 6f 76 65 72 20 74 68 61 74 to discover that
0550: 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 73 20 61 tessellations a
0560: 72 65 20 6f 66 74 65 6e 20 75 73 65 66 75 6c 20 re often useful
0570: 69 6e 20 67 65 6f 67 72 61 70 68 79 20 61 73 20 in geography as
0580: 77 65 6c 6c 2e 0d 0a 3c 68 33 3e 53 65 74 74 69 well...<h3>Setti
0590: 6e 67 20 75 70 20 61 20 74 65 73 74 62 65 64 20 ng up a testbed
05a0: 44 42 3c 2f 68 33 3e 0d 0a 49 6e 20 74 68 69 73 DB</h3>..In this
05b0: 20 73 68 6f 72 74 20 74 75 74 6f 72 69 61 6c 20 short tutorial
05c0: 77 65 27 6c 6c 20 75 73 65 20 61 20 76 65 72 79 we'll use a very
05d0: 20 73 69 6d 70 6c 65 20 53 70 61 74 69 61 4c 69 simple SpatiaLi
05e0: 74 65 20 44 42 2c 20 6a 75 73 74 20 63 6f 6e 74 te DB, just cont
05f0: 61 69 6e 69 6e 67 20 74 68 65 20 66 6f 6c 6c 6f aining the follo
0600: 77 69 6e 67 20 47 65 6f 6d 65 74 72 79 20 74 61 wing Geometry ta
0610: 62 6c 65 73 3a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 41 bles:<ul>..<li>A
0620: 64 6d 69 6e 69 73 74 72 61 74 69 76 65 20 62 6f dministrative bo
0630: 75 6e 64 61 72 69 65 73 20 66 6f 72 20 49 74 61 undaries for Ita
0640: 6c 79 20 72 65 67 69 6f 6e 73 3a 20 79 6f 75 20 ly regions: you
0650: 63 61 6e 20 3c 61 20 68 72 65 66 3d 22 68 74 74 can <a href="htt
0660: 70 3a 2f 2f 77 77 77 2e 69 73 74 61 74 2e 69 74 p://www.istat.it
0670: 2f 69 74 2f 66 69 6c 65 73 2f 32 30 31 31 2f 30 /it/files/2011/0
0680: 34 2f 72 65 67 32 30 31 31 2e 7a 69 70 22 3e 64 4/reg2011.zip">d
0690: 6f 77 6e 6c 6f 61 64 3c 2f 61 3e 20 74 68 69 73 ownload</a> this
06a0: 20 64 61 74 61 73 65 74 20 66 72 6f 6d 20 49 53 dataset from IS
06b0: 54 41 54 20 28 72 65 6c 65 61 73 65 64 20 6f 6e TAT (released on
06c0: 20 43 43 2d 42 59 20 6c 69 63 65 6e 73 65 20 74 CC-BY license t
06d0: 65 72 6d 73 29 2e 3c 62 72 3e 3c 2f 6c 69 3e 0d erms).<br></li>.
06e0: 0a 3c 6c 69 3e 4d 61 69 6e 20 49 74 61 6c 69 61 .<li>Main Italia
06f0: 6e 20 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 n populated plac
0700: 65 73 20 28 6e 61 6d 65 6c 79 2c 20 4c 6f 63 61 es (namely, Loca
0710: 6c 20 43 6f 75 6e 63 69 6c 73 29 3a 20 79 6f 75 l Councils): you
0720: 20 63 61 6e 20 3c 61 20 68 72 65 66 3d 22 68 74 can <a href="ht
0730: 74 70 3a 2f 2f 64 6f 77 6e 6c 6f 61 64 2e 67 65 tp://download.ge
0740: 6f 6e 61 6d 65 73 2e 6f 72 67 2f 65 78 70 6f 72 onames.org/expor
0750: 74 2f 64 75 6d 70 2f 61 6c 6c 43 6f 75 6e 74 72 t/dump/allCountr
0760: 69 65 73 2e 7a 69 70 22 3e 64 6f 77 6e 6c 6f 61 ies.zip">downloa
0770: 64 3c 2f 61 3e 20 74 68 69 73 20 64 61 74 61 73 d</a> this datas
0780: 65 74 20 66 72 6f 6d 20 47 65 6f 4e 61 6d 65 73 et from GeoNames
0790: 20 28 72 65 6c 65 61 73 65 64 20 6f 6e 20 43 43 (released on CC
07a0: 2d 42 59 20 6c 69 63 65 6e 73 65 20 74 65 72 6d -BY license term
07b0: 73 29 2e 3c 62 72 3e 0d 0a 50 6c 65 61 73 65 20 s).<br>..Please
07c0: 6e 6f 74 65 3a 20 74 68 69 73 20 6f 6e 65 20 69 note: this one i
07d0: 73 20 61 20 77 6f 72 6c 64 77 69 64 65 20 64 61 s a worldwide da
07e0: 74 61 73 65 74 3b 20 69 74 61 6c 69 61 6e 20 70 taset; italian p
07f0: 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 73 20 opulated places
0800: 68 61 76 65 20 74 68 65 6e 20 62 65 65 6e 20 65 have then been e
0810: 78 74 72 61 63 74 65 64 20 69 6d 70 6f 73 69 6e xtracted imposin
0820: 67 20 74 68 65 20 53 51 4c 20 63 6c 61 75 73 65 g the SQL clause
0830: 3c 62 72 3e 0d 0a 3c 62 3e 57 48 45 52 45 20 63 <br>..<b>WHERE c
0840: 6f 75 6e 74 79 5f 63 6f 64 65 20 3d 20 27 49 54 ounty_code = 'IT
0850: 27 20 41 4e 44 20 70 6f 70 75 6c 61 74 69 6f 6e ' AND population
0860: 20 3e 20 30 3c 2f 62 3e 3c 2f 6c 69 3e 0d 0a 3c > 0</b></li>..<
0870: 2f 75 6c 3e 3c 62 72 3e 0d 0a 4a 75 73 74 20 74 /ul><br>..Just t
0880: 6f 20 6b 65 65 70 20 61 6e 79 20 65 78 61 6d 70 o keep any examp
0890: 6c 65 20 61 73 20 73 69 6d 70 6c 65 20 61 73 20 le as simple as
08a0: 70 6f 73 73 69 62 6c 65 2c 20 62 6f 74 68 20 64 possible, both d
08b0: 61 74 61 73 65 74 73 20 68 61 76 65 20 62 65 65 atasets have bee
08c0: 6e 20 72 65 66 65 72 65 6e 63 65 64 20 69 6e 74 n referenced int
08d0: 6f 20 74 68 65 20 3c 62 3e 53 52 49 44 3d 32 33 o the <b>SRID=23
08e0: 30 33 32 20 2d 20 45 44 35 30 20 2f 20 55 4d 54 032 - ED50 / UMT
08f0: 33 32 20 7a 6f 6e 65 20 4e 3c 2f 62 3e 0d 0a 3c 32 zone N</b>..<
0900: 62 72 3e 3c 62 72 3e 3c 68 72 3e 0d 0a 3c 68 33 br><br><hr>..<h3
0910: 3e 43 72 65 61 74 69 6e 67 20 72 65 67 75 6c 61 >Creating regula
0920: 72 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 73 20 r tessellations
0930: 69 6e 20 53 70 61 74 69 61 6c 20 53 51 4c 3c 2f in Spatial SQL</
0940: 68 33 3e 0d 0a 3c 74 61 62 6c 65 20 63 65 6c 6c h3>..<table cell
0950: 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c spacing="4" cell
0960: 70 61 64 64 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 padding="4">..<t
0970: 72 3e 3c 74 64 20 63 6f 6c 73 70 61 6e 3d 22 32 r><td colspan="2
0980: 22 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c ">..<table bgcol
0990: 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 6c or="#f0f0f0" cel
09a0: 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c lspacing="4" cel
09b0: 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c lpadding="8">..<
09c0: 74 72 3e 3c 74 64 3e 0d 0a 3c 69 3e 67 65 6e 65 tr><td>..<i>gene
09d0: 72 69 63 20 70 72 6f 74 6f 74 79 70 65 73 3c 2f ric prototypes</
09e0: 69 3e 3a 3c 68 72 3e 0d 0a 53 54 5f 78 78 78 78 i>:<hr>..ST_xxxx
09f0: 47 72 69 64 28 20 69 6e 70 75 74 20 3c 69 3e 47 Grid( input <i>G
0a00: 65 6f 6d 65 74 72 79 3c 2f 69 3e 2c 20 73 69 7a eometry</i>, siz
0a10: 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 e <i>double prec
0a20: 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 67 72 ision</i> ) : gr
0a30: 69 64 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f id <i>Geometry</
0a40: 69 3e 3c 62 72 3e 0d 0a 53 54 5f 78 78 78 78 47 i><br>..ST_xxxxG
0a50: 72 69 64 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 rid( input <i>Ge
0a60: 6f 6d 65 74 72 79 3c 2f 69 3e 2c 20 73 69 7a 65 ometry</i>, size
0a70: 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 69 <i>double preci
0a80: 73 69 6f 6e 3c 2f 69 3e 2c 20 65 64 67 65 73 5f sion</i>, edges_
0a90: 6f 6e 6c 79 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c only <i>boolean<
0aa0: 2f 69 3e 20 29 20 3a 20 67 72 69 64 20 3c 69 3e /i> ) : grid <i>
0ab0: 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 72 3e Geometry</i><br>
0ac0: 0d 0a 53 54 5f 78 78 78 78 47 72 69 64 28 20 69 ..ST_xxxxGrid( i
0ad0: 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 nput <i>Geometry
0ae0: 3c 2f 69 3e 2c 20 73 69 7a 65 20 3c 69 3e 64 6f </i>, size <i>do
0af0: 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f uble precision</
0b00: 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c i>, edges_only <
0b10: 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 6f i>boolean</i>, o
0b20: 72 69 67 69 6e 20 3c 69 3e 47 65 6f 6d 65 74 72 rigin <i>Geometr
0b30: 79 3c 2f 69 3e 20 29 20 3a 20 67 72 69 64 20 3c y</i> ) : grid <
0b40: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 0d 0a i>Geometry</i>..
0b50: 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c </td></tr></tabl
0b60: 65 3e 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 e>..<ul>..<li>th
0b70: 65 20 3c 62 3e 69 6e 70 75 74 3c 2f 62 3e 20 47 e <b>input</b> G
0b80: 65 6f 6d 65 74 72 79 20 69 73 20 61 6c 77 61 79 eometry is alway
0b90: 73 20 65 78 70 65 63 74 65 64 20 74 6f 20 62 65 s expected to be
0ba0: 20 61 20 50 6f 6c 79 67 6f 6e 20 6f 72 20 61 20 a Polygon or a
0bb0: 4d 75 6c 74 69 50 6f 6c 79 67 6f 6e 2c 20 61 6e MultiPolygon, an
0bc0: 64 20 77 69 6c 6c 20 62 65 20 65 78 61 63 74 6c d will be exactl
0bd0: 79 20 63 6f 76 65 72 65 64 20 62 79 20 74 68 65 y covered by the
0be0: 20 72 65 74 75 72 6e 20 67 72 69 64 2e 3c 2f 6c return grid.</l
0bf0: 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 3c 62 3e 73 i>..<li>the <b>s
0c00: 69 7a 65 3c 2f 62 3e 20 61 72 67 75 6d 65 6e 74 ize</b> argument
0c10: 20 69 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 identifies the
0c20: 65 64 67 65 20 6c 65 6e 67 74 68 20 6f 66 20 74 edge length of t
0c30: 68 65 20 67 72 69 64 20 63 65 6c 6c 2e 3c 2f 6c he grid cell.</l
0c40: 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 66 61 63 75 i>..<li>the facu
0c50: 6c 74 61 74 69 76 65 20 3c 62 3e 65 64 67 65 73 ltative <b>edges
0c60: 5f 6f 6e 6c 79 3c 2f 62 3e 20 61 72 67 75 6d 65 _only</b> argume
0c70: 6e 74 20 77 69 6c 6c 20 62 65 20 69 6e 74 65 72 nt will be inter
0c80: 70 72 65 74 65 64 20 61 73 20 66 6f 6c 6c 6f 77 preted as follow
0c90: 73 3a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 69 66 20 3c s:<ul>..<li>if <
0ca0: 62 3e 46 41 4c 53 45 3c 2f 62 3e 20 28 3c 69 3e b>FALSE</b> (<i>
0cb0: 64 65 66 61 75 6c 74 20 76 61 6c 75 65 3c 2f 69 default value</i
0cc0: 3e 29 20 61 20 4d 75 6c 74 69 50 6f 6c 79 67 6f >) a MultiPolygo
0cd0: 6e 20 77 69 6c 6c 20 62 65 20 72 65 74 75 72 6e n will be return
0ce0: 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 69 66 ed.</li>..<li>if
0cf0: 20 3c 62 3e 54 52 55 45 3c 2f 62 3e 20 61 20 4d <b>TRUE</b> a M
0d00: 75 6c 74 69 4c 69 6e 65 73 74 72 69 6e 67 20 77 ultiLinestring w
0d10: 69 6c 6c 20 62 65 20 72 65 74 75 72 6e 65 64 20 ill be returned
0d20: 28 73 69 6d 70 6c 79 20 72 65 70 72 65 73 65 6e (simply represen
0d30: 74 69 6e 67 20 74 68 65 20 63 65 6c 6c 73 20 65 ting the cells e
0d40: 64 67 65 73 29 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 dges).</li>..</u
0d50: 6c 3e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 l></li>..<li>the
0d60: 20 66 61 63 75 6c 74 61 74 69 76 65 20 3c 62 3e facultative <b>
0d70: 6f 72 69 67 69 6e 3c 2f 62 3e 20 47 65 6f 6d 65 origin</b> Geome
0d80: 74 72 79 20 69 73 20 61 6c 77 61 79 73 20 61 73 try is always as
0d90: 73 75 6d 65 64 20 74 6f 20 62 65 20 61 20 50 6f sumed to be a Po
0da0: 69 6e 74 2c 20 61 6e 64 20 77 69 6c 6c 20 69 64 int, and will id
0db0: 65 6e 74 69 66 79 20 74 68 65 20 67 72 69 64 27 entify the grid'
0dc0: 73 20 6f 72 69 67 69 6e 2e 3c 62 72 3e 0d 0a 42 s origin.<br>..B
0dd0: 79 20 64 65 66 61 75 6c 74 20 61 20 3c 62 3e 28 y default a <b>(
0de0: 30 2c 20 30 29 3c 2f 62 3e 20 6f 72 69 67 69 6e 0, 0)</b> origin
0df0: 20 77 69 6c 6c 20 62 65 20 61 73 73 75 6d 65 64 will be assumed
0e00: 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f 74 .</li>..</ul></t
0e10: 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c 74 64 d></tr>..<tr><td
0e20: 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 20 53 71 75 >..<h4>using Squ
0e30: 61 72 65 20 63 65 6c 6c 73 3c 2f 68 34 3e 0d 0a are cells</h4>..
0e40: 3c 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 <table bgcolor="
0e50: 23 66 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 #f0f0f0" cellspa
0e60: 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 cing="4" cellpad
0e70: 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c ding="8">..<tr><
0e80: 74 64 3e 0d 0a 3c 62 3e 53 45 4c 45 43 54 20 53 td>..<b>SELECT S
0e90: 54 5f 53 71 75 61 72 65 47 72 69 64 28 67 65 6f T_SquareGrid(geo
0ea0: 6d 65 74 72 79 2c 20 31 30 30 30 30 29 3c 62 72 metry, 10000)<br
0eb0: 3e 0d 0a 46 52 4f 4d 20 72 65 67 69 6f 6e 73 3c >..FROM regions<
0ec0: 62 72 3e 57 48 45 52 45 20 63 6f 64 5f 72 65 67 br>WHERE cod_reg
0ed0: 20 3d 20 39 3b 3c 2f 62 3e 0d 0a 3c 2f 74 64 3e = 9;</b>..</td>
0ee0: 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 3c </tr>..</table><
0ef0: 62 72 3e 0d 0a 54 68 69 73 20 53 51 4c 20 71 75 br>..This SQL qu
0f00: 65 72 79 20 77 69 6c 6c 20 72 65 74 75 72 6e 20 ery will return
0f10: 61 20 72 65 67 75 6c 61 72 20 67 72 69 64 20 28 a regular grid (
0f20: 73 71 75 61 72 65 20 63 65 6c 6c 73 29 20 63 6f square cells) co
0f30: 76 65 72 69 6e 67 20 54 75 73 63 61 6e 79 20 28 vering Tuscany (
0f40: 3c 62 3e 63 6f 64 5f 72 65 67 3d 39 3c 2f 62 3e <b>cod_reg=9</b>
0f50: 29 2e 3c 62 72 3e 0d 0a 45 61 63 68 20 67 72 69 ).<br>..Each gri
0f60: 64 27 73 20 63 65 6c 6c 20 77 69 6c 6c 20 68 61 d's cell will ha
0f70: 76 65 20 61 6e 20 65 64 67 65 20 6c 65 6e 67 74 ve an edge lengt
0f80: 68 20 6f 66 20 65 78 61 63 74 6c 79 20 3c 62 3e h of exactly <b>
0f90: 31 30 20 4b 6d 3c 2f 62 3e 0d 0a 3c 2f 74 64 3e 10 Km</b>..</td>
0fa0: 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 ..<td><img borde
0fb0: 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a r="1" src="http:
0fc0: 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 //www.gaia-gis.i
0fd0: 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 t/gaia-sins/writ
0fe0: 65 2d 76 69 65 77 2d 70 69 63 73 2f 73 71 75 61 e-view-pics/squa
0ff0: 72 65 2d 67 72 69 64 2e 70 6e 67 22 20 61 6c 74 re-grid.png" alt
1000: 3d 22 73 71 75 61 72 65 20 67 72 69 64 22 3e 3c ="square grid"><
1010: 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c /td></tr>..<tr><
1020: 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 20 54 td>..<h4>using T
1030: 72 69 61 6e 67 75 6c 61 72 20 63 65 6c 6c 73 3c riangular cells<
1040: 2f 68 34 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 /h4>..<table bgc
1050: 6f 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 olor="#f0f0f0" c
1060: 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 ellspacing="4" c
1070: 65 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d ellpadding="8">.
1080: 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 .<tr><td>..<b>SE
1090: 4c 45 43 54 20 53 54 5f 54 72 69 61 6e 67 75 6c LECT ST_Triangul
10a0: 61 72 47 72 69 64 28 67 65 6f 6d 65 74 72 79 2c arGrid(geometry,
10b0: 20 31 30 30 30 30 29 3c 62 72 3e 0d 0a 46 52 4f 10000)<br>..FRO
10c0: 4d 20 72 65 67 69 6f 6e 73 3c 62 72 3e 57 48 45 M regions<br>WHE
10d0: 52 45 20 63 6f 64 5f 72 65 67 20 3d 20 39 3b 3c RE cod_reg = 9;<
10e0: 2f 62 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d /b>..</td></tr>.
10f0: 0a 3c 2f 74 61 62 6c 65 3e 3c 2f 74 64 3e 0d 0a .</table></td>..
1100: 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d <td><img border=
1110: 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f "1" src="http://
1120: 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f www.gaia-gis.it/
1130: 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d gaia-sins/write-
1140: 76 69 65 77 2d 70 69 63 73 2f 74 72 69 2d 67 72 view-pics/tri-gr
1150: 69 64 2e 70 6e 67 22 20 61 6c 74 3d 22 74 72 69 id.png" alt="tri
1160: 61 6e 67 75 6c 61 72 20 67 72 69 64 22 3e 3c 2f angular grid"></
1170: 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c 74 td></tr>..<tr><t
1180: 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 20 48 65 d>..<h4>using He
1190: 78 61 67 6f 6e 61 6c 20 63 65 6c 6c 73 3c 2f 68 xagonal cells</h
11a0: 34 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c 4>..<table bgcol
11b0: 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 6c or="#f0f0f0" cel
11c0: 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c lspacing="4" cel
11d0: 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c lpadding="8">..<
11e0: 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 4c 45 tr><td>..<b>SELE
11f0: 43 54 20 53 54 5f 48 65 78 61 67 6f 6e 61 6c 47 CT ST_HexagonalG
1200: 72 69 64 28 67 65 6f 6d 65 74 72 79 2c 20 31 30 rid(geometry, 10
1210: 30 30 30 29 3c 62 72 3e 0d 0a 46 52 4f 4d 20 72 000)<br>..FROM r
1220: 65 67 69 6f 6e 73 3c 62 72 3e 57 48 45 52 45 20 egions<br>WHERE
1230: 63 6f 64 5f 72 65 67 20 3d 20 39 3b 3c 2f 62 3e cod_reg = 9;</b>
1240: 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f ..</td></tr>..</
1250: 74 61 62 6c 65 3e 3c 2f 74 64 3e 0d 0a 3c 74 64 table></td>..<td
1260: 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 31 22 ><img border="1"
1270: 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 77 77 src="http://www
1280: 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 61 69 .gaia-gis.it/gai
1290: 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 69 65 a-sins/write-vie
12a0: 77 2d 70 69 63 73 2f 68 65 78 2d 67 72 69 64 2e w-pics/hex-grid.
12b0: 70 6e 67 22 20 61 6c 74 3d 22 68 65 78 61 67 6f png" alt="hexago
12c0: 6e 61 6c 20 67 72 69 64 22 3e 3c 2f 74 64 3e 3c nal grid"></td><
12d0: 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 0d 0a /tr>..</table>..
12e0: 3c 62 72 3e 3c 68 72 3e 0d 0a 3c 68 33 3e 44 65 <br><hr>..<h3>De
12f0: 6c 61 75 6e 61 79 20 54 72 69 61 6e 67 75 6c 61 launay Triangula
1300: 74 69 6f 6e 73 3c 2f 68 33 3e 0d 0a 54 72 69 61 tions</h3>..Tria
1310: 6e 67 75 6c 61 74 69 6f 6e 73 20 73 69 6d 70 6c ngulations simpl
1320: 79 20 72 65 70 72 65 73 65 6e 74 20 61 20 73 70 y represent a sp
1330: 65 63 69 61 6c 20 63 61 73 65 20 6f 66 20 74 65 ecial case of te
1340: 73 73 65 6c 6c 61 74 69 6f 6e 73 3a 20 69 6e 20 ssellations: in
1350: 74 68 69 73 20 63 61 73 65 20 61 6c 6c 20 63 65 this case all ce
1360: 6c 6c 73 20 61 72 65 20 72 65 70 72 65 73 65 6e lls are represen
1370: 74 65 64 20 62 79 20 67 65 6e 65 72 69 63 20 3c ted by generic <
1380: 62 3e 74 72 69 61 6e 67 6c 65 73 3c 2f 62 3e 2c b>triangles</b>,
1390: 20 6e 6f 74 20 6e 65 63 65 73 73 61 72 69 6c 79 not necessarily
13a0: 20 6f 66 20 74 68 65 20 65 71 75 69 6c 61 74 65 of the equilate
13b0: 72 61 6c 20 6b 69 6e 64 2e 3c 62 72 3e 0d 0a 41 ral kind.<br>..A
13c0: 20 3c 62 3e 44 65 6c 61 75 6e 61 79 20 54 72 69 <b>Delaunay Tri
13d0: 61 6e 67 75 6c 61 74 69 6f 6e 3c 2f 62 3e 20 69 angulation</b> i
13e0: 73 20 76 65 72 79 20 70 65 63 75 6c 69 61 72 2c s very peculiar,
13f0: 20 69 6d 70 6f 73 69 6e 67 20 61 20 73 70 65 63 imposing a spec
1400: 69 66 69 63 20 63 6f 6e 73 74 72 61 69 6e 74 2e ific constraint.
1410: 3c 62 72 3e 0d 0a 41 6c 6c 20 74 72 69 61 6e 67 <br>..All triang
1420: 6c 65 73 20 69 6e 20 61 20 44 65 6c 61 75 6e 61 les in a Delauna
1430: 79 20 74 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 y triangulation
1440: 6d 75 73 74 20 73 61 74 69 73 66 79 20 74 68 65 must satisfy the
1450: 20 3c 75 3e 3c 69 3e 65 6d 70 74 79 20 63 69 72 <u><i>empty cir
1460: 63 6c 65 3c 2f 69 3e 3c 2f 75 3e 20 70 72 6f 70 cle</i></u> prop
1470: 65 72 74 79 3a 20 69 2e 65 2e 20 66 6f 72 20 65 erty: i.e. for e
1480: 61 63 68 20 65 64 67 65 20 77 65 20 63 61 6e 20 ach edge we can
1490: 66 69 6e 64 20 61 20 63 69 72 63 6c 65 20 63 6f find a circle co
14a0: 6e 74 61 69 6e 69 6e 67 20 74 68 65 20 65 64 67 ntaining the edg
14b0: 65 27 73 20 65 6e 64 70 6f 69 6e 74 73 20 62 75 e's endpoints bu
14c0: 74 20 6e 6f 74 20 63 6f 6e 74 61 69 6e 69 6e 67 t not containing
14d0: 20 61 6e 79 20 6f 74 68 65 72 20 70 6f 69 6e 74 any other point
14e0: 73 2e 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 s...<a href="htt
14f0: 70 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 p://en.wikipedia
1500: 2e 6f 72 67 2f 77 69 6b 69 2f 44 65 6c 61 75 6e .org/wiki/Delaun
1510: 61 79 5f 74 72 69 61 6e 67 75 6c 61 74 69 6f 6e ay_triangulation
1520: 22 3e 72 65 61 64 20 6d 6f 72 65 3c 2f 61 3e 3c ">read more</a><
1530: 62 72 3e 3c 62 72 3e 0d 0a 43 6f 6d 70 75 74 69 br><br>..Computi
1540: 6e 67 20 61 20 44 65 6c 61 75 6e 61 79 20 54 72 ng a Delaunay Tr
1550: 69 61 6e 67 75 6c 61 74 69 6f 6e 20 72 65 70 72 iangulation repr
1560: 65 73 65 6e 74 69 6e 67 20 6d 61 6e 79 20 70 6f esenting many po
1570: 69 6e 74 73 20 69 73 20 61 20 76 65 72 79 20 63 ints is a very c
1580: 6f 6d 70 6c 65 78 20 6f 70 65 61 74 69 6f 6e 2c omplex opeation,
1590: 20 61 6e 64 20 6f 6e 65 20 70 6f 73 73 69 62 69 and one possibi
15a0: 6c 79 20 69 6d 70 6f 73 69 6e 67 20 61 20 68 75 ly imposing a hu
15b0: 67 65 20 63 6f 6d 70 75 74 61 74 69 6f 6e 61 6c ge computational
15c0: 20 6c 6f 61 64 20 61 6e 64 20 6d 61 79 20 62 65 load and may be
15d0: 20 72 65 71 75 69 72 69 6e 67 20 61 20 6c 6f 6e requiring a lon
15e0: 67 20 74 69 6d 65 2e 0d 0a 48 61 70 70 69 6c 79 g time...Happily
15f0: 20 65 6e 6f 75 67 68 20 6d 61 6e 79 20 68 69 67 enough many hig
1600: 68 6c 79 20 65 66 66 69 63 69 65 6e 74 20 61 6c hly efficient al
1610: 67 68 6f 72 69 74 68 6d 73 20 68 61 76 65 20 62 ghorithms have b
1620: 65 65 6e 20 61 6c 72 65 61 64 79 20 64 65 76 65 een already deve
1630: 6c 6f 70 65 64 20 66 6f 72 20 74 68 65 20 44 61 loped for the Da
1640: 6c 61 75 6e 61 79 20 70 72 6f 62 6c 65 6d 2e 3c launay problem.<
1650: 62 72 3e 0d 0a 54 68 65 20 6e 65 78 74 2d 74 6f br>..The next-to
1660: 2d 63 6f 6d 65 20 3c 61 20 68 72 65 66 3d 22 68 -come <a href="h
1670: 74 74 70 3a 2f 2f 74 72 61 63 2e 6f 73 67 65 6f ttp://trac.osgeo
1680: 2e 6f 72 67 2f 67 65 6f 73 2f 22 3e 47 45 4f 53 .org/geos/">GEOS
1690: 20 33 2e 34 2e 30 3c 2f 61 3e 20 77 69 6c 6c 20 3.4.0</a> will
16a0: 73 75 70 70 6f 72 74 20 44 65 6c 61 75 6e 61 79 support Delaunay
16b0: 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 73 3b Triangulations;
16c0: 20 74 68 69 73 20 47 45 4f 53 20 76 65 72 73 69 this GEOS versi
16d0: 6f 6e 20 69 73 20 63 75 72 72 65 6e 74 6c 79 20 on is currently
16e0: 73 74 69 6c 6c 20 75 6e 64 65 72 20 61 63 74 69 still under acti
16f0: 76 65 20 64 65 76 65 6c 6f 70 6d 65 6e 74 2c 20 ve development,
1700: 62 75 74 20 74 68 65 20 3c 69 3e 65 78 70 65 72 but the <i>exper
1710: 69 6d 65 6e 74 61 6c 3c 2f 69 3e 20 62 61 73 65 imental</i> base
1720: 2d 63 6f 64 65 20 28 3c 69 3e 74 72 75 6e 6b 3c -code (<i>trunk<
1730: 2f 69 3e 29 20 73 65 65 6d 73 20 74 6f 20 62 65 /i>) seems to be
1740: 20 73 74 61 62 6c 65 20 65 6e 6f 75 67 68 20 74 stable enough t
1750: 6f 20 62 65 20 73 61 66 65 6c 79 20 74 65 73 74 o be safely test
1760: 65 64 2e 0d 0a 53 70 61 74 69 61 4c 69 74 65 20 ed...SpatiaLite
1770: 61 6c 72 65 61 64 79 20 72 65 6c 69 65 73 20 6f already relies o
1780: 6e 20 47 45 4f 53 20 66 6f 72 20 6d 61 6e 79 20 n GEOS for many
1790: 74 61 73 6b 73 2c 20 73 6f 20 69 6e 74 65 67 72 tasks, so integr
17a0: 61 74 69 6e 67 20 61 20 73 6d 6f 6f 74 68 20 73 ating a smooth s
17b0: 75 70 70 6f 72 74 20 66 6f 72 20 44 65 6c 61 75 upport for Delau
17c0: 6e 61 79 20 54 72 69 61 6e 67 75 6c 61 74 69 6f nay Triangulatio
17d0: 6e 20 61 73 20 77 65 6c 6c 20 77 61 73 6e 27 74 n as well wasn't
17e0: 20 61 74 20 61 6c 6c 20 64 69 66 66 69 63 75 6c at all difficul
17f0: 74 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 3c 74 61 62 t.<br><br>..<tab
1800: 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 30 66 le bgcolor="#f0f
1810: 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 6e 67 0f0" cellspacing
1820: 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 ="4" cellpadding
1830: 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d ="8">..<tr><td>.
1840: 0a 3c 69 3e 70 72 6f 74 6f 74 79 70 65 3c 2f 69 .<i>prototype</i
1850: 3e 3a 3c 68 72 3e 0d 0a 53 54 5f 44 65 6c 61 75 >:<hr>..ST_Delau
1860: 6e 61 79 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e nayTriangulation
1870: 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 ( input <i>Geome
1880: 74 72 79 3c 2f 69 3e 20 29 20 3a 20 64 65 6c 61 try</i> ) : dela
1890: 75 6e 61 79 20 3c 69 3e 47 65 6f 6d 65 74 72 79 unay <i>Geometry
18a0: 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 44 65 6c </i><br>..ST_Del
18b0: 61 75 6e 61 79 54 72 69 61 6e 67 75 6c 61 74 69 aunayTriangulati
18c0: 6f 6e 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f on( input <i>Geo
18d0: 6d 65 74 72 79 3c 2f 69 3e 2c 20 65 64 67 65 73 metry</i>, edges
18e0: 5f 6f 6e 6c 79 20 3c 69 3e 62 6f 6f 6c 65 61 6e _only <i>boolean
18f0: 3c 2f 69 3e 20 29 20 3a 20 64 65 6c 61 75 6e 61 </i> ) : delauna
1900: 79 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 y <i>Geometry</i
1910: 3e 3c 62 72 3e 0d 0a 53 54 5f 44 65 6c 61 75 6e ><br>..ST_Delaun
1920: 61 79 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 28 ayTriangulation(
1930: 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 input <i>Geomet
1940: 72 79 3c 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e ry</i>, edges_on
1950: 6c 79 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 ly <i>boolean</i
1960: 3e 2c 20 74 6f 6c 65 72 61 6e 63 65 20 3c 69 3e >, tolerance <i>
1970: 64 6f 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e double precision
1980: 3c 2f 69 3e 20 29 20 3a 20 64 65 6c 61 75 6e 61 </i> ) : delauna
1990: 79 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 y <i>Geometry</i
19a0: 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 >..</td></tr></t
19b0: 61 62 6c 65 3e 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 able>..<ul>..<li
19c0: 3e 74 68 65 20 3c 62 3e 69 6e 70 75 74 3c 2f 62 >the <b>input</b
19d0: 3e 20 47 65 6f 6d 65 74 72 79 20 63 61 6e 20 62 > Geometry can b
19e0: 65 20 6f 66 20 61 62 73 6f 6c 75 74 65 6c 79 20 e of absolutely
19f0: 61 72 62 69 74 72 61 72 79 20 74 79 70 65 3b 20 arbitrary type;
1a00: 61 6c 6c 20 4c 69 6e 65 73 74 72 69 6e 67 73 20 all Linestrings
1a10: 61 6e 64 20 2f 20 6f 72 20 50 6f 6c 79 67 6f 77 and / or Polygow
1a20: 6e 73 20 77 69 6c 6c 20 65 76 65 6e 74 75 61 6c ns will eventual
1a30: 6c 79 20 62 65 20 64 69 73 73 6f 6c 76 65 64 20 ly be dissolved
1a40: 69 6e 74 6f 20 50 6f 69 6e 74 73 20 63 6f 72 72 into Points corr
1a50: 65 73 70 6f 6e 64 69 6e 67 20 74 6f 20 76 65 72 esponding to ver
1a60: 74 69 63 65 73 2e 3c 62 72 3e 0d 0a 53 6f 20 61 tices.<br>..So a
1a70: 66 74 65 72 20 61 6c 6c 20 53 54 5f 44 65 6c 61 fter all ST_Dela
1a80: 75 6e 61 79 54 72 69 61 6e 67 75 6c 61 74 69 6f unayTriangulatio
1a90: 6e 28 29 20 77 69 6c 6c 20 61 6c 77 61 79 73 20 n() will always
1aa0: 70 72 6f 63 65 73 73 20 61 20 4d 75 6c 74 69 50 process a MultiP
1ab0: 6f 69 6e 74 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e oint.</li>..<li>
1ac0: 74 68 65 20 66 61 63 75 6c 74 61 74 69 76 65 20 the facultative
1ad0: 3c 62 3e 65 64 67 65 73 5f 6f 6e 6c 79 3c 2f 62 <b>edges_only</b
1ae0: 3e 20 61 72 67 75 6d 65 6e 74 20 77 69 6c 6c 20 > argument will
1af0: 62 65 20 69 6e 74 65 72 70 72 65 74 65 64 20 61 be interpreted a
1b00: 73 20 66 6f 6c 6c 6f 77 73 3a 3c 75 6c 3e 0d 0a s follows:<ul>..
1b10: 3c 6c 69 3e 69 66 20 3c 62 3e 46 41 4c 53 45 3c <li>if <b>FALSE<
1b20: 2f 62 3e 20 28 3c 69 3e 64 65 66 61 75 6c 74 20 /b> (<i>default
1b30: 76 61 6c 75 65 3c 2f 69 3e 29 20 61 20 4d 75 6c value</i>) a Mul
1b40: 74 69 50 6f 6c 79 67 6f 6e 20 77 69 6c 6c 20 62 tiPolygon will b
1b50: 65 20 72 65 74 75 72 6e 65 64 2e 3c 2f 6c 69 3e e returned.</li>
1b60: 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 54 52 55 45 ..<li>if <b>TRUE
1b70: 3c 2f 62 3e 20 61 20 4d 75 6c 74 69 4c 69 6e 65 </b> a MultiLine
1b80: 73 74 72 69 6e 67 20 77 69 6c 6c 20 62 65 20 72 string will be r
1b90: 65 74 75 72 6e 65 64 20 28 73 69 6d 70 6c 79 20 eturned (simply
1ba0: 72 65 70 72 65 73 65 6e 74 69 6e 67 20 74 68 65 representing the
1bb0: 20 74 72 69 61 6e 67 6c 65 73 20 65 64 67 65 73 triangles edges
1bc0: 29 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f ).</li>..</ul></
1bd0: 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 66 61 63 li>..<li>the fac
1be0: 75 6c 74 61 74 69 76 65 20 3c 62 3e 74 6f 6c 65 ultative <b>tole
1bf0: 72 61 6e 63 65 3c 2f 62 3e 20 61 72 67 75 6d 65 rance</b> argume
1c00: 6e 74 20 69 73 20 69 6e 74 65 6e 64 65 64 20 74 nt is intended t
1c10: 6f 20 6e 6f 72 6d 61 6c 69 7a 65 20 74 68 65 20 o normalize the
1c20: 69 6e 70 75 74 20 70 6f 69 6e 74 2d 73 65 74 2c input point-set,
1c30: 20 73 75 70 70 72 65 73 73 69 6e 67 20 72 65 70 suppressing rep
1c40: 65 61 74 65 64 20 28 6f 72 20 74 6f 6f 20 6d 75 eated (or too mu
1c50: 63 68 20 63 6c 6f 73 65 29 20 70 6f 69 6e 74 73 ch close) points
1c60: 2e 3c 62 72 3e 0d 0a 42 79 20 64 65 66 61 75 6c .<br>..By defaul
1c70: 74 20 61 20 3c 62 3e 30 2e 30 3c 2f 62 3e 20 74 t a <b>0.0</b> t
1c80: 6f 6c 65 72 61 6e 63 65 20 77 69 6c 6c 20 62 65 olerance will be
1c90: 20 61 73 73 75 6d 65 64 2e 3c 2f 6c 69 3e 0d 0a assumed.</li>..
1ca0: 3c 2f 75 6c 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 3c </ul></td></tr><
1cb0: 2f 74 61 62 6c 65 3e 0d 0a 3c 74 61 62 6c 65 20 /table>..<table
1cc0: 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 cellspacing="4"
1cd0: 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 34 22 3e cellpadding="4">
1ce0: 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 74 61 62 ..<tr><td>..<tab
1cf0: 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 30 66 le bgcolor="#f0f
1d00: 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 6e 67 0f0" cellspacing
1d10: 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 ="4" cellpadding
1d20: 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d ="8">..<tr><td>.
1d30: 0a 3c 62 3e 53 45 4c 45 43 54 20 53 54 5f 44 65 .<b>SELECT ST_De
1d40: 6c 61 75 6e 61 79 54 72 69 61 6e 67 75 6c 61 74 launayTriangulat
1d50: 69 6f 6e 28 53 54 5f 43 6f 6c 6c 65 63 74 28 67 ion(ST_Collect(g
1d60: 65 6f 6d 65 74 72 79 29 29 3c 62 72 3e 0d 0a 46 eometry))<br>..F
1d70: 52 4f 4d 20 69 74 61 6c 79 5f 70 6f 70 75 6c 61 ROM italy_popula
1d80: 74 65 64 5f 70 6c 61 63 65 73 3b 3c 2f 62 3e 0d ted_places;</b>.
1d90: 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 .</td></tr>..</t
1da0: 61 62 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 able><br>..This
1db0: 53 51 4c 20 71 75 65 72 79 20 77 69 6c 6c 20 72 SQL query will r
1dc0: 65 74 75 72 6e 20 61 20 44 65 6c 61 75 6e 61 79 eturn a Delaunay
1dd0: 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 62 Triangulation b
1de0: 61 73 65 64 20 6f 6e 20 49 74 61 6c 79 27 73 20 ased on Italy's
1df0: 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 73 populated places
1e00: 20 28 61 62 6f 75 74 20 38 2c 30 30 30 2b 20 50 (about 8,000+ P
1e10: 6f 69 6e 74 73 29 2e 3c 62 72 3e 0d 0a 54 68 65 oints).<br>..The
1e20: 20 76 69 73 75 61 6c 20 65 78 61 6d 70 6c 65 20 visual example
1e30: 73 69 6d 70 6c 79 20 63 6f 76 65 72 73 20 54 75 simply covers Tu
1e40: 73 63 61 6e 79 2c 20 73 6f 20 74 68 65 20 65 6e scany, so the en
1e50: 73 75 72 65 20 61 6e 20 65 61 73 79 20 72 65 61 sure an easy rea
1e60: 64 69 62 69 6c 69 74 79 2e 20 0d 0a 3c 2f 74 64 dibility. ..</td
1e70: 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 >..<td><img bord
1e80: 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 er="1" src="http
1e90: 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e ://www.gaia-gis.
1ea0: 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 it/gaia-sins/wri
1eb0: 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 64 65 6c te-view-pics/del
1ec0: 61 75 6e 61 79 2e 70 6e 67 22 20 61 6c 74 3d 22 aunay.png" alt="
1ed0: 64 65 6c 61 75 6e 61 79 20 74 72 69 61 6e 67 75 delaunay triangu
1ee0: 6c 61 74 69 6f 6e 22 3e 3c 2f 74 64 3e 3c 2f 74 lation"></td></t
1ef0: 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 62 r>..</table>..<b
1f00: 72 3e 3c 68 72 3e 0d 0a 3c 68 33 3e 56 6f 72 6f r><hr>..<h3>Voro
1f10: 6e 6f 6a 20 44 69 61 67 72 61 6d 73 3c 2f 68 33 noj Diagrams</h3
1f20: 3e 0d 0a 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 >..<table cellsp
1f30: 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 acing="4" cellpa
1f40: 64 64 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e dding="4">..<tr>
1f50: 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d <td><img border=
1f60: 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f "1" src="http://
1f70: 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f www.gaia-gis.it/
1f80: 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d gaia-sins/write-
1f90: 76 69 65 77 2d 70 69 63 73 2f 76 6f 72 6f 6e 6f view-pics/vorono
1fa0: 6a 2d 31 2e 70 6e 67 22 20 61 6c 74 3d 22 76 6f j-1.png" alt="vo
1fb0: 72 6f 6e 6f 6a 2d 64 65 61 6c 61 75 6e 61 79 20 ronoj-dealaunay
1fc0: 72 65 6c 61 74 69 6f 6e 73 68 69 70 22 3e 0d 0a relationship">..
1fd0: 3c 2f 74 64 3e 3c 74 64 3e 0d 0a 54 68 65 20 3c </td><td>..The <
1fe0: 62 3e 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 61 b>Voronoj Diagra
1ff0: 6d 3c 2f 62 3e 20 73 69 6d 70 6c 79 20 69 73 20 m</b> simply is
2000: 74 68 65 20 3c 69 3e 3c 75 3e 64 75 61 6c 20 67 the <i><u>dual g
2010: 72 61 70 68 3c 2f 75 3e 3c 2f 69 3e 20 6f 66 20 raph</u></i> of
2020: 74 68 65 20 3c 62 3e 44 65 6c 61 75 6e 61 79 20 the <b>Delaunay
2030: 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 3c 2f 62 Triangulation</b
2040: 3e 2e 0d 0a 41 20 56 6f 72 6f 6e 6f 6a 20 44 69 >...A Voronoj Di
2050: 61 67 72 61 6d 20 73 74 69 6c 6c 20 69 73 20 61 agram still is a
2060: 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 2c 20 61 tessellation, a
2070: 6e 64 20 63 65 6c 6c 73 20 69 6e 20 61 20 56 6f nd cells in a Vo
2080: 72 6f 6e 6f 6a 20 63 61 6e 20 68 61 76 65 20 61 ronoj can have a
2090: 6e 79 20 61 72 62 69 74 72 61 72 79 20 70 6f 6c ny arbitrary pol
20a0: 79 67 6f 6e 61 6c 20 28 69 72 72 65 67 75 6c 61 ygonal (irregula
20b0: 72 29 20 73 68 61 70 65 2e 3c 62 72 3e 3c 62 72 r) shape.<br><br
20c0: 3e 0d 0a 54 68 69 73 20 66 69 67 75 72 65 20 63 >..This figure c
20d0: 6c 65 61 72 6c 79 20 73 68 6f 77 73 20 74 68 65 learly shows the
20e0: 20 72 65 6c 61 74 69 6f 6e 20 6a 6f 69 6e 69 6e relation joinin
20f0: 67 20 74 68 65 20 44 65 6c 61 75 6e 61 79 20 54 g the Delaunay T
2100: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 61 6e 64 riangulation and
2110: 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 the correspondi
2120: 6e 67 20 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 ng Voronoj Diagr
2130: 61 6d 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 45 61 63 am.<br><br>..Eac
2140: 68 20 73 69 6e 67 6c 65 20 56 6f 72 6f 6e 6f 6a h single Voronoj
2150: 27 73 20 63 65 6c 6c 20 69 73 20 6f 62 74 61 69 's cell is obtai
2160: 6e 65 64 20 62 79 20 63 6f 6e 6e 65 63 74 69 6e ned by connectin
2170: 67 20 61 6c 6c 20 74 68 65 20 3c 69 3e 63 69 72 g all the <i>cir
2180: 63 75 6d 63 65 6e 74 65 72 73 3c 2f 69 3e 20 6f cumcenters</i> o
2190: 66 20 61 64 6a 61 63 65 6e 74 20 44 65 6c 61 75 f adjacent Delau
21a0: 6e 61 79 27 73 20 74 72 69 61 6e 67 6c 65 73 3b nay's triangles;
21b0: 20 63 6f 6e 73 65 71 75 65 6e 74 6c 79 20 65 61 consequently ea
21c0: 63 68 20 56 6f 72 6f 6e 6f 6a 20 63 65 6c 6c 20 ch Voronoj cell
21d0: 73 75 72 65 6c 79 20 63 6f 6e 74 61 69 6e 73 20 surely contains
21e0: 6f 6e 65 20 28 61 6e 64 20 6f 6e 6c 79 20 6f 6e one (and only on
21f0: 65 29 20 44 65 6c 61 75 6e 61 79 27 73 20 6e 6f e) Delaunay's no
2200: 64 65 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 65 de.<br><br>..The
2210: 20 63 65 6c 6c 20 69 6e 20 74 68 65 20 56 6f 72 cell in the Vor
2220: 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 20 70 72 65 onoj Diagram pre
2230: 73 65 6e 74 73 20 61 6e 20 69 6e 74 65 72 65 73 sents an interes
2240: 74 69 6e 67 20 70 72 6f 70 65 72 74 79 3a 20 61 ting property: a
2250: 6c 6c 20 70 6f 69 6e 74 73 20 66 61 6c 6c 69 6e ll points fallin
2260: 67 20 77 69 74 68 69 6e 20 74 68 65 20 73 61 6d g within the sam
2270: 65 20 63 65 6c 6c 20 61 72 65 20 65 6e 73 75 72 e cell are ensur
2280: 65 64 20 74 6f 20 62 65 20 6e 65 61 72 65 73 74 ed to be nearest
2290: 20 74 6f 20 74 68 65 20 44 65 6c 61 75 6e 61 79 to the Delaunay
22a0: 27 73 20 6e 6f 64 65 20 70 6c 61 63 65 64 20 6f 's node placed o
22b0: 6e 20 74 68 65 20 63 65 6c 6c 20 69 74 73 65 6c n the cell itsel
22c0: 66 20 74 68 61 6e 20 74 6f 20 61 6e 79 20 6f 74 f than to any ot
22d0: 68 65 72 20 44 65 6c 61 75 6e 61 79 27 73 20 6e her Delaunay's n
22e0: 6f 64 65 20 70 6c 61 63 65 64 20 69 6e 20 61 20 ode placed in a
22f0: 64 69 66 66 65 72 65 6e 74 20 63 65 6c 6c 2e 3c different cell.<
2300: 62 72 3e 0d 0a 53 6f 20 74 68 65 20 56 6f 72 6f br>..So the Voro
2310: 6e 6f 6a 20 44 69 61 67 72 61 6d 20 69 73 20 61 noj Diagram is a
2320: 20 76 65 72 79 20 65 66 66 65 63 74 69 76 65 20 very effective
2330: 63 6f 6e 63 65 70 74 75 61 6c 20 74 6f 6f 6c 20 conceptual tool
2340: 61 6c 6c 6f 77 69 6e 67 20 74 6f 20 64 69 76 69 allowing to divi
2350: 64 65 20 61 6e 20 61 72 62 69 74 72 61 72 79 20 de an arbitrary
2360: 73 70 61 63 65 20 72 65 67 69 6f 6e 20 69 6e 20 space region in
2370: 6d 61 6e 79 20 3c 69 3e 72 61 74 69 6f 6e 61 6c many <i>rational
2380: 3c 2f 69 3e 20 63 65 6c 6c 73 2c 20 61 6e 64 20 </i> cells, and
2390: 69 73 20 74 68 75 73 20 77 69 64 65 6c 79 20 75 is thus widely u
23a0: 73 75 65 64 20 6f 6e 20 6d 61 6e 79 20 61 70 70 sued on many app
23b0: 6c 69 63 61 74 69 76 65 20 66 69 65 6c 64 73 2e licative fields.
23c0: 3c 62 72 3e 0d 0a 54 68 69 73 20 69 6e 63 6c 75 <br>..This inclu
23d0: 64 69 6e 67 20 47 65 6f 67 72 61 70 68 79 2c 20 ding Geography,
23e0: 6f 62 76 69 6f 75 73 6c 79 2e 3c 62 72 3e 3c 62 obviously.<br><b
23f0: 72 3e 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 r>..<a href="htt
2400: 70 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 p://en.wikipedia
2410: 2e 6f 72 67 2f 77 69 6b 69 2f 56 6f 72 6f 6e 6f .org/wiki/Vorono
2420: 69 5f 74 65 73 73 65 6c 6c 61 74 69 6f 6e 22 3e i_tessellation">
2430: 72 65 61 64 20 6d 6f 72 65 3c 2f 61 3e 0d 0a 3c read more</a>..<
2440: 62 72 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 br></td></tr></t
2450: 61 62 6c 65 3e 0d 0a 3c 61 20 68 72 65 66 3d 22 able>..<a href="
2460: 68 74 74 70 3a 2f 2f 74 72 61 63 2e 6f 73 67 65 http://trac.osge
2470: 6f 2e 6f 72 67 2f 67 65 6f 73 2f 22 3e 47 45 4f o.org/geos/">GEO
2480: 53 20 33 2e 34 2e 30 3c 2f 61 3e 20 77 69 6c 6c S 3.4.0</a> will
2490: 20 6e 6f 74 20 73 75 70 70 6f 72 74 20 56 6f 72 not support Vor
24a0: 6f 6e 6f 6a 3b 20 73 6f 20 74 68 65 20 53 70 61 onoj; so the Spa
24b0: 74 69 61 4c 69 74 65 20 6f 77 6e 20 73 75 70 70 tiaLite own supp
24c0: 6f 72 74 20 69 73 20 62 61 73 65 64 20 6f 6e 20 ort is based on
24d0: 61 6e 20 6f 72 69 67 69 6e 61 6c 20 69 6d 70 6c an original impl
24e0: 65 6d 65 6e 74 61 74 69 6f 6e 20 28 62 61 73 65 ementation (base
24f0: 64 20 69 6e 20 74 75 72 6e 20 6f 6e 20 74 68 65 d in turn on the
2500: 20 44 65 6c 61 75 6e 61 79 20 73 75 70 70 6f 72 Delaunay suppor
2510: 74 20 6d 61 64 65 20 61 76 61 69 6c 61 62 6c 65 t made available
2520: 20 62 79 20 47 45 4f 53 29 2e 3c 62 72 3e 3c 62 by GEOS).<br><b
2530: 72 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c r>..<table bgcol
2540: 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 6c or="#f0f0f0" cel
2550: 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c lspacing="4" cel
2560: 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c lpadding="8">..<
2570: 74 72 3e 3c 74 64 3e 0d 0a 3c 69 3e 70 72 6f 74 tr><td>..<i>prot
2580: 6f 74 79 70 65 3c 2f 69 3e 3a 3c 68 72 3e 0d 0a otype</i>:<hr>..
2590: 53 54 5f 56 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 ST_VoronojDiagra
25a0: 6d 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d m( input <i>Geom
25b0: 65 74 72 79 3c 2f 69 3e 20 29 20 3a 20 76 6f 72 etry</i> ) : vor
25c0: 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 74 72 79 onoj <i>Geometry
25d0: 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 56 6f 72 </i><br>..ST_Vor
25e0: 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 20 69 6e 70 onojDiagram( inp
25f0: 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f ut <i>Geometry</
2600: 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c i>, edges_only <
2610: 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 29 20 i>boolean</i> )
2620: 3a 20 76 6f 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f : voronoj <i>Geo
2630: 6d 65 74 72 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 metry</i><br>..S
2640: 54 5f 56 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 6d T_VoronojDiagram
2650: 6e 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d n( input <i>Geom
2660: 65 74 72 79 3c 2f 69 3e 2c 20 65 64 67 65 73 5f etry</i>, edges_
2670: 6f 6e 6c 79 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c only <i>boolean<
2680: 2f 69 3e 2c 20 65 78 74 72 61 5f 66 72 61 6d 65 /i>, extra_frame
2690: 5f 73 69 7a 65 20 3c 69 3e 64 6f 75 62 6c 65 20 _size <i>double
26a0: 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 precision</i> )
26b0: 3a 20 76 6f 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f : voronoj <i>Geo
26c0: 6d 65 74 72 79 3c 2f 69 3e 0d 0a 53 54 5f 56 6f metry</i>..ST_Vo
26d0: 72 6f 6e 6f 6a 44 69 61 67 72 61 6d 6e 28 20 69 ronojDiagramn( i
26e0: 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 nput <i>Geometry
26f0: 3c 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 </i>, edges_only
2700: 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c <i>boolean</i>,
2710: 20 65 78 74 72 61 5f 66 72 61 6d 65 5f 73 69 7a extra_frame_siz
2720: 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 e <i>double prec
2730: 69 73 69 6f 6e 3c 2f 69 3e 2c 20 74 6f 6c 65 72 ision</i>, toler
2740: 61 6e 63 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 ance <i>double p
2750: 72 65 63 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 3a recision</i> ) :
2760: 20 76 6f 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d voronoj <i>Geom
2770: 65 74 72 79 3c 2f 69 3e 0d 0a 3c 2f 74 64 3e 3c etry</i>..</td><
2780: 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 75 /tr></table>..<u
2790: 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 20 3c 62 3e 69 l>..<li>the <b>i
27a0: 6e 70 75 74 3c 2f 62 3e 20 47 65 6f 6d 65 74 72 nput</b> Geometr
27b0: 79 20 63 61 6e 20 62 65 20 6f 66 20 61 62 73 6f y can be of abso
27c0: 6c 75 74 65 6c 79 20 61 72 62 69 74 72 61 72 79 lutely arbitrary
27d0: 20 74 79 70 65 3b 20 61 6c 6c 20 4c 69 6e 65 73 type; all Lines
27e0: 74 72 69 6e 67 73 20 61 6e 64 20 2f 20 6f 72 20 trings and / or
27f0: 50 6f 6c 79 67 6f 77 6e 73 20 77 69 6c 6c 20 65 Polygowns will e
2800: 76 65 6e 74 75 61 6c 6c 79 20 62 65 20 64 69 73 ventually be dis
2810: 73 6f 6c 76 65 64 20 69 6e 74 6f 20 50 6f 69 6e solved into Poin
2820: 74 73 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 ts corresponding
2830: 20 74 6f 20 76 65 72 74 69 63 65 73 2e 3c 62 72 to vertices.<br
2840: 3e 0d 0a 53 6f 20 61 66 74 65 72 20 61 6c 6c 20 >..So after all
2850: 53 54 5f 56 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 ST_VoronojDiagra
2860: 6d 28 29 20 28 65 78 61 63 74 6c 79 20 61 73 20 m() (exactly as
2870: 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 69 61 6e ST_DelaunayTrian
2880: 67 75 6c 61 74 69 6f 6e 29 20 77 69 6c 6c 20 61 gulation) will a
2890: 6c 77 61 79 73 20 70 72 6f 63 65 73 73 20 61 20 lways process a
28a0: 4d 75 6c 74 69 50 6f 69 6e 74 2e 3c 2f 6c 69 3e MultiPoint.</li>
28b0: 0d 0a 3c 6c 69 3e 74 68 65 20 66 61 63 75 6c 74 ..<li>the facult
28c0: 61 74 69 76 65 20 3c 62 3e 65 64 67 65 73 5f 6f ative <b>edges_o
28d0: 6e 6c 79 3c 2f 62 3e 20 61 72 67 75 6d 65 6e 74 nly</b> argument
28e0: 20 77 69 6c 6c 20 62 65 20 69 6e 74 65 72 70 72 will be interpr
28f0: 65 74 65 64 20 61 73 20 66 6f 6c 6c 6f 77 73 3a eted as follows:
2900: 3c 75 6c 3e 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e <ul>..<li>if <b>
2910: 46 41 4c 53 45 3c 2f 62 3e 20 28 3c 69 3e 64 65 FALSE</b> (<i>de
2920: 66 61 75 6c 74 20 76 61 6c 75 65 3c 2f 69 3e 29 fault value</i>)
2930: 20 61 20 4d 75 6c 74 69 50 6f 6c 79 67 6f 6e 20 a MultiPolygon
2940: 77 69 6c 6c 20 62 65 20 72 65 74 75 72 6e 65 64 will be returned
2950: 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 69 66 20 3c .</li>..<li>if <
2960: 62 3e 54 52 55 45 3c 2f 62 3e 20 61 20 4d 75 6c b>TRUE</b> a Mul
2970: 74 69 4c 69 6e 65 73 74 72 69 6e 67 20 77 69 6c tiLinestring wil
2980: 6c 20 62 65 20 72 65 74 75 72 6e 65 64 20 28 73 l be returned (s
2990: 69 6d 70 6c 79 20 72 65 70 72 65 73 65 6e 74 69 imply representi
29a0: 6e 67 20 74 68 65 20 74 72 69 61 6e 67 6c 65 73 ng the triangles
29b0: 20 65 64 67 65 73 29 2e 3c 2f 6c 69 3e 0d 0a 3c edges).</li>..<
29c0: 2f 75 6c 3e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 /ul></li>..<li>t
29d0: 68 65 20 66 61 63 75 6c 74 61 74 69 76 65 20 3c he facultative <
29e0: 62 3e 65 78 74 72 61 5f 66 72 61 6d 65 5f 73 69 b>extra_frame_si
29f0: 7a 65 3c 2f 62 3e 20 78 78 78 78 78 78 0d 0a 3c ze</b> xxxxxx..<
2a00: 6c 69 3e 74 68 65 20 66 61 63 75 6c 74 61 74 69 li>the facultati
2a10: 76 65 20 3c 62 3e 74 6f 6c 65 72 61 6e 63 65 3c ve <b>tolerance<
2a20: 2f 62 3e 20 61 72 67 75 6d 65 6e 74 20 69 73 20 /b> argument is
2a30: 69 6e 74 65 6e 64 65 64 20 74 6f 20 6e 6f 72 6d intended to norm
2a40: 61 6c 69 7a 65 20 74 68 65 20 69 6e 70 75 74 20 alize the input
2a50: 70 6f 69 6e 74 2d 73 65 74 2c 20 73 75 70 70 72 point-set, suppr
2a60: 65 73 73 69 6e 67 20 72 65 70 65 61 74 65 64 20 essing repeated
2a70: 70 6f 69 6e 74 73 20 28 73 69 6d 70 6c 79 20 75 points (simply u
2a80: 73 65 64 20 77 68 65 6e 20 69 6e 74 65 72 6e 61 sed when interna
2a90: 6c 6c 79 20 63 6f 6d 70 75 74 69 6e 67 20 74 68 lly computing th
2aa0: 65 20 44 65 6c 61 75 6e 61 79 20 54 72 69 61 6e e Delaunay Trian
2ab0: 67 75 6c 61 74 69 6f 6e 29 2e 3c 62 72 3e 0d 0a gulation).<br>..
2ac0: 42 79 20 64 65 66 61 75 6c 74 20 61 20 3c 62 3e By default a <b>
2ad0: 30 2e 30 3c 2f 62 3e 20 74 6f 6c 65 72 61 6e 63 0.0</b> toleranc
2ae0: 65 20 77 69 6c 6c 20 62 65 20 61 73 73 75 6d 65 e will be assume
2af0: 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f d.</li>..</ul></
2b00: 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e td></tr></table>
2b10: 0d 0a 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 ..<table cellspa
2b20: 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 cing="4" cellpad
2b30: 64 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c ding="4">..<tr><
2b40: 74 64 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f td>..<table bgco
2b50: 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 lor="#f0f0f0" ce
2b60: 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 llspacing="4" ce
2b70: 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a llpadding="8">..
2b80: 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 4c <tr><td>..<b>SEL
2b90: 45 43 54 20 53 54 5f 56 6f 72 6f 6e 6f 6a 44 69 ECT ST_VoronojDi
2ba0: 61 67 6d 61 28 53 54 5f 43 6f 6c 6c 65 63 74 28 agma(ST_Collect(
2bb0: 67 65 6f 6d 65 74 72 79 29 29 3c 62 72 3e 0d 0a geometry))<br>..
2bc0: 46 52 4f 4d 20 69 74 61 6c 79 5f 70 6f 70 75 6c FROM italy_popul
2bd0: 61 74 65 64 5f 70 6c 61 63 65 73 3b 3c 2f 62 3e ated_places;</b>
2be0: 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f ..</td></tr>..</
2bf0: 74 61 62 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 73 table><br>..This
2c00: 20 53 51 4c 20 71 75 65 72 79 20 77 69 6c 6c 20 SQL query will
2c10: 72 65 74 75 72 6e 20 61 20 56 6f 72 6f 6e 6f 6a return a Voronoj
2c20: 20 44 69 61 67 72 61 6d 20 62 61 73 65 64 20 6f Diagram based o
2c30: 6e 20 49 74 61 6c 79 27 73 20 70 6f 70 75 6c 61 n Italy's popula
2c40: 74 65 64 20 70 6c 61 63 65 73 20 28 61 62 6f 75 ted places (abou
2c50: 74 20 38 2c 30 30 30 2b 20 50 6f 69 6e 74 73 29 t 8,000+ Points)
2c60: 2e 3c 62 72 3e 0d 0a 54 68 65 20 76 69 73 75 61 .<br>..The visua
2c70: 6c 20 65 78 61 6d 70 6c 65 20 73 69 6d 70 6c 79 l example simply
2c80: 20 63 6f 76 65 72 73 20 54 75 73 63 61 6e 79 2c covers Tuscany,
2c90: 20 73 6f 20 74 68 65 20 65 6e 73 75 72 65 20 61 so the ensure a
2ca0: 6e 20 65 61 73 79 20 72 65 61 64 69 62 69 6c 69 n easy readibili
2cb0: 74 79 2e 3c 62 72 3e 0d 0a 41 6c 6c 20 3c 69 3e ty.<br>..All <i>
2cc0: 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 73 populated places
2cd0: 3c 2f 69 3e 20 28 61 6b 61 20 63 65 6c 6c 27 73 </i> (aka cell's
2ce0: 20 73 65 65 64 73 29 20 61 72 65 20 65 78 70 6c seeds) are expl
2cf0: 69 63 69 74 6c 79 20 72 65 70 72 65 73 65 6e 74 icitly represent
2d00: 65 64 2e 20 0d 0a 3c 2f 74 64 3e 0d 0a 3c 74 64 ed. ..</td>..<td
2d10: 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 31 22 ><img border="1"
2d20: 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 77 77 src="http://www
2d30: 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 61 69 .gaia-gis.it/gai
2d40: 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 69 65 a-sins/write-vie
2d50: 77 2d 70 69 63 73 2f 76 6f 72 6f 6e 6f 6a 2d 32 w-pics/voronoj-2
2d60: 2e 70 6e 67 22 20 61 6c 74 3d 22 76 6f 72 6f 6e .png" alt="voron
2d70: 6f 6a 20 64 69 61 67 72 61 6d 22 3e 3c 2f 74 64 oj diagram"></td
2d80: 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e ></tr>..</table>
2d90: 0d 0a 3c 62 72 3e 3c 68 72 3e 0d 0a 42 61 63 6b ..<br><hr>..Back
2da0: 20 74 6f 20 3c 61 20 68 72 65 66 3d 22 68 74 74 to <a href="htt
2db0: 70 73 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 ps://www.gaia-gi
2dc0: 73 2e 69 74 2f 66 6f 73 73 69 6c 2f 6c 69 62 73 s.it/fossil/libs
2dd0: 70 61 74 69 61 6c 69 74 65 2f 77 69 6b 69 3f 6e patialite/wiki?n
2de0: 61 6d 65 3d 73 77 69 74 63 68 69 6e 67 2d 74 6f ame=switching-to
2df0: 2d 34 2e 30 23 74 65 73 73 65 6c 61 74 69 6f 6e -4.0#tesselation
2e00: 22 3e 6d 61 69 6e 20 70 61 67 65 3c 2f 61 3e 0d ">main page</a>.
2e10: 0a 0d 0a 0a 5a 20 31 65 64 39 66 34 66 62 37 35 ....Z 1ed9f4fb75
2e20: 65 62 31 33 63 36 64 64 30 66 33 63 38 64 65 63 eb13c6dd0f3c8dec
2e30: 30 31 62 64 38 63 0a 01bd8c.