0000: 44 20 32 30 31 32 2d 30 38 2d 33 30 54 31 33 3a D 2012-08-30T13:
0010: 33 31 3a 33 36 2e 31 31 31 0a 4c 20 74 65 73 73 31:36.111.L tess
0020: 65 6c 61 74 69 6f 6e 73 2d 34 2e 30 0a 50 20 34 elations-4.0.P 4
0030: 36 37 61 65 30 33 63 38 66 63 65 61 61 30 32 38 67ae03c8fceaa028
0040: 64 61 62 34 37 39 36 63 30 64 37 30 30 64 65 65 dab4796c0d700dee
0050: 38 33 39 31 37 64 66 0a 55 20 73 61 6e 64 72 6f 83917df.U sandro
0060: 0a 57 20 32 30 31 33 30 0a 3c 68 32 3e 54 65 73 .W 20130.<h2>Tes
0070: 73 65 6c 6c 61 74 69 6f 6e 2d 72 65 6c 61 74 65 sellation-relate
0080: 64 20 53 51 4c 20 66 75 6e 63 74 69 6f 6e 73 20 d SQL functions
0090: 73 75 70 70 6f 72 74 65 64 20 69 6e 20 76 65 72 supported in ver
00a0: 73 69 6f 6e 20 34 2e 30 2e 30 3c 2f 68 32 3e 0d sion 4.0.0</h2>.
00b0: 0a 42 61 63 6b 20 74 6f 20 3c 61 20 68 72 65 66 .Back to <a href
00c0: 3d 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 67 61 ="https://www.ga
00d0: 69 61 2d 67 69 73 2e 69 74 2f 66 6f 73 73 69 6c ia-gis.it/fossil
00e0: 2f 6c 69 62 73 70 61 74 69 61 6c 69 74 65 2f 77 /libspatialite/w
00f0: 69 6b 69 3f 6e 61 6d 65 3d 73 77 69 74 63 68 69 iki?name=switchi
0100: 6e 67 2d 74 6f 2d 34 2e 30 23 74 65 73 73 65 6c ng-to-4.0#tessel
0110: 6c 61 74 69 6f 6e 73 22 3e 6d 61 69 6e 20 70 61 lations">main pa
0120: 67 65 3c 2f 61 3e 0d 0a 3c 68 33 3e 47 65 6e 65 ge</a>..<h3>Gene
0130: 72 61 6c 69 74 69 65 73 20 61 62 6f 75 74 20 74 ralities about t
0140: 65 73 73 65 6c 6c 61 74 69 6f 6e 73 3c 2f 68 33 essellations</h3
0150: 3e 0d 0a 3c 69 3e 54 65 73 73 65 6c 6c 61 74 69 >..<i>Tessellati
0160: 6f 6e 20 69 73 20 74 68 65 20 70 72 6f 63 65 73 on is the proces
0170: 73 20 6f 66 20 63 72 65 61 74 69 6e 67 20 61 20 s of creating a
0180: 74 77 6f 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 two-dimensional
0190: 70 6c 61 6e 65 20 75 73 69 6e 67 20 74 68 65 20 plane using the
01a0: 72 65 70 65 74 69 74 69 6f 6e 20 6f 66 20 61 20 repetition of a
01b0: 67 65 6f 6d 65 74 72 69 63 20 73 68 61 70 65 20 geometric shape
01c0: 77 69 74 68 20 6e 6f 20 6f 76 65 72 6c 61 70 73 with no overlaps
01d0: 20 61 6e 64 20 6e 6f 20 67 61 70 73 2e 3c 2f 69 and no gaps.</i
01e0: 3e 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 70 >..<a href="http
01f0: 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e ://en.wikipedia.
0200: 6f 72 67 2f 77 69 6b 69 2f 54 65 73 73 65 6c 6c org/wiki/Tessell
0210: 61 74 69 6f 6e 22 3e 72 65 61 64 20 6d 6f 72 65 ation">read more
0220: 3c 2f 61 3e 3c 62 72 3e 3c 62 72 3e 0d 0a 41 20 </a><br><br>..A
0230: 74 65 73 73 65 6c 6c 61 74 69 6f 6e 20 63 6f 75 tessellation cou
0240: 6c 64 20 62 65 20 65 76 65 6e 74 75 61 6c 6c 79 ld be eventually
0250: 20 62 61 73 65 64 20 6f 6e 20 69 64 65 6e 74 69 based on identi
0260: 63 61 6c 20 3c 69 3e 63 65 6c 6c 73 3c 2f 69 3e cal <i>cells</i>
0270: 2c 20 61 6c 6c 20 6f 66 20 65 78 61 63 74 6c 79 , all of exactly
0280: 20 74 68 65 20 73 61 6d 65 20 73 68 61 70 65 20 the same shape
0290: 61 6e 64 20 73 69 7a 65 2e 0d 0a 49 6e 20 74 68 and size...In th
02a0: 69 73 20 63 61 73 65 20 77 65 27 6c 6c 20 68 61 is case we'll ha
02b0: 76 65 20 61 20 3c 69 3e 72 65 67 75 6c 61 72 20 ve a <i>regular
02c0: 74 65 73 73 65 6c 6c 61 74 69 6f 6e 3c 2f 69 3e tessellation</i>
02d0: 2e 3c 62 72 3e 0d 0a 4a 75 73 74 20 61 20 71 75 .<br>..Just a qu
02e0: 69 63 6b 20 72 65 63 61 6c 6c 20 6f 66 20 65 6c ick recall of el
02f0: 65 6d 65 6e 74 61 72 79 20 67 65 6f 6d 65 74 72 ementary geometr
0300: 79 3b 20 74 68 65 72 65 20 61 72 65 20 73 69 6d y; there are sim
0310: 70 6c 79 20 3c 62 3e 33 3c 2f 62 3e 20 72 65 67 ply <b>3</b> reg
0320: 75 6c 61 72 20 70 6f 6c 79 67 6f 6e 61 6c 20 73 ular polygonal s
0330: 68 61 70 65 73 20 77 65 20 63 61 6e 20 75 73 65 hapes we can use
0340: 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 67 65 74 in order to get
0350: 20 61 20 72 65 67 75 6c 61 72 20 74 65 73 73 65 a regular tesse
0360: 6c 6c 61 74 69 6f 6e 3a 20 74 68 65 20 3c 62 3e llation: the <b>
0370: 65 71 75 69 6c 61 74 65 72 61 6c 20 74 72 69 61 equilateral tria
0380: 6e 67 6c 65 3c 2f 62 3e 2c 20 74 68 65 20 3c 62 ngle</b>, the <b
0390: 3e 73 71 75 61 72 65 3c 2f 62 3e 20 61 6e 64 20 >square</b> and
03a0: 74 68 65 20 3c 62 3e 72 65 67 75 6c 61 72 20 68 the <b>regular h
03b0: 65 78 61 67 6f 6e 3c 2f 62 3e 2e 3c 62 72 3e 3c exagon</b>.<br><
03c0: 62 72 3e 0d 0a 4f 6e 20 74 68 65 20 6f 74 68 65 br>..On the othe
03d0: 72 20 77 61 79 20 6d 61 6e 79 20 74 65 73 73 65 r way many tesse
03e0: 6c 6c 61 74 69 6f 6e 73 20 61 72 65 6e 27 74 20 llations aren't
03f0: 72 65 67 75 6c 61 72 20 61 74 20 61 6c 6c 2c 20 regular at all,
0400: 62 65 63 61 75 73 65 20 65 61 63 68 20 73 69 6e because each sin
0410: 67 6c 65 20 63 65 6c 6c 20 68 61 73 20 61 6e 20 gle cell has an
0420: 69 6e 64 69 76 69 64 75 61 6c 20 73 69 7a 65 20 individual size
0430: 61 6e 64 20 73 68 61 70 65 20 6f 66 20 69 74 73 and shape of its
0440: 20 6f 77 6e 2e 3c 62 72 3e 0d 0a 49 74 27 73 20 own.<br>..It's
0450: 72 65 61 6c 6c 79 20 69 6e 74 65 72 65 73 74 69 really interesti
0460: 6e 67 20 74 6f 20 6e 6f 74 65 20 74 68 61 74 20 ng to note that
0470: 6d 61 6e 79 20 3c 69 3e 6e 61 74 75 72 61 6c 20 many <i>natural
0480: 73 68 61 70 65 73 3c 2f 69 3e 20 63 6c 6f 73 65 shapes</i> close
0490: 6c 79 20 72 65 73 65 6d 62 6c 65 20 61 20 74 65 ly resemble a te
04a0: 73 73 65 6c 6c 61 74 69 6f 6e 3a 20 67 6f 69 6e ssellation: goin
04b0: 67 20 66 72 6f 6d 20 62 69 6f 6c 6f 67 79 20 74 g from biology t
04c0: 6f 20 63 72 79 73 74 61 6c 6c 6f 67 72 61 70 68 o crystallograph
04d0: 79 20 73 69 6e 63 65 20 67 65 6f 6c 6f 67 79 20 y since geology
04e0: 61 6e 64 20 6c 61 6e 64 73 63 61 70 65 73 20 69 and landscapes i
04f0: 74 27 73 20 6e 6f 74 20 61 74 20 61 6c 6c 20 64 t's not at all d
0500: 69 66 66 69 63 75 6c 74 20 74 6f 20 69 64 65 6e ifficult to iden
0510: 74 69 66 79 20 6d 61 6e 79 20 6e 61 74 75 72 61 tify many natura
0520: 6c 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 20 65 l tessellation e
0530: 78 61 6d 70 6c 65 73 20 3c 69 3e 6f 6e 20 74 68 xamples <i>on th
0540: 65 20 77 69 6c 64 3c 2f 69 3e 2e 0d 0a 53 6f 20 e wild</i>...So
0550: 69 74 27 73 20 6e 6f 74 20 61 74 20 61 6c 6c 20 it's not at all
0560: 73 75 72 70 72 69 73 69 6e 67 20 74 6f 20 64 69 surprising to di
0570: 73 63 6f 76 65 72 20 74 68 61 74 20 74 65 73 73 scover that tess
0580: 65 6c 6c 61 74 69 6f 6e 73 20 61 72 65 20 6f 66 ellations are of
0590: 74 65 6e 20 75 73 65 66 75 6c 20 69 6e 20 67 65 ten useful in ge
05a0: 6f 67 72 61 70 68 79 20 61 73 20 77 65 6c 6c 2e ography as well.
05b0: 0d 0a 3c 68 33 3e 53 65 74 74 69 6e 67 20 75 70 ..<h3>Setting up
05c0: 20 61 20 74 65 73 74 62 65 64 20 44 42 3c 2f 68 a testbed DB</h
05d0: 33 3e 0d 0a 49 6e 20 74 68 69 73 20 73 68 6f 72 3>..In this shor
05e0: 74 20 74 75 74 6f 72 69 61 6c 20 77 65 27 6c 6c t tutorial we'll
05f0: 20 75 73 65 20 61 20 76 65 72 79 20 73 69 6d 70 use a very simp
0600: 6c 65 20 53 70 61 74 69 61 4c 69 74 65 20 44 42 le SpatiaLite DB
0610: 2c 20 6a 75 73 74 20 63 6f 6e 74 61 69 6e 69 6e , just containin
0620: 67 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 g the following
0630: 47 65 6f 6d 65 74 72 79 20 74 61 62 6c 65 73 3a Geometry tables:
0640: 3c 75 6c 3e 0d 0a 3c 6c 69 3e 41 64 6d 69 6e 69 <ul>..<li>Admini
0650: 73 74 72 61 74 69 76 65 20 62 6f 75 6e 64 61 72 strative boundar
0660: 69 65 73 20 66 6f 72 20 49 74 61 6c 79 20 72 65 ies for Italy re
0670: 67 69 6f 6e 73 3a 20 79 6f 75 20 63 61 6e 20 3c gions: you can <
0680: 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f 77 a href="http://w
0690: 77 77 2e 69 73 74 61 74 2e 69 74 2f 69 74 2f 66 ww.istat.it/it/f
06a0: 69 6c 65 73 2f 32 30 31 31 2f 30 34 2f 72 65 67 iles/2011/04/reg
06b0: 32 30 31 31 2e 7a 69 70 22 3e 64 6f 77 6e 6c 6f 2011.zip">downlo
06c0: 61 64 3c 2f 61 3e 20 74 68 69 73 20 64 61 74 61 ad</a> this data
06d0: 73 65 74 20 66 72 6f 6d 20 49 53 54 41 54 20 28 set from ISTAT (
06e0: 72 65 6c 65 61 73 65 64 20 6f 6e 20 43 43 2d 42 released on CC-B
06f0: 59 20 6c 69 63 65 6e 73 65 20 74 65 72 6d 73 29 Y license terms)
0700: 2e 3c 62 72 3e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e .<br></li>..<li>
0710: 4d 61 69 6e 20 49 74 61 6c 69 61 6e 20 70 6f 70 Main Italian pop
0720: 75 6c 61 74 65 64 20 70 6c 61 63 65 73 20 28 6e ulated places (n
0730: 61 6d 65 6c 79 2c 20 4c 6f 63 61 6c 20 43 6f 75 amely, Local Cou
0740: 6e 63 69 6c 73 29 3a 20 79 6f 75 20 63 61 6e 20 ncils): you can
0750: 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f <a href="http://
0760: 64 6f 77 6e 6c 6f 61 64 2e 67 65 6f 6e 61 6d 65 download.geoname
0770: 73 2e 6f 72 67 2f 65 78 70 6f 72 74 2f 64 75 6d s.org/export/dum
0780: 70 2f 61 6c 6c 43 6f 75 6e 74 72 69 65 73 2e 7a p/allCountries.z
0790: 69 70 22 3e 64 6f 77 6e 6c 6f 61 64 3c 2f 61 3e ip">download</a>
07a0: 20 74 68 69 73 20 64 61 74 61 73 65 74 20 66 72 this dataset fr
07b0: 6f 6d 20 47 65 6f 4e 61 6d 65 73 20 28 72 65 6c om GeoNames (rel
07c0: 65 61 73 65 64 20 6f 6e 20 43 43 2d 42 59 20 6c eased on CC-BY l
07d0: 69 63 65 6e 73 65 20 74 65 72 6d 73 29 2e 3c 62 icense terms).<b
07e0: 72 3e 0d 0a 50 6c 65 61 73 65 20 6e 6f 74 65 3a r>..Please note:
07f0: 20 74 68 69 73 20 6f 6e 65 20 69 73 20 61 20 77 this one is a w
0800: 6f 72 6c 64 77 69 64 65 20 64 61 74 61 73 65 74 orldwide dataset
0810: 3b 20 69 74 61 6c 69 61 6e 20 70 6f 70 75 6c 61 ; italian popula
0820: 74 65 64 20 70 6c 61 63 65 73 20 68 61 76 65 20 ted places have
0830: 74 68 65 6e 20 62 65 65 6e 20 65 78 74 72 61 63 then been extrac
0840: 74 65 64 20 69 6d 70 6f 73 69 6e 67 20 74 68 65 ted imposing the
0850: 20 53 51 4c 20 63 6c 61 75 73 65 3c 62 72 3e 0d SQL clause<br>.
0860: 0a 3c 62 3e 57 48 45 52 45 20 63 6f 75 6e 74 79 .<b>WHERE county
0870: 5f 63 6f 64 65 20 3d 20 27 49 54 27 20 41 4e 44 _code = 'IT' AND
0880: 20 70 6f 70 75 6c 61 74 69 6f 6e 20 3e 20 30 3c population > 0<
0890: 2f 62 3e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c /b></li>..</ul><
08a0: 62 72 3e 0d 0a 4a 75 73 74 20 74 6f 20 6b 65 65 br>..Just to kee
08b0: 70 20 61 6e 79 20 65 78 61 6d 70 6c 65 20 61 73 p any example as
08c0: 20 73 69 6d 70 6c 65 20 61 73 20 70 6f 73 73 69 simple as possi
08d0: 62 6c 65 2c 20 62 6f 74 68 20 64 61 74 61 73 65 ble, both datase
08e0: 74 73 20 68 61 76 65 20 62 65 65 6e 20 72 65 66 ts have been ref
08f0: 65 72 65 6e 63 65 64 20 69 6e 74 6f 20 74 68 65 erenced into the
0900: 20 3c 62 3e 53 52 49 44 3d 32 33 30 33 32 20 2d <b>SRID=23032 -
0910: 20 45 44 35 30 20 2f 20 55 54 4d 20 7a 6f 6e 65 ED50 / UTM zone
0920: 20 33 32 20 4e 3c 2f 62 3e 0d 0a 3c 62 72 3e 3c 32 N</b>..<br><
0930: 62 72 3e 3c 68 72 3e 0d 0a 3c 68 33 3e 43 72 65 br><hr>..<h3>Cre
0940: 61 74 69 6e 67 20 72 65 67 75 6c 61 72 20 74 65 ating regular te
0950: 73 73 65 6c 6c 61 74 69 6f 6e 73 20 69 6e 20 53 ssellations in S
0960: 70 61 74 69 61 6c 20 53 51 4c 3c 2f 68 33 3e 0d patial SQL</h3>.
0970: 0a 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 63 .<table cellspac
0980: 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 ing="4" cellpadd
0990: 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c 74 ing="4">..<tr><t
09a0: 64 20 63 6f 6c 73 70 61 6e 3d 22 32 22 3e 0d 0a d colspan="2">..
09b0: 3c 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 <table bgcolor="
09c0: 23 66 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 #f0f0f0" cellspa
09d0: 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 cing="4" cellpad
09e0: 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c ding="8">..<tr><
09f0: 74 64 3e 0d 0a 3c 69 3e 67 65 6e 65 72 69 63 20 td>..<i>generic
0a00: 70 72 6f 74 6f 74 79 70 65 73 3c 2f 69 3e 3a 3c prototypes</i>:<
0a10: 68 72 3e 0d 0a 53 54 5f 78 78 78 78 47 72 69 64 hr>..ST_xxxxGrid
0a20: 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 ( input <i>Geome
0a30: 74 72 79 3c 2f 69 3e 2c 20 73 69 7a 65 20 3c 69 try</i>, size <i
0a40: 3e 64 6f 75 62 6c 65 20 70 72 65 63 69 73 69 6f >double precisio
0a50: 6e 3c 2f 69 3e 20 29 20 3a 20 67 72 69 64 20 3c n</i> ) : grid <
0a60: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 i>Geometry</i><b
0a70: 72 3e 0d 0a 53 54 5f 78 78 78 78 47 72 69 64 28 r>..ST_xxxxGrid(
0a80: 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 input <i>Geomet
0a90: 72 79 3c 2f 69 3e 2c 20 73 69 7a 65 20 3c 69 3e ry</i>, size <i>
0aa0: 64 6f 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e double precision
0ab0: 3c 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 </i>, edges_only
0ac0: 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 <i>boolean</i>
0ad0: 29 20 3a 20 67 72 69 64 20 3c 69 3e 47 65 6f 6d ) : grid <i>Geom
0ae0: 65 74 72 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 etry</i><br>..ST
0af0: 5f 78 78 78 78 47 72 69 64 28 20 69 6e 70 75 74 _xxxxGrid( input
0b00: 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e <i>Geometry</i>
0b10: 2c 20 73 69 7a 65 20 3c 69 3e 64 6f 75 62 6c 65 , size <i>double
0b20: 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e 2c 20 precision</i>,
0b30: 65 64 67 65 73 5f 6f 6e 6c 79 20 3c 69 3e 62 6f edges_only <i>bo
0b40: 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 6f 72 69 67 69 olean</i>, origi
0b50: 6e 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 n <i>Geometry</i
0b60: 3e 20 29 20 3a 20 67 72 69 64 20 3c 69 3e 47 65 > ) : grid <i>Ge
0b70: 6f 6d 65 74 72 79 3c 2f 69 3e 0d 0a 3c 2f 74 64 ometry</i>..</td
0b80: 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 0d 0a ></tr></table>..
0b90: 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 20 3c 62 <ul>..<li>the <b
0ba0: 3e 69 6e 70 75 74 3c 2f 62 3e 20 47 65 6f 6d 65 >input</b> Geome
0bb0: 74 72 79 20 69 73 20 61 6c 77 61 79 73 20 65 78 try is always ex
0bc0: 70 65 63 74 65 64 20 74 6f 20 62 65 20 61 20 50 pected to be a P
0bd0: 6f 6c 79 67 6f 6e 20 6f 72 20 61 20 4d 75 6c 74 olygon or a Mult
0be0: 69 50 6f 6c 79 67 6f 6e 2c 20 61 6e 64 20 77 69 iPolygon, and wi
0bf0: 6c 6c 20 62 65 20 65 78 61 63 74 6c 79 20 63 6f ll be exactly co
0c00: 76 65 72 65 64 20 62 79 20 74 68 65 20 72 65 74 vered by the ret
0c10: 75 72 6e 65 64 20 67 72 69 64 2e 3c 2f 6c 69 3e urned grid.</li>
0c20: 0d 0a 3c 6c 69 3e 74 68 65 20 3c 62 3e 73 69 7a ..<li>the <b>siz
0c30: 65 3c 2f 62 3e 20 61 72 67 75 6d 65 6e 74 20 69 e</b> argument i
0c40: 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 65 64 dentifies the ed
0c50: 67 65 20 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 ge length of the
0c60: 20 67 72 69 64 20 63 65 6c 6c 2e 3c 2f 6c 69 3e grid cell.</li>
0c70: 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 69 6f 6e ..<li>the option
0c80: 61 6c 20 3c 62 3e 65 64 67 65 73 5f 6f 6e 6c 79 al <b>edges_only
0c90: 3c 2f 62 3e 20 61 72 67 75 6d 65 6e 74 20 77 69 </b> argument wi
0ca0: 6c 6c 20 62 65 20 69 6e 74 65 72 70 72 65 74 65 ll be interprete
0cb0: 64 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 3c 75 6c d as follows:<ul
0cc0: 3e 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 46 41 4c >..<li>if <b>FAL
0cd0: 53 45 3c 2f 62 3e 20 28 3c 69 3e 64 65 66 61 75 SE</b> (<i>defau
0ce0: 6c 74 20 76 61 6c 75 65 3c 2f 69 3e 29 20 61 20 lt value</i>) a
0cf0: 4d 75 6c 74 69 50 6f 6c 79 67 6f 6e 20 77 69 6c MultiPolygon wil
0d00: 6c 20 62 65 20 72 65 74 75 72 6e 65 64 2e 3c 2f l be returned.</
0d10: 6c 69 3e 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 54 li>..<li>if <b>T
0d20: 52 55 45 3c 2f 62 3e 20 61 20 4d 75 6c 74 69 4c RUE</b> a MultiL
0d30: 69 6e 65 73 74 72 69 6e 67 20 77 69 6c 6c 20 62 inestring will b
0d40: 65 20 72 65 74 75 72 6e 65 64 20 28 73 69 6d 70 e returned (simp
0d50: 6c 79 20 72 65 70 72 65 73 65 6e 74 69 6e 67 20 ly representing
0d60: 74 68 65 20 63 65 6c 6c 73 20 65 64 67 65 73 29 the cells edges)
0d70: 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f 6c .</li>..</ul></l
0d80: 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 69 i>..<li>the opti
0d90: 6f 6e 61 6c 20 3c 62 3e 6f 72 69 67 69 6e 3c 2f onal <b>origin</
0da0: 62 3e 20 47 65 6f 6d 65 74 72 79 20 69 73 20 61 b> Geometry is a
0db0: 6c 77 61 79 73 20 61 73 73 75 6d 65 64 20 74 6f lways assumed to
0dc0: 20 62 65 20 61 20 50 6f 69 6e 74 2c 20 61 6e 64 be a Point, and
0dd0: 20 77 69 6c 6c 20 69 64 65 6e 74 69 66 79 20 74 will identify t
0de0: 68 65 20 67 72 69 64 27 73 20 6f 72 69 67 69 6e he grid's origin
0df0: 2e 0d 0a 42 79 20 64 65 66 61 75 6c 74 20 61 20 ...By default a
0e00: 3c 62 3e 28 30 2c 20 30 29 3c 2f 62 3e 20 6f 72 <b>(0, 0)</b> or
0e10: 69 67 69 6e 20 77 69 6c 6c 20 62 65 20 61 73 73 igin will be ass
0e20: 75 6d 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c umed.</li>..</ul
0e30: 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 ></td></tr>..<tr
0e40: 3e 3c 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 ><td>..<h4>using
0e50: 20 53 71 75 61 72 65 20 63 65 6c 6c 73 3c 2f 68 Square cells</h
0e60: 34 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c 4>..<table bgcol
0e70: 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 6c or="#f0f0f0" cel
0e80: 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c lspacing="4" cel
0e90: 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c lpadding="8">..<
0ea0: 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 4c 45 tr><td>..<b>SELE
0eb0: 43 54 20 53 54 5f 53 71 75 61 72 65 47 72 69 64 CT ST_SquareGrid
0ec0: 28 67 65 6f 6d 65 74 72 79 2c 20 31 30 30 30 30 (geometry, 10000
0ed0: 29 3c 62 72 3e 0d 0a 46 52 4f 4d 20 72 65 67 69 )<br>..FROM regi
0ee0: 6f 6e 73 3c 62 72 3e 57 48 45 52 45 20 63 6f 64 ons<br>WHERE cod
0ef0: 5f 72 65 67 20 3d 20 39 3b 3c 2f 62 3e 0d 0a 3c _reg = 9;</b>..<
0f00: 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 /td></tr>..</tab
0f10: 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 53 51 le><br>..This SQ
0f20: 4c 20 71 75 65 72 79 20 77 69 6c 6c 20 72 65 74 L query will ret
0f30: 75 72 6e 20 61 20 72 65 67 75 6c 61 72 20 67 72 urn a regular gr
0f40: 69 64 20 28 73 71 75 61 72 65 20 63 65 6c 6c 73 id (square cells
0f50: 29 20 63 6f 76 65 72 69 6e 67 20 54 75 73 63 61 ) covering Tusca
0f60: 6e 79 20 28 3c 62 3e 63 6f 64 5f 72 65 67 3d 39 ny (<b>cod_reg=9
0f70: 3c 2f 62 3e 29 2e 3c 62 72 3e 0d 0a 45 61 63 68 </b>).<br>..Each
0f80: 20 67 72 69 64 27 73 20 63 65 6c 6c 20 77 69 6c grid's cell wil
0f90: 6c 20 68 61 76 65 20 61 6e 20 65 64 67 65 20 6c l have an edge l
0fa0: 65 6e 67 74 68 20 6f 66 20 65 78 61 63 74 6c 79 ength of exactly
0fb0: 20 3c 62 3e 31 30 20 4b 6d 3c 2f 62 3e 0d 0a 3c <b>10 Km</b>..<
0fc0: 2f 74 64 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 /td>..<td><img b
0fd0: 6f 72 64 65 72 3d 22 31 22 20 73 72 63 3d 22 68 order="1" src="h
0fe0: 74 74 70 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 ttp://www.gaia-g
0ff0: 69 73 2e 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f is.it/gaia-sins/
1000: 77 72 69 74 65 2d 76 69 65 77 2d 70 69 63 73 2f write-view-pics/
1010: 73 71 75 61 72 65 2d 67 72 69 64 2e 70 6e 67 22 square-grid.png"
1020: 20 61 6c 74 3d 22 73 71 75 61 72 65 20 67 72 69 alt="square gri
1030: 64 22 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c d"></td></tr>..<
1040: 74 72 3e 3c 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 tr><td>..<h4>usi
1050: 6e 67 20 54 72 69 61 6e 67 75 6c 61 72 20 63 65 ng Triangular ce
1060: 6c 6c 73 3c 2f 68 34 3e 0d 0a 3c 74 61 62 6c 65 lls</h4>..<table
1070: 20 62 67 63 6f 6c 6f 72 3d 22 23 66 30 66 30 66 bgcolor="#f0f0f
1080: 30 22 20 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 0" cellspacing="
1090: 34 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 4" cellpadding="
10a0: 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 8">..<tr><td>..<
10b0: 62 3e 53 45 4c 45 43 54 20 53 54 5f 54 72 69 61 b>SELECT ST_Tria
10c0: 6e 67 75 6c 61 72 47 72 69 64 28 67 65 6f 6d 65 ngularGrid(geome
10d0: 74 72 79 2c 20 31 30 30 30 30 29 3c 62 72 3e 0d try, 10000)<br>.
10e0: 0a 46 52 4f 4d 20 72 65 67 69 6f 6e 73 3c 62 72 .FROM regions<br
10f0: 3e 57 48 45 52 45 20 63 6f 64 5f 72 65 67 20 3d >WHERE cod_reg =
1100: 20 39 3b 3c 2f 62 3e 0d 0a 3c 2f 74 64 3e 3c 2f 9;</b>..</td></
1110: 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 3c 2f 74 tr>..</table></t
1120: 64 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 d>..<td><img bor
1130: 64 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 der="1" src="htt
1140: 70 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 p://www.gaia-gis
1150: 2e 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 .it/gaia-sins/wr
1160: 69 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 74 72 ite-view-pics/tr
1170: 69 2d 67 72 69 64 2e 70 6e 67 22 20 61 6c 74 3d i-grid.png" alt=
1180: 22 74 72 69 61 6e 67 75 6c 61 72 20 67 72 69 64 "triangular grid
1190: 22 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 "></td></tr>..<t
11a0: 72 3e 3c 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e r><td>..<h4>usin
11b0: 67 20 48 65 78 61 67 6f 6e 61 6c 20 63 65 6c 6c g Hexagonal cell
11c0: 73 3c 2f 68 34 3e 0d 0a 3c 74 61 62 6c 65 20 62 s</h4>..<table b
11d0: 67 63 6f 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 gcolor="#f0f0f0"
11e0: 20 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 cellspacing="4"
11f0: 20 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 cellpadding="8"
1200: 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e >..<tr><td>..<b>
1210: 53 45 4c 45 43 54 20 53 54 5f 48 65 78 61 67 6f SELECT ST_Hexago
1220: 6e 61 6c 47 72 69 64 28 67 65 6f 6d 65 74 72 79 nalGrid(geometry
1230: 2c 20 31 30 30 30 30 29 3c 62 72 3e 0d 0a 46 52 , 10000)<br>..FR
1240: 4f 4d 20 72 65 67 69 6f 6e 73 3c 62 72 3e 57 48 OM regions<br>WH
1250: 45 52 45 20 63 6f 64 5f 72 65 67 20 3d 20 39 3b ERE cod_reg = 9;
1260: 3c 2f 62 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e </b>..</td></tr>
1270: 0d 0a 3c 2f 74 61 62 6c 65 3e 3c 2f 74 64 3e 0d ..</table></td>.
1280: 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 72 .<td><img border
1290: 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f ="1" src="http:/
12a0: 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 /www.gaia-gis.it
12b0: 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 /gaia-sins/write
12c0: 2d 76 69 65 77 2d 70 69 63 73 2f 68 65 78 2d 67 -view-pics/hex-g
12d0: 72 69 64 2e 70 6e 67 22 20 61 6c 74 3d 22 68 65 rid.png" alt="he
12e0: 78 61 67 6f 6e 61 6c 20 67 72 69 64 22 3e 3c 2f xagonal grid"></
12f0: 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c td></tr>..</tabl
1300: 65 3e 0d 0a 3c 62 72 3e 3c 68 72 3e 0d 0a 3c 68 e>..<br><hr>..<h
1310: 33 3e 44 65 6c 61 75 6e 61 79 20 54 72 69 61 6e 3>Delaunay Trian
1320: 67 75 6c 61 74 69 6f 6e 73 3c 2f 68 33 3e 0d 0a gulations</h3>..
1330: 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 73 20 73 Triangulations s
1340: 69 6d 70 6c 79 20 72 65 70 72 65 73 65 6e 74 20 imply represent
1350: 61 20 73 70 65 63 69 61 6c 20 63 61 73 65 20 6f a special case o
1360: 66 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 73 3a f tessellations:
1370: 20 69 6e 20 74 68 69 73 20 63 61 73 65 20 61 6c in this case al
1380: 6c 20 63 65 6c 6c 73 20 61 72 65 20 72 65 70 72 l cells are repr
1390: 65 73 65 6e 74 65 64 20 62 79 20 67 65 6e 65 72 esented by gener
13a0: 69 63 20 3c 62 3e 74 72 69 61 6e 67 6c 65 73 3c ic <b>triangles<
13b0: 2f 62 3e 2c 20 6e 6f 74 20 6e 65 63 65 73 73 61 /b>, not necessa
13c0: 72 69 6c 79 20 6f 66 20 74 68 65 20 65 71 75 69 rily of the equi
13d0: 6c 61 74 65 72 61 6c 20 6b 69 6e 64 2e 3c 62 72 lateral kind.<br
13e0: 3e 0d 0a 41 20 3c 62 3e 44 65 6c 61 75 6e 61 79 >..A <b>Delaunay
13f0: 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 3c 2f Triangulation</
1400: 62 3e 20 69 73 20 76 65 72 79 20 70 65 63 75 6c b> is very pecul
1410: 69 61 72 20 62 65 63 61 75 73 65 20 61 20 73 70 iar because a sp
1420: 65 63 69 66 69 63 20 63 6f 6e 73 74 72 61 69 6e ecific constrain
1430: 74 20 69 73 20 69 6d 70 6f 73 65 64 2e 3c 62 72 t is imposed.<br
1440: 3e 0d 0a 41 6c 6c 20 74 72 69 61 6e 67 6c 65 73 >..All triangles
1450: 20 69 6e 20 61 20 44 65 6c 61 75 6e 61 79 20 74 in a Delaunay t
1460: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 6d 75 73 riangulation mus
1470: 74 20 73 61 74 69 73 66 79 20 74 68 65 20 3c 75 t satisfy the <u
1480: 3e 3c 69 3e 65 6d 70 74 79 20 63 69 72 63 6c 65 ><i>empty circle
1490: 3c 2f 69 3e 3c 2f 75 3e 20 70 72 6f 70 65 72 74 </i></u> propert
14a0: 79 3a 20 69 2e 65 2e 20 66 6f 72 20 65 61 63 68 y: i.e. for each
14b0: 20 65 64 67 65 20 77 65 20 63 61 6e 20 66 69 6e edge we can fin
14c0: 64 20 61 20 63 69 72 63 6c 65 20 63 6f 6e 74 61 d a circle conta
14d0: 69 6e 69 6e 67 20 74 68 65 20 65 64 67 65 27 73 ining the edge's
14e0: 20 65 6e 64 70 6f 69 6e 74 73 20 62 75 74 20 6e endpoints but n
14f0: 6f 74 20 63 6f 6e 74 61 69 6e 69 6e 67 20 61 6e ot containing an
1500: 79 20 6f 74 68 65 72 20 70 6f 69 6e 74 73 2e 0d y other points..
1510: 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f .<a href="http:/
1520: 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f 72 /en.wikipedia.or
1530: 67 2f 77 69 6b 69 2f 44 65 6c 61 75 6e 61 79 5f g/wiki/Delaunay_
1540: 74 72 69 61 6e 67 75 6c 61 74 69 6f 6e 22 3e 72 triangulation">r
1550: 65 61 64 20 6d 6f 72 65 3c 2f 61 3e 3c 62 72 3e ead more</a><br>
1560: 3c 62 72 3e 0d 0a 43 6f 6d 70 75 74 69 6e 67 20 <br>..Computing
1570: 61 20 44 65 6c 61 75 6e 61 79 20 54 72 69 61 6e a Delaunay Trian
1580: 67 75 6c 61 74 69 6f 6e 20 72 65 70 72 65 73 65 gulation represe
1590: 6e 74 69 6e 67 20 6d 61 6e 79 20 70 6f 69 6e 74 nting many point
15a0: 73 20 69 73 20 61 20 76 65 72 79 20 63 6f 6d 70 s is a very comp
15b0: 6c 65 78 20 6f 70 65 72 61 74 69 6f 6e 2c 20 61 lex operation, a
15c0: 6e 64 20 6f 6e 65 20 70 6f 73 73 69 62 6c 79 20 nd one possibly
15d0: 69 6d 70 6f 73 69 6e 67 20 61 20 68 75 67 65 20 imposing a huge
15e0: 63 6f 6d 70 75 74 61 74 69 6f 6e 61 6c 20 6c 6f computational lo
15f0: 61 64 20 61 6e 64 20 6d 61 79 20 62 65 20 72 65 ad and may be re
1600: 71 75 69 72 69 6e 67 20 61 20 6c 6f 6e 67 20 74 quiring a long t
1610: 69 6d 65 2e 0d 0a 48 61 70 70 69 6c 79 20 65 6e ime...Happily en
1620: 6f 75 67 68 20 6d 61 6e 79 20 68 69 67 68 6c 79 ough many highly
1630: 20 65 66 66 69 63 69 65 6e 74 20 61 6c 67 6f 72 efficient algor
1640: 69 74 68 6d 73 20 68 61 76 65 20 62 65 65 6e 20 ithms have been
1650: 61 6c 72 65 61 64 79 20 64 65 76 65 6c 6f 70 65 already develope
1660: 64 20 66 6f 72 20 74 68 65 20 44 65 6c 61 75 6e d for the Delaun
1670: 61 79 20 70 72 6f 62 6c 65 6d 2e 3c 62 72 3e 0d ay problem.<br>.
1680: 0a 54 68 65 20 6e 65 78 74 2d 74 6f 2d 63 6f 6d .The next-to-com
1690: 65 20 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a e <a href="http:
16a0: 2f 2f 74 72 61 63 2e 6f 73 67 65 6f 2e 6f 72 67 //trac.osgeo.org
16b0: 2f 67 65 6f 73 2f 22 3e 47 45 4f 53 20 33 2e 34 /geos/">GEOS 3.4
16c0: 2e 30 3c 2f 61 3e 20 77 69 6c 6c 20 73 75 70 70 .0</a> will supp
16d0: 6f 72 74 20 44 65 6c 61 75 6e 61 79 20 54 72 69 ort Delaunay Tri
16e0: 61 6e 67 75 6c 61 74 69 6f 6e 73 3b 20 74 68 69 angulations; thi
16f0: 73 20 47 45 4f 53 20 76 65 72 73 69 6f 6e 20 69 s GEOS version i
1700: 73 20 63 75 72 72 65 6e 74 6c 79 20 73 74 69 6c s currently stil
1710: 6c 20 75 6e 64 65 72 20 61 63 74 69 76 65 20 64 l under active d
1720: 65 76 65 6c 6f 70 6d 65 6e 74 2c 20 62 75 74 20 evelopment, but
1730: 74 68 65 20 3c 69 3e 65 78 70 65 72 69 6d 65 6e the <i>experimen
1740: 74 61 6c 3c 2f 69 3e 20 62 61 73 65 2d 63 6f 64 tal</i> base-cod
1750: 65 20 28 3c 69 3e 74 72 75 6e 6b 3c 2f 69 3e 29 e (<i>trunk</i>)
1760: 20 73 65 65 6d 73 20 74 6f 20 62 65 20 73 74 61 seems to be sta
1770: 62 6c 65 20 65 6e 6f 75 67 68 20 74 6f 20 62 65 ble enough to be
1780: 20 73 61 66 65 6c 79 20 74 65 73 74 65 64 2e 0d safely tested..
1790: 0a 53 70 61 74 69 61 4c 69 74 65 20 61 6c 72 65 .SpatiaLite alre
17a0: 61 64 79 20 72 65 6c 69 65 73 20 6f 6e 20 47 45 ady relies on GE
17b0: 4f 53 20 66 6f 72 20 6d 61 6e 79 20 74 61 73 6b OS for many task
17c0: 73 2c 20 73 6f 20 69 6e 74 65 67 72 61 74 69 6e s, so integratin
17d0: 67 20 61 20 73 6d 6f 6f 74 68 20 73 75 70 70 6f g a smooth suppo
17e0: 72 74 20 66 6f 72 20 44 65 6c 61 75 6e 61 79 20 rt for Delaunay
17f0: 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 61 73 Triangulation as
1800: 20 77 65 6c 6c 20 77 61 73 6e 27 74 20 61 74 20 well wasn't at
1810: 61 6c 6c 20 64 69 66 66 69 63 75 6c 74 2e 3c 62 all difficult.<b
1820: 72 3e 3c 62 72 3e 0d 0a 3c 74 61 62 6c 65 20 62 r><br>..<table b
1830: 67 63 6f 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 gcolor="#f0f0f0"
1840: 20 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 cellspacing="4"
1850: 20 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 cellpadding="8"
1860: 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 69 3e >..<tr><td>..<i>
1870: 70 72 6f 74 6f 74 79 70 65 3c 2f 69 3e 3a 3c 68 prototype</i>:<h
1880: 72 3e 0d 0a 53 54 5f 44 65 6c 61 75 6e 61 79 54 r>..ST_DelaunayT
1890: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 28 20 69 6e riangulation( in
18a0: 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c put <i>Geometry<
18b0: 2f 69 3e 20 29 20 3a 20 64 65 6c 61 75 6e 61 79 /i> ) : delaunay
18c0: 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e <i>Geometry</i>
18d0: 3c 62 72 3e 0d 0a 53 54 5f 44 65 6c 61 75 6e 61 <br>..ST_Delauna
18e0: 79 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 28 20 yTriangulation(
18f0: 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 input <i>Geometr
1900: 79 3c 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c y</i>, edges_onl
1910: 79 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e y <i>boolean</i>
1920: 20 29 20 3a 20 64 65 6c 61 75 6e 61 79 20 3c 69 ) : delaunay <i
1930: 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 72 >Geometry</i><br
1940: 3e 0d 0a 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 >..ST_DelaunayTr
1950: 69 61 6e 67 75 6c 61 74 69 6f 6e 28 20 69 6e 70 iangulation( inp
1960: 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f ut <i>Geometry</
1970: 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c i>, edges_only <
1980: 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 74 i>boolean</i>, t
1990: 6f 6c 65 72 61 6e 63 65 20 3c 69 3e 64 6f 75 62 olerance <i>doub
19a0: 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e le precision</i>
19b0: 20 29 20 3a 20 64 65 6c 61 75 6e 61 79 20 3c 69 ) : delaunay <i
19c0: 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 0d 0a 3c >Geometry</i>..<
19d0: 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 /td></tr></table
19e0: 3e 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 >..<ul>..<li>the
19f0: 20 3c 62 3e 69 6e 70 75 74 3c 2f 62 3e 20 47 65 <b>input</b> Ge
1a00: 6f 6d 65 74 72 79 20 63 61 6e 20 62 65 20 6f 66 ometry can be of
1a10: 20 61 62 73 6f 6c 75 74 65 6c 79 20 61 72 62 69 absolutely arbi
1a20: 74 72 61 72 79 20 74 79 70 65 3b 20 61 6c 6c 20 trary type; all
1a30: 4c 69 6e 65 73 74 72 69 6e 67 73 20 61 6e 64 20 Linestrings and
1a40: 2f 20 6f 72 20 50 6f 6c 79 67 6f 77 6e 73 20 77 / or Polygowns w
1a50: 69 6c 6c 20 65 76 65 6e 74 75 61 6c 6c 79 20 62 ill eventually b
1a60: 65 20 64 69 73 73 6f 6c 76 65 64 20 69 6e 74 6f e dissolved into
1a70: 20 50 6f 69 6e 74 73 20 63 6f 72 72 65 73 70 6f Points correspo
1a80: 6e 64 69 6e 67 20 74 6f 20 76 65 72 74 69 63 65 nding to vertice
1a90: 73 2e 3c 62 72 3e 0d 0a 53 6f 20 61 66 74 65 72 s.<br>..So after
1aa0: 20 61 6c 6c 20 53 54 5f 44 65 6c 61 75 6e 61 79 all ST_Delaunay
1ab0: 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 28 29 20 Triangulation()
1ac0: 77 69 6c 6c 20 61 6c 77 61 79 73 20 70 72 6f 63 will always proc
1ad0: 65 73 73 20 61 20 4d 75 6c 74 69 50 6f 69 6e 74 ess a MultiPoint
1ae0: 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 .</li>..<li>the
1af0: 6f 70 74 69 6f 6e 61 6c 20 3c 62 3e 65 64 67 65 optional <b>edge
1b00: 73 5f 6f 6e 6c 79 3c 2f 62 3e 20 61 72 67 75 6d s_only</b> argum
1b10: 65 6e 74 20 77 69 6c 6c 20 62 65 20 69 6e 74 65 ent will be inte
1b20: 72 70 72 65 74 65 64 20 61 73 20 66 6f 6c 6c 6f rpreted as follo
1b30: 77 73 3a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 69 66 20 ws:<ul>..<li>if
1b40: 3c 62 3e 46 41 4c 53 45 3c 2f 62 3e 20 28 3c 69 <b>FALSE</b> (<i
1b50: 3e 64 65 66 61 75 6c 74 20 76 61 6c 75 65 3c 2f >default value</
1b60: 69 3e 29 20 61 20 4d 75 6c 74 69 50 6f 6c 79 67 i>) a MultiPolyg
1b70: 6f 6e 20 77 69 6c 6c 20 62 65 20 72 65 74 75 72 on will be retur
1b80: 6e 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 69 ned.</li>..<li>i
1b90: 66 20 3c 62 3e 54 52 55 45 3c 2f 62 3e 20 61 20 f <b>TRUE</b> a
1ba0: 4d 75 6c 74 69 4c 69 6e 65 73 74 72 69 6e 67 20 MultiLinestring
1bb0: 77 69 6c 6c 20 62 65 20 72 65 74 75 72 6e 65 64 will be returned
1bc0: 20 28 73 69 6d 70 6c 79 20 72 65 70 72 65 73 65 (simply represe
1bd0: 6e 74 69 6e 67 20 74 68 65 20 74 72 69 61 6e 67 nting the triang
1be0: 6c 65 73 20 65 64 67 65 73 29 2e 3c 2f 6c 69 3e les edges).</li>
1bf0: 0d 0a 3c 2f 75 6c 3e 3c 2f 6c 69 3e 0d 0a 3c 6c ..</ul></li>..<l
1c00: 69 3e 74 68 65 20 6f 70 74 69 6f 6e 61 6c 20 3c i>the optional <
1c10: 62 3e 74 6f 6c 65 72 61 6e 63 65 3c 2f 62 3e 20 b>tolerance</b>
1c20: 61 72 67 75 6d 65 6e 74 20 69 73 20 69 6e 74 65 argument is inte
1c30: 6e 64 65 64 20 74 6f 20 6e 6f 72 6d 61 6c 69 7a nded to normaliz
1c40: 65 20 74 68 65 20 69 6e 70 75 74 20 70 6f 69 6e e the input poin
1c50: 74 2d 73 65 74 2c 20 73 75 70 70 72 65 73 73 69 t-set, suppressi
1c60: 6e 67 20 72 65 70 65 61 74 65 64 20 28 6f 72 20 ng repeated (or
1c70: 74 6f 6f 20 6d 75 63 68 20 63 6c 6f 73 65 29 20 too much close)
1c80: 70 6f 69 6e 74 73 2e 0d 0a 42 79 20 64 65 66 61 points...By defa
1c90: 75 6c 74 20 61 20 3c 62 3e 30 2e 30 3c 2f 62 3e ult a <b>0.0</b>
1ca0: 20 74 6f 6c 65 72 61 6e 63 65 20 77 69 6c 6c 20 tolerance will
1cb0: 62 65 20 61 73 73 75 6d 65 64 2e 3c 2f 6c 69 3e be assumed.</li>
1cc0: 0d 0a 3c 2f 75 6c 3e 3c 2f 74 64 3e 3c 2f 74 72 ..</ul></td></tr
1cd0: 3e 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 74 61 62 6c ></table>..<tabl
1ce0: 65 20 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 e cellspacing="4
1cf0: 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 34 " cellpadding="4
1d00: 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 74 ">..<tr><td>..<t
1d10: 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 able bgcolor="#f
1d20: 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 0f0f0" cellspaci
1d30: 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 ng="4" cellpaddi
1d40: 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 ng="8">..<tr><td
1d50: 3e 0d 0a 3c 62 3e 53 45 4c 45 43 54 20 53 54 5f >..<b>SELECT ST_
1d60: 44 65 6c 61 75 6e 61 79 54 72 69 61 6e 67 75 6c DelaunayTriangul
1d70: 61 74 69 6f 6e 28 53 54 5f 43 6f 6c 6c 65 63 74 ation(ST_Collect
1d80: 28 67 65 6f 6d 65 74 72 79 29 29 3c 62 72 3e 0d (geometry))<br>.
1d90: 0a 46 52 4f 4d 20 69 74 61 6c 79 5f 70 6f 70 75 .FROM italy_popu
1da0: 6c 61 74 65 64 5f 70 6c 61 63 65 73 3b 3c 2f 62 lated_places;</b
1db0: 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c >..</td></tr>..<
1dc0: 2f 74 61 62 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 /table><br>..Thi
1dd0: 73 20 53 51 4c 20 71 75 65 72 79 20 77 69 6c 6c s SQL query will
1de0: 20 72 65 74 75 72 6e 20 61 20 44 65 6c 61 75 6e return a Delaun
1df0: 61 79 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e ay Triangulation
1e00: 20 62 61 73 65 64 20 6f 6e 20 49 74 61 6c 79 27 based on Italy'
1e10: 73 20 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 s populated plac
1e20: 65 73 20 28 61 62 6f 75 74 20 38 2c 30 30 30 2b es (about 8,000+
1e30: 20 50 6f 69 6e 74 73 29 2e 3c 62 72 3e 0d 0a 54 Points).<br>..T
1e40: 68 65 20 76 69 73 75 61 6c 20 65 78 61 6d 70 6c he visual exampl
1e50: 65 20 73 69 6d 70 6c 79 20 63 6f 76 65 72 73 20 e simply covers
1e60: 54 75 73 63 61 6e 79 2c 20 73 6f 20 74 68 65 20 Tuscany, so the
1e70: 65 6e 73 75 72 65 20 61 6e 20 65 61 73 79 20 72 ensure an easy r
1e80: 65 61 64 61 62 69 6c 69 74 79 2e 20 0d 0a 3c 2f eadability. ..</
1e90: 74 64 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f td>..<td><img bo
1ea0: 72 64 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 rder="1" src="ht
1eb0: 74 70 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 tp://www.gaia-gi
1ec0: 73 2e 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 s.it/gaia-sins/w
1ed0: 72 69 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 64 rite-view-pics/d
1ee0: 65 6c 61 75 6e 61 79 2e 70 6e 67 22 20 61 6c 74 elaunay.png" alt
1ef0: 3d 22 64 65 6c 61 75 6e 61 79 20 74 72 69 61 6e ="delaunay trian
1f00: 67 75 6c 61 74 69 6f 6e 22 3e 3c 2f 74 64 3e 3c gulation"></td><
1f10: 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 0d 0a /tr>..</table>..
1f20: 3c 62 72 3e 3c 68 72 3e 0d 0a 3c 68 33 3e 56 6f <br><hr>..<h3>Vo
1f30: 72 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 73 3c 2f ronoj Diagrams</
1f40: 68 33 3e 0d 0a 3c 74 61 62 6c 65 20 63 65 6c 6c h3>..<table cell
1f50: 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c spacing="4" cell
1f60: 70 61 64 64 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 padding="4">..<t
1f70: 72 3e 3c 74 64 20 61 6c 69 67 6e 3d 22 63 65 6e r><td align="cen
1f80: 74 65 72 22 3e 3c 69 6d 67 20 62 6f 72 64 65 72 ter"><img border
1f90: 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f ="1" src="http:/
1fa0: 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 /www.gaia-gis.it
1fb0: 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 /gaia-sins/write
1fc0: 2d 76 69 65 77 2d 70 69 63 73 2f 76 6f 72 6f 6e -view-pics/voron
1fd0: 6f 6a 2d 31 2e 70 6e 67 22 20 61 6c 74 3d 22 76 oj-1.png" alt="v
1fe0: 6f 72 6f 6e 6f 6a 2d 64 65 6c 61 75 6e 61 79 20 oronoj-delaunay
1ff0: 72 65 6c 61 74 69 6f 6e 73 68 69 70 22 3e 0d 0a relationship">..
2000: 3c 2f 74 64 3e 3c 74 64 3e 0d 0a 54 68 65 20 3c </td><td>..The <
2010: 62 3e 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 61 b>Voronoj Diagra
2020: 6d 3c 2f 62 3e 20 73 69 6d 70 6c 79 20 69 73 20 m</b> simply is
2030: 74 68 65 20 3c 69 3e 3c 75 3e 64 75 61 6c 20 67 the <i><u>dual g
2040: 72 61 70 68 3c 2f 75 3e 3c 2f 69 3e 20 6f 66 20 raph</u></i> of
2050: 74 68 65 20 3c 62 3e 44 65 6c 61 75 6e 61 79 20 the <b>Delaunay
2060: 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 3c 2f 62 Triangulation</b
2070: 3e 2e 0d 0a 41 20 56 6f 72 6f 6e 6f 6a 20 44 69 >...A Voronoj Di
2080: 61 67 72 61 6d 20 73 74 69 6c 6c 20 69 73 20 61 agram still is a
2090: 20 74 65 73 73 65 6c 6c 61 74 69 6f 6e 2c 20 61 tessellation, a
20a0: 6e 64 20 63 65 6c 6c 73 20 69 6e 20 61 20 56 6f nd cells in a Vo
20b0: 72 6f 6e 6f 6a 20 63 61 6e 20 68 61 76 65 20 61 ronoj can have a
20c0: 6e 79 20 61 72 62 69 74 72 61 72 79 20 70 6f 6c ny arbitrary pol
20d0: 79 67 6f 6e 61 6c 20 28 69 72 72 65 67 75 6c 61 ygonal (irregula
20e0: 72 29 20 73 68 61 70 65 2e 3c 62 72 3e 3c 62 72 r) shape.<br><br
20f0: 3e 0d 0a 54 68 69 73 20 66 69 67 75 72 65 20 63 >..This figure c
2100: 6c 65 61 72 6c 79 20 73 68 6f 77 73 20 74 68 65 learly shows the
2110: 20 72 65 6c 61 74 69 6f 6e 20 6a 6f 69 6e 69 6e relation joinin
2120: 67 20 74 68 65 20 44 65 6c 61 75 6e 61 79 20 54 g the Delaunay T
2130: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 61 6e 64 riangulation and
2140: 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 the correspondi
2150: 6e 67 20 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 ng Voronoj Diagr
2160: 61 6d 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 45 61 63 am.<br><br>..Eac
2170: 68 20 73 69 6e 67 6c 65 20 56 6f 72 6f 6e 6f 6a h single Voronoj
2180: 27 73 20 63 65 6c 6c 20 69 73 20 6f 62 74 61 69 's cell is obtai
2190: 6e 65 64 20 62 79 20 63 6f 6e 6e 65 63 74 69 6e ned by connectin
21a0: 67 20 61 6c 6c 20 74 68 65 20 3c 69 3e 63 69 72 g all the <i>cir
21b0: 63 75 6d 63 65 6e 74 65 72 73 3c 2f 69 3e 20 6f cumcenters</i> o
21c0: 66 20 61 64 6a 61 63 65 6e 74 20 44 65 6c 61 75 f adjacent Delau
21d0: 6e 61 79 27 73 20 74 72 69 61 6e 67 6c 65 73 3b nay's triangles;
21e0: 20 63 6f 6e 73 65 71 75 65 6e 74 6c 79 20 65 61 consequently ea
21f0: 63 68 20 56 6f 72 6f 6e 6f 6a 20 63 65 6c 6c 20 ch Voronoj cell
2200: 73 75 72 65 6c 79 20 63 6f 6e 74 61 69 6e 73 20 surely contains
2210: 6f 6e 65 20 28 61 6e 64 20 6f 6e 6c 79 20 6f 6e one (and only on
2220: 65 29 20 44 65 6c 61 75 6e 61 79 27 73 20 6e 6f e) Delaunay's no
2230: 64 65 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 65 de.<br><br>..The
2240: 20 63 65 6c 6c 20 69 6e 20 74 68 65 20 56 6f 72 cell in the Vor
2250: 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 20 70 72 65 onoj Diagram pre
2260: 73 65 6e 74 73 20 61 6e 20 69 6e 74 65 72 65 73 sents an interes
2270: 74 69 6e 67 20 70 72 6f 70 65 72 74 79 3a 20 61 ting property: a
2280: 6c 6c 20 70 6f 69 6e 74 73 20 66 61 6c 6c 69 6e ll points fallin
2290: 67 20 77 69 74 68 69 6e 20 74 68 65 20 73 61 6d g within the sam
22a0: 65 20 63 65 6c 6c 20 61 72 65 20 65 6e 73 75 72 e cell are ensur
22b0: 65 64 20 74 6f 20 62 65 20 6e 65 61 72 65 73 74 ed to be nearest
22c0: 20 74 6f 20 74 68 65 20 44 65 6c 61 75 6e 61 79 to the Delaunay
22d0: 27 73 20 6e 6f 64 65 20 70 6c 61 63 65 64 20 6f 's node placed o
22e0: 6e 20 74 68 65 20 63 65 6c 6c 20 69 74 73 65 6c n the cell itsel
22f0: 66 20 74 68 61 6e 20 74 6f 20 61 6e 79 20 6f 74 f than to any ot
2300: 68 65 72 20 44 65 6c 61 75 6e 61 79 27 73 20 6e her Delaunay's n
2310: 6f 64 65 20 70 6c 61 63 65 64 20 69 6e 20 61 20 ode placed in a
2320: 64 69 66 66 65 72 65 6e 74 20 63 65 6c 6c 2e 3c different cell.<
2330: 62 72 3e 3c 62 72 3e 0d 0a 53 6f 20 74 68 65 20 br><br>..So the
2340: 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 20 Voronoj Diagram
2350: 69 73 20 61 20 76 65 72 79 20 65 66 66 65 63 74 is a very effect
2360: 69 76 65 20 63 6f 6e 63 65 70 74 75 61 6c 20 74 ive conceptual t
2370: 6f 6f 6c 20 61 6c 6c 6f 77 69 6e 67 20 74 6f 20 ool allowing to
2380: 64 69 76 69 64 65 20 61 6e 20 61 72 62 69 74 72 divide an arbitr
2390: 61 72 79 20 73 70 61 63 65 20 72 65 67 69 6f 6e ary space region
23a0: 20 69 6e 74 6f 20 6d 61 6e 79 20 3c 69 3e 72 61 into many <i>ra
23b0: 74 69 6f 6e 61 6c 6c 79 20 64 65 66 69 6e 65 64 tionally defined
23c0: 3c 2f 69 3e 20 63 65 6c 6c 73 2c 20 61 6e 64 20 </i> cells, and
23d0: 69 73 20 74 68 75 73 20 77 69 64 65 6c 79 20 75 is thus widely u
23e0: 73 65 64 20 6f 6e 20 6d 61 6e 79 20 61 70 70 6c sed on many appl
23f0: 69 63 61 74 69 76 65 20 66 69 65 6c 64 73 20 62 icative fields b
2400: 61 73 65 64 20 6f 6e 20 43 6f 6d 70 75 74 61 74 ased on Computat
2410: 69 6f 6e 61 6c 20 47 65 6f 6d 65 74 72 79 2e 0d ional Geometry..
2420: 0a 54 68 69 73 20 6f 62 76 69 6f 75 73 6c 79 20 .This obviously
2430: 69 6e 63 6c 75 64 69 6e 67 20 47 65 6f 67 72 61 including Geogra
2440: 70 68 79 20 69 74 73 65 6c 66 2e 3c 62 72 3e 3c phy itself.<br><
2450: 62 72 3e 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 br>..<a href="ht
2460: 74 70 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 tp://en.wikipedi
2470: 61 2e 6f 72 67 2f 77 69 6b 69 2f 56 6f 72 6f 6e a.org/wiki/Voron
2480: 6f 69 5f 74 65 73 73 65 6c 6c 61 74 69 6f 6e 22 oi_tessellation"
2490: 3e 72 65 61 64 20 6d 6f 72 65 3c 2f 61 3e 0d 0a >read more</a>..
24a0: 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e </td></tr>..<tr>
24b0: 3c 74 64 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 <td align="cente
24c0: 72 22 3e 0d 0a 3c 69 6d 67 20 62 6f 72 64 65 72 r">..<img border
24d0: 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f ="1" src="http:/
24e0: 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 /www.gaia-gis.it
24f0: 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 /gaia-sins/write
2500: 2d 76 69 65 77 2d 70 69 63 73 2f 76 6f 72 6f 6e -view-pics/voron
2510: 6f 6a 2d 6f 70 65 6e 2e 70 6e 67 22 20 61 6c 74 oj-open.png" alt
2520: 3d 22 76 6f 72 6f 6e 6f 6a 20 6f 70 65 6e 22 3e ="voronoj open">
2530: 20 0d 0a 3c 2f 74 64 3e 3c 74 64 3e 0d 0a 3c 75 ..</td><td>..<u
2540: 3e 50 6c 65 61 73 65 20 6e 6f 74 65 3c 2f 75 3e >Please note</u>
2550: 3a 20 61 6e 79 20 56 6f 72 6f 6e 6f 6a 20 44 69 : any Voronoj Di
2560: 61 67 72 61 6d 20 77 69 6c 6c 20 61 6c 77 61 79 agram will alway
2570: 73 20 70 72 65 73 65 6e 74 20 61 6e 20 75 6e 70 s present an unp
2580: 6c 65 61 73 61 6e 74 20 63 6f 6d 70 6c 69 63 61 leasant complica
2590: 74 69 6f 6e 3b 20 77 68 65 6e 20 72 65 61 63 68 tion; when reach
25a0: 69 6e 67 20 74 68 65 20 65 78 74 65 72 69 6f 72 ing the exterior
25b0: 20 62 6f 75 6e 64 61 72 79 20 6f 66 20 74 68 65 boundary of the
25c0: 20 69 6e 70 75 74 20 70 6f 69 6e 74 2d 73 65 74 input point-set
25d0: 2c 20 74 68 65 72 65 20 61 72 65 6e 27 74 20 65 , there aren't e
25e0: 6e 6f 75 67 68 20 70 6f 69 6e 74 73 20 61 6c 6c nough points all
25f0: 6f 77 69 6e 67 20 74 6f 20 70 72 6f 70 65 72 6c owing to properl
2600: 79 20 63 6c 6f 73 65 20 61 20 63 65 6c 6c 2e 3c y close a cell.<
2610: 62 72 3e 0d 0a 41 6e 64 20 63 6f 6e 73 65 71 75 br>..And consequ
2620: 65 6e 74 6c 79 20 6d 61 6e 79 20 63 65 6c 6c 73 ently many cells
2630: 20 6c 61 79 69 6e 67 20 6e 65 61 72 20 74 6f 20 laying near to
2640: 74 68 65 20 65 78 74 65 72 69 6f 72 20 62 6f 75 the exterior bou
2650: 6e 64 61 72 79 20 61 63 74 75 61 6c 6c 79 20 61 ndary actually a
2660: 72 65 20 3c 69 3e 6f 70 65 6e 20 63 65 6c 6c 73 re <i>open cells
2670: 3c 2f 69 3e 2c 20 70 72 65 73 65 6e 74 69 6e 67 </i>, presenting
2680: 20 65 64 67 65 73 20 67 6f 69 6e 67 20 64 69 72 edges going dir
2690: 65 63 74 6c 79 20 74 6f 20 74 68 65 20 3c 69 3e ectly to the <i>
26a0: 69 6e 66 69 6e 69 74 65 3c 2f 69 3e 2e 3c 62 72 infinite</i>.<br
26b0: 3e 3c 62 72 3e 0d 0a 54 68 65 20 64 69 72 65 63 ><br>..The direc
26c0: 74 69 6f 6e 73 20 6f 66 20 73 75 63 68 20 65 64 tions of such ed
26d0: 67 65 73 20 61 72 65 20 61 62 73 6f 6c 75 74 65 ges are absolute
26e0: 6c 79 20 77 65 6c 6c 20 64 65 74 65 72 6d 69 6e ly well determin
26f0: 65 64 3b 20 62 75 74 20 61 73 73 69 67 6e 69 6e ed; but assignin
2700: 67 20 74 68 65 6d 20 61 20 66 69 6e 69 74 65 20 g them a finite
2710: 6c 65 6e 67 74 68 20 69 73 6e 27 74 20 61 6c 6c length isn't all
2720: 6f 77 65 64 20 61 74 20 61 6c 6c 2e 20 41 6e 64 owed at all. And
2730: 20 63 6f 6e 73 65 71 75 65 6e 74 6c 79 20 69 73 consequently is
2740: 6e 27 74 20 70 6f 73 73 69 62 6c 65 20 64 65 66 n't possible def
2750: 69 6e 69 6e 67 20 61 20 70 6f 6c 79 67 6f 6e 20 ining a polygon
2760: 72 65 70 72 65 73 65 6e 74 69 6e 67 20 74 68 65 representing the
2770: 73 65 20 63 65 6c 6c 73 2e 3c 62 72 3e 3c 62 72 se cells.<br><br
2780: 3e 0d 0a 54 68 69 73 20 66 69 67 75 72 65 20 73 >..This figure s
2790: 68 6f 77 73 20 61 20 6c 69 6d 69 74 65 64 20 56 hows a limited V
27a0: 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 20 61 oronoj Diagram a
27b0: 6c 77 61 79 73 20 62 61 73 65 64 20 6f 6e 20 74 lways based on t
27c0: 68 65 20 73 61 6d 65 20 64 61 74 61 73 65 74 20 he same dataset
27d0: 61 73 20 61 62 6f 76 65 2c 20 62 75 74 20 74 68 as above, but th
27e0: 69 73 20 74 69 6d 65 20 69 6e 63 6c 75 64 69 6e is time includin
27f0: 67 20 6f 6e 6c 79 20 50 6f 70 75 6c 61 74 65 64 g only Populated
2800: 20 50 6c 61 63 65 73 20 6c 61 79 69 6e 67 20 6f Places laying o
2810: 6e 20 74 68 65 20 49 73 6c 61 6e 64 20 6f 66 20 n the Island of
2820: 45 6c 62 61 2e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 Elba...</td></tr
2830: 3e 0d 0a 3c 74 72 3e 3c 74 64 20 61 6c 69 67 6e >..<tr><td align
2840: 3d 22 63 65 6e 74 65 72 22 3e 0d 0a 3c 69 6d 67 ="center">..<img
2850: 20 62 6f 72 64 65 72 3d 22 31 22 20 73 72 63 3d border="1" src=
2860: 22 68 74 74 70 3a 2f 2f 77 77 77 2e 67 61 69 61 "http://www.gaia
2870: 2d 67 69 73 2e 69 74 2f 67 61 69 61 2d 73 69 6e -gis.it/gaia-sin
2880: 73 2f 77 72 69 74 65 2d 76 69 65 77 2d 70 69 63 s/write-view-pic
2890: 73 2f 76 6f 72 6f 6e 6f 6a 2d 66 72 61 6d 65 2e s/voronoj-frame.
28a0: 70 6e 67 22 20 61 6c 74 3d 22 76 6f 72 6f 6e 6f png" alt="vorono
28b0: 6a 20 66 72 61 6d 65 22 3e 20 0d 0a 3c 2f 74 64 j frame"> ..</td
28c0: 3e 3c 74 64 3e 0d 0a 41 6e 79 77 61 79 20 77 65 ><td>..Anyway we
28d0: 20 63 61 6e 20 75 73 65 66 75 6c 6c 79 20 61 70 can usefully ap
28e0: 70 6c 79 20 61 20 3c 69 3e 74 72 69 63 6b 3c 2f ply a <i>trick</
28f0: 69 3e 20 65 66 66 65 63 74 69 76 65 6c 79 20 61 i> effectively a
2900: 6c 6c 6f 77 69 6e 67 20 74 6f 20 65 6e 73 75 72 llowing to ensur
2910: 65 20 74 68 61 74 20 61 6c 6c 20 63 65 6c 6c 73 e that all cells
2920: 20 69 6e 20 61 20 56 6f 72 6f 6e 6f 6a 20 77 69 in a Voronoj wi
2930: 6c 6c 20 62 65 20 70 72 6f 70 65 72 6c 79 20 3c ll be properly <
2940: 69 3e 63 6c 6f 73 65 64 3c 2f 69 3e 2e 3c 62 72 i>closed</i>.<br
2950: 3e 3c 62 72 3e 0d 0a 57 65 20 73 69 6d 70 6c 79 ><br>..We simply
2960: 20 68 61 76 65 20 74 6f 20 63 6f 6e 73 74 72 61 have to constra
2970: 69 6e 20 74 68 65 20 56 6f 72 6f 6e 6f 6a 20 44 in the Voronoj D
2980: 69 61 67 72 61 6d 20 77 69 74 68 69 6e 20 61 20 iagram within a
2990: 72 65 63 74 61 6e 67 75 6c 61 72 20 66 72 61 6d rectangular fram
29a0: 65 20 6f 66 20 61 72 62 69 74 72 61 72 79 20 73 e of arbitrary s
29b0: 69 7a 65 2c 20 74 68 65 6e 20 63 6f 6d 70 75 74 ize, then comput
29c0: 69 6e 67 20 74 68 65 20 69 6e 74 65 72 73 65 63 ing the intersec
29d0: 74 69 6f 6e 73 20 62 65 74 77 65 65 6e 20 69 6e tions between in
29e0: 66 69 6e 69 74 65 20 6c 69 6e 65 73 20 61 6e 64 finite lines and
29f0: 20 74 68 65 20 66 72 61 6d 65 20 69 74 73 65 6c the frame itsel
2a00: 66 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 69 73 f.<br><br>..This
2a10: 20 66 69 67 75 72 65 20 73 68 6f 77 73 20 74 68 figure shows th
2a20: 65 20 73 61 6d 65 20 56 6f 72 6f 6e 6f 6a 20 61 e same Voronoj a
2a30: 73 20 62 65 66 6f 72 65 2c 20 74 68 69 73 20 74 s before, this t
2a40: 69 6d 65 20 6f 70 70 6f 72 74 75 6e 65 6c 79 20 ime opportunely
2a50: 66 72 61 6d 65 64 3b 20 61 73 20 79 6f 75 20 63 framed; as you c
2a60: 61 6e 20 65 61 73 69 6c 79 20 6e 6f 74 69 63 65 an easily notice
2a70: 2c 20 6e 6f 77 20 61 6c 6c 20 63 65 6c 6c 73 20 , now all cells
2a80: 61 72 65 20 73 75 72 65 6c 79 20 63 6c 6f 73 65 are surely close
2a90: 64 20 61 6e 64 20 63 61 6e 20 62 65 20 73 61 66 d and can be saf
2aa0: 65 6c 79 20 62 65 20 72 65 70 72 65 73 65 6e 74 ely be represent
2ab0: 65 64 20 62 79 20 61 20 77 65 6c 6c 20 64 65 66 ed by a well def
2ac0: 69 6e 65 64 20 70 6f 6c 79 67 6f 6e 2e 3c 62 72 ined polygon.<br
2ad0: 3e 3c 62 72 3e 0d 0a 54 68 65 20 73 69 7a 65 20 ><br>..The size
2ae0: 28 61 6b 61 20 65 78 74 65 6e 74 29 20 6f 66 20 (aka extent) of
2af0: 74 68 65 20 66 72 61 6d 65 20 69 73 20 61 62 73 the frame is abs
2b00: 6f 6c 75 74 65 6c 79 20 61 72 62 69 74 72 61 72 olutely arbitrar
2b10: 79 2c 20 61 6e 64 20 63 61 6e 20 62 65 20 66 72 y, and can be fr
2b20: 65 65 6c 79 20 73 65 74 20 61 73 20 79 6f 75 20 eely set as you
2b30: 77 69 73 68 20 62 65 74 74 65 72 20 61 63 63 6f wish better acco
2b40: 72 64 69 6e 67 6c 79 20 74 6f 20 79 6f 75 72 20 rdingly to your
2b50: 73 70 65 63 69 66 69 63 20 72 65 71 75 69 72 65 specific require
2b60: 6d 65 6e 74 73 2e 3c 62 72 3e 0d 0a 3c 75 3e 50 ments.<br>..<u>P
2b70: 6c 65 61 73 65 20 6e 6f 74 69 63 65 3c 2f 75 3e lease notice</u>
2b80: 3a 20 74 68 65 20 62 6c 75 65 20 61 6e 64 20 74 : the blue and t
2b90: 68 65 20 72 65 64 20 66 72 61 6d 65 20 68 61 76 he red frame hav
2ba0: 65 20 61 20 73 74 72 6f 6e 67 6c 79 20 64 69 66 e a strongly dif
2bb0: 66 65 72 65 6e 74 20 65 78 74 65 6e 74 2c 20 62 ferent extent, b
2bc0: 75 74 20 62 6f 74 68 20 74 68 65 6d 20 68 61 76 ut both them hav
2bd0: 65 20 74 68 65 20 73 61 6d 65 20 69 64 65 6e 74 e the same ident
2be0: 69 63 61 6c 20 6f 76 65 72 61 6c 6c 20 73 68 61 ical overall sha
2bf0: 70 65 2e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d pe...</td></tr>.
2c00: 0a 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 61 20 68 72 .</table>..<a hr
2c10: 65 66 3d 22 68 74 74 70 3a 2f 2f 74 72 61 63 2e ef="http://trac.
2c20: 6f 73 67 65 6f 2e 6f 72 67 2f 67 65 6f 73 2f 22 osgeo.org/geos/"
2c30: 3e 47 45 4f 53 20 33 2e 34 2e 30 3c 2f 61 3e 20 >GEOS 3.4.0</a>
2c40: 77 69 6c 6c 20 6e 6f 74 20 64 69 72 65 63 74 6c will not directl
2c50: 79 20 73 75 70 70 6f 72 74 20 56 6f 72 6f 6e 6f y support Vorono
2c60: 6a 3b 20 73 6f 20 74 68 65 20 53 70 61 74 69 61 j; so the Spatia
2c70: 4c 69 74 65 20 6f 77 6e 20 73 75 70 70 6f 72 74 Lite own support
2c80: 20 69 73 20 62 61 73 65 64 20 6f 6e 20 61 6e 20 is based on an
2c90: 6f 72 69 67 69 6e 61 6c 20 69 6d 70 6c 65 6d 65 original impleme
2ca0: 6e 74 61 74 69 6f 6e 20 28 62 61 73 65 64 20 69 ntation (based i
2cb0: 6e 20 74 75 72 6e 20 6f 6e 20 74 68 65 20 44 65 n turn on the De
2cc0: 6c 61 75 6e 61 79 20 73 75 70 70 6f 72 74 20 6d launay support m
2cd0: 61 64 65 20 61 76 61 69 6c 61 62 6c 65 20 62 79 ade available by
2ce0: 20 47 45 4f 53 29 2e 3c 62 72 3e 3c 62 72 3e 0d GEOS).<br><br>.
2cf0: 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d .<table bgcolor=
2d00: 22 23 66 30 66 30 66 30 22 20 63 65 6c 6c 73 70 "#f0f0f0" cellsp
2d10: 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 acing="4" cellpa
2d20: 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e dding="8">..<tr>
2d30: 3c 74 64 3e 0d 0a 3c 69 3e 70 72 6f 74 6f 74 79 <td>..<i>prototy
2d40: 70 65 3c 2f 69 3e 3a 3c 68 72 3e 0d 0a 53 54 5f pe</i>:<hr>..ST_
2d50: 56 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 20 VoronojDiagram(
2d60: 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 input <i>Geometr
2d70: 79 3c 2f 69 3e 20 29 20 3a 20 76 6f 72 6f 6e 6f y</i> ) : vorono
2d80: 6a 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 j <i>Geometry</i
2d90: 3e 3c 62 72 3e 0d 0a 53 54 5f 56 6f 72 6f 6e 6f ><br>..ST_Vorono
2da0: 6a 44 69 61 67 72 61 6d 28 20 69 6e 70 75 74 20 jDiagram( input
2db0: 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 2c <i>Geometry</i>,
2dc0: 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c 69 3e 62 edges_only <i>b
2dd0: 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 29 20 3a 20 76 oolean</i> ) : v
2de0: 6f 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 74 oronoj <i>Geomet
2df0: 72 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 56 ry</i><br>..ST_V
2e00: 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 20 69 oronojDiagram( i
2e10: 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 nput <i>Geometry
2e20: 3c 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 </i>, edges_only
2e30: 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c <i>boolean</i>,
2e40: 20 65 78 74 72 61 5f 66 72 61 6d 65 5f 73 69 7a extra_frame_siz
2e50: 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 e <i>double prec
2e60: 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 76 6f ision</i> ) : vo
2e70: 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 74 72 ronoj <i>Geometr
2e80: 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 56 6f y</i><br>..ST_Vo
2e90: 72 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 20 69 6e ronojDiagram( in
2ea0: 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c put <i>Geometry<
2eb0: 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 /i>, edges_only
2ec0: 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 <i>boolean</i>,
2ed0: 65 78 74 72 61 5f 66 72 61 6d 65 5f 73 69 7a 65 extra_frame_size
2ee0: 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 69 <i>double preci
2ef0: 73 69 6f 6e 3c 2f 69 3e 2c 20 74 6f 6c 65 72 61 sion</i>, tolera
2f00: 6e 63 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 nce <i>double pr
2f10: 65 63 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 ecision</i> ) :
2f20: 76 6f 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 voronoj <i>Geome
2f30: 74 72 79 3c 2f 69 3e 0d 0a 3c 2f 74 64 3e 3c 2f try</i>..</td></
2f40: 74 72 3e 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 75 6c tr></table>..<ul
2f50: 3e 0d 0a 3c 6c 69 3e 74 68 65 20 3c 62 3e 69 6e >..<li>the <b>in
2f60: 70 75 74 3c 2f 62 3e 20 47 65 6f 6d 65 74 72 79 put</b> Geometry
2f70: 20 63 61 6e 20 62 65 20 6f 66 20 61 62 73 6f 6c can be of absol
2f80: 75 74 65 6c 79 20 61 72 62 69 74 72 61 72 79 20 utely arbitrary
2f90: 74 79 70 65 3b 20 61 6c 6c 20 4c 69 6e 65 73 74 type; all Linest
2fa0: 72 69 6e 67 73 20 61 6e 64 20 2f 20 6f 72 20 50 rings and / or P
2fb0: 6f 6c 79 67 6f 77 6e 73 20 77 69 6c 6c 20 65 76 olygowns will ev
2fc0: 65 6e 74 75 61 6c 6c 79 20 62 65 20 64 69 73 73 entually be diss
2fd0: 6f 6c 76 65 64 20 69 6e 74 6f 20 50 6f 69 6e 74 olved into Point
2fe0: 73 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 s corresponding
2ff0: 74 6f 20 76 65 72 74 69 63 65 73 2e 3c 62 72 3e to vertices.<br>
3000: 0d 0a 53 6f 20 61 66 74 65 72 20 61 6c 6c 20 53 ..So after all S
3010: 54 5f 56 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 6d T_VoronojDiagram
3020: 28 29 20 28 65 78 61 63 74 6c 79 20 61 73 20 53 () (exactly as S
3030: 54 5f 44 65 6c 61 75 6e 61 79 54 72 69 61 6e 67 T_DelaunayTriang
3040: 75 6c 61 74 69 6f 6e 29 20 77 69 6c 6c 20 61 6c ulation) will al
3050: 77 61 79 73 20 70 72 6f 63 65 73 73 20 61 20 4d ways process a M
3060: 75 6c 74 69 50 6f 69 6e 74 2e 3c 2f 6c 69 3e 0d ultiPoint.</li>.
3070: 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 69 6f 6e 61 .<li>the optiona
3080: 6c 20 3c 62 3e 65 64 67 65 73 5f 6f 6e 6c 79 3c l <b>edges_only<
3090: 2f 62 3e 20 61 72 67 75 6d 65 6e 74 20 77 69 6c /b> argument wil
30a0: 6c 20 62 65 20 69 6e 74 65 72 70 72 65 74 65 64 l be interpreted
30b0: 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 3c 75 6c 3e as follows:<ul>
30c0: 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 46 41 4c 53 ..<li>if <b>FALS
30d0: 45 3c 2f 62 3e 20 28 3c 69 3e 64 65 66 61 75 6c E</b> (<i>defaul
30e0: 74 20 76 61 6c 75 65 3c 2f 69 3e 29 20 61 20 4d t value</i>) a M
30f0: 75 6c 74 69 50 6f 6c 79 67 6f 6e 20 77 69 6c 6c ultiPolygon will
3100: 20 62 65 20 72 65 74 75 72 6e 65 64 2e 3c 2f 6c be returned.</l
3110: 69 3e 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 54 52 i>..<li>if <b>TR
3120: 55 45 3c 2f 62 3e 20 61 20 4d 75 6c 74 69 4c 69 UE</b> a MultiLi
3130: 6e 65 73 74 72 69 6e 67 20 77 69 6c 6c 20 62 65 nestring will be
3140: 20 72 65 74 75 72 6e 65 64 20 28 73 69 6d 70 6c returned (simpl
3150: 79 20 72 65 70 72 65 73 65 6e 74 69 6e 67 20 74 y representing t
3160: 68 65 20 74 72 69 61 6e 67 6c 65 73 20 65 64 67 he triangles edg
3170: 65 73 29 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e es).</li>..</ul>
3180: 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f </li>..<li>the o
3190: 70 74 69 6f 6e 61 6c 20 3c 62 3e 65 78 74 72 61 ptional <b>extra
31a0: 5f 66 72 61 6d 65 5f 73 69 7a 65 3c 2f 62 3e 20 _frame_size</b>
31b0: 61 6c 6c 6f 77 73 20 74 6f 20 66 72 65 65 6c 79 allows to freely
31c0: 20 73 65 74 20 74 68 65 20 65 78 74 65 6e 74 20 set the extent
31d0: 6f 66 20 74 68 65 20 66 72 61 6d 65 2e 3c 62 72 of the frame.<br
31e0: 3e 0d 0a 54 68 69 73 20 61 72 67 75 6d 65 6e 74 >..This argument
31f0: 20 69 73 20 69 6e 74 65 6e 64 65 64 20 61 73 20 is intended as
3200: 61 20 3c 69 3e 70 65 72 63 65 6e 74 3c 2f 69 3e a <i>percent</i>
3210: 20 69 6e 63 72 65 61 73 65 20 6f 66 20 74 68 65 increase of the
3220: 20 3c 69 3e 6e 61 74 75 72 61 6c 20 65 78 74 65 <i>natural exte
3230: 6e 74 3c 2f 69 3e 20 6f 66 20 56 6f 72 6f 6e 6f nt</i> of Vorono
3240: 6a 20 61 73 20 64 65 74 65 72 6d 69 6e 65 64 20 j as determined
3250: 62 79 20 65 76 61 6c 75 61 74 69 6e 67 20 61 6c by evaluating al
3260: 6c 20 44 65 6c 61 75 6e 61 79 27 73 20 6e 6f 64 l Delaunay's nod
3270: 65 73 20 61 6e 64 20 63 69 72 63 75 6d 63 65 6e es and circumcen
3280: 74 65 72 73 2e 3c 62 72 3e 0d 0a 42 79 20 64 65 ters.<br>..By de
3290: 66 61 75 6c 74 20 61 20 3c 62 3e 35 25 20 65 78 fault a <b>5% ex
32a0: 74 72 61 5f 66 72 61 6d 65 5f 73 69 7a 65 3c 2f tra_frame_size</
32b0: 62 3e 20 69 73 20 61 73 73 75 6d 65 64 2e 3c 2f b> is assumed.</
32c0: 6c 69 3e 20 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 li> ..<li>the op
32d0: 74 69 6f 6e 61 6c 20 3c 62 3e 74 6f 6c 65 72 61 tional <b>tolera
32e0: 6e 63 65 3c 2f 62 3e 20 61 72 67 75 6d 65 6e 74 nce</b> argument
32f0: 20 69 73 20 69 6e 74 65 6e 64 65 64 20 74 6f 20 is intended to
3300: 6e 6f 72 6d 61 6c 69 7a 65 20 74 68 65 20 69 6e normalize the in
3310: 70 75 74 20 70 6f 69 6e 74 2d 73 65 74 2c 20 73 put point-set, s
3320: 75 70 70 72 65 73 73 69 6e 67 20 72 65 70 65 61 uppressing repea
3330: 74 65 64 20 70 6f 69 6e 74 73 20 28 73 69 6d 70 ted points (simp
3340: 6c 79 20 75 73 65 64 20 77 68 65 6e 20 69 6e 74 ly used when int
3350: 65 72 6e 61 6c 6c 79 20 63 6f 6d 70 75 74 69 6e ernally computin
3360: 67 20 74 68 65 20 44 65 6c 61 75 6e 61 79 20 54 g the Delaunay T
3370: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 29 2e 0d 0a riangulation)...
3380: 42 79 20 64 65 66 61 75 6c 74 20 61 20 3c 62 3e By default a <b>
3390: 30 2e 30 3c 2f 62 3e 20 74 6f 6c 65 72 61 6e 63 0.0</b> toleranc
33a0: 65 20 77 69 6c 6c 20 62 65 20 61 73 73 75 6d 65 e will be assume
33b0: 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f d.</li>..</ul></
33c0: 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e td></tr></table>
33d0: 0d 0a 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 ..<table cellspa
33e0: 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 cing="4" cellpad
33f0: 64 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c ding="4">..<tr><
3400: 74 64 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f td>..<table bgco
3410: 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 lor="#f0f0f0" ce
3420: 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 llspacing="4" ce
3430: 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a llpadding="8">..
3440: 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 4c <tr><td>..<b>SEL
3450: 45 43 54 20 53 54 5f 56 6f 72 6f 6e 6f 6a 44 69 ECT ST_VoronojDi
3460: 61 67 72 61 6d 28 53 54 5f 43 6f 6c 6c 65 63 74 agram(ST_Collect
3470: 28 67 65 6f 6d 65 74 72 79 29 29 3c 62 72 3e 0d (geometry))<br>.
3480: 0a 46 52 4f 4d 20 69 74 61 6c 79 5f 70 6f 70 75 .FROM italy_popu
3490: 6c 61 74 65 64 5f 70 6c 61 63 65 73 3b 3c 2f 62 lated_places;</b
34a0: 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c >..</td></tr>..<
34b0: 2f 74 61 62 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 /table><br>..Thi
34c0: 73 20 53 51 4c 20 71 75 65 72 79 20 77 69 6c 6c s SQL query will
34d0: 20 72 65 74 75 72 6e 20 61 20 56 6f 72 6f 6e 6f return a Vorono
34e0: 6a 20 44 69 61 67 72 61 6d 20 62 61 73 65 64 20 j Diagram based
34f0: 6f 6e 20 49 74 61 6c 79 27 73 20 70 6f 70 75 6c on Italy's popul
3500: 61 74 65 64 20 70 6c 61 63 65 73 20 28 61 62 6f ated places (abo
3510: 75 74 20 38 2c 30 30 30 2b 20 50 6f 69 6e 74 73 ut 8,000+ Points
3520: 29 2e 3c 62 72 3e 0d 0a 54 68 65 20 76 69 73 75 ).<br>..The visu
3530: 61 6c 20 65 78 61 6d 70 6c 65 20 73 69 6d 70 6c al example simpl
3540: 79 20 63 6f 76 65 72 73 20 54 75 73 63 61 6e 79 y covers Tuscany
3550: 2c 20 73 6f 20 74 68 65 20 65 6e 73 75 72 65 20 , so the ensure
3560: 61 6e 20 65 61 73 79 20 72 65 61 64 61 62 69 6c an easy readabil
3570: 69 74 79 2e 3c 62 72 3e 0d 0a 41 6c 6c 20 3c 69 ity.<br>..All <i
3580: 3e 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 >populated place
3590: 73 3c 2f 69 3e 20 28 61 6b 61 20 63 65 6c 6c 20 s</i> (aka cell
35a0: 3c 69 3e 73 65 65 64 73 3c 2f 69 3e 29 20 61 72 <i>seeds</i>) ar
35b0: 65 20 65 78 70 6c 69 63 69 74 6c 79 20 72 65 70 e explicitly rep
35c0: 72 65 73 65 6e 74 65 64 2e 20 0d 0a 3c 2f 74 64 resented. ..</td
35d0: 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 >..<td><img bord
35e0: 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 er="1" src="http
35f0: 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e ://www.gaia-gis.
3600: 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 it/gaia-sins/wri
3610: 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 76 6f 72 te-view-pics/vor
3620: 6f 6e 6f 6a 2d 32 2e 70 6e 67 22 20 61 6c 74 3d onoj-2.png" alt=
3630: 22 76 6f 72 6f 6e 6f 6a 20 64 69 61 67 72 61 6d "voronoj diagram
3640: 22 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f "></td></tr>..</
3650: 74 61 62 6c 65 3e 0d 0a 3c 62 72 3e 3c 68 72 3e table>..<br><hr>
3660: 0d 0a 3c 68 33 3e 44 65 6c 61 75 6e 61 79 20 54 ..<h3>Delaunay T
3670: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 2c 20 43 6f riangulation, Co
3680: 6e 76 65 78 20 48 75 6c 6c 20 61 6e 64 20 43 6f nvex Hull and Co
3690: 6e 63 61 76 65 20 48 75 6c 6c 3c 2f 68 33 3e 0d ncave Hull</h3>.
36a0: 0a 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 63 .<table cellspac
36b0: 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 ing="4" cellpadd
36c0: 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c 74 ing="4">..<tr><t
36d0: 64 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 31 d><img border="1
36e0: 22 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 77 " src="http://ww
36f0: 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 61 w.gaia-gis.it/ga
3700: 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 69 ia-sins/write-vi
3710: 65 77 2d 70 69 63 73 2f 63 6f 6e 76 65 78 2e 70 ew-pics/convex.p
3720: 6e 67 22 20 61 6c 74 3d 22 64 65 6c 61 75 6e 61 ng" alt="delauna
3730: 79 2d 63 6f 6e 76 65 78 68 75 6c 6c 20 72 65 6c y-convexhull rel
3740: 61 74 69 6f 6e 73 68 69 70 22 3e 0d 0a 3c 2f 74 ationship">..</t
3750: 64 3e 3c 74 64 3e 0d 0a 41 6e 20 69 6e 74 65 72 d><td>..An inter
3760: 65 73 74 69 6e 67 20 70 6f 69 6e 74 20 61 62 73 esting point abs
3770: 6f 6c 75 74 65 6c 79 20 77 6f 72 74 68 20 74 6f olutely worth to
3780: 20 62 65 20 65 78 70 6c 69 63 69 74 6c 79 20 6e be explicitly n
3790: 6f 74 65 64 3a 20 74 68 65 20 62 6f 75 6e 64 61 oted: the bounda
37a0: 72 79 20 6f 66 20 61 6e 79 20 3c 62 3e 44 65 6c ry of any <b>Del
37b0: 61 75 6e 61 79 20 54 72 69 61 6e 67 75 6c 61 74 aunay Triangulat
37c0: 69 6f 6e 3c 2f 62 3e 20 65 78 61 63 74 6c 79 20 ion</b> exactly
37d0: 63 6f 72 72 65 73 70 6f 6e 64 73 20 74 6f 20 74 corresponds to t
37e0: 68 65 20 3c 62 3e 43 6f 6e 76 65 78 20 48 75 6c he <b>Convex Hul
37f0: 6c 3c 2f 62 3e 20 66 6f 72 20 74 68 65 20 73 61 l</b> for the sa
3800: 6d 65 20 69 6e 70 75 74 20 47 65 6f 6d 65 74 72 me input Geometr
3810: 79 2e 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 y...<a href="htt
3820: 70 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 p://en.wikipedia
3830: 2e 6f 72 67 2f 77 69 6b 69 2f 43 6f 6e 76 65 78 .org/wiki/Convex
3840: 5f 68 75 6c 6c 22 3e 72 65 61 64 20 6d 6f 72 65 _hull">read more
3850: 3c 2f 61 3e 3c 62 72 3e 3c 62 72 3e 0d 0a 41 6e </a><br><br>..An
3860: 64 20 74 68 69 73 20 69 6e 20 74 75 72 6e 20 6f d this in turn o
3870: 70 65 6e 73 20 74 68 65 20 77 61 79 20 74 6f 20 pens the way to
3880: 61 20 66 75 72 74 68 65 72 20 63 6f 6e 73 69 64 a further consid
3890: 65 72 61 74 69 6f 6e 3a 20 77 65 20 63 6f 75 6c eration: we coul
38a0: 64 20 70 75 72 70 6f 73 65 6c 79 20 73 69 6d 70 d purposely simp
38b0: 6c 69 66 79 20 61 20 44 65 6c 61 75 6e 61 79 20 lify a Delaunay
38c0: 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 73 6f Triangulation so
38d0: 20 74 6f 20 67 65 74 20 61 20 3c 62 3e 63 6f 6e to get a <b>con
38e0: 63 61 76 65 20 68 75 6c 6c 3c 2f 62 3e 2e 3c 62 cave hull</b>.<b
38f0: 72 3e 0d 0a 59 6f 75 20 63 61 6e 20 67 65 74 20 r>..You can get
3900: 6d 6f 72 65 20 65 78 74 65 6e 73 69 76 65 20 69 more extensive i
3910: 6e 66 6f 72 6d 61 74 69 6f 6e 73 20 61 62 6f 75 nformations abou
3920: 74 20 74 68 69 73 20 61 70 70 72 6f 61 63 68 20 t this approach
3930: 66 72 6f 6d 20 3c 61 20 68 72 65 66 3d 22 68 74 from <a href="ht
3940: 74 70 3a 2f 2f 67 72 61 73 73 2e 6f 73 67 65 6f tp://grass.osgeo
3950: 2e 6f 72 67 2f 77 69 6b 69 2f 43 72 65 61 74 65 .org/wiki/Create
3960: 5f 63 6f 6e 63 61 76 65 5f 68 75 6c 6c 22 3e 68 _concave_hull">h
3970: 65 72 65 3c 2f 61 3e 3c 62 72 3e 3c 62 72 3e 0d ere</a><br><br>.
3980: 0a 3c 75 3e 50 6c 65 61 73 65 20 6e 6f 74 65 20 .<u>Please note
3990: 77 65 6c 6c 3c 2f 75 3e 3a 20 74 68 65 20 3c 62 well</u>: the <b
39a0: 3e 63 6f 6e 76 65 78 20 68 75 6c 6c 3c 2f 62 3e >convex hull</b>
39b0: 20 63 6f 6e 63 65 70 74 20 63 6f 72 72 65 73 70 concept corresp
39c0: 6f 6e 64 73 20 74 6f 20 61 20 72 6f 62 75 73 74 onds to a robust
39d0: 20 61 6e 64 20 66 6f 72 6d 61 6c 20 6d 61 74 68 and formal math
39e0: 65 6d 61 74 69 63 61 6c 20 64 65 66 69 6e 69 74 ematical definit
39f0: 69 6f 6e 2e 20 4f 6e 20 74 68 65 20 6f 74 68 65 ion. On the othe
3a00: 72 20 73 69 64 65 20 74 68 65 20 3c 62 3e 63 6f r side the <b>co
3a10: 6e 63 61 76 65 20 68 75 6c 6c 3c 2f 62 3e 20 69 ncave hull</b> i
3a20: 73 20 61 20 6d 75 63 68 20 6d 6f 72 65 20 76 61 s a much more va
3a30: 67 75 65 20 61 6e 64 20 75 6e 64 65 74 65 72 6d gue and undeterm
3a40: 69 6e 65 64 20 6e 6f 74 69 6f 6e 2e 3c 62 72 3e ined notion.<br>
3a50: 0d 0a 54 68 65 72 65 20 69 73 20 6f 6e 65 20 61 ..There is one a
3a60: 6e 64 20 6f 6e 6c 79 20 6f 6e 65 20 43 6f 6e 76 nd only one Conv
3a70: 65 78 48 75 6c 6c 20 66 6f 72 20 61 20 67 69 76 exHull for a giv
3a80: 65 6e 20 47 65 6f 6d 65 74 72 79 3b 20 62 75 74 en Geometry; but
3a90: 20 6d 61 6e 79 20 43 6f 6e 63 61 76 65 48 75 6c many ConcaveHul
3aa0: 6c 73 20 61 72 65 20 70 6f 73 73 69 62 6c 65 2e ls are possible.
3ab0: 0d 0a 43 68 6f 6f 73 69 6e 67 20 74 68 65 20 6f ..Choosing the o
3ac0: 6e 65 20 6f 72 20 74 68 65 20 6f 74 68 65 72 20 ne or the other
3ad0: 69 73 20 6d 75 63 68 20 6d 6f 72 65 20 61 20 6d is much more a m
3ae0: 61 74 74 65 72 20 6f 66 20 70 65 72 73 6f 6e 61 atter of persona
3af0: 6c 20 74 61 73 74 65 20 74 68 61 6e 20 61 20 6d l taste than a m
3b00: 61 74 68 65 6d 61 74 69 63 61 6c 20 6f 70 65 72 athematical oper
3b10: 61 74 69 6f 6e 20 66 6f 72 6d 61 6c 6c 79 20 64 ation formally d
3b20: 65 66 69 6e 65 64 2e 3c 62 72 3e 0d 0a 43 6f 6d efined.<br>..Com
3b30: 70 75 74 69 6e 67 20 61 20 43 6f 6e 63 61 76 65 puting a Concave
3b40: 48 75 6c 6c 20 61 6c 77 61 79 73 20 69 73 20 61 Hull always is a
3b50: 6e 20 69 6e 68 65 72 65 6e 74 6c 79 20 61 72 62 n inherently arb
3b60: 69 74 72 61 72 79 20 61 6e 64 20 68 65 75 72 69 itrary and heuri
3b70: 73 74 69 63 20 70 72 6f 63 65 73 73 2e 0d 0a 3c stic process...<
3b80: 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c /td></tr>..<tr><
3b90: 74 64 3e 0d 0a 3c 68 34 3e 54 68 65 20 53 70 61 td>..<h4>The Spa
3ba0: 74 69 61 4c 69 74 65 27 73 20 6f 77 6e 20 61 70 tiaLite's own ap
3bb0: 70 72 6f 61 63 68 20 74 6f 20 43 6f 6e 63 61 76 proach to Concav
3bc0: 65 48 75 6c 6c 3c 2f 68 34 3e 0d 0a 3c 6f 6c 3e eHull</h4>..<ol>
3bd0: 0d 0a 3c 6c 69 3e 74 68 65 20 44 65 6c 61 75 6e ..<li>the Delaun
3be0: 61 79 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e ay Triangulation
3bf0: 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 corresponding t
3c00: 6f 20 74 68 65 20 69 6e 70 75 74 20 47 65 6f 6d o the input Geom
3c10: 65 74 72 79 20 77 69 6c 6c 20 62 65 20 63 6f 6d etry will be com
3c20: 70 75 74 65 64 20 66 69 72 73 74 2e 3c 2f 6c 69 puted first.</li
3c30: 3e 0d 0a 3c 6c 69 3e 74 68 65 6e 20 74 68 65 20 >..<li>then the
3c40: 73 74 61 74 69 73 74 69 63 61 6c 20 64 69 73 74 statistical dist
3c50: 72 69 62 75 74 69 6f 6e 20 6f 66 20 61 6c 6c 20 ribution of all
3c60: 74 72 69 61 6e 67 6c 65 20 65 64 67 65 27 73 20 triangle edge's
3c70: 6c 65 6e 67 74 68 73 20 77 69 6c 6c 20 62 65 20 lengths will be
3c80: 65 76 61 6c 75 61 74 65 64 2c 20 73 6f 20 74 6f evaluated, so to
3c90: 20 64 65 74 65 72 6d 69 6e 65 20 3c 62 3e 26 73 determine <b>&s
3ca0: 69 67 6d 61 3b 3c 2f 62 3e 20 28 61 6b 61 20 74 igma;</b> (aka t
3cb0: 68 65 20 3c 69 3e 73 74 61 6e 64 61 72 64 20 64 he <i>standard d
3cc0: 65 76 69 61 74 69 6f 6e 3c 2f 69 3e 29 3c 2f 6c eviation</i>)</l
3cd0: 69 3e 0d 0a 3c 6c 69 3e 61 20 73 65 63 6f 6e 64 i>..<li>a second
3ce0: 20 70 61 73 73 20 77 69 6c 6c 20 6e 6f 77 20 65 pass will now e
3cf0: 78 61 6d 69 6e 65 20 79 65 74 20 61 67 61 69 6e xamine yet again
3d00: 20 61 6c 6c 20 44 65 6c 61 75 6e 61 79 27 73 20 all Delaunay's
3d10: 74 72 69 61 6e 67 6c 65 73 3b 20 61 6e 79 20 74 triangles; any t
3d20: 72 69 61 6e 67 6c 65 20 70 72 65 73 65 6e 74 69 riangle presenti
3d30: 6e 67 20 61 74 20 6c 65 61 73 74 20 6f 6e 65 20 ng at least one
3d40: 65 64 67 65 20 6c 6f 6e 67 65 72 20 74 68 61 6e edge longer than
3d50: 20 3c 62 3e 26 73 69 67 6d 61 3b 20 2a 20 66 61 <b>σ * fa
3d60: 63 74 6f 72 3c 2f 62 3e 20 77 69 6c 6c 20 62 65 ctor</b> will be
3d70: 20 64 69 73 63 61 72 64 65 64 2e 3c 2f 6c 69 3e discarded.</li>
3d80: 0d 0a 3c 6c 69 3e 61 6e 64 20 66 69 6e 61 6c 6c ..<li>and finall
3d90: 79 20 61 6c 6c 20 66 69 6c 74 65 72 65 64 20 74 y all filtered t
3da0: 72 69 61 6e 67 6c 65 73 20 77 69 6c 6c 20 62 65 riangles will be
3db0: 20 64 69 73 73 6f 6c 76 65 64 20 73 6f 20 74 6f dissolved so to
3dc0: 20 66 6f 72 6d 20 74 68 65 20 43 6f 6e 63 61 76 form the Concav
3dd0: 65 48 75 6c 6c 20 74 6f 20 62 65 20 72 65 74 75 eHull to be retu
3de0: 72 6e 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 6f 6c rned.</li>..</ol
3df0: 3e 0d 0a 3c 75 3e 50 6c 65 61 73 65 20 6e 6f 74 >..<u>Please not
3e00: 65 3c 2f 75 3e 3a 20 62 79 20 73 65 74 74 69 6e e</u>: by settin
3e10: 67 20 61 6e 20 61 70 70 72 6f 70 72 69 61 74 65 g an appropriate
3e20: 20 76 61 6c 75 65 20 74 6f 20 3c 62 3e 66 61 63 value to <b>fac
3e30: 74 6f 72 3c 2f 62 3e 20 79 6f 75 20 63 61 6e 20 tor</b> you can
3e40: 66 72 65 65 6c 79 20 69 6e 66 6c 75 65 6e 63 65 freely influence
3e50: 20 68 6f 77 20 6d 75 63 68 20 3c 69 3e 61 67 67 how much <i>agg
3e60: 72 65 73 73 69 76 65 3c 2f 69 3e 20 74 68 65 20 ressive</i> the
3e70: 66 69 6c 74 65 72 69 6e 67 20 70 61 73 73 20 77 filtering pass w
3e80: 69 6c 6c 20 62 65 2e 3c 62 72 3e 0d 0a 41 64 6f ill be.<br>..Ado
3e90: 70 74 69 6e 67 20 61 20 76 65 72 79 20 68 69 67 pting a very hig
3ea0: 68 20 3c 62 3e 66 61 63 74 6f 72 3c 2f 62 3e 20 h <b>factor</b>
3eb0: 76 61 6c 75 65 20 70 72 61 63 74 69 63 61 6c 6c value practicall
3ec0: 79 20 6d 65 61 6e 73 20 61 70 70 6c 79 69 6e 67 y means applying
3ed0: 20 61 20 76 65 72 79 20 62 6c 61 6e 64 20 66 69 a very bland fi
3ee0: 6c 74 65 72 69 6e 67 20 28 76 65 72 79 20 66 65 ltering (very fe
3ef0: 77 20 74 72 69 61 6e 67 6c 65 73 20 77 69 6c 6c w triangles will
3f00: 20 62 65 20 64 69 73 63 61 72 64 65 64 2c 20 61 be discarded, a
3f10: 6e 64 20 79 6f 75 27 6c 6c 20 63 6f 6e 73 65 71 nd you'll conseq
3f20: 75 65 6e 74 6c 79 20 67 65 74 20 61 20 72 61 74 uently get a rat
3f30: 68 65 72 20 3c 69 3e 63 6f 6e 76 65 78 3c 2f 69 her <i>convex</i
3f40: 3e 20 73 68 61 70 65 29 2e 0d 0a 4f 6e 20 74 68 > shape)...On th
3f50: 65 20 6f 74 68 65 72 20 73 69 64 65 20 61 64 6f e other side ado
3f60: 70 74 69 6e 67 20 61 20 76 65 72 79 20 6c 6f 77 pting a very low
3f70: 20 3c 62 3e 66 61 63 74 6f 72 3c 2f 62 3e 20 76 <b>factor</b> v
3f80: 61 6c 75 65 73 20 77 69 6c 6c 20 61 70 70 6c 79 alues will apply
3f90: 20 61 20 76 65 72 79 20 73 74 72 6f 6e 67 20 66 a very strong f
3fa0: 69 6c 74 65 72 69 6e 67 20 28 6d 61 6e 79 20 74 iltering (many t
3fb0: 72 69 61 6e 67 6c 65 73 20 77 69 6c 6c 20 62 65 riangles will be
3fc0: 20 6e 6f 77 20 64 69 73 63 61 72 64 65 64 2c 20 now discarded,
3fd0: 61 6e 64 20 79 6f 75 27 6c 6c 20 67 65 74 20 61 and you'll get a
3fe0: 20 76 65 72 79 20 3c 69 3e 63 6f 6e 63 61 76 65 very <i>concave
3ff0: 3c 2f 69 3e 20 73 68 61 70 65 29 2e 3c 62 72 3e </i> shape).<br>
4000: 3c 62 72 3e 0d 0a 3c 75 3e 55 73 65 66 75 6c 20 <br>..<u>Useful
4010: 63 6f 6e 73 74 61 6e 74 73 3c 2f 75 3e 3a 20 61 constants</u>: a
4020: 73 73 75 6d 69 6e 67 20 61 20 70 65 72 66 65 63 ssuming a perfec
4030: 74 6c 79 20 6e 6f 72 6d 61 6c 20 64 69 73 74 72 tly normal distr
4040: 69 62 75 74 69 6f 6e 20 6f 66 20 65 64 67 65 20 ibution of edge
4050: 6c 65 6e 67 74 68 73 20 28 61 20 62 79 20 66 61 lengths (a by fa
4060: 72 20 75 6e 72 65 61 6c 69 73 74 69 63 20 61 73 r unrealistic as
4070: 73 75 6d 70 74 69 6f 6e 20 66 6f 72 20 72 65 61 sumption for rea
4080: 6c 20 77 6f 72 6c 64 20 64 61 74 61 73 65 74 73 l world datasets
4090: 29 2c 20 3c 62 3e 33 26 73 69 67 6d 61 3b 3c 2f ), <b>3σ</
40a0: 62 3e 20 77 69 6c 6c 20 69 6d 70 6c 79 20 73 75 b> will imply su
40b0: 70 70 72 65 73 73 69 6e 67 20 61 62 6f 75 74 20 ppressing about
40c0: 3c 62 3e 30 2e 31 25 3c 2f 62 3e 20 74 72 69 61 <b>0.1%</b> tria
40d0: 6e 67 6c 65 73 20 28 6f 6e 6c 79 20 74 68 65 20 ngles (only the
40e0: 66 65 77 20 6f 6e 65 73 20 70 72 65 73 65 6e 74 few ones present
40f0: 69 6e 67 20 61 62 6e 6f 72 6d 61 6c 6c 79 20 6c ing abnormally l
4100: 65 6e 67 74 68 79 20 65 64 67 65 73 29 2c 20 3c engthy edges), <
4110: 62 3e 32 26 73 69 67 6d 61 3b 3c 2f 62 3e 20 63 b>2σ</b> c
4120: 6f 72 72 65 73 70 6f 6e 64 73 20 74 6f 20 61 62 orresponds to ab
4130: 6f 75 74 20 3c 62 3e 32 2e 31 25 3c 2f 62 3e 2c out <b>2.1%</b>,
4140: 20 61 6e 64 20 3c 62 3e 31 26 73 69 67 6d 61 3b and <b>1σ
4150: 3c 2f 62 3e 20 72 6f 75 67 68 6c 79 20 63 6f 72 </b> roughly cor
4160: 72 65 73 70 6f 6e 64 73 20 74 6f 20 20 3c 62 3e responds to <b>
4170: 31 35 2e 38 25 3c 2f 62 3e 2e 3c 62 72 3e 0d 0a 15.8%</b>.<br>..
4180: 55 73 75 61 6c 6c 79 20 76 61 6c 75 65 73 20 72 Usually values r
4190: 61 6e 67 69 6e 67 20 62 65 74 77 65 65 6e 20 3c anging between <
41a0: 62 3e 33 26 73 69 67 6d 61 3b 3c 2f 62 3e 20 61 b>3σ</b> a
41b0: 6e 64 20 3c 62 3e 32 26 73 69 67 6d 61 3b 3c 2f nd <b>2σ</
41c0: 62 3e 20 61 72 65 20 74 68 65 20 6d 6f 73 74 20 b> are the most
41d0: 61 70 70 72 6f 70 72 69 61 74 65 20 74 6f 20 62 appropriate to b
41e0: 65 20 75 73 65 64 2e 3c 62 72 3e 3c 62 72 3e 0d e used.<br><br>.
41f0: 0a 54 68 65 20 66 69 67 75 72 65 20 73 68 6f 77 .The figure show
4200: 73 20 77 68 61 74 20 79 6f 75 20 63 61 6e 20 61 s what you can a
4210: 63 74 75 61 6c 6c 79 20 67 65 74 20 62 79 20 61 ctually get by a
4220: 70 70 6c 79 69 6e 67 20 61 20 3c 62 3e 33 26 73 pplying a <b>3&s
4230: 69 67 6d 61 3b 3c 2f 62 3e 20 66 69 6c 74 65 72 igma;</b> filter
4240: 69 6e 67 20 74 6f 20 49 74 61 6c 69 61 6e 20 50 ing to Italian P
4250: 6f 70 75 6c 61 74 65 64 20 50 6c 61 63 65 73 3b opulated Places;
4260: 20 66 6f 72 20 63 6c 61 72 69 74 79 20 61 6c 6c for clarity all
4270: 20 49 74 61 6c 69 61 6e 20 52 65 67 69 6f 6e 73 Italian Regions
4280: 20 61 72 65 20 72 65 70 72 65 73 65 6e 74 65 64 are represented
4290: 20 69 6e 20 79 65 6c 6c 6f 77 2c 20 61 6e 64 20 in yellow, and
42a0: 74 68 65 20 43 6f 6e 76 65 78 48 75 6c 6c 20 69 the ConvexHull i
42b0: 73 20 72 65 70 72 65 73 65 6e 74 65 64 20 69 6e s represented in
42c0: 20 62 6c 75 65 2e 20 54 68 65 20 43 6f 6e 63 61 blue. The Conca
42d0: 76 65 48 75 6c 6c 20 69 74 73 65 6c 66 20 69 73 veHull itself is
42e0: 20 72 65 70 72 65 73 65 6e 74 65 64 20 69 6e 20 represented in
42f0: 72 65 64 2e 0d 0a 3c 2f 74 64 3e 3c 74 64 3e 0d red...</td><td>.
4300: 0a 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 31 22 .<img border="1"
4310: 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 77 77 src="http://www
4320: 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 61 69 .gaia-gis.it/gai
4330: 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 69 65 a-sins/write-vie
4340: 77 2d 70 69 63 73 2f 63 6f 6e 63 61 76 65 33 2e w-pics/concave3.
4350: 70 6e 67 22 20 61 6c 74 3d 22 63 6f 6e 63 61 76 png" alt="concav
4360: 65 68 75 6c 6c 2d 31 22 3e 0d 0a 3c 2f 74 64 3e ehull-1">..</td>
4370: 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 0d </tr>..</table>.
4380: 0a 3c 62 72 3e 0d 0a 3c 62 3e 3c 75 3e 50 6c 65 .<br>..<b><u>Ple
4390: 61 73 65 20 6e 6f 74 65 20 77 65 6c 6c 3c 2f 75 ase note well</u
43a0: 3e 3c 2f 62 3e 3a 20 50 6f 73 74 47 49 53 20 73 ></b>: PostGIS s
43b0: 75 70 70 6f 72 74 73 20 69 74 73 20 6f 77 6e 20 upports its own
43c0: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f implementation o
43d0: 66 20 53 54 5f 43 6f 6e 63 61 76 65 48 75 6c 6c f ST_ConcaveHull
43e0: 28 29 2c 20 62 65 69 6e 67 20 62 61 73 65 64 20 (), being based
43f0: 6f 6e 20 61 20 63 6f 6d 70 6c 65 74 65 6c 79 20 on a completely
4400: 64 69 66 66 65 72 65 6e 74 20 61 70 70 72 6f 61 different approa
4410: 63 68 2e 20 59 6f 75 20 63 61 6e 20 67 65 74 20 ch. You can get
4420: 6d 6f 72 65 20 64 65 74 61 69 6c 73 20 66 72 6f more details fro
4430: 6d 20 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a m <a href="http:
4440: 2f 2f 77 77 77 2e 62 6f 73 74 6f 6e 67 69 73 2e //www.bostongis.
4450: 63 6f 6d 2f 70 6f 73 74 67 69 73 5f 63 6f 6e 63 com/postgis_conc
4460: 61 76 65 68 75 6c 6c 2e 73 6e 69 70 70 65 74 22 avehull.snippet"
4470: 3e 68 65 72 65 3c 2f 61 3e 3c 62 72 3e 0d 0a 50 >here</a><br>..P
4480: 6c 65 61 73 65 2c 20 64 6f 6e 27 74 20 62 65 20 lease, don't be
4490: 63 6f 6e 66 75 73 65 64 3a 20 74 68 65 20 53 70 confused: the Sp
44a0: 61 74 69 61 4c 69 74 65 20 61 6e 64 20 50 6f 73 atiaLite and Pos
44b0: 74 47 49 53 20 69 6d 70 6c 65 6d 65 6e 74 61 74 tGIS implementat
44c0: 69 6f 6e 73 20 61 72 65 20 63 6f 6d 70 6c 65 74 ions are complet
44d0: 65 6c 79 20 75 6e 72 65 6c 61 74 65 64 2e 20 41 ely unrelated. A
44e0: 6e 79 77 61 79 2c 20 69 74 20 63 6f 75 6c 64 20 nyway, it could
44f0: 62 65 20 69 6e 74 65 72 65 73 74 69 6e 67 20 6e be interesting n
4500: 6f 74 69 6e 67 20 74 68 61 74 20 74 68 65 20 53 oting that the S
4510: 70 61 74 69 61 4c 69 74 65 27 73 20 6f 77 6e 20 patiaLite's own
4520: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 73 implementation s
4530: 65 65 6d 73 20 74 6f 20 62 65 20 6d 75 63 68 20 eems to be much
4540: 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74 20 61 more efficient a
4550: 6e 64 20 66 61 73 74 2c 20 61 6e 64 20 63 61 6e nd fast, and can
4560: 20 62 65 20 72 65 61 6c 69 73 74 69 63 61 6c 6c be realisticall
4570: 79 20 61 70 70 6c 69 65 64 20 65 76 65 6e 20 74 y applied even t
4580: 6f 20 76 65 72 79 20 68 75 67 65 20 70 6f 69 6e o very huge poin
4590: 74 2d 73 65 74 73 2e 3c 62 72 3e 3c 62 72 3e 0d t-sets.<br><br>.
45a0: 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d .<table bgcolor=
45b0: 22 23 66 30 66 30 66 30 22 20 63 65 6c 6c 73 70 "#f0f0f0" cellsp
45c0: 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 acing="4" cellpa
45d0: 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e dding="8">..<tr>
45e0: 3c 74 64 3e 0d 0a 3c 69 3e 70 72 6f 74 6f 74 79 <td>..<i>prototy
45f0: 70 65 3c 2f 69 3e 3a 3c 68 72 3e 0d 0a 53 54 5f pe</i>:<hr>..ST_
4600: 43 6f 6e 63 61 76 65 48 75 6c 6c 28 20 69 6e 70 ConcaveHull( inp
4610: 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f ut <i>Geometry</
4620: 69 3e 20 29 20 3a 20 63 6f 6e 63 61 76 65 20 3c i> ) : concave <
4630: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 i>Geometry</i><b
4640: 72 3e 0d 0a 53 54 5f 43 6f 6e 63 61 76 65 48 75 r>..ST_ConcaveHu
4650: 6c 6c 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f ll( input <i>Geo
4660: 6d 65 74 72 79 3c 2f 69 3e 2c 20 66 61 63 74 6f metry</i>, facto
4670: 72 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 r <i>double prec
4680: 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 63 6f ision</i> ) : co
4690: 6e 63 61 76 65 20 3c 69 3e 47 65 6f 6d 65 74 72 ncave <i>Geometr
46a0: 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 43 6f y</i><br>..ST_Co
46b0: 6e 63 61 76 65 48 75 6c 6c 28 20 69 6e 70 75 74 ncaveHull( input
46c0: 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e <i>Geometry</i>
46d0: 2c 20 66 61 63 74 6f 72 20 3c 69 3e 64 6f 75 62 , factor <i>doub
46e0: 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e le precision</i>
46f0: 2c 20 61 6c 6c 6f 77 5f 68 6f 6c 65 73 20 3c 69 , allow_holes <i
4700: 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 29 20 3a >boolean</i> ) :
4710: 20 63 6f 6e 63 61 76 65 20 3c 69 3e 47 65 6f 6d concave <i>Geom
4720: 65 74 72 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 etry</i><br>..ST
4730: 5f 43 6f 6e 63 61 76 65 48 75 6c 6c 28 20 69 6e _ConcaveHull( in
4740: 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c put <i>Geometry<
4750: 2f 69 3e 2c 20 66 61 63 74 6f 72 20 3c 69 3e 64 /i>, factor <i>d
4760: 6f 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c ouble precision<
4770: 2f 69 3e 2c 20 61 6c 6c 6f 77 5f 68 6f 6c 65 73 /i>, allow_holes
4780: 20 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c <i>boolean</i>,
4790: 20 74 6f 6c 65 72 61 6e 63 65 20 3c 69 3e 64 6f tolerance <i>do
47a0: 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f uble precision</
47b0: 69 3e 20 29 20 3a 20 63 6f 6e 63 61 76 65 20 3c i> ) : concave <
47c0: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 0d 0a i>Geometry</i>..
47d0: 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c </td></tr></tabl
47e0: 65 3e 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 e>..<ul>..<li>th
47f0: 65 20 3c 62 3e 69 6e 70 75 74 3c 2f 62 3e 20 47 e <b>input</b> G
4800: 65 6f 6d 65 74 72 79 20 63 61 6e 20 62 65 20 6f eometry can be o
4810: 66 20 61 62 73 6f 6c 75 74 65 6c 79 20 61 72 62 f absolutely arb
4820: 69 74 72 61 72 79 20 74 79 70 65 3b 20 61 6c 6c itrary type; all
4830: 20 4c 69 6e 65 73 74 72 69 6e 67 73 20 61 6e 64 Linestrings and
4840: 20 2f 20 6f 72 20 50 6f 6c 79 67 6f 77 6e 73 20 / or Polygowns
4850: 77 69 6c 6c 20 65 76 65 6e 74 75 61 6c 6c 79 20 will eventually
4860: 62 65 20 64 69 73 73 6f 6c 76 65 64 20 69 6e 74 be dissolved int
4870: 6f 20 50 6f 69 6e 74 73 20 63 6f 72 72 65 73 70 o Points corresp
4880: 6f 6e 64 69 6e 67 20 74 6f 20 76 65 72 74 69 63 onding to vertic
4890: 65 73 2e 3c 62 72 3e 0d 0a 53 6f 20 61 66 74 65 es.<br>..So afte
48a0: 72 20 61 6c 6c 20 53 54 5f 43 6f 6e 63 61 76 65 r all ST_Concave
48b0: 48 75 6c 6c 28 29 20 28 65 78 61 63 74 6c 79 20 Hull() (exactly
48c0: 61 73 20 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 as ST_DelaunayTr
48d0: 69 61 6e 67 75 6c 61 74 69 6f 6e 29 20 77 69 6c iangulation) wil
48e0: 6c 20 61 6c 77 61 79 73 20 70 72 6f 63 65 73 73 l always process
48f0: 20 61 20 4d 75 6c 74 69 50 6f 69 6e 74 2e 3c 2f a MultiPoint.</
4900: 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 li>..<li>the opt
4910: 69 6f 6e 61 6c 20 3c 62 3e 66 61 63 74 6f 72 3c ional <b>factor<
4920: 2f 62 3e 20 69 73 20 69 6e 74 65 6e 64 65 64 20 /b> is intended
4930: 74 6f 20 62 65 20 61 20 3c 62 3e 26 73 69 67 6d to be a <b>&sigm
4940: 61 3b 3c 2f 62 3e 20 6d 75 6c 74 69 70 6c 69 65 a;</b> multiplie
4950: 72 2c 20 74 68 75 73 20 64 65 74 65 72 6d 69 6e r, thus determin
4960: 69 6e 67 20 74 68 65 20 66 69 6c 74 65 72 69 6e ing the filterin
4970: 67 20 74 68 72 65 73 68 6f 6c 64 2e 3c 62 72 3e g threshold.<br>
4980: 0d 0a 42 79 20 64 65 66 61 75 6c 74 20 61 20 3c ..By default a <
4990: 62 3e 33 26 73 69 67 6d 61 3b 20 66 61 63 74 6f b>3σ facto
49a0: 72 3c 2f 62 3e 20 69 73 20 61 73 73 75 6d 65 64 r</b> is assumed
49b0: 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 .</li>..<li>the
49c0: 6f 70 74 69 6f 6e 61 6c 20 3c 62 3e 61 6c 6c 6f optional <b>allo
49d0: 77 5f 68 6f 6c 65 73 3c 2f 62 3e 20 61 72 67 75 w_holes</b> argu
49e0: 6d 65 6e 74 20 77 69 6c 6c 20 62 65 20 69 6e 74 ment will be int
49f0: 65 72 70 72 65 74 65 64 20 61 73 20 66 6f 6c 6c erpreted as foll
4a00: 6f 77 73 3a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 69 66 ows:<ul>..<li>if
4a10: 20 3c 62 3e 46 41 4c 53 45 3c 2f 62 3e 20 28 3c <b>FALSE</b> (<
4a20: 69 3e 64 65 66 61 75 6c 74 20 76 61 6c 75 65 3c i>default value<
4a30: 2f 69 3e 29 20 61 6e 79 20 65 76 65 6e 74 75 61 /i>) any eventua
4a40: 6c 20 69 6e 74 65 72 69 6f 72 20 68 6f 6c 65 20 l interior hole
4a50: 77 69 6c 6c 20 62 65 20 73 75 70 70 72 65 73 73 will be suppress
4a60: 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 69 66 ed.</li>..<li>if
4a70: 20 3c 62 3e 54 52 55 45 3c 2f 62 3e 20 61 6e 79 <b>TRUE</b> any
4a80: 20 65 76 65 6e 74 75 61 6c 20 69 6e 74 65 72 69 eventual interi
4a90: 6f 72 20 68 6f 6c 65 73 20 77 69 6c 6c 20 62 65 or holes will be
4aa0: 20 70 72 65 73 65 72 76 65 64 2e 3c 2f 6c 69 3e preserved.</li>
4ab0: 0d 0a 3c 2f 75 6c 3e 3c 2f 6c 69 3e 20 0d 0a 3c ..</ul></li> ..<
4ac0: 6c 69 3e 74 68 65 20 6f 70 74 69 6f 6e 61 6c 20 li>the optional
4ad0: 3c 62 3e 74 6f 6c 65 72 61 6e 63 65 3c 2f 62 3e <b>tolerance</b>
4ae0: 20 61 72 67 75 6d 65 6e 74 20 69 73 20 69 6e 74 argument is int
4af0: 65 6e 64 65 64 20 74 6f 20 6e 6f 72 6d 61 6c 69 ended to normali
4b00: 7a 65 20 74 68 65 20 69 6e 70 75 74 20 70 6f 69 ze the input poi
4b10: 6e 74 2d 73 65 74 2c 20 73 75 70 70 72 65 73 73 nt-set, suppress
4b20: 69 6e 67 20 72 65 70 65 61 74 65 64 20 70 6f 69 ing repeated poi
4b30: 6e 74 73 20 28 73 69 6d 70 6c 79 20 75 73 65 64 nts (simply used
4b40: 20 77 68 65 6e 20 69 6e 74 65 72 6e 61 6c 6c 79 when internally
4b50: 20 63 6f 6d 70 75 74 69 6e 67 20 74 68 65 20 44 computing the D
4b60: 65 6c 61 75 6e 61 79 20 54 72 69 61 6e 67 75 6c elaunay Triangul
4b70: 61 74 69 6f 6e 29 2e 0d 0a 42 79 20 64 65 66 61 ation)...By defa
4b80: 75 6c 74 20 61 20 3c 62 3e 30 2e 30 3c 2f 62 3e ult a <b>0.0</b>
4b90: 20 74 6f 6c 65 72 61 6e 63 65 20 77 69 6c 6c 20 tolerance will
4ba0: 62 65 20 61 73 73 75 6d 65 64 2e 3c 2f 6c 69 3e be assumed.</li>
4bb0: 0d 0a 3c 2f 75 6c 3e 3c 2f 74 64 3e 3c 2f 74 72 ..</ul></td></tr
4bc0: 3e 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 74 61 62 6c ></table>..<tabl
4bd0: 65 20 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 e cellspacing="4
4be0: 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 34 " cellpadding="4
4bf0: 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 74 ">..<tr><td>..<t
4c00: 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 able bgcolor="#f
4c10: 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 0f0f0" cellspaci
4c20: 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 ng="4" cellpaddi
4c30: 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 ng="8">..<tr><td
4c40: 3e 0d 0a 3c 62 3e 53 45 4c 45 43 54 20 53 54 5f >..<b>SELECT ST_
4c50: 43 6f 6e 63 61 76 65 48 75 6c 6c 28 53 54 5f 43 ConcaveHull(ST_C
4c60: 6f 6c 6c 65 63 74 28 67 65 6f 6d 65 74 72 79 29 ollect(geometry)
4c70: 2c 20 32 2e 35 29 3c 62 72 3e 0d 0a 46 52 4f 4d , 2.5)<br>..FROM
4c80: 20 69 74 61 6c 79 5f 70 6f 70 75 6c 61 74 65 64 italy_populated
4c90: 5f 70 6c 61 63 65 73 3b 3c 2f 62 3e 0d 0a 3c 2f _places;</b>..</
4ca0: 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c td></tr>..</tabl
4cb0: 65 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 53 51 4c e><br>..This SQL
4cc0: 20 71 75 65 72 79 20 77 69 6c 6c 20 72 65 74 75 query will retu
4cd0: 72 6e 20 61 20 43 6f 6e 63 61 76 65 48 75 6c 6c rn a ConcaveHull
4ce0: 20 62 61 73 65 64 20 6f 6e 20 49 74 61 6c 79 27 based on Italy'
4cf0: 73 20 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 s populated plac
4d00: 65 73 20 28 61 62 6f 75 74 20 38 2c 30 30 30 2b es (about 8,000+
4d10: 20 50 6f 69 6e 74 73 29 20 62 79 20 61 70 70 6c Points) by appl
4d20: 79 69 6e 67 20 61 20 3c 62 3e 32 2e 35 26 73 69 ying a <b>2.5&si
4d30: 67 6d 61 3b 3c 2f 62 3e 20 66 69 6c 74 65 72 69 gma;</b> filteri
4d40: 6e 67 20 66 61 63 74 6f 72 2e 3c 62 72 3e 3c 62 ng factor.<br><b
4d50: 72 3e 0d 0a 54 68 65 20 66 69 67 75 72 65 20 61 r>..The figure a
4d60: 6c 73 6f 20 73 68 6f 77 73 20 74 68 65 20 43 6f lso shows the Co
4d70: 6e 63 61 76 65 48 75 6c 6c 20 72 65 74 75 72 6e ncaveHull return
4d80: 65 64 20 62 79 20 74 68 65 20 70 72 65 76 69 6f ed by the previo
4d90: 75 73 20 65 78 61 6d 70 6c 65 20 62 79 20 61 70 us example by ap
4da0: 70 6c 79 69 6e 67 20 61 20 3c 62 3e 33 26 73 69 plying a <b>3&si
4db0: 67 6d 61 3b 3c 2f 62 3e 20 66 61 63 74 6f 72 20 gma;</b> factor
4dc0: 28 72 65 64 20 62 6f 75 6e 64 61 72 79 29 2c 20 (red boundary),
4dd0: 73 6f 20 74 6f 20 65 76 69 64 65 6e 74 69 61 74 so to evidentiat
4de0: 65 20 74 68 65 20 72 65 6c 61 74 69 76 65 20 64 e the relative d
4df0: 69 66 66 65 72 65 6e 63 65 73 2e 20 0d 0a 3c 2f ifferences. ..</
4e00: 74 64 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f td>..<td><img bo
4e10: 72 64 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 rder="1" src="ht
4e20: 74 70 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 tp://www.gaia-gi
4e30: 73 2e 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 s.it/gaia-sins/w
4e40: 72 69 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 63 rite-view-pics/c
4e50: 6f 6e 63 61 76 65 32 35 2e 70 6e 67 22 20 61 6c oncave25.png" al
4e60: 74 3d 22 63 6f 6e 63 61 76 65 68 75 6c 6c 2d 32 t="concavehull-2
4e70: 22 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f "></td></tr>..</
4e80: 74 61 62 6c 65 3e 0d 0a 3c 62 72 3e 3c 68 72 3e table>..<br><hr>
4e90: 0d 0a 42 61 63 6b 20 74 6f 20 3c 61 20 68 72 65 ..Back to <a hre
4ea0: 66 3d 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 67 f="https://www.g
4eb0: 61 69 61 2d 67 69 73 2e 69 74 2f 66 6f 73 73 69 aia-gis.it/fossi
4ec0: 6c 2f 6c 69 62 73 70 61 74 69 61 6c 69 74 65 2f l/libspatialite/
4ed0: 77 69 6b 69 3f 6e 61 6d 65 3d 73 77 69 74 63 68 wiki?name=switch
4ee0: 69 6e 67 2d 74 6f 2d 34 2e 30 23 74 65 73 73 65 ing-to-4.0#tesse
4ef0: 6c 6c 61 74 69 6f 6e 73 22 3e 6d 61 69 6e 20 70 llations">main p
4f00: 61 67 65 3c 2f 61 3e 0d 0a 0d 0a 0a 5a 20 35 65 age</a>.....Z 5e
4f10: 66 65 63 37 37 65 61 34 36 34 66 64 35 39 34 62 fec77ea464fd594b
4f20: 35 31 33 62 61 65 37 39 35 37 63 30 61 34 0a 513bae7957c0a4.