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