0000: 44 20 32 30 31 32 2d 30 38 2d 33 30 54 31 30 3a D 2012-08-30T10:
0010: 32 37 3a 35 34 2e 32 38 36 0a 4c 20 74 65 73 73 27:54.286.L tess
0020: 65 6c 61 74 69 6f 6e 73 2d 34 2e 30 0a 50 20 33 elations-4.0.P 3
0030: 34 31 38 39 36 63 66 38 63 38 39 38 33 63 66 37 41896cf8c8983cf7
0040: 38 31 61 35 36 63 65 32 30 33 36 65 62 66 64 37 81a56ce2036ebfd7
0050: 64 61 62 30 36 37 36 0a 55 20 73 61 6e 64 72 6f dab0676.U sandro
0060: 0a 57 20 32 30 31 32 36 0a 3c 68 32 3e 54 65 73 .W 20126.<h2>Tes
0070: 73 65 6c 61 74 69 6f 6e 2d 72 65 6c 61 74 65 64 selation-related
0080: 20 53 51 4c 20 66 75 6e 63 74 69 6f 6e 73 20 73 SQL functions s
0090: 75 70 70 6f 72 74 65 64 20 69 6e 20 76 65 72 73 upported in vers
00a0: 69 6f 6e 20 34 2e 30 2e 30 3c 2f 68 32 3e 0d 0a ion 4.0.0</h2>..
00b0: 42 61 63 6b 20 74 6f 20 3c 61 20 68 72 65 66 3d Back to <a href=
00c0: 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 67 61 69 "https://www.gai
00d0: 61 2d 67 69 73 2e 69 74 2f 66 6f 73 73 69 6c 2f a-gis.it/fossil/
00e0: 6c 69 62 73 70 61 74 69 61 6c 69 74 65 2f 77 69 libspatialite/wi
00f0: 6b 69 3f 6e 61 6d 65 3d 73 77 69 74 63 68 69 6e ki?name=switchin
0100: 67 2d 74 6f 2d 34 2e 30 23 74 65 73 73 65 6c 6c g-to-4.0#tessell
0110: 61 74 69 6f 6e 22 3e 6d 61 69 6e 20 70 61 67 65 ation">main page
0120: 3c 2f 61 3e 0d 0a 3c 68 33 3e 47 65 6e 65 72 61 </a>..<h3>Genera
0130: 6c 69 74 69 65 73 20 61 62 6f 75 74 20 74 65 73 lities about tes
0140: 73 65 6c 6c 61 74 69 6f 6e 73 3c 2f 68 33 3e 0d sellations</h3>.
0150: 0a 3c 69 3e 54 65 73 73 65 6c 6c 61 74 69 6f 6e .<i>Tessellation
0160: 20 69 73 20 74 68 65 20 70 72 6f 63 65 73 73 20 is the process
0170: 6f 66 20 63 72 65 61 74 69 6e 67 20 61 20 74 77 of creating a tw
0180: 6f 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 70 6c o-dimensional pl
0190: 61 6e 65 20 75 73 69 6e 67 20 74 68 65 20 72 65 ane using the re
01a0: 70 65 74 69 74 69 6f 6e 20 6f 66 20 61 20 67 65 petition of a ge
01b0: 6f 6d 65 74 72 69 63 20 73 68 61 70 65 20 77 69 ometric shape wi
01c0: 74 68 20 6e 6f 20 6f 76 65 72 6c 61 70 73 20 61 th no overlaps a
01d0: 6e 64 20 6e 6f 20 67 61 70 73 2e 3c 2f 69 3e 0d nd no gaps.</i>.
01e0: 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f .<a href="http:/
01f0: 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f 72 /en.wikipedia.or
0200: 67 2f 77 69 6b 69 2f 54 65 73 73 65 6c 6c 61 74 g/wiki/Tessellat
0210: 69 6f 6e 22 3e 72 65 61 64 20 6d 6f 72 65 3c 2f ion">read more</
0220: 61 3e 3c 62 72 3e 3c 62 72 3e 0d 0a 41 20 74 65 a><br><br>..A te
0230: 73 73 65 6c 6c 61 74 69 6f 6e 20 63 6f 75 6c 64 ssellation could
0240: 20 62 65 20 65 76 65 6e 74 75 61 6c 6c 79 20 62 be eventually b
0250: 61 73 65 64 20 6f 6e 20 69 64 65 6e 74 69 63 61 ased on identica
0260: 6c 20 3c 69 3e 63 65 6c 6c 73 3c 2f 69 3e 2c 20 l <i>cells</i>,
0270: 61 6c 6c 20 6f 66 20 65 78 61 63 74 6c 79 20 74 all of exactly t
0280: 68 65 20 73 61 6d 65 20 73 68 61 70 65 20 61 6e he same shape an
0290: 64 20 73 69 7a 65 2e 0d 0a 49 6e 20 74 68 69 73 d size...In this
02a0: 20 63 61 73 65 20 77 65 27 6c 6c 20 68 61 76 65 case we'll have
02b0: 20 61 20 3c 69 3e 72 65 67 75 6c 61 72 20 74 65 a <i>regular te
02c0: 73 73 65 6c 6c 61 74 69 6f 6e 3c 2f 69 3e 2e 3c ssellation</i>.<
02d0: 62 72 3e 0d 0a 4a 75 73 74 20 61 20 71 75 69 63 br>..Just a quic
02e0: 6b 20 72 65 63 61 6c 6c 20 6f 66 20 65 6c 65 6d k recall of elem
02f0: 65 6e 74 61 72 79 20 67 65 6f 6d 65 74 72 79 3b entary geometry;
0300: 20 74 68 65 72 65 20 61 72 65 20 73 69 6d 70 6c there are simpl
0310: 79 20 3c 62 3e 33 3c 2f 62 3e 20 72 65 67 75 6c y <b>3</b> regul
0320: 61 72 20 70 6f 6c 79 67 6f 6e 61 6c 20 73 68 61 ar polygonal sha
0330: 70 65 73 20 77 65 20 63 61 6e 20 75 73 65 20 69 pes we can use i
0340: 6e 20 6f 72 64 65 72 20 74 6f 20 67 65 74 20 61 n order to get a
0350: 20 72 65 67 75 6c 61 72 20 74 65 73 73 65 6c 6c regular tessell
0360: 61 74 69 6f 6e 3a 20 74 68 65 20 3c 62 3e 65 71 ation: the <b>eq
0370: 75 69 6c 61 74 65 72 61 6c 20 74 72 69 61 6e 67 uilateral triang
0380: 6c 65 3c 2f 62 3e 2c 20 74 68 65 20 3c 62 3e 73 le</b>, the <b>s
0390: 71 75 61 72 65 3c 2f 62 3e 20 61 6e 64 20 74 68 quare</b> and th
03a0: 65 20 3c 62 3e 72 65 67 75 6c 61 72 20 68 65 78 e <b>regular hex
03b0: 61 67 6f 6e 3c 2f 62 3e 2e 3c 62 72 3e 3c 62 72 agon</b>.<br><br
03c0: 3e 0d 0a 4f 6e 20 74 68 65 20 6f 74 68 65 72 20 >..On the other
03d0: 77 61 79 20 6d 61 6e 79 20 74 65 73 73 65 6c 6c way many tessell
03e0: 61 74 69 6f 6e 73 20 61 72 65 6e 27 74 20 72 65 ations aren't re
03f0: 67 75 6c 61 72 20 61 74 20 61 6c 6c 2c 20 62 65 gular at all, be
0400: 63 61 75 73 65 20 65 61 63 68 20 73 69 6e 67 6c cause each singl
0410: 65 20 63 65 6c 6c 20 68 61 73 20 61 6e 20 69 6e e cell has an in
0420: 64 69 76 69 64 75 61 6c 20 73 69 7a 65 20 61 6e dividual size an
0430: 64 20 73 68 61 70 65 20 6f 66 20 69 74 73 20 6f d shape of its o
0440: 77 6e 2e 3c 62 72 3e 0d 0a 49 74 27 73 20 72 65 wn.<br>..It's re
0450: 61 6c 6c 79 20 69 6e 74 65 72 65 73 74 69 6e 67 ally interesting
0460: 20 74 6f 20 6e 6f 74 65 20 74 68 61 74 20 6d 61 to note that ma
0470: 6e 79 20 3c 69 3e 6e 61 74 75 72 61 6c 20 73 68 ny <i>natural sh
0480: 61 70 65 73 3c 2f 69 3e 20 63 6c 6f 73 65 6c 79 apes</i> closely
0490: 20 72 65 73 65 6d 62 6c 65 20 61 20 74 65 73 73 resemble a tess
04a0: 65 6c 6c 61 74 69 6f 6e 3a 20 67 6f 69 6e 67 20 ellation: going
04b0: 66 72 6f 6d 20 62 69 6f 6c 6f 67 79 20 74 6f 20 from biology to
04c0: 63 72 79 73 74 61 6c 6c 6f 67 72 61 70 68 79 20 crystallography
04d0: 73 69 6e 63 65 20 67 65 6f 6c 6f 67 79 20 61 6e since geology an
04e0: 64 20 6c 61 6e 64 73 63 61 70 65 73 20 69 74 27 d landscapes it'
04f0: 73 20 6e 6f 74 20 61 74 20 61 6c 6c 20 64 69 66 s not at all dif
0500: 66 69 63 75 6c 74 20 74 6f 20 69 64 65 6e 74 69 ficult to identi
0510: 66 79 20 6d 61 6e 79 20 6e 61 74 75 72 61 6c 20 fy many natural
0520: 74 65 73 73 65 6c 6c 61 74 69 6f 6e 20 65 78 61 tessellation exa
0530: 6d 70 6c 65 73 20 3c 69 3e 6f 6e 20 74 68 65 20 mples <i>on the
0540: 77 69 6c 64 3c 2f 69 3e 2e 0d 0a 53 6f 20 69 74 wild</i>...So it
0550: 27 73 20 6e 6f 74 20 61 74 20 61 6c 6c 20 73 75 's not at all su
0560: 72 70 72 69 73 69 6e 67 20 74 6f 20 64 69 73 63 rprising to disc
0570: 6f 76 65 72 20 74 68 61 74 20 74 65 73 73 65 6c over that tessel
0580: 6c 61 74 69 6f 6e 73 20 61 72 65 20 6f 66 74 65 lations are ofte
0590: 6e 20 75 73 65 66 75 6c 20 69 6e 20 67 65 6f 67 n useful in geog
05a0: 72 61 70 68 79 20 61 73 20 77 65 6c 6c 2e 0d 0a raphy as well...
05b0: 3c 68 33 3e 53 65 74 74 69 6e 67 20 75 70 20 61 <h3>Setting up a
05c0: 20 74 65 73 74 62 65 64 20 44 42 3c 2f 68 33 3e testbed DB</h3>
05d0: 0d 0a 49 6e 20 74 68 69 73 20 73 68 6f 72 74 20 ..In this short
05e0: 74 75 74 6f 72 69 61 6c 20 77 65 27 6c 6c 20 75 tutorial we'll u
05f0: 73 65 20 61 20 76 65 72 79 20 73 69 6d 70 6c 65 se a very simple
0600: 20 53 70 61 74 69 61 4c 69 74 65 20 44 42 2c 20 SpatiaLite DB,
0610: 6a 75 73 74 20 63 6f 6e 74 61 69 6e 69 6e 67 20 just containing
0620: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 47 65 the following Ge
0630: 6f 6d 65 74 72 79 20 74 61 62 6c 65 73 3a 3c 75 ometry tables:<u
0640: 6c 3e 0d 0a 3c 6c 69 3e 41 64 6d 69 6e 69 73 74 l>..<li>Administ
0650: 72 61 74 69 76 65 20 62 6f 75 6e 64 61 72 69 65 rative boundarie
0660: 73 20 66 6f 72 20 49 74 61 6c 79 20 72 65 67 69 s for Italy regi
0670: 6f 6e 73 3a 20 79 6f 75 20 63 61 6e 20 3c 61 20 ons: you can <a
0680: 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f 77 77 77 href="http://www
0690: 2e 69 73 74 61 74 2e 69 74 2f 69 74 2f 66 69 6c .istat.it/it/fil
06a0: 65 73 2f 32 30 31 31 2f 30 34 2f 72 65 67 32 30 es/2011/04/reg20
06b0: 31 31 2e 7a 69 70 22 3e 64 6f 77 6e 6c 6f 61 64 11.zip">download
06c0: 3c 2f 61 3e 20 74 68 69 73 20 64 61 74 61 73 65 </a> this datase
06d0: 74 20 66 72 6f 6d 20 49 53 54 41 54 20 28 72 65 t from ISTAT (re
06e0: 6c 65 61 73 65 64 20 6f 6e 20 43 43 2d 42 59 20 leased on CC-BY
06f0: 6c 69 63 65 6e 73 65 20 74 65 72 6d 73 29 2e 3c license terms).<
0700: 62 72 3e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 4d 61 br></li>..<li>Ma
0710: 69 6e 20 49 74 61 6c 69 61 6e 20 70 6f 70 75 6c in Italian popul
0720: 61 74 65 64 20 70 6c 61 63 65 73 20 28 6e 61 6d ated places (nam
0730: 65 6c 79 2c 20 4c 6f 63 61 6c 20 43 6f 75 6e 63 ely, Local Counc
0740: 69 6c 73 29 3a 20 79 6f 75 20 63 61 6e 20 3c 61 ils): you can <a
0750: 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f 64 6f href="http://do
0760: 77 6e 6c 6f 61 64 2e 67 65 6f 6e 61 6d 65 73 2e wnload.geonames.
0770: 6f 72 67 2f 65 78 70 6f 72 74 2f 64 75 6d 70 2f org/export/dump/
0780: 61 6c 6c 43 6f 75 6e 74 72 69 65 73 2e 7a 69 70 allCountries.zip
0790: 22 3e 64 6f 77 6e 6c 6f 61 64 3c 2f 61 3e 20 74 ">download</a> t
07a0: 68 69 73 20 64 61 74 61 73 65 74 20 66 72 6f 6d his dataset from
07b0: 20 47 65 6f 4e 61 6d 65 73 20 28 72 65 6c 65 61 GeoNames (relea
07c0: 73 65 64 20 6f 6e 20 43 43 2d 42 59 20 6c 69 63 sed on CC-BY lic
07d0: 65 6e 73 65 20 74 65 72 6d 73 29 2e 3c 62 72 3e ense terms).<br>
07e0: 0d 0a 50 6c 65 61 73 65 20 6e 6f 74 65 3a 20 74 ..Please note: t
07f0: 68 69 73 20 6f 6e 65 20 69 73 20 61 20 77 6f 72 his one is a wor
0800: 6c 64 77 69 64 65 20 64 61 74 61 73 65 74 3b 20 ldwide dataset;
0810: 69 74 61 6c 69 61 6e 20 70 6f 70 75 6c 61 74 65 italian populate
0820: 64 20 70 6c 61 63 65 73 20 68 61 76 65 20 74 68 d places have th
0830: 65 6e 20 62 65 65 6e 20 65 78 74 72 61 63 74 65 en been extracte
0840: 64 20 69 6d 70 6f 73 69 6e 67 20 74 68 65 20 53 d imposing the S
0850: 51 4c 20 63 6c 61 75 73 65 3c 62 72 3e 0d 0a 3c QL clause<br>..<
0860: 62 3e 57 48 45 52 45 20 63 6f 75 6e 74 79 5f 63 b>WHERE county_c
0870: 6f 64 65 20 3d 20 27 49 54 27 20 41 4e 44 20 70 ode = 'IT' AND p
0880: 6f 70 75 6c 61 74 69 6f 6e 20 3e 20 30 3c 2f 62 opulation > 0</b
0890: 3e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 62 72 ></li>..</ul><br
08a0: 3e 0d 0a 4a 75 73 74 20 74 6f 20 6b 65 65 70 20 >..Just to keep
08b0: 61 6e 79 20 65 78 61 6d 70 6c 65 20 61 73 20 73 any example as s
08c0: 69 6d 70 6c 65 20 61 73 20 70 6f 73 73 69 62 6c imple as possibl
08d0: 65 2c 20 62 6f 74 68 20 64 61 74 61 73 65 74 73 e, both datasets
08e0: 20 68 61 76 65 20 62 65 65 6e 20 72 65 66 65 72 have been refer
08f0: 65 6e 63 65 64 20 69 6e 74 6f 20 74 68 65 20 3c enced into the <
0900: 62 3e 53 52 49 44 3d 32 33 30 33 32 20 2d 20 45 b>SRID=23032 - E
0910: 44 35 30 20 2f 20 55 54 4d 20 7a 6f 6e 65 20 33 D50 / UTM zone 3
0920: 32 20 4e 3c 2f 62 3e 0d 0a 3c 62 72 3e 3c 62 72 2 N</b>..<br><br
0930: 3e 3c 68 72 3e 0d 0a 3c 68 33 3e 43 72 65 61 74 ><hr>..<h3>Creat
0940: 69 6e 67 20 72 65 67 75 6c 61 72 20 74 65 73 73 ing regular tess
0950: 65 6c 6c 61 74 69 6f 6e 73 20 69 6e 20 53 70 61 ellations in Spa
0960: 74 69 61 6c 20 53 51 4c 3c 2f 68 33 3e 0d 0a 3c tial SQL</h3>..<
0970: 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 63 69 6e table cellspacin
0980: 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 6e g="4" cellpaddin
0990: 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c 74 64 20 g="4">..<tr><td
09a0: 63 6f 6c 73 70 61 6e 3d 22 32 22 3e 0d 0a 3c 74 colspan="2">..<t
09b0: 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 able bgcolor="#f
09c0: 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 0f0f0" cellspaci
09d0: 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 ng="4" cellpaddi
09e0: 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 ng="8">..<tr><td
09f0: 3e 0d 0a 3c 69 3e 67 65 6e 65 72 69 63 20 70 72 >..<i>generic pr
0a00: 6f 74 6f 74 79 70 65 73 3c 2f 69 3e 3a 3c 68 72 ototypes</i>:<hr
0a10: 3e 0d 0a 53 54 5f 78 78 78 78 47 72 69 64 28 20 >..ST_xxxxGrid(
0a20: 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 input <i>Geometr
0a30: 79 3c 2f 69 3e 2c 20 73 69 7a 65 20 3c 69 3e 64 y</i>, size <i>d
0a40: 6f 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c ouble precision<
0a50: 2f 69 3e 20 29 20 3a 20 67 72 69 64 20 3c 69 3e /i> ) : grid <i>
0a60: 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 72 3e Geometry</i><br>
0a70: 0d 0a 53 54 5f 78 78 78 78 47 72 69 64 28 20 69 ..ST_xxxxGrid( i
0a80: 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 nput <i>Geometry
0a90: 3c 2f 69 3e 2c 20 73 69 7a 65 20 3c 69 3e 64 6f </i>, size <i>do
0aa0: 75 62 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f uble precision</
0ab0: 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c i>, edges_only <
0ac0: 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 29 20 i>boolean</i> )
0ad0: 3a 20 67 72 69 64 20 3c 69 3e 47 65 6f 6d 65 74 : grid <i>Geomet
0ae0: 72 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 78 ry</i><br>..ST_x
0af0: 78 78 78 47 72 69 64 28 20 69 6e 70 75 74 20 3c xxxGrid( input <
0b00: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 2c 20 i>Geometry</i>,
0b10: 73 69 7a 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 size <i>double p
0b20: 72 65 63 69 73 69 6f 6e 3c 2f 69 3e 2c 20 65 64 recision</i>, ed
0b30: 67 65 73 5f 6f 6e 6c 79 20 3c 69 3e 62 6f 6f 6c ges_only <i>bool
0b40: 65 61 6e 3c 2f 69 3e 2c 20 6f 72 69 67 69 6e 20 ean</i>, origin
0b50: 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 20 <i>Geometry</i>
0b60: 29 20 3a 20 67 72 69 64 20 3c 69 3e 47 65 6f 6d ) : grid <i>Geom
0b70: 65 74 72 79 3c 2f 69 3e 0d 0a 3c 2f 74 64 3e 3c etry</i>..</td><
0b80: 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 75 /tr></table>..<u
0b90: 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 20 3c 62 3e 69 l>..<li>the <b>i
0ba0: 6e 70 75 74 3c 2f 62 3e 20 47 65 6f 6d 65 74 72 nput</b> Geometr
0bb0: 79 20 69 73 20 61 6c 77 61 79 73 20 65 78 70 65 y is always expe
0bc0: 63 74 65 64 20 74 6f 20 62 65 20 61 20 50 6f 6c cted to be a Pol
0bd0: 79 67 6f 6e 20 6f 72 20 61 20 4d 75 6c 74 69 50 ygon or a MultiP
0be0: 6f 6c 79 67 6f 6e 2c 20 61 6e 64 20 77 69 6c 6c olygon, and will
0bf0: 20 62 65 20 65 78 61 63 74 6c 79 20 63 6f 76 65 be exactly cove
0c00: 72 65 64 20 62 79 20 74 68 65 20 72 65 74 75 72 red by the retur
0c10: 6e 65 64 20 67 72 69 64 2e 3c 2f 6c 69 3e 0d 0a ned grid.</li>..
0c20: 3c 6c 69 3e 74 68 65 20 3c 62 3e 73 69 7a 65 3c <li>the <b>size<
0c30: 2f 62 3e 20 61 72 67 75 6d 65 6e 74 20 69 64 65 /b> argument ide
0c40: 6e 74 69 66 69 65 73 20 74 68 65 20 65 64 67 65 ntifies the edge
0c50: 20 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 20 67 length of the g
0c60: 72 69 64 20 63 65 6c 6c 2e 3c 2f 6c 69 3e 0d 0a rid cell.</li>..
0c70: 3c 6c 69 3e 74 68 65 20 6f 70 74 69 6f 6e 61 6c <li>the optional
0c80: 20 3c 62 3e 65 64 67 65 73 5f 6f 6e 6c 79 3c 2f <b>edges_only</
0c90: 62 3e 20 61 72 67 75 6d 65 6e 74 20 77 69 6c 6c b> argument will
0ca0: 20 62 65 20 69 6e 74 65 72 70 72 65 74 65 64 20 be interpreted
0cb0: 61 73 20 66 6f 6c 6c 6f 77 73 3a 3c 75 6c 3e 0d as follows:<ul>.
0cc0: 0a 3c 6c 69 3e 69 66 20 3c 62 3e 46 41 4c 53 45 .<li>if <b>FALSE
0cd0: 3c 2f 62 3e 20 28 3c 69 3e 64 65 66 61 75 6c 74 </b> (<i>default
0ce0: 20 76 61 6c 75 65 3c 2f 69 3e 29 20 61 20 4d 75 value</i>) a Mu
0cf0: 6c 74 69 50 6f 6c 79 67 6f 6e 20 77 69 6c 6c 20 ltiPolygon will
0d00: 62 65 20 72 65 74 75 72 6e 65 64 2e 3c 2f 6c 69 be returned.</li
0d10: 3e 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 54 52 55 >..<li>if <b>TRU
0d20: 45 3c 2f 62 3e 20 61 20 4d 75 6c 74 69 4c 69 6e E</b> a MultiLin
0d30: 65 73 74 72 69 6e 67 20 77 69 6c 6c 20 62 65 20 estring will be
0d40: 72 65 74 75 72 6e 65 64 20 28 73 69 6d 70 6c 79 returned (simply
0d50: 20 72 65 70 72 65 73 65 6e 74 69 6e 67 20 74 68 representing th
0d60: 65 20 63 65 6c 6c 73 20 65 64 67 65 73 29 2e 3c e cells edges).<
0d70: 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f 6c 69 3e /li>..</ul></li>
0d80: 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 69 6f 6e ..<li>the option
0d90: 61 6c 20 3c 62 3e 6f 72 69 67 69 6e 3c 2f 62 3e al <b>origin</b>
0da0: 20 47 65 6f 6d 65 74 72 79 20 69 73 20 61 6c 77 Geometry is alw
0db0: 61 79 73 20 61 73 73 75 6d 65 64 20 74 6f 20 62 ays assumed to b
0dc0: 65 20 61 20 50 6f 69 6e 74 2c 20 61 6e 64 20 77 e a Point, and w
0dd0: 69 6c 6c 20 69 64 65 6e 74 69 66 79 20 74 68 65 ill identify the
0de0: 20 67 72 69 64 27 73 20 6f 72 69 67 69 6e 2e 0d grid's origin..
0df0: 0a 42 79 20 64 65 66 61 75 6c 74 20 61 20 3c 62 .By default a <b
0e00: 3e 28 30 2c 20 30 29 3c 2f 62 3e 20 6f 72 69 67 >(0, 0)</b> orig
0e10: 69 6e 20 77 69 6c 6c 20 62 65 20 61 73 73 75 6d in will be assum
0e20: 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c ed.</li>..</ul><
0e30: 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c /td></tr>..<tr><
0e40: 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 20 53 td>..<h4>using S
0e50: 71 75 61 72 65 20 63 65 6c 6c 73 3c 2f 68 34 3e quare cells</h4>
0e60: 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 ..<table bgcolor
0e70: 3d 22 23 66 30 66 30 66 30 22 20 63 65 6c 6c 73 ="#f0f0f0" cells
0e80: 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 pacing="4" cellp
0e90: 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 adding="8">..<tr
0ea0: 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 4c 45 43 54 ><td>..<b>SELECT
0eb0: 20 53 54 5f 53 71 75 61 72 65 47 72 69 64 28 67 ST_SquareGrid(g
0ec0: 65 6f 6d 65 74 72 79 2c 20 31 30 30 30 30 29 3c eometry, 10000)<
0ed0: 62 72 3e 0d 0a 46 52 4f 4d 20 72 65 67 69 6f 6e br>..FROM region
0ee0: 73 3c 62 72 3e 57 48 45 52 45 20 63 6f 64 5f 72 s<br>WHERE cod_r
0ef0: 65 67 20 3d 20 39 3b 3c 2f 62 3e 0d 0a 3c 2f 74 eg = 9;</b>..</t
0f00: 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 d></tr>..</table
0f10: 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 53 51 4c 20 ><br>..This SQL
0f20: 71 75 65 72 79 20 77 69 6c 6c 20 72 65 74 75 72 query will retur
0f30: 6e 20 61 20 72 65 67 75 6c 61 72 20 67 72 69 64 n a regular grid
0f40: 20 28 73 71 75 61 72 65 20 63 65 6c 6c 73 29 20 (square cells)
0f50: 63 6f 76 65 72 69 6e 67 20 54 75 73 63 61 6e 79 covering Tuscany
0f60: 20 28 3c 62 3e 63 6f 64 5f 72 65 67 3d 39 3c 2f (<b>cod_reg=9</
0f70: 62 3e 29 2e 3c 62 72 3e 0d 0a 45 61 63 68 20 67 b>).<br>..Each g
0f80: 72 69 64 27 73 20 63 65 6c 6c 20 77 69 6c 6c 20 rid's cell will
0f90: 68 61 76 65 20 61 6e 20 65 64 67 65 20 6c 65 6e have an edge len
0fa0: 67 74 68 20 6f 66 20 65 78 61 63 74 6c 79 20 3c gth of exactly <
0fb0: 62 3e 31 30 20 4b 6d 3c 2f 62 3e 0d 0a 3c 2f 74 b>10 Km</b>..</t
0fc0: 64 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 d>..<td><img bor
0fd0: 64 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 der="1" src="htt
0fe0: 70 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 p://www.gaia-gis
0ff0: 2e 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 .it/gaia-sins/wr
1000: 69 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 73 71 ite-view-pics/sq
1010: 75 61 72 65 2d 67 72 69 64 2e 70 6e 67 22 20 61 uare-grid.png" a
1020: 6c 74 3d 22 73 71 75 61 72 65 20 67 72 69 64 22 lt="square grid"
1030: 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 ></td></tr>..<tr
1040: 3e 3c 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 ><td>..<h4>using
1050: 20 54 72 69 61 6e 67 75 6c 61 72 20 63 65 6c 6c Triangular cell
1060: 73 3c 2f 68 34 3e 0d 0a 3c 74 61 62 6c 65 20 62 s</h4>..<table b
1070: 67 63 6f 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 gcolor="#f0f0f0"
1080: 20 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 cellspacing="4"
1090: 20 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 cellpadding="8"
10a0: 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e >..<tr><td>..<b>
10b0: 53 45 4c 45 43 54 20 53 54 5f 54 72 69 61 6e 67 SELECT ST_Triang
10c0: 75 6c 61 72 47 72 69 64 28 67 65 6f 6d 65 74 72 ularGrid(geometr
10d0: 79 2c 20 31 30 30 30 30 29 3c 62 72 3e 0d 0a 46 y, 10000)<br>..F
10e0: 52 4f 4d 20 72 65 67 69 6f 6e 73 3c 62 72 3e 57 ROM regions<br>W
10f0: 48 45 52 45 20 63 6f 64 5f 72 65 67 20 3d 20 39 HERE cod_reg = 9
1100: 3b 3c 2f 62 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 ;</b>..</td></tr
1110: 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 3c 2f 74 64 3e >..</table></td>
1120: 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 ..<td><img borde
1130: 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a r="1" src="http:
1140: 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 //www.gaia-gis.i
1150: 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 t/gaia-sins/writ
1160: 65 2d 76 69 65 77 2d 70 69 63 73 2f 74 72 69 2d e-view-pics/tri-
1170: 67 72 69 64 2e 70 6e 67 22 20 61 6c 74 3d 22 74 grid.png" alt="t
1180: 72 69 61 6e 67 75 6c 61 72 20 67 72 69 64 22 3e riangular grid">
1190: 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e </td></tr>..<tr>
11a0: 3c 74 64 3e 0d 0a 3c 68 34 3e 75 73 69 6e 67 20 <td>..<h4>using
11b0: 48 65 78 61 67 6f 6e 61 6c 20 63 65 6c 6c 73 3c Hexagonal cells<
11c0: 2f 68 34 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 /h4>..<table bgc
11d0: 6f 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 olor="#f0f0f0" c
11e0: 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 ellspacing="4" c
11f0: 65 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d ellpadding="8">.
1200: 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 .<tr><td>..<b>SE
1210: 4c 45 43 54 20 53 54 5f 48 65 78 61 67 6f 6e 61 LECT ST_Hexagona
1220: 6c 47 72 69 64 28 67 65 6f 6d 65 74 72 79 2c 20 lGrid(geometry,
1230: 31 30 30 30 30 29 3c 62 72 3e 0d 0a 46 52 4f 4d 10000)<br>..FROM
1240: 20 72 65 67 69 6f 6e 73 3c 62 72 3e 57 48 45 52 regions<br>WHER
1250: 45 20 63 6f 64 5f 72 65 67 20 3d 20 39 3b 3c 2f E cod_reg = 9;</
1260: 62 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a b>..</td></tr>..
1270: 3c 2f 74 61 62 6c 65 3e 3c 2f 74 64 3e 0d 0a 3c </table></td>..<
1280: 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 td><img border="
1290: 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 1" src="http://w
12a0: 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 ww.gaia-gis.it/g
12b0: 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 aia-sins/write-v
12c0: 69 65 77 2d 70 69 63 73 2f 68 65 78 2d 67 72 69 iew-pics/hex-gri
12d0: 64 2e 70 6e 67 22 20 61 6c 74 3d 22 68 65 78 61 d.png" alt="hexa
12e0: 67 6f 6e 61 6c 20 67 72 69 64 22 3e 3c 2f 74 64 gonal grid"></td
12f0: 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e ></tr>..</table>
1300: 0d 0a 3c 62 72 3e 3c 68 72 3e 0d 0a 3c 68 33 3e ..<br><hr>..<h3>
1310: 44 65 6c 61 75 6e 61 79 20 54 72 69 61 6e 67 75 Delaunay Triangu
1320: 6c 61 74 69 6f 6e 73 3c 2f 68 33 3e 0d 0a 54 72 lations</h3>..Tr
1330: 69 61 6e 67 75 6c 61 74 69 6f 6e 73 20 73 69 6d iangulations sim
1340: 70 6c 79 20 72 65 70 72 65 73 65 6e 74 20 61 20 ply represent a
1350: 73 70 65 63 69 61 6c 20 63 61 73 65 20 6f 66 20 special case of
1360: 74 65 73 73 65 6c 6c 61 74 69 6f 6e 73 3a 20 69 tessellations: i
1370: 6e 20 74 68 69 73 20 63 61 73 65 20 61 6c 6c 20 n this case all
1380: 63 65 6c 6c 73 20 61 72 65 20 72 65 70 72 65 73 cells are repres
1390: 65 6e 74 65 64 20 62 79 20 67 65 6e 65 72 69 63 ented by generic
13a0: 20 3c 62 3e 74 72 69 61 6e 67 6c 65 73 3c 2f 62 <b>triangles</b
13b0: 3e 2c 20 6e 6f 74 20 6e 65 63 65 73 73 61 72 69 >, not necessari
13c0: 6c 79 20 6f 66 20 74 68 65 20 65 71 75 69 6c 61 ly of the equila
13d0: 74 65 72 61 6c 20 6b 69 6e 64 2e 3c 62 72 3e 0d teral kind.<br>.
13e0: 0a 41 20 3c 62 3e 44 65 6c 61 75 6e 61 79 20 54 .A <b>Delaunay T
13f0: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 3c 2f 62 3e riangulation</b>
1400: 20 69 73 20 76 65 72 79 20 70 65 63 75 6c 69 61 is very peculia
1410: 72 20 62 65 63 61 75 73 65 20 61 20 73 70 65 63 r because a spec
1420: 69 66 69 63 20 63 6f 6e 73 74 72 61 69 6e 74 20 ific constraint
1430: 69 73 20 69 6d 70 6f 73 65 64 2e 3c 62 72 3e 0d is imposed.<br>.
1440: 0a 41 6c 6c 20 74 72 69 61 6e 67 6c 65 73 20 69 .All triangles i
1450: 6e 20 61 20 44 65 6c 61 75 6e 61 79 20 74 72 69 n a Delaunay tri
1460: 61 6e 67 75 6c 61 74 69 6f 6e 20 6d 75 73 74 20 angulation must
1470: 73 61 74 69 73 66 79 20 74 68 65 20 3c 75 3e 3c satisfy the <u><
1480: 69 3e 65 6d 70 74 79 20 63 69 72 63 6c 65 3c 2f i>empty circle</
1490: 69 3e 3c 2f 75 3e 20 70 72 6f 70 65 72 74 79 3a i></u> property:
14a0: 20 69 2e 65 2e 20 66 6f 72 20 65 61 63 68 20 65 i.e. for each e
14b0: 64 67 65 20 77 65 20 63 61 6e 20 66 69 6e 64 20 dge we can find
14c0: 61 20 63 69 72 63 6c 65 20 63 6f 6e 74 61 69 6e a circle contain
14d0: 69 6e 67 20 74 68 65 20 65 64 67 65 27 73 20 65 ing the edge's e
14e0: 6e 64 70 6f 69 6e 74 73 20 62 75 74 20 6e 6f 74 ndpoints but not
14f0: 20 63 6f 6e 74 61 69 6e 69 6e 67 20 61 6e 79 20 containing any
1500: 6f 74 68 65 72 20 70 6f 69 6e 74 73 2e 0d 0a 3c other points...<
1510: 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f 65 a href="http://e
1520: 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f 72 67 2f n.wikipedia.org/
1530: 77 69 6b 69 2f 44 65 6c 61 75 6e 61 79 5f 74 72 wiki/Delaunay_tr
1540: 69 61 6e 67 75 6c 61 74 69 6f 6e 22 3e 72 65 61 iangulation">rea
1550: 64 20 6d 6f 72 65 3c 2f 61 3e 3c 62 72 3e 3c 62 d more</a><br><b
1560: 72 3e 0d 0a 43 6f 6d 70 75 74 69 6e 67 20 61 20 r>..Computing a
1570: 44 65 6c 61 75 6e 61 79 20 54 72 69 61 6e 67 75 Delaunay Triangu
1580: 6c 61 74 69 6f 6e 20 72 65 70 72 65 73 65 6e 74 lation represent
1590: 69 6e 67 20 6d 61 6e 79 20 70 6f 69 6e 74 73 20 ing many points
15a0: 69 73 20 61 20 76 65 72 79 20 63 6f 6d 70 6c 65 is a very comple
15b0: 78 20 6f 70 65 72 61 74 69 6f 6e 2c 20 61 6e 64 x operation, and
15c0: 20 6f 6e 65 20 70 6f 73 73 69 62 6c 79 20 69 6d one possibly im
15d0: 70 6f 73 69 6e 67 20 61 20 68 75 67 65 20 63 6f posing a huge co
15e0: 6d 70 75 74 61 74 69 6f 6e 61 6c 20 6c 6f 61 64 mputational load
15f0: 20 61 6e 64 20 6d 61 79 20 62 65 20 72 65 71 75 and may be requ
1600: 69 72 69 6e 67 20 61 20 6c 6f 6e 67 20 74 69 6d iring a long tim
1610: 65 2e 0d 0a 48 61 70 70 69 6c 79 20 65 6e 6f 75 e...Happily enou
1620: 67 68 20 6d 61 6e 79 20 68 69 67 68 6c 79 20 65 gh many highly e
1630: 66 66 69 63 69 65 6e 74 20 61 6c 67 6f 72 69 74 fficient algorit
1640: 68 6d 73 20 68 61 76 65 20 62 65 65 6e 20 61 6c hms have been al
1650: 72 65 61 64 79 20 64 65 76 65 6c 6f 70 65 64 20 ready developed
1660: 66 6f 72 20 74 68 65 20 44 65 6c 61 75 6e 61 79 for the Delaunay
1670: 20 70 72 6f 62 6c 65 6d 2e 3c 62 72 3e 0d 0a 54 problem.<br>..T
1680: 68 65 20 6e 65 78 74 2d 74 6f 2d 63 6f 6d 65 20 he next-to-come
1690: 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f <a href="http://
16a0: 74 72 61 63 2e 6f 73 67 65 6f 2e 6f 72 67 2f 67 trac.osgeo.org/g
16b0: 65 6f 73 2f 22 3e 47 45 4f 53 20 33 2e 34 2e 30 eos/">GEOS 3.4.0
16c0: 3c 2f 61 3e 20 77 69 6c 6c 20 73 75 70 70 6f 72 </a> will suppor
16d0: 74 20 44 65 6c 61 75 6e 61 79 20 54 72 69 61 6e t Delaunay Trian
16e0: 67 75 6c 61 74 69 6f 6e 73 3b 20 74 68 69 73 20 gulations; this
16f0: 47 45 4f 53 20 76 65 72 73 69 6f 6e 20 69 73 20 GEOS version is
1700: 63 75 72 72 65 6e 74 6c 79 20 73 74 69 6c 6c 20 currently still
1710: 75 6e 64 65 72 20 61 63 74 69 76 65 20 64 65 76 under active dev
1720: 65 6c 6f 70 6d 65 6e 74 2c 20 62 75 74 20 74 68 elopment, but th
1730: 65 20 3c 69 3e 65 78 70 65 72 69 6d 65 6e 74 61 e <i>experimenta
1740: 6c 3c 2f 69 3e 20 62 61 73 65 2d 63 6f 64 65 20 l</i> base-code
1750: 28 3c 69 3e 74 72 75 6e 6b 3c 2f 69 3e 29 20 73 (<i>trunk</i>) s
1760: 65 65 6d 73 20 74 6f 20 62 65 20 73 74 61 62 6c eems to be stabl
1770: 65 20 65 6e 6f 75 67 68 20 74 6f 20 62 65 20 73 e enough to be s
1780: 61 66 65 6c 79 20 74 65 73 74 65 64 2e 0d 0a 53 afely tested...S
1790: 70 61 74 69 61 4c 69 74 65 20 61 6c 72 65 61 64 patiaLite alread
17a0: 79 20 72 65 6c 69 65 73 20 6f 6e 20 47 45 4f 53 y relies on GEOS
17b0: 20 66 6f 72 20 6d 61 6e 79 20 74 61 73 6b 73 2c for many tasks,
17c0: 20 73 6f 20 69 6e 74 65 67 72 61 74 69 6e 67 20 so integrating
17d0: 61 20 73 6d 6f 6f 74 68 20 73 75 70 70 6f 72 74 a smooth support
17e0: 20 66 6f 72 20 44 65 6c 61 75 6e 61 79 20 54 72 for Delaunay Tr
17f0: 69 61 6e 67 75 6c 61 74 69 6f 6e 20 61 73 20 77 iangulation as w
1800: 65 6c 6c 20 77 61 73 6e 27 74 20 61 74 20 61 6c ell wasn't at al
1810: 6c 20 64 69 66 66 69 63 75 6c 74 2e 3c 62 72 3e l difficult.<br>
1820: 3c 62 72 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 <br>..<table bgc
1830: 6f 6c 6f 72 3d 22 23 66 30 66 30 66 30 22 20 63 olor="#f0f0f0" c
1840: 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 63 ellspacing="4" c
1850: 65 6c 6c 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d ellpadding="8">.
1860: 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 69 3e 70 72 .<tr><td>..<i>pr
1870: 6f 74 6f 74 79 70 65 3c 2f 69 3e 3a 3c 68 72 3e ototype</i>:<hr>
1880: 0d 0a 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 69 ..ST_DelaunayTri
1890: 61 6e 67 75 6c 61 74 69 6f 6e 28 20 69 6e 70 75 angulation( inpu
18a0: 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 t <i>Geometry</i
18b0: 3e 20 29 20 3a 20 64 65 6c 61 75 6e 61 79 20 3c > ) : delaunay <
18c0: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 i>Geometry</i><b
18d0: 72 3e 0d 0a 53 54 5f 44 65 6c 61 75 6e 61 79 54 r>..ST_DelaunayT
18e0: 72 69 61 6e 67 75 6c 61 74 69 6f 6e 28 20 69 6e riangulation( in
18f0: 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c put <i>Geometry<
1900: 2f 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 /i>, edges_only
1910: 3c 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 29 <i>boolean</i> )
1920: 20 3a 20 64 65 6c 61 75 6e 61 79 20 3c 69 3e 47 : delaunay <i>G
1930: 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 72 3e 0d eometry</i><br>.
1940: 0a 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 69 61 .ST_DelaunayTria
1950: 6e 67 75 6c 61 74 69 6f 6e 28 20 69 6e 70 75 74 ngulation( input
1960: 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e <i>Geometry</i>
1970: 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c 69 3e , edges_only <i>
1980: 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 74 6f 6c boolean</i>, tol
1990: 65 72 61 6e 63 65 20 3c 69 3e 64 6f 75 62 6c 65 erance <i>double
19a0: 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e 20 29 precision</i> )
19b0: 20 3a 20 64 65 6c 61 75 6e 61 79 20 3c 69 3e 47 : delaunay <i>G
19c0: 65 6f 6d 65 74 72 79 3c 2f 69 3e 0d 0a 3c 2f 74 eometry</i>..</t
19d0: 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 0d d></tr></table>.
19e0: 0a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 20 3c .<ul>..<li>the <
19f0: 62 3e 69 6e 70 75 74 3c 2f 62 3e 20 47 65 6f 6d b>input</b> Geom
1a00: 65 74 72 79 20 63 61 6e 20 62 65 20 6f 66 20 61 etry can be of a
1a10: 62 73 6f 6c 75 74 65 6c 79 20 61 72 62 69 74 72 bsolutely arbitr
1a20: 61 72 79 20 74 79 70 65 3b 20 61 6c 6c 20 4c 69 ary type; all Li
1a30: 6e 65 73 74 72 69 6e 67 73 20 61 6e 64 20 2f 20 nestrings and /
1a40: 6f 72 20 50 6f 6c 79 67 6f 77 6e 73 20 77 69 6c or Polygowns wil
1a50: 6c 20 65 76 65 6e 74 75 61 6c 6c 79 20 62 65 20 l eventually be
1a60: 64 69 73 73 6f 6c 76 65 64 20 69 6e 74 6f 20 50 dissolved into P
1a70: 6f 69 6e 74 73 20 63 6f 72 72 65 73 70 6f 6e 64 oints correspond
1a80: 69 6e 67 20 74 6f 20 76 65 72 74 69 63 65 73 2e ing to vertices.
1a90: 3c 62 72 3e 0d 0a 53 6f 20 61 66 74 65 72 20 61 <br>..So after a
1aa0: 6c 6c 20 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 ll ST_DelaunayTr
1ab0: 69 61 6e 67 75 6c 61 74 69 6f 6e 28 29 20 77 69 iangulation() wi
1ac0: 6c 6c 20 61 6c 77 61 79 73 20 70 72 6f 63 65 73 ll always proces
1ad0: 73 20 61 20 4d 75 6c 74 69 50 6f 69 6e 74 2e 3c s a MultiPoint.<
1ae0: 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 /li>..<li>the op
1af0: 74 69 6f 6e 61 6c 20 3c 62 3e 65 64 67 65 73 5f tional <b>edges_
1b00: 6f 6e 6c 79 3c 2f 62 3e 20 61 72 67 75 6d 65 6e only</b> argumen
1b10: 74 20 77 69 6c 6c 20 62 65 20 69 6e 74 65 72 70 t will be interp
1b20: 72 65 74 65 64 20 61 73 20 66 6f 6c 6c 6f 77 73 reted as follows
1b30: 3a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 69 66 20 3c 62 :<ul>..<li>if <b
1b40: 3e 46 41 4c 53 45 3c 2f 62 3e 20 28 3c 69 3e 64 >FALSE</b> (<i>d
1b50: 65 66 61 75 6c 74 20 76 61 6c 75 65 3c 2f 69 3e efault value</i>
1b60: 29 20 61 20 4d 75 6c 74 69 50 6f 6c 79 67 6f 6e ) a MultiPolygon
1b70: 20 77 69 6c 6c 20 62 65 20 72 65 74 75 72 6e 65 will be returne
1b80: 64 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 69 66 20 d.</li>..<li>if
1b90: 3c 62 3e 54 52 55 45 3c 2f 62 3e 20 61 20 4d 75 <b>TRUE</b> a Mu
1ba0: 6c 74 69 4c 69 6e 65 73 74 72 69 6e 67 20 77 69 ltiLinestring wi
1bb0: 6c 6c 20 62 65 20 72 65 74 75 72 6e 65 64 20 28 ll be returned (
1bc0: 73 69 6d 70 6c 79 20 72 65 70 72 65 73 65 6e 74 simply represent
1bd0: 69 6e 67 20 74 68 65 20 74 72 69 61 6e 67 6c 65 ing the triangle
1be0: 73 20 65 64 67 65 73 29 2e 3c 2f 6c 69 3e 0d 0a s edges).</li>..
1bf0: 3c 2f 75 6c 3e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e </ul></li>..<li>
1c00: 74 68 65 20 6f 70 74 69 6f 6e 61 6c 20 3c 62 3e the optional <b>
1c10: 74 6f 6c 65 72 61 6e 63 65 3c 2f 62 3e 20 61 72 tolerance</b> ar
1c20: 67 75 6d 65 6e 74 20 69 73 20 69 6e 74 65 6e 64 gument is intend
1c30: 65 64 20 74 6f 20 6e 6f 72 6d 61 6c 69 7a 65 20 ed to normalize
1c40: 74 68 65 20 69 6e 70 75 74 20 70 6f 69 6e 74 2d the input point-
1c50: 73 65 74 2c 20 73 75 70 70 72 65 73 73 69 6e 67 set, suppressing
1c60: 20 72 65 70 65 61 74 65 64 20 28 6f 72 20 74 6f repeated (or to
1c70: 6f 20 6d 75 63 68 20 63 6c 6f 73 65 29 20 70 6f o much close) po
1c80: 69 6e 74 73 2e 0d 0a 42 79 20 64 65 66 61 75 6c ints...By defaul
1c90: 74 20 61 20 3c 62 3e 30 2e 30 3c 2f 62 3e 20 74 t a <b>0.0</b> t
1ca0: 6f 6c 65 72 61 6e 63 65 20 77 69 6c 6c 20 62 65 olerance will be
1cb0: 20 61 73 73 75 6d 65 64 2e 3c 2f 6c 69 3e 0d 0a assumed.</li>..
1cc0: 3c 2f 75 6c 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 3c </ul></td></tr><
1cd0: 2f 74 61 62 6c 65 3e 0d 0a 3c 74 61 62 6c 65 20 /table>..<table
1ce0: 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 cellspacing="4"
1cf0: 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 34 22 3e cellpadding="4">
1d00: 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 74 61 62 ..<tr><td>..<tab
1d10: 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 30 66 le bgcolor="#f0f
1d20: 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 6e 67 0f0" cellspacing
1d30: 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 ="4" cellpadding
1d40: 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d ="8">..<tr><td>.
1d50: 0a 3c 62 3e 53 45 4c 45 43 54 20 53 54 5f 44 65 .<b>SELECT ST_De
1d60: 6c 61 75 6e 61 79 54 72 69 61 6e 67 75 6c 61 74 launayTriangulat
1d70: 69 6f 6e 28 53 54 5f 43 6f 6c 6c 65 63 74 28 67 ion(ST_Collect(g
1d80: 65 6f 6d 65 74 72 79 29 29 3c 62 72 3e 0d 0a 46 eometry))<br>..F
1d90: 52 4f 4d 20 69 74 61 6c 79 5f 70 6f 70 75 6c 61 ROM italy_popula
1da0: 74 65 64 5f 70 6c 61 63 65 73 3b 3c 2f 62 3e 0d ted_places;</b>.
1db0: 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 .</td></tr>..</t
1dc0: 61 62 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 able><br>..This
1dd0: 53 51 4c 20 71 75 65 72 79 20 77 69 6c 6c 20 72 SQL query will r
1de0: 65 74 75 72 6e 20 61 20 44 65 6c 61 75 6e 61 79 eturn a Delaunay
1df0: 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 62 Triangulation b
1e00: 61 73 65 64 20 6f 6e 20 49 74 61 6c 79 27 73 20 ased on Italy's
1e10: 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 73 populated places
1e20: 20 28 61 62 6f 75 74 20 38 2c 30 30 30 2b 20 50 (about 8,000+ P
1e30: 6f 69 6e 74 73 29 2e 3c 62 72 3e 0d 0a 54 68 65 oints).<br>..The
1e40: 20 76 69 73 75 61 6c 20 65 78 61 6d 70 6c 65 20 visual example
1e50: 73 69 6d 70 6c 79 20 63 6f 76 65 72 73 20 54 75 simply covers Tu
1e60: 73 63 61 6e 79 2c 20 73 6f 20 74 68 65 20 65 6e scany, so the en
1e70: 73 75 72 65 20 61 6e 20 65 61 73 79 20 72 65 61 sure an easy rea
1e80: 64 61 62 69 6c 69 74 79 2e 20 0d 0a 3c 2f 74 64 dability. ..</td
1e90: 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 >..<td><img bord
1ea0: 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 er="1" src="http
1eb0: 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e ://www.gaia-gis.
1ec0: 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 it/gaia-sins/wri
1ed0: 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 64 65 6c te-view-pics/del
1ee0: 61 75 6e 61 79 2e 70 6e 67 22 20 61 6c 74 3d 22 aunay.png" alt="
1ef0: 64 65 6c 61 75 6e 61 79 20 74 72 69 61 6e 67 75 delaunay triangu
1f00: 6c 61 74 69 6f 6e 22 3e 3c 2f 74 64 3e 3c 2f 74 lation"></td></t
1f10: 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 62 r>..</table>..<b
1f20: 72 3e 3c 68 72 3e 0d 0a 3c 68 33 3e 56 6f 72 6f r><hr>..<h3>Voro
1f30: 6e 6f 6a 20 44 69 61 67 72 61 6d 73 3c 2f 68 33 noj Diagrams</h3
1f40: 3e 0d 0a 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 >..<table cellsp
1f50: 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 acing="4" cellpa
1f60: 64 64 69 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e dding="4">..<tr>
1f70: 3c 74 64 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 <td align="cente
1f80: 72 22 3e 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 r"><img border="
1f90: 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 1" src="http://w
1fa0: 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 ww.gaia-gis.it/g
1fb0: 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 aia-sins/write-v
1fc0: 69 65 77 2d 70 69 63 73 2f 76 6f 72 6f 6e 6f 6a iew-pics/voronoj
1fd0: 2d 31 2e 70 6e 67 22 20 61 6c 74 3d 22 76 6f 72 -1.png" alt="vor
1fe0: 6f 6e 6f 6a 2d 64 65 6c 61 75 6e 61 79 20 72 65 onoj-delaunay re
1ff0: 6c 61 74 69 6f 6e 73 68 69 70 22 3e 0d 0a 3c 2f lationship">..</
2000: 74 64 3e 3c 74 64 3e 0d 0a 54 68 65 20 3c 62 3e td><td>..The <b>
2010: 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 3c Voronoj Diagram<
2020: 2f 62 3e 20 73 69 6d 70 6c 79 20 69 73 20 74 68 /b> simply is th
2030: 65 20 3c 69 3e 3c 75 3e 64 75 61 6c 20 67 72 61 e <i><u>dual gra
2040: 70 68 3c 2f 75 3e 3c 2f 69 3e 20 6f 66 20 74 68 ph</u></i> of th
2050: 65 20 3c 62 3e 44 65 6c 61 75 6e 61 79 20 54 72 e <b>Delaunay Tr
2060: 69 61 6e 67 75 6c 61 74 69 6f 6e 3c 2f 62 3e 2e iangulation</b>.
2070: 0d 0a 41 20 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 ..A Voronoj Diag
2080: 72 61 6d 20 73 74 69 6c 6c 20 69 73 20 61 20 74 ram still is a t
2090: 65 73 73 65 6c 6c 61 74 69 6f 6e 2c 20 61 6e 64 essellation, and
20a0: 20 63 65 6c 6c 73 20 69 6e 20 61 20 56 6f 72 6f cells in a Voro
20b0: 6e 6f 6a 20 63 61 6e 20 68 61 76 65 20 61 6e 79 noj can have any
20c0: 20 61 72 62 69 74 72 61 72 79 20 70 6f 6c 79 67 arbitrary polyg
20d0: 6f 6e 61 6c 20 28 69 72 72 65 67 75 6c 61 72 29 onal (irregular)
20e0: 20 73 68 61 70 65 2e 3c 62 72 3e 3c 62 72 3e 0d shape.<br><br>.
20f0: 0a 54 68 69 73 20 66 69 67 75 72 65 20 63 6c 65 .This figure cle
2100: 61 72 6c 79 20 73 68 6f 77 73 20 74 68 65 20 72 arly shows the r
2110: 65 6c 61 74 69 6f 6e 20 6a 6f 69 6e 69 6e 67 20 elation joining
2120: 74 68 65 20 44 65 6c 61 75 6e 61 79 20 54 72 69 the Delaunay Tri
2130: 61 6e 67 75 6c 61 74 69 6f 6e 20 61 6e 64 20 74 angulation and t
2140: 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 he corresponding
2150: 20 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 72 61 6d Voronoj Diagram
2160: 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 45 61 63 68 20 .<br><br>..Each
2170: 73 69 6e 67 6c 65 20 56 6f 72 6f 6e 6f 6a 27 73 single Voronoj's
2180: 20 63 65 6c 6c 20 69 73 20 6f 62 74 61 69 6e 65 cell is obtaine
2190: 64 20 62 79 20 63 6f 6e 6e 65 63 74 69 6e 67 20 d by connecting
21a0: 61 6c 6c 20 74 68 65 20 3c 69 3e 63 69 72 63 75 all the <i>circu
21b0: 6d 63 65 6e 74 65 72 73 3c 2f 69 3e 20 6f 66 20 mcenters</i> of
21c0: 61 64 6a 61 63 65 6e 74 20 44 65 6c 61 75 6e 61 adjacent Delauna
21d0: 79 27 73 20 74 72 69 61 6e 67 6c 65 73 3b 20 63 y's triangles; c
21e0: 6f 6e 73 65 71 75 65 6e 74 6c 79 20 65 61 63 68 onsequently each
21f0: 20 56 6f 72 6f 6e 6f 6a 20 63 65 6c 6c 20 73 75 Voronoj cell su
2200: 72 65 6c 79 20 63 6f 6e 74 61 69 6e 73 20 6f 6e rely contains on
2210: 65 20 28 61 6e 64 20 6f 6e 6c 79 20 6f 6e 65 29 e (and only one)
2220: 20 44 65 6c 61 75 6e 61 79 27 73 20 6e 6f 64 65 Delaunay's node
2230: 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 65 20 63 .<br><br>..The c
2240: 65 6c 6c 20 69 6e 20 74 68 65 20 56 6f 72 6f 6e ell in the Voron
2250: 6f 6a 20 44 69 61 67 72 61 6d 20 70 72 65 73 65 oj Diagram prese
2260: 6e 74 73 20 61 6e 20 69 6e 74 65 72 65 73 74 69 nts an interesti
2270: 6e 67 20 70 72 6f 70 65 72 74 79 3a 20 61 6c 6c ng property: all
2280: 20 70 6f 69 6e 74 73 20 66 61 6c 6c 69 6e 67 20 points falling
2290: 77 69 74 68 69 6e 20 74 68 65 20 73 61 6d 65 20 within the same
22a0: 63 65 6c 6c 20 61 72 65 20 65 6e 73 75 72 65 64 cell are ensured
22b0: 20 74 6f 20 62 65 20 6e 65 61 72 65 73 74 20 74 to be nearest t
22c0: 6f 20 74 68 65 20 44 65 6c 61 75 6e 61 79 27 73 o the Delaunay's
22d0: 20 6e 6f 64 65 20 70 6c 61 63 65 64 20 6f 6e 20 node placed on
22e0: 74 68 65 20 63 65 6c 6c 20 69 74 73 65 6c 66 20 the cell itself
22f0: 74 68 61 6e 20 74 6f 20 61 6e 79 20 6f 74 68 65 than to any othe
2300: 72 20 44 65 6c 61 75 6e 61 79 27 73 20 6e 6f 64 r Delaunay's nod
2310: 65 20 70 6c 61 63 65 64 20 69 6e 20 61 20 64 69 e placed in a di
2320: 66 66 65 72 65 6e 74 20 63 65 6c 6c 2e 3c 62 72 fferent cell.<br
2330: 3e 3c 62 72 3e 0d 0a 53 6f 20 74 68 65 20 56 6f ><br>..So the Vo
2340: 72 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 20 69 73 ronoj Diagram is
2350: 20 61 20 76 65 72 79 20 65 66 66 65 63 74 69 76 a very effectiv
2360: 65 20 63 6f 6e 63 65 70 74 75 61 6c 20 74 6f 6f e conceptual too
2370: 6c 20 61 6c 6c 6f 77 69 6e 67 20 74 6f 20 64 69 l allowing to di
2380: 76 69 64 65 20 61 6e 20 61 72 62 69 74 72 61 72 vide an arbitrar
2390: 79 20 73 70 61 63 65 20 72 65 67 69 6f 6e 20 69 y space region i
23a0: 6e 74 6f 20 6d 61 6e 79 20 3c 69 3e 72 61 74 69 nto many <i>rati
23b0: 6f 6e 61 6c 6c 79 20 64 65 66 69 6e 65 64 3c 2f onally defined</
23c0: 69 3e 20 63 65 6c 6c 73 2c 20 61 6e 64 20 69 73 i> cells, and is
23d0: 20 74 68 75 73 20 77 69 64 65 6c 79 20 75 73 65 thus widely use
23e0: 64 20 6f 6e 20 6d 61 6e 79 20 61 70 70 6c 69 63 d on many applic
23f0: 61 74 69 76 65 20 66 69 65 6c 64 73 20 62 61 73 ative fields bas
2400: 65 64 20 6f 6e 20 43 6f 6d 70 75 74 61 74 69 6f ed on Computatio
2410: 6e 61 6c 20 47 65 6f 6d 65 74 72 79 2e 0d 0a 54 nal Geometry...T
2420: 68 69 73 20 6f 62 76 69 6f 75 73 6c 79 20 69 6e his obviously in
2430: 63 6c 75 64 69 6e 67 20 47 65 6f 67 72 61 70 68 cluding Geograph
2440: 79 20 69 74 73 65 6c 66 2e 3c 62 72 3e 3c 62 72 y itself.<br><br
2450: 3e 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 70 >..<a href="http
2460: 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e ://en.wikipedia.
2470: 6f 72 67 2f 77 69 6b 69 2f 56 6f 72 6f 6e 6f 69 org/wiki/Voronoi
2480: 5f 74 65 73 73 65 6c 6c 61 74 69 6f 6e 22 3e 72 _tessellation">r
2490: 65 61 64 20 6d 6f 72 65 3c 2f 61 3e 0d 0a 3c 2f ead more</a>..</
24a0: 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c 74 td></tr>..<tr><t
24b0: 64 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 d align="center"
24c0: 3e 0d 0a 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 >..<img border="
24d0: 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 1" src="http://w
24e0: 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 ww.gaia-gis.it/g
24f0: 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 aia-sins/write-v
2500: 69 65 77 2d 70 69 63 73 2f 76 6f 72 6f 6e 6f 6a iew-pics/voronoj
2510: 2d 6f 70 65 6e 2e 70 6e 67 22 20 61 6c 74 3d 22 -open.png" alt="
2520: 76 6f 72 6f 6e 6f 6a 20 6f 70 65 6e 22 3e 20 0d voronoj open"> .
2530: 0a 3c 2f 74 64 3e 3c 74 64 3e 0d 0a 3c 75 3e 50 .</td><td>..<u>P
2540: 6c 65 61 73 65 20 6e 6f 74 65 3c 2f 75 3e 3a 20 lease note</u>:
2550: 61 6e 79 20 56 6f 72 6f 6e 6f 6a 20 44 69 61 67 any Voronoj Diag
2560: 72 61 6d 20 77 69 6c 6c 20 61 6c 77 61 79 73 20 ram will always
2570: 70 72 65 73 65 6e 74 20 61 6e 20 75 6e 70 6c 65 present an unple
2580: 61 73 61 6e 74 20 63 6f 6d 70 6c 69 63 61 74 69 asant complicati
2590: 6f 6e 3b 20 77 68 65 6e 20 72 65 61 63 68 69 6e on; when reachin
25a0: 67 20 74 68 65 20 65 78 74 65 72 69 6f 72 20 62 g the exterior b
25b0: 6f 75 6e 64 61 72 79 20 6f 66 20 74 68 65 20 69 oundary of the i
25c0: 6e 70 75 74 20 70 6f 69 6e 74 2d 73 65 74 2c 20 nput point-set,
25d0: 74 68 65 72 65 20 61 72 65 6e 27 74 20 65 6e 6f there aren't eno
25e0: 75 67 68 20 70 6f 69 6e 74 73 20 61 6c 6c 6f 77 ugh points allow
25f0: 69 6e 67 20 74 6f 20 70 72 6f 70 65 72 6c 79 20 ing to properly
2600: 63 6c 6f 73 65 20 61 20 63 65 6c 6c 2e 3c 62 72 close a cell.<br
2610: 3e 0d 0a 41 6e 64 20 63 6f 6e 73 65 71 75 65 6e >..And consequen
2620: 74 6c 79 20 6d 61 6e 79 20 63 65 6c 6c 73 20 6c tly many cells l
2630: 61 79 69 6e 67 20 6e 65 61 72 20 74 6f 20 74 68 aying near to th
2640: 65 20 65 78 74 65 72 69 6f 72 20 62 6f 75 6e 64 e exterior bound
2650: 61 72 79 20 61 63 74 75 61 6c 6c 79 20 61 72 65 ary actually are
2660: 20 3c 69 3e 6f 70 65 6e 20 63 65 6c 6c 73 3c 2f <i>open cells</
2670: 69 3e 2c 20 70 72 65 73 65 6e 74 69 6e 67 20 65 i>, presenting e
2680: 64 67 65 73 20 67 6f 69 6e 67 20 64 69 72 65 63 dges going direc
2690: 74 6c 79 20 74 6f 20 74 68 65 20 3c 69 3e 69 6e tly to the <i>in
26a0: 66 69 6e 69 74 65 3c 2f 69 3e 2e 3c 62 72 3e 3c finite</i>.<br><
26b0: 62 72 3e 0d 0a 54 68 65 20 64 69 72 65 63 74 69 br>..The directi
26c0: 6f 6e 73 20 6f 66 20 73 75 63 68 20 65 64 67 65 ons of such edge
26d0: 73 20 61 72 65 20 61 62 73 6f 6c 75 74 65 6c 79 s are absolutely
26e0: 20 77 65 6c 6c 20 64 65 74 65 72 6d 69 6e 65 64 well determined
26f0: 3b 20 62 75 74 20 61 73 73 69 67 6e 69 6e 67 20 ; but assigning
2700: 74 68 65 6d 20 61 20 66 69 6e 69 74 65 20 6c 65 them a finite le
2710: 6e 67 74 68 20 69 73 6e 27 74 20 61 6c 6c 6f 77 ngth isn't allow
2720: 65 64 20 61 74 20 61 6c 6c 2e 20 41 6e 64 20 63 ed at all. And c
2730: 6f 6e 73 65 71 75 65 6e 74 6c 79 20 69 73 6e 27 onsequently isn'
2740: 74 20 70 6f 73 73 69 62 6c 65 20 64 65 66 69 6e t possible defin
2750: 69 6e 67 20 61 20 70 6f 6c 79 67 6f 6e 20 72 65 ing a polygon re
2760: 70 72 65 73 65 6e 74 69 6e 67 20 74 68 65 73 65 presenting these
2770: 20 63 65 6c 6c 73 2e 3c 62 72 3e 3c 62 72 3e 0d cells.<br><br>.
2780: 0a 54 68 69 73 20 66 69 67 75 72 65 20 73 68 6f .This figure sho
2790: 77 73 20 61 20 6c 69 6d 69 74 65 64 20 56 6f 72 ws a limited Vor
27a0: 6f 6e 6f 6a 20 44 69 61 67 72 61 6d 20 61 6c 77 onoj Diagram alw
27b0: 61 79 73 20 62 61 73 65 64 20 6f 6e 20 74 68 65 ays based on the
27c0: 20 73 61 6d 65 20 64 61 74 61 73 65 74 20 61 73 same dataset as
27d0: 20 61 62 6f 76 65 2c 20 62 75 74 20 74 68 69 73 above, but this
27e0: 20 74 69 6d 65 20 69 6e 63 6c 75 64 69 6e 67 20 time including
27f0: 6f 6e 6c 79 20 50 6f 70 75 6c 61 74 65 64 20 50 only Populated P
2800: 6c 61 63 65 73 20 6c 61 79 69 6e 67 20 6f 6e 20 laces laying on
2810: 74 68 65 20 49 73 6c 61 6e 64 20 6f 66 20 45 6c the Island of El
2820: 62 61 2e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d ba...</td></tr>.
2830: 0a 3c 74 72 3e 3c 74 64 20 61 6c 69 67 6e 3d 22 .<tr><td align="
2840: 63 65 6e 74 65 72 22 3e 0d 0a 3c 69 6d 67 20 62 center">..<img b
2850: 6f 72 64 65 72 3d 22 31 22 20 73 72 63 3d 22 68 order="1" src="h
2860: 74 74 70 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 ttp://www.gaia-g
2870: 69 73 2e 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f is.it/gaia-sins/
2880: 77 72 69 74 65 2d 76 69 65 77 2d 70 69 63 73 2f write-view-pics/
2890: 76 6f 72 6f 6e 6f 6a 2d 66 72 61 6d 65 2e 70 6e voronoj-frame.pn
28a0: 67 22 20 61 6c 74 3d 22 76 6f 72 6f 6e 6f 6a 20 g" alt="voronoj
28b0: 66 72 61 6d 65 22 3e 20 0d 0a 3c 2f 74 64 3e 3c frame"> ..</td><
28c0: 74 64 3e 0d 0a 41 6e 79 77 61 79 20 77 65 20 63 td>..Anyway we c
28d0: 61 6e 20 75 73 65 66 75 6c 6c 79 20 61 70 70 6c an usefully appl
28e0: 79 20 61 20 3c 69 3e 74 72 69 63 6b 3c 2f 69 3e y a <i>trick</i>
28f0: 20 65 66 66 65 63 74 69 76 65 6c 79 20 61 6c 6c effectively all
2900: 6f 77 69 6e 67 20 74 6f 20 65 6e 73 75 72 65 20 owing to ensure
2910: 74 68 61 74 20 61 6c 6c 20 63 65 6c 6c 73 20 69 that all cells i
2920: 6e 20 61 20 56 6f 72 6f 6e 6f 6a 20 77 69 6c 6c n a Voronoj will
2930: 20 62 65 20 70 72 6f 70 65 72 6c 79 20 3c 69 3e be properly <i>
2940: 63 6c 6f 73 65 64 3c 2f 69 3e 2e 3c 62 72 3e 3c closed</i>.<br><
2950: 62 72 3e 0d 0a 57 65 20 73 69 6d 70 6c 79 20 68 br>..We simply h
2960: 61 76 65 20 74 6f 20 63 6f 6e 73 74 72 61 69 6e ave to constrain
2970: 20 74 68 65 20 56 6f 72 6f 6e 6f 6a 20 44 69 61 the Voronoj Dia
2980: 67 72 61 6d 20 77 69 74 68 69 6e 20 61 20 72 65 gram within a re
2990: 63 74 61 6e 67 75 6c 61 72 20 66 72 61 6d 65 20 ctangular frame
29a0: 6f 66 20 61 72 62 69 74 72 61 72 79 20 73 69 7a of arbitrary siz
29b0: 65 2c 20 74 68 65 6e 20 63 6f 6d 70 75 74 69 6e e, then computin
29c0: 67 20 74 68 65 20 69 6e 74 65 72 73 65 63 74 69 g the intersecti
29d0: 6f 6e 73 20 62 65 74 77 65 65 6e 20 69 6e 66 69 ons between infi
29e0: 6e 69 74 65 20 6c 69 6e 65 73 20 61 6e 64 20 74 nite lines and t
29f0: 68 65 20 66 72 61 6d 65 20 69 74 73 65 6c 66 2e he frame itself.
2a00: 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 66 <br><br>..This f
2a10: 69 67 75 72 65 20 73 68 6f 77 73 20 74 68 65 20 igure shows the
2a20: 73 61 6d 65 20 56 6f 72 6f 6e 6f 6a 20 61 73 20 same Voronoj as
2a30: 62 65 66 6f 72 65 2c 20 74 68 69 73 20 74 69 6d before, this tim
2a40: 65 20 6f 70 70 6f 72 74 75 6e 65 6c 79 20 66 72 e opportunely fr
2a50: 61 6d 65 64 3b 20 61 73 20 79 6f 75 20 63 61 6e amed; as you can
2a60: 20 65 61 73 69 6c 79 20 6e 6f 74 69 63 65 2c 20 easily notice,
2a70: 6e 6f 77 20 61 6c 6c 20 63 65 6c 6c 73 20 61 72 now all cells ar
2a80: 65 20 73 75 72 65 6c 79 20 63 6c 6f 73 65 64 20 e surely closed
2a90: 61 6e 64 20 63 61 6e 20 62 65 20 73 61 66 65 6c and can be safel
2aa0: 79 20 62 65 20 72 65 70 72 65 73 65 6e 74 65 64 y be represented
2ab0: 20 62 79 20 61 20 77 65 6c 6c 20 64 65 66 69 6e by a well defin
2ac0: 65 64 20 70 6f 6c 79 67 6f 6e 2e 3c 62 72 3e 3c ed polygon.<br><
2ad0: 62 72 3e 0d 0a 54 68 65 20 73 69 7a 65 20 28 61 br>..The size (a
2ae0: 6b 61 20 65 78 74 65 6e 74 29 20 6f 66 20 74 68 ka extent) of th
2af0: 65 20 66 72 61 6d 65 20 69 73 20 61 62 73 6f 6c e frame is absol
2b00: 75 74 65 6c 79 20 61 72 62 69 74 72 61 72 79 2c utely arbitrary,
2b10: 20 61 6e 64 20 63 61 6e 20 62 65 20 66 72 65 65 and can be free
2b20: 6c 79 20 73 65 74 20 61 73 20 79 6f 75 20 77 69 ly set as you wi
2b30: 73 68 20 62 65 74 74 65 72 20 61 63 63 6f 72 64 sh better accord
2b40: 69 6e 67 6c 79 20 74 6f 20 79 6f 75 72 20 73 70 ingly to your sp
2b50: 65 63 69 66 69 63 20 72 65 71 75 69 72 65 6d 65 ecific requireme
2b60: 6e 74 73 2e 3c 62 72 3e 0d 0a 3c 75 3e 50 6c 65 nts.<br>..<u>Ple
2b70: 61 73 65 20 6e 6f 74 69 63 65 3c 2f 75 3e 3a 20 ase notice</u>:
2b80: 74 68 65 20 62 6c 75 65 20 61 6e 64 20 74 68 65 the blue and the
2b90: 20 72 65 64 20 66 72 61 6d 65 20 68 61 76 65 20 red frame have
2ba0: 61 20 73 74 72 6f 6e 67 6c 79 20 64 69 66 66 65 a strongly diffe
2bb0: 72 65 6e 74 20 65 78 74 65 6e 74 2c 20 62 75 74 rent extent, but
2bc0: 20 62 6f 74 68 20 74 68 65 6d 20 68 61 76 65 20 both them have
2bd0: 74 68 65 20 73 61 6d 65 20 69 64 65 6e 74 69 63 the same identic
2be0: 61 6c 20 6f 76 65 72 61 6c 6c 20 73 68 61 70 65 al overall shape
2bf0: 2e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c ...</td></tr>..<
2c00: 2f 74 61 62 6c 65 3e 0d 0a 3c 61 20 68 72 65 66 /table>..<a href
2c10: 3d 22 68 74 74 70 3a 2f 2f 74 72 61 63 2e 6f 73 ="http://trac.os
2c20: 67 65 6f 2e 6f 72 67 2f 67 65 6f 73 2f 22 3e 47 geo.org/geos/">G
2c30: 45 4f 53 20 33 2e 34 2e 30 3c 2f 61 3e 20 77 69 EOS 3.4.0</a> wi
2c40: 6c 6c 20 6e 6f 74 20 64 69 72 65 63 74 6c 79 20 ll not directly
2c50: 73 75 70 70 6f 72 74 20 56 6f 72 6f 6e 6f 6a 3b support Voronoj;
2c60: 20 73 6f 20 74 68 65 20 53 70 61 74 69 61 4c 69 so the SpatiaLi
2c70: 74 65 20 6f 77 6e 20 73 75 70 70 6f 72 74 20 69 te own support i
2c80: 73 20 62 61 73 65 64 20 6f 6e 20 61 6e 20 6f 72 s based on an or
2c90: 69 67 69 6e 61 6c 20 69 6d 70 6c 65 6d 65 6e 74 iginal implement
2ca0: 61 74 69 6f 6e 20 28 62 61 73 65 64 20 69 6e 20 ation (based in
2cb0: 74 75 72 6e 20 6f 6e 20 74 68 65 20 44 65 6c 61 turn on the Dela
2cc0: 75 6e 61 79 20 73 75 70 70 6f 72 74 20 6d 61 64 unay support mad
2cd0: 65 20 61 76 61 69 6c 61 62 6c 65 20 62 79 20 47 e available by G
2ce0: 45 4f 53 29 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 3c EOS).<br><br>..<
2cf0: 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 table bgcolor="#
2d00: 66 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 63 f0f0f0" cellspac
2d10: 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 ing="4" cellpadd
2d20: 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 ing="8">..<tr><t
2d30: 64 3e 0d 0a 3c 69 3e 70 72 6f 74 6f 74 79 70 65 d>..<i>prototype
2d40: 3c 2f 69 3e 3a 3c 68 72 3e 0d 0a 53 54 5f 56 6f </i>:<hr>..ST_Vo
2d50: 72 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 20 69 6e ronojDiagram( in
2d60: 70 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c put <i>Geometry<
2d70: 2f 69 3e 20 29 20 3a 20 76 6f 72 6f 6e 6f 6a 20 /i> ) : voronoj
2d80: 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c <i>Geometry</i><
2d90: 62 72 3e 0d 0a 53 54 5f 56 6f 72 6f 6e 6f 6a 44 br>..ST_VoronojD
2da0: 69 61 67 72 61 6d 28 20 69 6e 70 75 74 20 3c 69 iagram( input <i
2db0: 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 2c 20 65 >Geometry</i>, e
2dc0: 64 67 65 73 5f 6f 6e 6c 79 20 3c 69 3e 62 6f 6f dges_only <i>boo
2dd0: 6c 65 61 6e 3c 2f 69 3e 20 29 20 3a 20 76 6f 72 lean</i> ) : vor
2de0: 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 74 72 79 onoj <i>Geometry
2df0: 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 56 6f 72 </i><br>..ST_Vor
2e00: 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 20 69 6e 70 onojDiagram( inp
2e10: 75 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f ut <i>Geometry</
2e20: 69 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c i>, edges_only <
2e30: 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 65 i>boolean</i>, e
2e40: 78 74 72 61 5f 66 72 61 6d 65 5f 73 69 7a 65 20 xtra_frame_size
2e50: 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 69 73 <i>double precis
2e60: 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 76 6f 72 6f ion</i> ) : voro
2e70: 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c noj <i>Geometry<
2e80: 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 56 6f 72 6f /i><br>..ST_Voro
2e90: 6e 6f 6a 44 69 61 67 72 61 6d 28 20 69 6e 70 75 nojDiagram( inpu
2ea0: 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 t <i>Geometry</i
2eb0: 3e 2c 20 65 64 67 65 73 5f 6f 6e 6c 79 20 3c 69 >, edges_only <i
2ec0: 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 65 78 >boolean</i>, ex
2ed0: 74 72 61 5f 66 72 61 6d 65 5f 73 69 7a 65 20 3c tra_frame_size <
2ee0: 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 69 73 69 i>double precisi
2ef0: 6f 6e 3c 2f 69 3e 2c 20 74 6f 6c 65 72 61 6e 63 on</i>, toleranc
2f00: 65 20 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 e <i>double prec
2f10: 69 73 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 76 6f ision</i> ) : vo
2f20: 72 6f 6e 6f 6a 20 3c 69 3e 47 65 6f 6d 65 74 72 ronoj <i>Geometr
2f30: 79 3c 2f 69 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 y</i>..</td></tr
2f40: 3e 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 75 6c 3e 0d ></table>..<ul>.
2f50: 0a 3c 6c 69 3e 74 68 65 20 3c 62 3e 69 6e 70 75 .<li>the <b>inpu
2f60: 74 3c 2f 62 3e 20 47 65 6f 6d 65 74 72 79 20 63 t</b> Geometry c
2f70: 61 6e 20 62 65 20 6f 66 20 61 62 73 6f 6c 75 74 an be of absolut
2f80: 65 6c 79 20 61 72 62 69 74 72 61 72 79 20 74 79 ely arbitrary ty
2f90: 70 65 3b 20 61 6c 6c 20 4c 69 6e 65 73 74 72 69 pe; all Linestri
2fa0: 6e 67 73 20 61 6e 64 20 2f 20 6f 72 20 50 6f 6c ngs and / or Pol
2fb0: 79 67 6f 77 6e 73 20 77 69 6c 6c 20 65 76 65 6e ygowns will even
2fc0: 74 75 61 6c 6c 79 20 62 65 20 64 69 73 73 6f 6c tually be dissol
2fd0: 76 65 64 20 69 6e 74 6f 20 50 6f 69 6e 74 73 20 ved into Points
2fe0: 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f corresponding to
2ff0: 20 76 65 72 74 69 63 65 73 2e 3c 62 72 3e 0d 0a vertices.<br>..
3000: 53 6f 20 61 66 74 65 72 20 61 6c 6c 20 53 54 5f So after all ST_
3010: 56 6f 72 6f 6e 6f 6a 44 69 61 67 72 61 6d 28 29 VoronojDiagram()
3020: 20 28 65 78 61 63 74 6c 79 20 61 73 20 53 54 5f (exactly as ST_
3030: 44 65 6c 61 75 6e 61 79 54 72 69 61 6e 67 75 6c DelaunayTriangul
3040: 61 74 69 6f 6e 29 20 77 69 6c 6c 20 61 6c 77 61 ation) will alwa
3050: 79 73 20 70 72 6f 63 65 73 73 20 61 20 4d 75 6c ys process a Mul
3060: 74 69 50 6f 69 6e 74 2e 3c 2f 6c 69 3e 0d 0a 3c tiPoint.</li>..<
3070: 6c 69 3e 74 68 65 20 6f 70 74 69 6f 6e 61 6c 20 li>the optional
3080: 3c 62 3e 65 64 67 65 73 5f 6f 6e 6c 79 3c 2f 62 <b>edges_only</b
3090: 3e 20 61 72 67 75 6d 65 6e 74 20 77 69 6c 6c 20 > argument will
30a0: 62 65 20 69 6e 74 65 72 70 72 65 74 65 64 20 61 be interpreted a
30b0: 73 20 66 6f 6c 6c 6f 77 73 3a 3c 75 6c 3e 0d 0a s follows:<ul>..
30c0: 3c 6c 69 3e 69 66 20 3c 62 3e 46 41 4c 53 45 3c <li>if <b>FALSE<
30d0: 2f 62 3e 20 28 3c 69 3e 64 65 66 61 75 6c 74 20 /b> (<i>default
30e0: 76 61 6c 75 65 3c 2f 69 3e 29 20 61 20 4d 75 6c value</i>) a Mul
30f0: 74 69 50 6f 6c 79 67 6f 6e 20 77 69 6c 6c 20 62 tiPolygon will b
3100: 65 20 72 65 74 75 72 6e 65 64 2e 3c 2f 6c 69 3e e returned.</li>
3110: 0d 0a 3c 6c 69 3e 69 66 20 3c 62 3e 54 52 55 45 ..<li>if <b>TRUE
3120: 3c 2f 62 3e 20 61 20 4d 75 6c 74 69 4c 69 6e 65 </b> a MultiLine
3130: 73 74 72 69 6e 67 20 77 69 6c 6c 20 62 65 20 72 string will be r
3140: 65 74 75 72 6e 65 64 20 28 73 69 6d 70 6c 79 20 eturned (simply
3150: 72 65 70 72 65 73 65 6e 74 69 6e 67 20 74 68 65 representing the
3160: 20 74 72 69 61 6e 67 6c 65 73 20 65 64 67 65 73 triangles edges
3170: 29 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f ).</li>..</ul></
3180: 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 li>..<li>the opt
3190: 69 6f 6e 61 6c 20 3c 62 3e 65 78 74 72 61 5f 66 ional <b>extra_f
31a0: 72 61 6d 65 5f 73 69 7a 65 3c 2f 62 3e 20 61 6c rame_size</b> al
31b0: 6c 6f 77 73 20 74 6f 20 66 72 65 65 6c 79 20 73 lows to freely s
31c0: 65 74 20 74 68 65 20 65 78 74 65 6e 74 20 6f 66 et the extent of
31d0: 20 74 68 65 20 66 72 61 6d 65 2e 3c 62 72 3e 0d the frame.<br>.
31e0: 0a 54 68 69 73 20 61 72 67 75 6d 65 6e 74 20 69 .This argument i
31f0: 73 20 69 6e 74 65 6e 64 65 64 20 61 73 20 61 20 s intended as a
3200: 3c 69 3e 70 65 72 63 65 6e 74 3c 2f 69 3e 20 69 <i>percent</i> i
3210: 6e 63 72 65 61 73 65 20 6f 66 20 74 68 65 20 3c ncrease of the <
3220: 69 3e 6e 61 74 75 72 61 6c 20 65 78 74 65 6e 74 i>natural extent
3230: 3c 2f 69 3e 20 6f 66 20 56 6f 72 6f 6e 6f 6a 20 </i> of Voronoj
3240: 61 73 20 64 65 74 65 72 6d 69 6e 65 64 20 62 79 as determined by
3250: 20 65 76 61 6c 75 61 74 69 6e 67 20 61 6c 6c 20 evaluating all
3260: 44 65 6c 61 75 6e 61 79 27 73 20 6e 6f 64 65 73 Delaunay's nodes
3270: 20 61 6e 64 20 63 69 72 63 75 6d 63 65 6e 74 65 and circumcente
3280: 72 73 2e 3c 62 72 3e 0d 0a 42 79 20 64 65 66 61 rs.<br>..By defa
3290: 75 6c 74 20 61 20 3c 62 3e 35 25 20 65 78 74 72 ult a <b>5% extr
32a0: 61 5f 66 72 61 6d 65 5f 73 69 7a 65 3c 2f 62 3e a_frame_size</b>
32b0: 20 69 73 20 61 73 73 75 6d 65 64 2e 3c 2f 6c 69 is assumed.</li
32c0: 3e 20 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 69 > ..<li>the opti
32d0: 6f 6e 61 6c 20 3c 62 3e 74 6f 6c 65 72 61 6e 63 onal <b>toleranc
32e0: 65 3c 2f 62 3e 20 61 72 67 75 6d 65 6e 74 20 69 e</b> argument i
32f0: 73 20 69 6e 74 65 6e 64 65 64 20 74 6f 20 6e 6f s intended to no
3300: 72 6d 61 6c 69 7a 65 20 74 68 65 20 69 6e 70 75 rmalize the inpu
3310: 74 20 70 6f 69 6e 74 2d 73 65 74 2c 20 73 75 70 t point-set, sup
3320: 70 72 65 73 73 69 6e 67 20 72 65 70 65 61 74 65 pressing repeate
3330: 64 20 70 6f 69 6e 74 73 20 28 73 69 6d 70 6c 79 d points (simply
3340: 20 75 73 65 64 20 77 68 65 6e 20 69 6e 74 65 72 used when inter
3350: 6e 61 6c 6c 79 20 63 6f 6d 70 75 74 69 6e 67 20 nally computing
3360: 74 68 65 20 44 65 6c 61 75 6e 61 79 20 54 72 69 the Delaunay Tri
3370: 61 6e 67 75 6c 61 74 69 6f 6e 29 2e 0d 0a 42 79 angulation)...By
3380: 20 64 65 66 61 75 6c 74 20 61 20 3c 62 3e 30 2e default a <b>0.
3390: 30 3c 2f 62 3e 20 74 6f 6c 65 72 61 6e 63 65 20 0</b> tolerance
33a0: 77 69 6c 6c 20 62 65 20 61 73 73 75 6d 65 64 2e will be assumed.
33b0: 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f 74 64 </li>..</ul></td
33c0: 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 0d 0a ></tr></table>..
33d0: 3c 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 63 69 <table cellspaci
33e0: 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 ng="4" cellpaddi
33f0: 6e 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c 74 64 ng="4">..<tr><td
3400: 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 6f 6c 6f >..<table bgcolo
3410: 72 3d 22 23 66 30 66 30 66 30 22 20 63 65 6c 6c r="#f0f0f0" cell
3420: 73 70 61 63 69 6e 67 3d 22 34 22 20 63 65 6c 6c spacing="4" cell
3430: 70 61 64 64 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 padding="8">..<t
3440: 72 3e 3c 74 64 3e 0d 0a 3c 62 3e 53 45 4c 45 43 r><td>..<b>SELEC
3450: 54 20 53 54 5f 56 6f 72 6f 6e 6f 6a 44 69 61 67 T ST_VoronojDiag
3460: 72 61 6d 28 53 54 5f 43 6f 6c 6c 65 63 74 28 67 ram(ST_Collect(g
3470: 65 6f 6d 65 74 72 79 29 29 3c 62 72 3e 0d 0a 46 eometry))<br>..F
3480: 52 4f 4d 20 69 74 61 6c 79 5f 70 6f 70 75 6c 61 ROM italy_popula
3490: 74 65 64 5f 70 6c 61 63 65 73 3b 3c 2f 62 3e 0d ted_places;</b>.
34a0: 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 .</td></tr>..</t
34b0: 61 62 6c 65 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 able><br>..This
34c0: 53 51 4c 20 71 75 65 72 79 20 77 69 6c 6c 20 72 SQL query will r
34d0: 65 74 75 72 6e 20 61 20 56 6f 72 6f 6e 6f 6a 20 eturn a Voronoj
34e0: 44 69 61 67 72 61 6d 20 62 61 73 65 64 20 6f 6e Diagram based on
34f0: 20 49 74 61 6c 79 27 73 20 70 6f 70 75 6c 61 74 Italy's populat
3500: 65 64 20 70 6c 61 63 65 73 20 28 61 62 6f 75 74 ed places (about
3510: 20 38 2c 30 30 30 2b 20 50 6f 69 6e 74 73 29 2e 8,000+ Points).
3520: 3c 62 72 3e 0d 0a 54 68 65 20 76 69 73 75 61 6c <br>..The visual
3530: 20 65 78 61 6d 70 6c 65 20 73 69 6d 70 6c 79 20 example simply
3540: 63 6f 76 65 72 73 20 54 75 73 63 61 6e 79 2c 20 covers Tuscany,
3550: 73 6f 20 74 68 65 20 65 6e 73 75 72 65 20 61 6e so the ensure an
3560: 20 65 61 73 79 20 72 65 61 64 61 62 69 6c 69 74 easy readabilit
3570: 79 2e 3c 62 72 3e 0d 0a 41 6c 6c 20 3c 69 3e 70 y.<br>..All <i>p
3580: 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 73 3c opulated places<
3590: 2f 69 3e 20 28 61 6b 61 20 63 65 6c 6c 20 3c 69 /i> (aka cell <i
35a0: 3e 73 65 65 64 73 3c 2f 69 3e 29 20 61 72 65 20 >seeds</i>) are
35b0: 65 78 70 6c 69 63 69 74 6c 79 20 72 65 70 72 65 explicitly repre
35c0: 73 65 6e 74 65 64 2e 20 0d 0a 3c 2f 74 64 3e 0d sented. ..</td>.
35d0: 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 65 72 .<td><img border
35e0: 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 3a 2f ="1" src="http:/
35f0: 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 /www.gaia-gis.it
3600: 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 74 65 /gaia-sins/write
3610: 2d 76 69 65 77 2d 70 69 63 73 2f 76 6f 72 6f 6e -view-pics/voron
3620: 6f 6a 2d 32 2e 70 6e 67 22 20 61 6c 74 3d 22 76 oj-2.png" alt="v
3630: 6f 72 6f 6e 6f 6a 20 64 69 61 67 72 61 6d 22 3e oronoj diagram">
3640: 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 </td></tr>..</ta
3650: 62 6c 65 3e 0d 0a 3c 62 72 3e 3c 68 72 3e 0d 0a ble>..<br><hr>..
3660: 3c 68 33 3e 44 65 6c 61 75 6e 61 79 20 54 72 69 <h3>Delaunay Tri
3670: 61 6e 67 75 6c 61 74 69 6f 6e 2c 20 43 6f 6e 76 angulation, Conv
3680: 65 78 20 48 75 6c 6c 20 61 6e 64 20 43 6f 6e 63 ex Hull and Conc
3690: 61 76 65 20 48 75 6c 6c 3c 2f 68 33 3e 0d 0a 3c ave Hull</h3>..<
36a0: 74 61 62 6c 65 20 63 65 6c 6c 73 70 61 63 69 6e table cellspacin
36b0: 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 6e g="4" cellpaddin
36c0: 67 3d 22 34 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e g="4">..<tr><td>
36d0: 3c 69 6d 67 20 62 6f 72 64 65 72 3d 22 31 22 20 <img border="1"
36e0: 73 72 63 3d 22 68 74 74 70 3a 2f 2f 77 77 77 2e src="http://www.
36f0: 67 61 69 61 2d 67 69 73 2e 69 74 2f 67 61 69 61 gaia-gis.it/gaia
3700: 2d 73 69 6e 73 2f 77 72 69 74 65 2d 76 69 65 77 -sins/write-view
3710: 2d 70 69 63 73 2f 63 6f 6e 76 65 78 2e 70 6e 67 -pics/convex.png
3720: 22 20 61 6c 74 3d 22 64 65 6c 61 75 6e 61 79 2d " alt="delaunay-
3730: 63 6f 6e 76 65 78 68 75 6c 6c 20 72 65 6c 61 74 convexhull relat
3740: 69 6f 6e 73 68 69 70 22 3e 0d 0a 3c 2f 74 64 3e ionship">..</td>
3750: 3c 74 64 3e 0d 0a 41 6e 20 69 6e 74 65 72 65 73 <td>..An interes
3760: 74 69 6e 67 20 70 6f 69 6e 74 20 61 62 73 6f 6c ting point absol
3770: 75 74 65 6c 79 20 77 6f 72 74 68 20 74 6f 20 62 utely worth to b
3780: 65 20 65 78 70 6c 69 63 69 74 6c 79 20 6e 6f 74 e explicitly not
3790: 65 64 3a 20 74 68 65 20 62 6f 75 6e 64 61 72 79 ed: the boundary
37a0: 20 6f 66 20 61 6e 79 20 3c 62 3e 44 65 6c 61 75 of any <b>Delau
37b0: 6e 61 79 20 54 72 69 61 6e 67 75 6c 61 74 69 6f nay Triangulatio
37c0: 6e 3c 2f 62 3e 20 65 78 61 63 74 6c 79 20 63 6f n</b> exactly co
37d0: 72 72 65 73 70 6f 6e 64 73 20 74 6f 20 74 68 65 rresponds to the
37e0: 20 3c 62 3e 43 6f 6e 76 65 78 20 48 75 6c 6c 3c <b>Convex Hull<
37f0: 2f 62 3e 20 66 6f 72 20 74 68 65 20 73 61 6d 65 /b> for the same
3800: 20 69 6e 70 75 74 20 47 65 6f 6d 65 74 72 79 2e input Geometry.
3810: 0d 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a ..<a href="http:
3820: 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f //en.wikipedia.o
3830: 72 67 2f 77 69 6b 69 2f 43 6f 6e 76 65 78 5f 68 rg/wiki/Convex_h
3840: 75 6c 6c 22 3e 72 65 61 64 20 6d 6f 72 65 3c 2f ull">read more</
3850: 61 3e 3c 62 72 3e 3c 62 72 3e 0d 0a 41 6e 64 20 a><br><br>..And
3860: 74 68 69 73 20 69 6e 20 74 75 72 6e 20 6f 70 65 this in turn ope
3870: 6e 73 20 74 68 65 20 77 61 79 20 74 6f 20 61 20 ns the way to a
3880: 66 75 72 74 68 65 72 20 63 6f 6e 73 69 64 65 72 further consider
3890: 61 74 69 6f 6e 3a 20 77 65 20 63 6f 75 6c 64 20 ation: we could
38a0: 70 75 72 70 6f 73 65 6c 79 20 73 69 6d 70 6c 69 purposely simpli
38b0: 66 79 20 61 20 44 65 6c 61 75 6e 61 79 20 54 72 fy a Delaunay Tr
38c0: 69 61 6e 67 75 6c 61 74 69 6f 6e 20 73 6f 20 74 iangulation so t
38d0: 6f 20 67 65 74 20 61 20 3c 62 3e 63 6f 6e 63 61 o get a <b>conca
38e0: 76 65 20 68 75 6c 6c 3c 2f 62 3e 2e 3c 62 72 3e ve hull</b>.<br>
38f0: 0d 0a 59 6f 75 20 63 61 6e 20 67 65 74 20 6d 6f ..You can get mo
3900: 72 65 20 65 78 74 65 6e 73 69 76 65 20 69 6e 66 re extensive inf
3910: 6f 72 6d 61 74 69 6f 6e 73 20 61 62 6f 75 74 20 ormations about
3920: 74 68 69 73 20 61 70 70 72 6f 61 63 68 20 66 72 this approach fr
3930: 6f 6d 20 3c 61 20 68 72 65 66 3d 22 68 74 74 70 om <a href="http
3940: 3a 2f 2f 67 72 61 73 73 2e 6f 73 67 65 6f 2e 6f ://grass.osgeo.o
3950: 72 67 2f 77 69 6b 69 2f 43 72 65 61 74 65 5f 63 rg/wiki/Create_c
3960: 6f 6e 63 61 76 65 5f 68 75 6c 6c 22 3e 68 65 72 oncave_hull">her
3970: 65 3c 2f 61 3e 3c 62 72 3e 3c 62 72 3e 0d 0a 3c e</a><br><br>..<
3980: 75 3e 50 6c 65 61 73 65 20 6e 6f 74 65 20 77 65 u>Please note we
3990: 6c 6c 3c 2f 75 3e 3a 20 74 68 65 20 3c 62 3e 63 ll</u>: the <b>c
39a0: 6f 6e 76 65 78 20 68 75 6c 6c 3c 2f 62 3e 20 63 onvex hull</b> c
39b0: 6f 6e 63 65 70 74 20 63 6f 72 72 65 73 70 6f 6e oncept correspon
39c0: 64 73 20 74 6f 20 61 20 72 6f 62 75 73 74 20 61 ds to a robust a
39d0: 6e 64 20 66 6f 72 6d 61 6c 20 6d 61 74 68 65 6d nd formal mathem
39e0: 61 74 69 63 61 6c 20 64 65 66 69 6e 69 74 69 6f atical definitio
39f0: 6e 2e 20 4f 6e 20 74 68 65 20 6f 74 68 65 72 20 n. On the other
3a00: 73 69 64 65 20 74 68 65 20 3c 62 3e 63 6f 6e 63 side the <b>conc
3a10: 61 76 65 20 68 75 6c 6c 3c 2f 62 3e 20 69 73 20 ave hull</b> is
3a20: 61 20 6d 75 63 68 20 6d 6f 72 65 20 76 61 67 75 a much more vagu
3a30: 65 20 61 6e 64 20 75 6e 64 65 74 65 72 6d 69 6e e and undetermin
3a40: 65 64 20 6e 6f 74 69 6f 6e 2e 3c 62 72 3e 0d 0a ed notion.<br>..
3a50: 54 68 65 72 65 20 69 73 20 6f 6e 65 20 61 6e 64 There is one and
3a60: 20 6f 6e 6c 79 20 6f 6e 65 20 43 6f 6e 76 65 78 only one Convex
3a70: 48 75 6c 6c 20 66 6f 72 20 61 20 67 69 76 65 6e Hull for a given
3a80: 20 47 65 6f 6d 65 74 72 79 3b 20 62 75 74 20 6d Geometry; but m
3a90: 61 6e 79 20 43 6f 6e 63 61 76 65 48 75 6c 6c 73 any ConcaveHulls
3aa0: 20 61 72 65 20 70 6f 73 73 69 62 6c 65 2e 0d 0a are possible...
3ab0: 43 68 6f 6f 73 69 6e 67 20 74 68 65 20 6f 6e 65 Choosing the one
3ac0: 20 6f 72 20 74 68 65 20 6f 74 68 65 72 20 69 73 or the other is
3ad0: 20 6d 75 63 68 20 6d 6f 72 65 20 61 20 6d 61 74 much more a mat
3ae0: 74 65 72 20 6f 66 20 70 65 72 73 6f 6e 61 6c 20 ter of personal
3af0: 74 61 73 74 65 20 74 68 61 6e 20 61 20 6d 61 74 taste than a mat
3b00: 68 65 6d 61 74 69 63 61 6c 20 6f 70 65 72 61 74 hematical operat
3b10: 69 6f 6e 20 66 6f 72 6d 61 6c 6c 79 20 64 65 66 ion formally def
3b20: 69 6e 65 64 2e 3c 62 72 3e 0d 0a 43 6f 6d 70 75 ined.<br>..Compu
3b30: 74 69 6e 67 20 61 20 43 6f 6e 63 61 76 65 48 75 ting a ConcaveHu
3b40: 6c 6c 20 61 6c 77 61 79 73 20 69 73 20 61 6e 20 ll always is an
3b50: 69 6e 68 65 72 65 6e 74 6c 79 20 61 72 62 69 74 inherently arbit
3b60: 72 61 72 79 20 61 6e 64 20 68 65 75 72 69 73 74 rary and heurist
3b70: 69 63 20 70 72 6f 63 65 73 73 2e 0d 0a 3c 2f 74 ic process...</t
3b80: 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c 74 64 d></tr>..<tr><td
3b90: 3e 0d 0a 3c 68 34 3e 54 68 65 20 53 70 61 74 69 >..<h4>The Spati
3ba0: 61 4c 69 74 65 27 73 20 6f 77 6e 20 61 70 70 72 aLite's own appr
3bb0: 6f 61 63 68 20 74 6f 20 43 6f 6e 63 61 76 65 48 oach to ConcaveH
3bc0: 75 6c 6c 3c 2f 68 34 3e 0d 0a 3c 6f 6c 3e 0d 0a ull</h4>..<ol>..
3bd0: 3c 6c 69 3e 74 68 65 20 44 65 6c 61 75 6e 61 79 <li>the Delaunay
3be0: 20 54 72 69 61 6e 67 75 6c 61 74 69 6f 6e 20 63 Triangulation c
3bf0: 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f 20 orresponding to
3c00: 74 68 65 20 69 6e 70 75 74 20 47 65 6f 6d 65 74 the input Geomet
3c10: 72 79 20 77 69 6c 6c 20 62 65 20 63 6f 6d 70 75 ry will be compu
3c20: 74 65 64 20 66 69 72 73 74 2e 3c 2f 6c 69 3e 0d ted first.</li>.
3c30: 0a 3c 6c 69 3e 74 68 65 6e 20 74 68 65 20 73 74 .<li>then the st
3c40: 61 74 69 73 74 69 63 61 6c 20 64 69 73 74 72 69 atistical distri
3c50: 62 75 74 69 6f 6e 20 6f 66 20 61 6c 6c 20 74 72 bution of all tr
3c60: 69 61 6e 67 6c 65 20 65 64 67 65 27 73 20 6c 65 iangle edge's le
3c70: 6e 67 74 68 73 20 77 69 6c 6c 20 62 65 20 65 76 ngths will be ev
3c80: 61 6c 75 61 74 65 64 2c 20 73 6f 20 74 6f 20 64 aluated, so to d
3c90: 65 74 65 72 6d 69 6e 65 20 3c 62 3e 26 73 69 67 etermine <b>&sig
3ca0: 6d 61 3b 3c 2f 62 3e 20 28 61 6b 61 20 74 68 65 ma;</b> (aka the
3cb0: 20 3c 69 3e 73 74 61 6e 64 61 72 64 20 64 65 76 <i>standard dev
3cc0: 69 61 74 69 6f 6e 3c 2f 69 3e 29 3c 2f 6c 69 3e iation</i>)</li>
3cd0: 0d 0a 3c 6c 69 3e 61 20 73 65 63 6f 6e 64 20 70 ..<li>a second p
3ce0: 61 73 73 20 77 69 6c 6c 20 6e 6f 77 20 65 78 61 ass will now exa
3cf0: 6d 69 6e 65 20 79 65 74 20 61 67 61 69 6e 20 61 mine yet again a
3d00: 6c 6c 20 44 65 6c 61 75 6e 61 79 27 73 20 74 72 ll Delaunay's tr
3d10: 69 61 6e 67 6c 65 73 3b 20 61 6e 79 20 74 72 69 iangles; any tri
3d20: 61 6e 67 6c 65 20 70 72 65 73 65 6e 74 69 6e 67 angle presenting
3d30: 20 61 74 20 6c 65 61 73 74 20 6f 6e 65 20 65 64 at least one ed
3d40: 67 65 20 6c 6f 6e 67 65 72 20 74 68 61 6e 20 3c ge longer than <
3d50: 62 3e 26 73 69 67 6d 61 3b 20 2a 20 66 61 63 74 b>σ * fact
3d60: 6f 72 3c 2f 62 3e 20 77 69 6c 6c 20 62 65 20 64 or</b> will be d
3d70: 69 73 63 61 72 64 65 64 2e 3c 2f 6c 69 3e 0d 0a iscarded.</li>..
3d80: 3c 6c 69 3e 61 6e 64 20 66 69 6e 61 6c 6c 79 20 <li>and finally
3d90: 61 6c 6c 20 66 69 6c 74 65 72 65 64 20 74 72 69 all filtered tri
3da0: 61 6e 67 6c 65 73 20 77 69 6c 6c 20 62 65 20 64 angles will be d
3db0: 69 73 73 6f 6c 76 65 64 20 73 6f 20 74 6f 20 66 issolved so to f
3dc0: 6f 72 6d 20 74 68 65 20 43 6f 6e 63 61 76 65 48 orm the ConcaveH
3dd0: 75 6c 6c 20 74 6f 20 62 65 20 72 65 74 75 72 6e ull to be return
3de0: 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 6f 6c 3e 0d ed.</li>..</ol>.
3df0: 0a 3c 75 3e 50 6c 65 61 73 65 20 6e 6f 74 65 3c .<u>Please note<
3e00: 2f 75 3e 3a 20 62 79 20 73 65 74 74 69 6e 67 20 /u>: by setting
3e10: 61 6e 20 61 70 70 72 6f 70 72 69 61 74 65 20 76 an appropriate v
3e20: 61 6c 75 65 20 74 6f 20 3c 62 3e 66 61 63 74 6f alue to <b>facto
3e30: 72 3c 2f 62 3e 20 79 6f 75 20 63 61 6e 20 66 72 r</b> you can fr
3e40: 65 65 6c 79 20 69 6e 66 6c 75 65 6e 63 65 20 68 eely influence h
3e50: 6f 77 20 6d 75 63 68 20 3c 69 3e 61 67 67 72 65 ow much <i>aggre
3e60: 73 73 69 76 65 3c 2f 69 3e 20 74 68 65 20 66 69 ssive</i> the fi
3e70: 6c 74 65 72 69 6e 67 20 70 61 73 73 20 77 69 6c ltering pass wil
3e80: 6c 20 62 65 2e 3c 62 72 3e 0d 0a 41 64 6f 70 74 l be.<br>..Adopt
3e90: 69 6e 67 20 61 20 76 65 72 79 20 68 69 67 68 20 ing a very high
3ea0: 3c 62 3e 66 61 63 74 6f 72 3c 2f 62 3e 20 76 61 <b>factor</b> va
3eb0: 6c 75 65 20 70 72 61 63 74 69 63 61 6c 6c 79 20 lue practically
3ec0: 6d 65 61 6e 73 20 61 70 70 6c 79 69 6e 67 20 61 means applying a
3ed0: 20 76 65 72 79 20 62 6c 61 6e 64 20 66 69 6c 74 very bland filt
3ee0: 65 72 69 6e 67 20 28 76 65 72 79 20 66 65 77 20 ering (very few
3ef0: 74 72 69 61 6e 67 6c 65 73 20 77 69 6c 6c 20 62 triangles will b
3f00: 65 20 64 69 73 63 61 72 64 65 64 2c 20 61 6e 64 e discarded, and
3f10: 20 79 6f 75 27 6c 6c 20 63 6f 6e 73 65 71 75 65 you'll conseque
3f20: 6e 74 6c 79 20 67 65 74 20 61 20 72 61 74 68 65 ntly get a rathe
3f30: 72 20 3c 69 3e 63 6f 6e 76 65 78 3c 2f 69 3e 20 r <i>convex</i>
3f40: 73 68 61 70 65 29 2e 0d 0a 4f 6e 20 74 68 65 20 shape)...On the
3f50: 6f 74 68 65 72 20 73 69 64 65 20 61 64 6f 70 74 other side adopt
3f60: 69 6e 67 20 61 20 76 65 72 79 20 6c 6f 77 20 3c ing a very low <
3f70: 62 3e 66 61 63 74 6f 72 3c 2f 62 3e 20 76 61 6c b>factor</b> val
3f80: 75 65 73 20 77 69 6c 6c 20 61 70 70 6c 79 20 61 ues will apply a
3f90: 20 76 65 72 79 20 73 74 72 6f 6e 67 20 66 69 6c very strong fil
3fa0: 74 65 72 69 6e 67 20 28 6d 61 6e 79 20 74 72 69 tering (many tri
3fb0: 61 6e 67 6c 65 73 20 77 69 6c 6c 20 62 65 20 6e angles will be n
3fc0: 6f 77 20 64 69 73 63 61 72 64 65 64 2c 20 61 6e ow discarded, an
3fd0: 64 20 79 6f 75 27 6c 6c 20 67 65 74 20 61 20 76 d you'll get a v
3fe0: 65 72 79 20 3c 69 3e 63 6f 6e 63 61 76 65 3c 2f ery <i>concave</
3ff0: 69 3e 20 73 68 61 70 65 29 2e 3c 62 72 3e 3c 62 i> shape).<br><b
4000: 72 3e 0d 0a 3c 75 3e 55 73 65 66 75 6c 20 63 6f r>..<u>Useful co
4010: 6e 73 74 61 6e 74 73 3c 2f 75 3e 3a 20 61 73 73 nstants</u>: ass
4020: 75 6d 69 6e 67 20 61 20 70 65 72 66 65 63 74 6c uming a perfectl
4030: 79 20 6e 6f 72 6d 61 6c 20 64 69 73 74 72 69 62 y normal distrib
4040: 75 74 69 6f 6e 20 6f 66 20 65 64 67 65 20 6c 65 ution of edge le
4050: 6e 67 74 68 73 20 28 61 20 62 79 20 66 61 72 20 ngths (a by far
4060: 75 6e 72 65 61 6c 69 73 74 69 63 20 61 73 73 75 unrealistic assu
4070: 6d 70 74 69 6f 6e 20 66 6f 72 20 72 65 61 6c 20 mption for real
4080: 77 6f 72 6c 64 20 64 61 74 61 73 65 74 73 29 2c world datasets),
4090: 20 3c 62 3e 33 26 73 69 67 6d 61 3b 3c 2f 62 3e <b>3σ</b>
40a0: 20 77 69 6c 6c 20 69 6d 70 6c 79 20 73 75 70 70 will imply supp
40b0: 72 65 73 73 69 6e 67 20 61 62 6f 75 74 20 3c 62 ressing about <b
40c0: 3e 30 2e 31 25 3c 2f 62 3e 20 74 72 69 61 6e 67 >0.1%</b> triang
40d0: 6c 65 73 20 28 6f 6e 6c 79 20 74 68 65 20 66 65 les (only the fe
40e0: 77 20 6f 6e 65 73 20 70 72 65 73 65 6e 74 69 6e w ones presentin
40f0: 67 20 61 62 6e 6f 72 6d 61 6c 6c 79 20 6c 65 6e g abnormally len
4100: 67 74 68 79 20 65 64 67 65 73 29 2c 20 3c 62 3e gthy edges), <b>
4110: 32 26 73 69 67 6d 61 3b 3c 2f 62 3e 20 63 6f 72 2σ</b> cor
4120: 72 65 73 70 6f 6e 64 73 20 74 6f 20 61 62 6f 75 responds to abou
4130: 74 20 3c 62 3e 32 2e 31 25 3c 2f 62 3e 2c 20 61 t <b>2.1%</b>, a
4140: 6e 64 20 3c 62 3e 31 26 73 69 67 6d 61 3b 3c 2f nd <b>1σ</
4150: 62 3e 20 72 6f 75 67 68 6c 79 20 63 6f 72 72 65 b> roughly corre
4160: 73 70 6f 6e 64 73 20 74 6f 20 20 3c 62 3e 31 35 sponds to <b>15
4170: 2e 38 25 3c 2f 62 3e 2e 3c 62 72 3e 0d 0a 55 73 .8%</b>.<br>..Us
4180: 75 61 6c 6c 79 20 76 61 6c 75 65 73 20 72 61 6e ually values ran
4190: 67 69 6e 67 20 62 65 74 77 65 65 6e 20 3c 62 3e ging between <b>
41a0: 33 26 73 69 67 6d 61 3b 3c 2f 62 3e 20 61 6e 64 3σ</b> and
41b0: 20 3c 62 3e 32 26 73 69 67 6d 61 3b 3c 2f 62 3e <b>2σ</b>
41c0: 20 61 72 65 20 74 68 65 20 6d 6f 73 74 20 61 70 are the most ap
41d0: 70 72 6f 70 72 69 61 74 65 20 74 6f 20 62 65 20 propriate to be
41e0: 75 73 65 64 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 54 used.<br><br>..T
41f0: 68 65 20 66 69 67 75 72 65 20 73 68 6f 77 73 20 he figure shows
4200: 77 68 61 74 20 79 6f 75 20 63 61 6e 20 61 63 74 what you can act
4210: 75 61 6c 6c 79 20 67 65 74 20 62 79 20 61 70 70 ually get by app
4220: 6c 79 69 6e 67 20 61 20 3c 62 3e 33 26 73 69 67 lying a <b>3&sig
4230: 6d 61 3b 3c 2f 62 3e 20 66 69 6c 74 65 72 69 6e ma;</b> filterin
4240: 67 20 74 6f 20 49 74 61 6c 69 61 6e 20 50 6f 70 g to Italian Pop
4250: 75 6c 61 74 65 64 20 50 6c 61 63 65 73 3b 20 66 ulated Places; f
4260: 6f 72 20 63 6c 61 72 69 74 79 20 61 6c 6c 20 49 or clarity all I
4270: 74 61 6c 69 61 6e 20 52 65 67 69 6f 6e 73 20 61 talian Regions a
4280: 72 65 20 72 65 70 72 65 73 65 6e 74 65 64 20 69 re represented i
4290: 6e 20 79 65 6c 6c 6f 77 2c 20 61 6e 64 20 74 68 n yellow, and th
42a0: 65 20 43 6f 6e 76 65 78 48 75 6c 6c 20 69 73 20 e ConvexHull is
42b0: 72 65 70 72 65 73 65 6e 74 65 64 20 69 6e 20 62 represented in b
42c0: 6c 75 65 2e 20 54 68 65 20 43 6f 6e 63 61 76 65 lue. The Concave
42d0: 48 75 6c 6c 20 69 74 73 65 6c 66 20 69 73 20 72 Hull itself is r
42e0: 65 70 72 65 73 65 6e 74 65 64 20 69 6e 20 72 65 epresented in re
42f0: 64 2e 0d 0a 3c 2f 74 64 3e 3c 74 64 3e 0d 0a 3c d...</td><td>..<
4300: 69 6d 67 20 62 6f 72 64 65 72 3d 22 31 22 20 73 img border="1" s
4310: 72 63 3d 22 68 74 74 70 3a 2f 2f 77 77 77 2e 67 rc="http://www.g
4320: 61 69 61 2d 67 69 73 2e 69 74 2f 67 61 69 61 2d aia-gis.it/gaia-
4330: 73 69 6e 73 2f 77 72 69 74 65 2d 76 69 65 77 2d sins/write-view-
4340: 70 69 63 73 2f 63 6f 6e 63 61 76 65 33 2e 70 6e pics/concave3.pn
4350: 67 22 20 61 6c 74 3d 22 63 6f 6e 63 61 76 65 68 g" alt="concaveh
4360: 75 6c 6c 2d 31 22 3e 0d 0a 3c 2f 74 64 3e 3c 2f ull-1">..</td></
4370: 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e 0d 0a 3c tr>..</table>..<
4380: 62 72 3e 0d 0a 3c 62 3e 3c 75 3e 50 6c 65 61 73 br>..<b><u>Pleas
4390: 65 20 6e 6f 74 65 20 77 65 6c 6c 3c 2f 75 3e 3c e note well</u><
43a0: 2f 62 3e 3a 20 50 6f 73 74 47 49 53 20 73 75 70 /b>: PostGIS sup
43b0: 70 6f 72 74 73 20 69 74 73 20 6f 77 6e 20 69 6d ports its own im
43c0: 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 plementation of
43d0: 53 54 5f 43 6f 6e 63 61 76 65 48 75 6c 6c 28 29 ST_ConcaveHull()
43e0: 2c 20 62 65 69 6e 67 20 62 61 73 65 64 20 6f 6e , being based on
43f0: 20 61 20 63 6f 6d 70 6c 65 74 65 6c 79 20 64 69 a completely di
4400: 66 66 65 72 65 6e 74 20 61 70 70 72 6f 61 63 68 fferent approach
4410: 2e 20 59 6f 75 20 63 61 6e 20 67 65 74 20 6d 6f . You can get mo
4420: 72 65 20 64 65 74 61 69 6c 73 20 66 72 6f 6d 20 re details from
4430: 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f <a href="http://
4440: 77 77 77 2e 62 6f 73 74 6f 6e 67 69 73 2e 63 6f www.bostongis.co
4450: 6d 2f 70 6f 73 74 67 69 73 5f 63 6f 6e 63 61 76 m/postgis_concav
4460: 65 68 75 6c 6c 2e 73 6e 69 70 70 65 74 22 3e 68 ehull.snippet">h
4470: 65 72 65 3c 2f 61 3e 3c 62 72 3e 0d 0a 50 6c 65 ere</a><br>..Ple
4480: 61 73 65 2c 20 64 6f 6e 27 74 20 62 65 20 63 6f ase, don't be co
4490: 6e 66 75 73 65 64 3a 20 74 68 65 20 53 70 61 74 nfused: the Spat
44a0: 69 61 4c 69 74 65 20 61 6e 64 20 50 6f 73 74 47 iaLite and PostG
44b0: 49 53 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f IS implementatio
44c0: 6e 73 20 61 72 65 20 63 6f 6d 70 6c 65 74 65 6c ns are completel
44d0: 79 20 75 6e 72 65 6c 61 74 65 64 2e 20 41 6e 79 y unrelated. Any
44e0: 77 61 79 2c 20 69 74 20 63 6f 75 6c 64 20 62 65 way, it could be
44f0: 20 69 6e 74 65 72 65 73 74 69 6e 67 20 6e 6f 74 interesting not
4500: 69 6e 67 20 74 68 61 74 20 74 68 65 20 53 70 61 ing that the Spa
4510: 74 69 61 4c 69 74 65 27 73 20 6f 77 6e 20 69 6d tiaLite's own im
4520: 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 73 65 65 plementation see
4530: 6d 73 20 74 6f 20 62 65 20 6d 75 63 68 20 6d 6f ms to be much mo
4540: 72 65 20 65 66 66 69 63 69 65 6e 74 20 61 6e 64 re efficient and
4550: 20 66 61 73 74 2c 20 61 6e 64 20 63 61 6e 20 62 fast, and can b
4560: 65 20 72 65 61 6c 69 73 74 69 63 61 6c 6c 79 20 e realistically
4570: 61 70 70 6c 69 65 64 20 65 76 65 6e 20 74 6f 20 applied even to
4580: 76 65 72 79 20 68 75 67 65 20 70 6f 69 6e 74 2d very huge point-
4590: 73 65 74 73 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 3c sets.<br><br>..<
45a0: 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 table bgcolor="#
45b0: 66 30 66 30 66 30 22 20 63 65 6c 6c 73 70 61 63 f0f0f0" cellspac
45c0: 69 6e 67 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 ing="4" cellpadd
45d0: 69 6e 67 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 ing="8">..<tr><t
45e0: 64 3e 0d 0a 3c 69 3e 70 72 6f 74 6f 74 79 70 65 d>..<i>prototype
45f0: 3c 2f 69 3e 3a 3c 68 72 3e 0d 0a 53 54 5f 43 6f </i>:<hr>..ST_Co
4600: 6e 63 61 76 65 48 75 6c 6c 28 20 69 6e 70 75 74 ncaveHull( input
4610: 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e <i>Geometry</i>
4620: 20 29 20 3a 20 63 6f 6e 63 61 76 65 20 3c 69 3e ) : concave <i>
4630: 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 3c 62 72 3e Geometry</i><br>
4640: 0d 0a 53 54 5f 43 6f 6e 63 61 76 65 48 75 6c 6c ..ST_ConcaveHull
4650: 28 20 69 6e 70 75 74 20 3c 69 3e 47 65 6f 6d 65 ( input <i>Geome
4660: 74 72 79 3c 2f 69 3e 2c 20 66 61 63 74 6f 72 20 try</i>, factor
4670: 3c 69 3e 64 6f 75 62 6c 65 20 70 72 65 63 69 73 <i>double precis
4680: 69 6f 6e 3c 2f 69 3e 20 29 20 3a 20 63 6f 6e 63 ion</i> ) : conc
4690: 61 76 65 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c ave <i>Geometry<
46a0: 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 43 6f 6e 63 /i><br>..ST_Conc
46b0: 61 76 65 48 75 6c 6c 28 20 69 6e 70 75 74 20 3c aveHull( input <
46c0: 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 2c 20 i>Geometry</i>,
46d0: 66 61 63 74 6f 72 20 3c 69 3e 64 6f 75 62 6c 65 factor <i>double
46e0: 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e 2c 20 precision</i>,
46f0: 61 6c 6c 6f 77 5f 68 6f 6c 65 73 20 3c 69 3e 62 allow_holes <i>b
4700: 6f 6f 6c 65 61 6e 3c 2f 69 3e 20 29 20 3a 20 63 oolean</i> ) : c
4710: 6f 6e 63 61 76 65 20 3c 69 3e 47 65 6f 6d 65 74 oncave <i>Geomet
4720: 72 79 3c 2f 69 3e 3c 62 72 3e 0d 0a 53 54 5f 43 ry</i><br>..ST_C
4730: 6f 6e 63 61 76 65 48 75 6c 6c 28 20 69 6e 70 75 oncaveHull( inpu
4740: 74 20 3c 69 3e 47 65 6f 6d 65 74 72 79 3c 2f 69 t <i>Geometry</i
4750: 3e 2c 20 66 61 63 74 6f 72 20 3c 69 3e 64 6f 75 >, factor <i>dou
4760: 62 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 ble precision</i
4770: 3e 2c 20 61 6c 6c 6f 77 5f 68 6f 6c 65 73 20 3c >, allow_holes <
4780: 69 3e 62 6f 6f 6c 65 61 6e 3c 2f 69 3e 2c 20 74 i>boolean</i>, t
4790: 6f 6c 65 72 61 6e 63 65 20 3c 69 3e 64 6f 75 62 olerance <i>doub
47a0: 6c 65 20 70 72 65 63 69 73 69 6f 6e 3c 2f 69 3e le precision</i>
47b0: 20 29 20 3a 20 63 6f 6e 63 61 76 65 20 3c 69 3e ) : concave <i>
47c0: 47 65 6f 6d 65 74 72 79 3c 2f 69 3e 0d 0a 3c 2f Geometry</i>..</
47d0: 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e td></tr></table>
47e0: 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 20 ..<ul>..<li>the
47f0: 3c 62 3e 69 6e 70 75 74 3c 2f 62 3e 20 47 65 6f <b>input</b> Geo
4800: 6d 65 74 72 79 20 63 61 6e 20 62 65 20 6f 66 20 metry can be of
4810: 61 62 73 6f 6c 75 74 65 6c 79 20 61 72 62 69 74 absolutely arbit
4820: 72 61 72 79 20 74 79 70 65 3b 20 61 6c 6c 20 4c rary type; all L
4830: 69 6e 65 73 74 72 69 6e 67 73 20 61 6e 64 20 2f inestrings and /
4840: 20 6f 72 20 50 6f 6c 79 67 6f 77 6e 73 20 77 69 or Polygowns wi
4850: 6c 6c 20 65 76 65 6e 74 75 61 6c 6c 79 20 62 65 ll eventually be
4860: 20 64 69 73 73 6f 6c 76 65 64 20 69 6e 74 6f 20 dissolved into
4870: 50 6f 69 6e 74 73 20 63 6f 72 72 65 73 70 6f 6e Points correspon
4880: 64 69 6e 67 20 74 6f 20 76 65 72 74 69 63 65 73 ding to vertices
4890: 2e 3c 62 72 3e 0d 0a 53 6f 20 61 66 74 65 72 20 .<br>..So after
48a0: 61 6c 6c 20 53 54 5f 43 6f 6e 63 61 76 65 48 75 all ST_ConcaveHu
48b0: 6c 6c 28 29 20 28 65 78 61 63 74 6c 79 20 61 73 ll() (exactly as
48c0: 20 53 54 5f 44 65 6c 61 75 6e 61 79 54 72 69 61 ST_DelaunayTria
48d0: 6e 67 75 6c 61 74 69 6f 6e 29 20 77 69 6c 6c 20 ngulation) will
48e0: 61 6c 77 61 79 73 20 70 72 6f 63 65 73 73 20 61 always process a
48f0: 20 4d 75 6c 74 69 50 6f 69 6e 74 2e 3c 2f 6c 69 MultiPoint.</li
4900: 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 74 69 6f >..<li>the optio
4910: 6e 61 6c 20 3c 62 3e 66 61 63 74 6f 72 3c 2f 62 nal <b>factor</b
4920: 3e 20 69 73 20 69 6e 74 65 6e 64 65 64 20 74 6f > is intended to
4930: 20 62 65 20 61 20 3c 62 3e 26 73 69 67 6d 61 3b be a <b>σ
4940: 3c 2f 62 3e 20 6d 75 6c 74 69 70 6c 69 65 72 2c </b> multiplier,
4950: 20 74 68 75 73 20 64 65 74 65 72 6d 69 6e 69 6e thus determinin
4960: 67 20 74 68 65 20 66 69 6c 74 65 72 69 6e 67 20 g the filtering
4970: 74 68 72 65 73 68 6f 6c 64 2e 3c 62 72 3e 0d 0a threshold.<br>..
4980: 42 79 20 64 65 66 61 75 6c 74 20 61 20 3c 62 3e By default a <b>
4990: 33 26 73 69 67 6d 61 3b 20 66 61 63 74 6f 72 3c 3σ factor<
49a0: 2f 62 3e 20 69 73 20 61 73 73 75 6d 65 64 2e 3c /b> is assumed.<
49b0: 2f 6c 69 3e 0d 0a 3c 6c 69 3e 74 68 65 20 6f 70 /li>..<li>the op
49c0: 74 69 6f 6e 61 6c 20 3c 62 3e 61 6c 6c 6f 77 5f tional <b>allow_
49d0: 68 6f 6c 65 73 3c 2f 62 3e 20 61 72 67 75 6d 65 holes</b> argume
49e0: 6e 74 20 77 69 6c 6c 20 62 65 20 69 6e 74 65 72 nt will be inter
49f0: 70 72 65 74 65 64 20 61 73 20 66 6f 6c 6c 6f 77 preted as follow
4a00: 73 3a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 69 66 20 3c s:<ul>..<li>if <
4a10: 62 3e 46 41 4c 53 45 3c 2f 62 3e 20 28 3c 69 3e b>FALSE</b> (<i>
4a20: 64 65 66 61 75 6c 74 20 76 61 6c 75 65 3c 2f 69 default value</i
4a30: 3e 29 20 61 6e 79 20 65 76 65 6e 74 75 61 6c 20 >) any eventual
4a40: 69 6e 74 65 72 69 6f 72 20 68 6f 6c 65 20 77 69 interior hole wi
4a50: 6c 6c 20 62 65 20 73 75 70 70 72 65 73 73 65 64 ll be suppressed
4a60: 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 69 66 20 3c .</li>..<li>if <
4a70: 62 3e 54 52 55 45 3c 2f 62 3e 20 61 6e 79 20 65 b>TRUE</b> any e
4a80: 76 65 6e 74 75 61 6c 20 69 6e 74 65 72 69 6f 72 ventual interior
4a90: 20 68 6f 6c 65 73 20 77 69 6c 6c 20 62 65 20 70 holes will be p
4aa0: 72 65 73 65 72 76 65 64 2e 3c 2f 6c 69 3e 0d 0a reserved.</li>..
4ab0: 3c 2f 75 6c 3e 3c 2f 6c 69 3e 20 0d 0a 3c 6c 69 </ul></li> ..<li
4ac0: 3e 74 68 65 20 6f 70 74 69 6f 6e 61 6c 20 3c 62 >the optional <b
4ad0: 3e 74 6f 6c 65 72 61 6e 63 65 3c 2f 62 3e 20 61 >tolerance</b> a
4ae0: 72 67 75 6d 65 6e 74 20 69 73 20 69 6e 74 65 6e rgument is inten
4af0: 64 65 64 20 74 6f 20 6e 6f 72 6d 61 6c 69 7a 65 ded to normalize
4b00: 20 74 68 65 20 69 6e 70 75 74 20 70 6f 69 6e 74 the input point
4b10: 2d 73 65 74 2c 20 73 75 70 70 72 65 73 73 69 6e -set, suppressin
4b20: 67 20 72 65 70 65 61 74 65 64 20 70 6f 69 6e 74 g repeated point
4b30: 73 20 28 73 69 6d 70 6c 79 20 75 73 65 64 20 77 s (simply used w
4b40: 68 65 6e 20 69 6e 74 65 72 6e 61 6c 6c 79 20 63 hen internally c
4b50: 6f 6d 70 75 74 69 6e 67 20 74 68 65 20 44 65 6c omputing the Del
4b60: 61 75 6e 61 79 20 54 72 69 61 6e 67 75 6c 61 74 aunay Triangulat
4b70: 69 6f 6e 29 2e 0d 0a 42 79 20 64 65 66 61 75 6c ion)...By defaul
4b80: 74 20 61 20 3c 62 3e 30 2e 30 3c 2f 62 3e 20 74 t a <b>0.0</b> t
4b90: 6f 6c 65 72 61 6e 63 65 20 77 69 6c 6c 20 62 65 olerance will be
4ba0: 20 61 73 73 75 6d 65 64 2e 3c 2f 6c 69 3e 0d 0a assumed.</li>..
4bb0: 3c 2f 75 6c 3e 3c 2f 74 64 3e 3c 2f 74 72 3e 3c </ul></td></tr><
4bc0: 2f 74 61 62 6c 65 3e 0d 0a 3c 74 61 62 6c 65 20 /table>..<table
4bd0: 63 65 6c 6c 73 70 61 63 69 6e 67 3d 22 34 22 20 cellspacing="4"
4be0: 63 65 6c 6c 70 61 64 64 69 6e 67 3d 22 34 22 3e cellpadding="4">
4bf0: 0d 0a 3c 74 72 3e 3c 74 64 3e 0d 0a 3c 74 61 62 ..<tr><td>..<tab
4c00: 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 66 30 66 le bgcolor="#f0f
4c10: 30 66 30 22 20 63 65 6c 6c 73 70 61 63 69 6e 67 0f0" cellspacing
4c20: 3d 22 34 22 20 63 65 6c 6c 70 61 64 64 69 6e 67 ="4" cellpadding
4c30: 3d 22 38 22 3e 0d 0a 3c 74 72 3e 3c 74 64 3e 0d ="8">..<tr><td>.
4c40: 0a 3c 62 3e 53 45 4c 45 43 54 20 53 54 5f 43 6f .<b>SELECT ST_Co
4c50: 6e 63 61 76 65 48 75 6c 6c 28 53 54 5f 43 6f 6c ncaveHull(ST_Col
4c60: 6c 65 63 74 28 67 65 6f 6d 65 74 72 79 29 2c 20 lect(geometry),
4c70: 32 2e 35 29 3c 62 72 3e 0d 0a 46 52 4f 4d 20 69 2.5)<br>..FROM i
4c80: 74 61 6c 79 5f 70 6f 70 75 6c 61 74 65 64 5f 70 taly_populated_p
4c90: 6c 61 63 65 73 3b 3c 2f 62 3e 0d 0a 3c 2f 74 64 laces;</b>..</td
4ca0: 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 3e ></tr>..</table>
4cb0: 3c 62 72 3e 0d 0a 54 68 69 73 20 53 51 4c 20 71 <br>..This SQL q
4cc0: 75 65 72 79 20 77 69 6c 6c 20 72 65 74 75 72 6e uery will return
4cd0: 20 61 20 43 6f 6e 63 61 76 65 48 75 6c 6c 20 62 a ConcaveHull b
4ce0: 61 73 65 64 20 6f 6e 20 49 74 61 6c 79 27 73 20 ased on Italy's
4cf0: 70 6f 70 75 6c 61 74 65 64 20 70 6c 61 63 65 73 populated places
4d00: 20 28 61 62 6f 75 74 20 38 2c 30 30 30 2b 20 50 (about 8,000+ P
4d10: 6f 69 6e 74 73 29 20 62 79 20 61 70 70 6c 79 69 oints) by applyi
4d20: 6e 67 20 61 20 3c 62 3e 32 2e 35 26 73 69 67 6d ng a <b>2.5&sigm
4d30: 61 3b 3c 2f 62 3e 20 66 69 6c 74 65 72 69 6e 67 a;</b> filtering
4d40: 20 66 61 63 74 6f 72 2e 3c 62 72 3e 3c 62 72 3e factor.<br><br>
4d50: 0d 0a 54 68 65 20 66 69 67 75 72 65 20 61 6c 73 ..The figure als
4d60: 6f 20 73 68 6f 77 73 20 74 68 65 20 43 6f 6e 63 o shows the Conc
4d70: 61 76 65 48 75 6c 6c 20 72 65 74 75 72 6e 65 64 aveHull returned
4d80: 20 62 79 20 74 68 65 20 70 72 65 76 69 6f 75 73 by the previous
4d90: 20 65 78 61 6d 70 6c 65 20 62 79 20 61 70 70 6c example by appl
4da0: 79 69 6e 67 20 61 20 3c 62 3e 33 26 73 69 67 6d ying a <b>3&sigm
4db0: 61 3b 3c 2f 62 3e 20 66 61 63 74 6f 72 20 28 72 a;</b> factor (r
4dc0: 65 64 20 62 6f 75 6e 64 61 72 79 29 2c 20 73 6f ed boundary), so
4dd0: 20 74 6f 20 65 76 69 64 65 6e 74 69 61 74 65 20 to evidentiate
4de0: 74 68 65 20 72 65 6c 61 74 69 76 65 20 64 69 66 the relative dif
4df0: 66 65 72 65 6e 63 65 73 2e 20 0d 0a 3c 2f 74 64 ferences. ..</td
4e00: 3e 0d 0a 3c 74 64 3e 3c 69 6d 67 20 62 6f 72 64 >..<td><img bord
4e10: 65 72 3d 22 31 22 20 73 72 63 3d 22 68 74 74 70 er="1" src="http
4e20: 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e ://www.gaia-gis.
4e30: 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 77 72 69 it/gaia-sins/wri
4e40: 74 65 2d 76 69 65 77 2d 70 69 63 73 2f 63 6f 6e te-view-pics/con
4e50: 63 61 76 65 32 35 2e 70 6e 67 22 20 61 6c 74 3d cave25.png" alt=
4e60: 22 63 6f 6e 63 61 76 65 68 75 6c 6c 2d 32 22 3e "concavehull-2">
4e70: 3c 2f 74 64 3e 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 </td></tr>..</ta
4e80: 62 6c 65 3e 0d 0a 3c 62 72 3e 3c 68 72 3e 0d 0a ble>..<br><hr>..
4e90: 42 61 63 6b 20 74 6f 20 3c 61 20 68 72 65 66 3d Back to <a href=
4ea0: 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 67 61 69 "https://www.gai
4eb0: 61 2d 67 69 73 2e 69 74 2f 66 6f 73 73 69 6c 2f a-gis.it/fossil/
4ec0: 6c 69 62 73 70 61 74 69 61 6c 69 74 65 2f 77 69 libspatialite/wi
4ed0: 6b 69 3f 6e 61 6d 65 3d 73 77 69 74 63 68 69 6e ki?name=switchin
4ee0: 67 2d 74 6f 2d 34 2e 30 23 74 65 73 73 65 6c 61 g-to-4.0#tessela
4ef0: 74 69 6f 6e 22 3e 6d 61 69 6e 20 70 61 67 65 3c tion">main page<
4f00: 2f 61 3e 0d 0a 0d 0a 0a 5a 20 33 63 62 64 34 34 /a>.....Z 3cbd44
4f10: 35 64 66 64 65 64 30 64 66 37 39 66 30 35 32 37 5dfded0df79f0527
4f20: 63 32 66 34 38 36 63 35 64 61 0a c2f486c5da.