0000: 44 20 32 30 31 39 2d 30 32 2d 32 34 54 31 37 3a D 2019-02-24T17:
0010: 32 36 3a 31 35 2e 33 35 33 0a 4c 20 41 62 6f 75 26:15.353.L Abou
0020: 74 5c 73 53 54 5f 53 75 62 64 69 76 69 64 65 28 t\sST_Subdivide(
0030: 29 0a 50 20 32 32 66 34 66 35 35 30 38 34 31 63 ).P 22f4f550841c
0040: 36 31 33 34 37 66 63 39 65 64 64 62 38 36 64 39 61347fc9eddb86d9
0050: 63 64 62 63 31 66 65 34 32 30 31 63 0a 55 20 73 cdbc1fe4201c.U s
0060: 61 6e 64 72 6f 0a 57 20 31 32 35 34 36 0a 3c 74 andro.W 12546.<t
0070: 61 62 6c 65 20 63 65 6c 6c 73 70 61 63 69 6e 67 able cellspacing
0080: 3d 22 31 32 22 20 77 69 64 74 68 3d 22 31 30 30 ="12" width="100
0090: 25 22 3e 0d 0a 3c 74 72 3e 3c 74 64 20 63 6f 6c %">..<tr><td col
00a0: 73 70 61 6e 3d 22 32 22 3e 0d 0a 3c 74 61 62 6c span="2">..<tabl
00b0: 65 20 77 69 64 74 68 3d 22 31 30 30 25 22 20 62 e width="100%" b
00c0: 67 63 6f 6c 6f 72 3d 22 23 66 30 66 30 66 38 22 gcolor="#f0f0f8"
00d0: 3e 0d 0a 3c 74 72 3e 3c 74 64 20 61 6c 69 67 6e >..<tr><td align
00e0: 3d 22 63 65 6e 74 65 72 22 3e 0d 0a 3c 68 31 3e ="center">..<h1>
00f0: 53 54 5f 53 75 62 64 69 76 69 64 65 28 29 3a 20 ST_Subdivide():
0100: 61 20 71 75 69 63 6b 20 69 6e 74 72 6f 3c 2f 68 a quick intro</h
0110: 31 3e 0d 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 1>..</td></tr></
0120: 74 61 62 6c 65 3e 0d 0a 3c 74 61 62 6c 65 20 77 table>..<table w
0130: 69 64 74 68 3d 22 31 30 30 25 22 3e 3c 74 72 3e idth="100%"><tr>
0140: 0d 0a 3c 74 64 20 77 69 64 74 68 3d 22 33 33 25 ..<td width="33%
0150: 22 20 61 6c 69 67 6e 3d 22 6c 65 66 74 22 3e 3c " align="left"><
0160: 2f 74 64 3e 0d 0a 3c 74 64 20 61 6c 69 67 6e 3d /td>..<td align=
0170: 22 63 65 6e 74 65 72 22 3e 3c 61 20 68 72 65 66 "center"><a href
0180: 3d 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 67 61 ="https://www.ga
0190: 69 61 2d 67 69 73 2e 69 74 2f 66 6f 73 73 69 6c ia-gis.it/fossil
01a0: 2f 6c 69 62 73 70 61 74 69 61 6c 69 74 65 2f 77 /libspatialite/w
01b0: 69 6b 69 3f 6e 61 6d 65 3d 34 2e 33 2e 30 2b 64 iki?name=4.3.0+d
01c0: 6f 63 22 3e 62 61 63 6b 20 74 6f 20 69 6e 64 65 oc">back to inde
01d0: 78 3c 2f 61 3e 3c 2f 74 64 3e 0d 0a 3c 74 64 20 x</a></td>..<td
01e0: 77 69 64 74 68 3d 22 33 33 25 22 20 61 6c 69 67 width="33%" alig
01f0: 6e 3d 22 72 69 67 68 74 22 3e 3c 2f 74 64 3e 0d n="right"></td>.
0200: 0a 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 3c 62 .</tr></table><b
0210: 72 3e 0d 0a 3c 68 32 3e 41 62 6f 75 74 20 53 54 r>..<h2>About ST
0220: 5f 53 75 62 64 69 76 69 64 65 28 29 3c 2f 68 32 _Subdivide()</h2
0230: 3e 0d 0a 53 74 61 72 74 69 6e 67 20 77 69 74 68 >..Starting with
0240: 20 76 65 72 73 69 6f 6e 20 3c 62 3e 35 2e 30 2e version <b>5.0.
0250: 30 3c 2f 62 3e 20 53 70 61 74 69 61 4c 69 74 65 0</b> SpatiaLite
0260: 20 73 75 70 70 6f 72 74 73 20 3c 62 3e 53 54 5f supports <b>ST_
0270: 53 75 62 64 69 76 69 64 65 28 29 3c 2f 62 3e 2c Subdivide()</b>,
0280: 20 61 6e 20 61 64 76 61 6e 63 65 64 20 53 51 4c an advanced SQL
0290: 20 66 75 6e 63 74 69 6f 6e 20 61 6c 72 65 61 64 function alread
02a0: 79 20 61 76 61 69 6c 61 62 6c 65 20 6f 6e 20 3c y available on <
02b0: 61 20 68 72 65 66 3d 22 68 74 74 70 73 3a 2f 2f a href="https://
02c0: 70 6f 73 74 67 69 73 2e 6e 65 74 2f 64 6f 63 73 postgis.net/docs
02d0: 2f 53 54 5f 53 75 62 64 69 76 69 64 65 2e 68 74 /ST_Subdivide.ht
02e0: 6d 6c 22 3e 50 6f 73 74 47 49 53 3c 2f 61 3e 2e ml">PostGIS</a>.
02f0: 3c 62 72 3e 0d 0a 54 68 65 20 69 6d 70 6c 65 6d <br>..The implem
0300: 65 6e 74 61 74 69 6f 6e 20 69 73 20 76 65 72 79 entation is very
0310: 20 73 69 6d 69 6c 61 72 20 69 6e 20 62 6f 74 68 similar in both
0320: 20 53 70 61 74 69 61 6c 20 44 42 4d 53 65 73 20 Spatial DBMSes
0330: 62 65 63 61 75 73 65 20 69 6e 20 50 6f 73 74 47 because in PostG
0340: 49 53 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20 IS the function
0350: 69 73 20 63 72 65 61 74 65 64 20 77 69 74 68 20 is created with
0360: 74 68 65 20 69 6e 74 65 72 6e 61 6c 20 3c 62 3e the internal <b>
0370: 6c 77 67 65 6f 6d 3c 2f 62 3e 20 6c 69 62 72 61 lwgeom</b> libra
0380: 72 79 2c 20 61 6e 64 20 69 6e 20 53 70 61 74 69 ry, and in Spati
0390: 61 4c 69 74 65 20 77 69 74 68 20 3c 62 3e 6c 69 aLite with <b>li
03a0: 62 72 74 74 6f 70 6f 3c 2f 62 3e 2c 20 77 68 69 brttopo</b>, whi
03b0: 63 68 20 69 73 20 61 20 75 6e 69 76 65 72 73 61 ch is a universa
03c0: 6c 20 70 6f 72 74 69 6e 67 20 6f 66 20 6c 77 67 l porting of lwg
03d0: 65 6f 6d 20 77 69 74 68 6f 75 74 20 50 6f 73 74 eom without Post
03e0: 47 49 53 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 41 20 GIS.<br><br>..A
03f0: 73 68 6f 72 74 20 72 61 74 69 6f 6e 61 6c 65 3a short rationale:
0400: 20 70 72 6f 63 65 73 73 69 6e 67 20 68 75 67 65 processing huge
0410: 20 67 65 6f 6d 65 74 72 69 65 73 20 68 61 76 69 geometries havi
0420: 6e 67 20 61 6e 20 69 6d 70 72 65 73 73 69 76 65 ng an impressive
0430: 20 6e 75 6d 62 65 72 20 6f 66 20 56 65 72 74 69 number of Verti
0440: 63 65 73 20 28 6d 61 6e 79 20 74 68 6f 75 73 61 ces (many thousa
0450: 6e 64 73 20 6f 72 20 65 76 65 6e 20 6d 6f 72 65 nds or even more
0460: 29 20 69 73 20 61 6e 20 65 78 74 72 65 6d 65 6c ) is an extremel
0470: 79 20 73 6c 6f 77 20 70 72 6f 63 65 73 73 2e 3c y slow process.<
0480: 62 72 3e 0d 0a 53 75 62 64 69 76 69 64 69 6e 67 br>..Subdividing
0490: 20 74 68 65 6d 20 69 6e 74 6f 20 6d 61 6e 79 20 them into many
04a0: 73 6d 61 6c 6c 65 72 20 70 61 72 74 73 20 28 77 smaller parts (w
04b0: 68 69 6c 65 20 70 72 65 73 65 72 76 69 6e 67 20 hile preserving
04c0: 66 75 6c 6c 20 74 6f 70 6f 6c 6f 67 69 63 61 6c full topological
04d0: 20 63 6f 6e 73 69 73 74 65 6e 63 79 29 20 75 73 consistency) us
04e0: 75 61 6c 6c 79 20 72 65 73 75 6c 74 73 20 69 6e ually results in
04f0: 20 61 20 73 61 74 69 73 66 79 69 6e 67 20 70 72 a satisfying pr
0500: 6f 63 65 73 73 69 6e 67 20 73 70 65 65 64 2e 0d ocessing speed..
0510: 0a 54 68 69 73 20 69 73 20 65 78 61 63 74 6c 79 .This is exactly
0520: 20 74 68 65 20 69 6e 74 65 6e 64 65 64 20 73 63 the intended sc
0530: 6f 70 65 20 6f 66 20 3c 62 3e 53 54 5f 53 75 62 ope of <b>ST_Sub
0540: 64 69 76 69 64 65 28 29 3c 2f 62 3e 3a 0d 0a 3c divide()</b>:..<
0550: 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 69 73 20 66 75 ul>..<li>this fu
0560: 6e 63 74 69 6f 6e 20 77 69 6c 6c 20 72 65 63 65 nction will rece
0570: 69 76 65 20 61 6e 20 69 6e 70 75 74 20 67 65 6f ive an input geo
0580: 6d 65 74 72 79 20 28 77 68 69 63 68 20 6d 61 79 metry (which may
0590: 20 76 65 72 79 20 77 65 6c 6c 20 62 65 20 65 78 very well be ex
05a0: 74 72 65 6d 65 6c 79 20 6c 61 72 67 65 29 2e 3c tremely large).<
05b0: 2f 6c 69 3e 0d 0a 3c 6c 69 3e 65 61 63 68 20 3c /li>..<li>each <
05c0: 62 3e 4c 69 6e 65 73 74 72 69 6e 67 3c 2f 62 3e b>Linestring</b>
05d0: 20 6f 72 20 3c 62 3e 50 6f 6c 79 67 6f 6e 3c 2f or <b>Polygon</
05e0: 62 3e 20 66 6f 75 6e 64 20 77 69 74 68 69 6e 20 b> found within
05f0: 74 68 65 20 69 6e 70 75 74 20 67 65 6f 6d 65 74 the input geomet
0600: 72 79 20 77 69 6c 6c 20 62 65 20 70 72 6f 63 65 ry will be proce
0610: 73 73 65 64 3a 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 ssed:..<ul>..<li
0620: 3e 61 6c 6c 20 4c 69 6e 65 73 74 72 69 6e 67 73 >all Linestrings
0630: 20 6f 72 20 50 6f 6c 79 67 6f 6e 73 20 75 73 69 or Polygons usi
0640: 6e 67 20 61 20 6e 75 6d 62 65 72 20 6f 66 20 56 ng a number of V
0650: 65 72 74 69 63 65 73 20 6c 65 73 73 65 72 20 6f ertices lesser o
0660: 72 20 65 71 75 61 6c 20 74 68 61 6e 20 74 68 65 r equal than the
0670: 20 67 69 76 65 6e 20 74 68 72 65 73 68 6f 6c 64 given threshold
0680: 20 77 69 6c 6c 20 62 65 20 72 65 74 75 72 6e 65 will be returne
0690: 64 20 61 73 20 74 68 65 79 20 61 72 65 2e 3c 2f d as they are.</
06a0: 6c 69 3e 0d 0a 3c 6c 69 3e 65 76 65 72 79 74 68 li>..<li>everyth
06b0: 69 6e 67 20 65 6c 73 65 20 77 69 6c 6c 20 62 65 ing else will be
06c0: 20 72 65 63 75 72 73 69 76 65 6c 79 20 73 70 6c recursively spl
06d0: 69 74 2c 20 75 6e 74 69 6c 20 61 20 3c 62 3e 63 it, until a <b>c
06e0: 6f 6c 6c 65 63 74 69 6f 6e 3c 2f 62 3e 20 6f 66 ollection</b> of
06f0: 20 65 6c 65 6d 65 6e 74 61 72 79 20 70 61 72 74 elementary part
0700: 73 20 65 78 69 73 74 73 2c 20 75 73 69 6e 67 20 s exists, using
0710: 6e 6f 20 6d 6f 72 65 20 74 68 61 6e 20 74 68 65 no more than the
0720: 20 72 65 71 75 69 72 65 64 20 6e 75 6d 62 65 72 required number
0730: 20 6f 66 20 76 65 72 74 69 63 65 73 2e 3c 2f 6c of vertices.</l
0740: 69 3e 0d 0a 3c 2f 75 6c 3e 3c 2f 6c 69 3e 0d 0a i>..</ul></li>..
0750: 3c 6c 69 3e 77 68 65 6e 20 63 6f 6d 70 6c 65 61 <li>when complea
0760: 74 65 64 2c 20 74 68 65 20 66 75 6e 63 74 69 6f ted, the functio
0770: 6e 20 77 69 6c 6c 20 72 65 74 75 72 6e 20 6f 6e n will return on
0780: 65 20 67 65 6f 6d 65 74 72 79 20 61 73 20 61 20 e geometry as a
0790: 63 6f 6c 6c 65 63 74 69 6f 6e 20 63 6f 6e 74 61 collection conta
07a0: 69 6e 69 6e 67 20 61 6c 6c 20 6f 66 20 74 68 65 ining all of the
07b0: 20 65 6c 65 6d 65 6e 74 61 72 79 20 70 61 72 74 elementary part
07c0: 73 20 28 61 20 3c 62 3e 4d 75 6c 74 69 4c 69 6e s (a <b>MultiLin
07d0: 65 73 74 72 69 6e 67 3c 2f 62 3e 20 6f 72 20 61 estring</b> or a
07e0: 20 3c 62 3e 4d 75 6c 74 69 50 6f 6c 79 67 6f 6e <b>MultiPolygon
07f0: 3c 2f 62 3e 20 64 65 70 65 6e 64 69 6e 67 20 6f </b> depending o
0800: 6e 20 74 68 65 20 6e 61 74 75 72 65 20 6f 66 20 n the nature of
0810: 74 68 65 20 69 6e 70 75 74 20 67 65 6f 6d 65 74 the input geomet
0820: 72 79 29 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e ry).</li>..</ul>
0830: 0d 0a 3c 68 32 3e 42 61 73 69 63 20 53 61 6d 70 ..<h2>Basic Samp
0840: 6c 65 73 3c 2f 68 32 3e 0d 0a 54 68 65 20 66 6f les</h2>..The fo
0850: 6c 6c 6f 77 69 6e 67 20 73 61 6d 70 6c 65 73 73 llowing sampless
0860: 20 61 72 65 20 62 61 73 65 64 20 6f 6e 20 74 68 are based on th
0870: 65 2c 20 66 72 65 65 6c 79 20 61 76 61 69 6c 61 e, freely availa
0880: 62 6c 65 2c 20 3c 62 3e 61 6d 5f 72 65 67 5f 6d ble, <b>am_reg_m
0890: 75 6c 74 69 70 61 72 74 3c 2f 62 3e 20 53 68 61 ultipart</b> Sha
08a0: 70 65 66 69 6c 65 20 61 6e 64 20 63 61 6e 20 62 pefile and can b
08b0: 65 20 64 6f 77 6e 6c 6f 61 64 20 66 72 6f 6d 20 e download from
08c0: 68 65 72 65 20 20 3c 61 20 68 72 65 66 3d 22 68 here <a href="h
08d0: 74 74 70 3a 2f 2f 77 77 77 35 30 32 2e 72 65 67 ttp://www502.reg
08e0: 69 6f 6e 65 2e 74 6f 73 63 61 6e 61 2e 69 74 2f ione.toscana.it/
08f0: 67 65 6f 73 63 6f 70 69 6f 2f 63 61 72 74 6f 74 geoscopio/cartot
0900: 65 63 61 2e 68 74 6d 6c 22 3e 68 65 72 65 3c 2f eca.html">here</
0910: 61 3e 20 28 73 65 61 72 63 68 20 66 6f 72 20 3c a> (search for <
0920: 62 3e 41 6d 62 69 74 69 20 41 6d 6d 69 6e 69 73 b>Ambiti Amminis
0930: 74 72 61 74 69 76 69 3c 2f 62 3e 20 2d 20 3c 69 trativi</b> - <i
0940: 3e 41 64 6d 69 6e 69 73 74 72 61 74 69 76 65 20 >Administrative
0950: 42 6f 75 6e 64 61 72 69 65 73 3c 2f 69 3e 29 2e Boundaries</i>).
0960: 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 53 <br><br>..This S
0970: 68 61 70 65 66 69 6c 65 20 73 75 70 70 6f 72 74 hapefile support
0980: 73 20 61 20 76 65 72 79 20 61 63 63 75 72 61 74 s a very accurat
0990: 65 20 61 6e 64 20 70 72 65 63 69 73 65 20 6d 61 e and precise ma
09a0: 70 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e p representation
09b0: 2c 20 61 6e 64 20 74 68 65 20 6d 61 69 6e 20 65 , and the main e
09c0: 78 74 65 72 69 6f 72 20 72 69 6e 67 20 68 61 73 xterior ring has
09d0: 20 6d 6f 72 65 20 74 68 61 6e 20 31 30 30 2c 30 more than 100,0
09e0: 30 30 2b 20 56 65 72 74 69 63 65 73 2e 3c 62 72 00+ Vertices.<br
09f0: 3e 0d 0a 49 74 27 73 20 61 20 76 65 72 79 20 67 >..It's a very g
0a00: 6f 6f 64 20 65 78 61 6d 70 6c 65 20 6f 66 20 61 ood example of a
0a10: 20 47 65 6f 6d 65 74 72 79 2c 20 74 68 61 74 20 Geometry, that
0a20: 69 73 20 73 6f 20 68 75 67 65 20 61 6e 64 20 77 is so huge and w
0a30: 69 6c 6c 20 63 61 75 73 65 20 61 6e 79 20 53 70 ill cause any Sp
0a40: 61 74 69 61 6c 20 6f 70 65 72 61 74 6f 72 2c 20 atial operator,
0a50: 73 75 63 68 20 61 73 20 53 54 5f 49 6e 74 65 72 such as ST_Inter
0a60: 73 65 63 74 73 2c 20 53 54 5f 54 6f 75 63 68 65 sects, ST_Touche
0a70: 73 2c 20 53 54 5f 43 6f 76 65 72 73 20 65 74 63 s, ST_Covers etc
0a80: 2e 2c 20 74 6f 20 62 65 63 6f 6d 65 20 65 78 74 ., to become ext
0a90: 72 65 6d 65 6c 79 20 73 6c 6f 77 2e 3c 62 72 3e remely slow.<br>
0aa0: 3c 62 72 3e 0d 0a 3c 74 61 62 6c 65 20 62 67 63 <br>..<table bgc
0ab0: 6f 6c 6f 72 3d 22 23 65 30 66 66 65 30 22 20 63 olor="#e0ffe0" c
0ac0: 65 6c 6c 73 70 61 63 69 6e 67 3d 22 38 22 20 63 ellspacing="8" c
0ad0: 65 6c 6c 70 61 64 64 69 6e 67 3d 22 36 22 20 62 ellpadding="6" b
0ae0: 6f 72 64 65 72 3d 22 31 22 3e 0d 0a 3c 74 72 3e order="1">..<tr>
0af0: 3c 74 68 3e 53 51 4c 20 71 75 65 72 79 3c 2f 74 <th>SQL query</t
0b00: 68 3e 3c 74 68 3e 56 69 73 75 61 6c 20 53 61 6d h><th>Visual Sam
0b10: 70 6c 65 3c 2f 74 68 3e 3c 2f 74 72 3e 0d 0a 3c ple</th></tr>..<
0b20: 74 72 3e 0d 0a 3c 74 64 3e 0d 0a 3c 76 65 72 62 tr>..<td>..<verb
0b30: 61 74 69 6d 3e 0d 0a 53 45 4c 45 43 54 20 53 54 atim>..SELECT ST
0b40: 5f 53 75 62 64 69 76 69 64 65 28 67 65 6f 6d 65 _Subdivide(geome
0b50: 74 72 79 29 20 46 52 4f 4d 20 74 75 73 63 61 6e try) FROM tuscan
0b60: 79 3b 0d 0a 3c 2f 76 65 72 62 61 74 69 6d 3e 0d y;..</verbatim>.
0b70: 0a 69 6e 20 74 68 69 73 20 66 69 72 73 74 20 63 .in this first c
0b80: 61 6c 6c 2c 20 77 69 74 68 20 6e 6f 20 6f 70 74 all, with no opt
0b90: 69 6f 6e 61 6c 20 61 72 67 75 6d 65 6e 74 20 73 ional argument s
0ba0: 70 65 63 69 66 69 65 64 2c 20 3c 62 3e 53 54 5f pecified, <b>ST_
0bb0: 53 75 62 64 69 76 69 64 65 28 29 3c 2f 62 3e 20 Subdivide()</b>
0bc0: 77 69 6c 6c 20 73 74 61 72 74 20 73 70 6c 69 74 will start split
0bd0: 74 69 6e 67 20 3c 62 3e 61 66 74 65 72 3c 2f 62 ting <b>after</b
0be0: 3e 20 75 73 65 20 74 68 65 20 73 74 61 6e 64 61 > use the standa
0bf0: 72 64 20 74 68 72 65 73 68 6f 6c 64 20 6f 66 20 rd threshold of
0c00: 3c 62 3e 31 32 38 20 56 65 72 74 69 63 65 73 3c <b>128 Vertices<
0c10: 2f 62 3e 20 69 73 20 65 78 63 65 65 64 65 64 2e /b> is exceeded.
0c20: 3c 62 72 3e 3c 62 72 3e 0d 0a 41 73 20 74 68 65 <br><br>..As the
0c30: 20 73 69 64 65 20 66 69 67 75 72 65 20 73 68 6f side figure sho
0c40: 77 73 2c 20 74 68 65 20 72 65 74 75 72 6e 65 64 ws, the returned
0c50: 20 72 65 73 75 6c 74 20 69 73 20 61 20 63 6f 6c result is a col
0c60: 6c 65 63 74 69 6f 6e 20 6f 66 20 61 62 6f 75 74 lection of about
0c70: 20 34 2c 33 30 30 2b 20 65 6c 65 6d 65 6e 74 61 4,300+ elementa
0c80: 72 79 20 70 61 72 74 73 2e 0d 0a 3c 2f 74 64 3e ry parts...</td>
0c90: 0d 0a 3c 74 64 3e 0d 0a 3c 69 6d 67 20 73 72 63 ..<td>..<img src
0ca0: 3d 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 67 61 ="https://www.ga
0cb0: 69 61 2d 67 69 73 2e 69 74 2f 67 61 69 61 2d 73 ia-gis.it/gaia-s
0cc0: 69 6e 73 2f 73 75 62 64 69 76 69 64 65 2f 73 75 ins/subdivide/su
0cd0: 62 31 32 38 2e 70 6e 67 22 20 61 6c 74 3d 22 6d b128.png" alt="m
0ce0: 61 78 3d 31 32 38 22 3e 0d 0a 3c 2f 74 64 3e 0d ax=128">..</td>.
0cf0: 0a 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 0d 0a 3c 74 .</tr>..<tr>..<t
0d00: 64 3e 0d 0a 3c 76 65 72 62 61 74 69 6d 3e 0d 0a d>..<verbatim>..
0d10: 53 45 4c 45 43 54 20 53 54 5f 53 75 62 64 69 76 SELECT ST_Subdiv
0d20: 69 64 65 28 67 65 6f 6d 65 74 72 79 2c 20 35 31 ide(geometry, 51
0d30: 32 29 20 46 52 4f 4d 20 74 75 73 63 61 6e 79 3b 2) FROM tuscany;
0d40: 0d 0a 3c 2f 76 65 72 62 61 74 69 6d 3e 0d 0a 69 ..</verbatim>..i
0d50: 6e 20 74 68 69 73 20 73 65 63 6f 6e 64 20 63 61 n this second ca
0d60: 6c 6c 20 74 68 65 20 6f 70 74 69 6f 6e 61 6c 20 ll the optional
0d70: 61 72 67 75 6d 65 6e 74 20 69 73 20 65 78 70 6c argument is expl
0d80: 69 63 69 74 6c 79 20 73 65 74 2c 20 61 6e 64 20 icitly set, and
0d90: 3c 62 3e 53 54 5f 53 75 62 64 69 76 69 64 65 28 <b>ST_Subdivide(
0da0: 29 3c 2f 62 3e 20 69 73 20 6e 6f 77 20 61 73 73 )</b> is now ass
0db0: 75 6d 69 6e 67 20 61 20 74 68 72 65 73 68 6f 6c uming a threshol
0dc0: 64 20 6f 66 20 3c 62 3e 35 31 32 20 56 65 72 74 d of <b>512 Vert
0dd0: 69 63 65 73 3c 2f 62 3e 2e 3c 62 72 3e 3c 62 72 ices</b>.<br><br
0de0: 3e 0d 0a 41 73 20 74 68 65 20 73 69 64 65 20 66 >..As the side f
0df0: 69 67 75 72 65 20 73 68 6f 77 73 2c 20 74 68 65 igure shows, the
0e00: 20 72 65 74 75 72 6e 65 64 20 72 65 73 75 6c 74 returned result
0e10: 20 69 73 20 61 20 63 6f 6c 6c 65 63 74 69 6f 6e is a collection
0e20: 20 6f 66 20 61 62 6f 75 74 20 31 2c 38 30 30 2b of about 1,800+
0e30: 20 65 6c 65 6d 65 6e 74 61 72 79 20 70 61 72 74 elementary part
0e40: 73 2e 0d 0a 3c 2f 74 64 3e 0d 0a 3c 74 64 3e 0d s...</td>..<td>.
0e50: 0a 3c 69 6d 67 20 73 72 63 3d 22 68 74 74 70 73 .<img src="https
0e60: 3a 2f 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e ://www.gaia-gis.
0e70: 69 74 2f 67 61 69 61 2d 73 69 6e 73 2f 73 75 62 it/gaia-sins/sub
0e80: 64 69 76 69 64 65 2f 73 75 62 35 31 32 2e 70 6e divide/sub512.pn
0e90: 67 22 20 61 6c 74 3d 22 6d 61 78 3d 35 31 32 22 g" alt="max=512"
0ea0: 3e 0d 0a 3c 2f 74 64 3e 0d 0a 3c 2f 74 72 3e 0d >..</td>..</tr>.
0eb0: 0a 3c 74 72 3e 0d 0a 3c 74 64 3e 0d 0a 3c 76 65 .<tr>..<td>..<ve
0ec0: 72 62 61 74 69 6d 3e 0d 0a 53 45 4c 45 43 54 20 rbatim>..SELECT
0ed0: 53 54 5f 53 75 62 64 69 76 69 64 65 28 67 65 6f ST_Subdivide(geo
0ee0: 6d 65 74 72 79 2c 20 32 30 34 38 29 20 46 52 4f metry, 2048) FRO
0ef0: 4d 20 74 75 73 63 61 6e 79 3b 0d 0a 3c 2f 76 65 M tuscany;..</ve
0f00: 72 62 61 74 69 6d 3e 0d 0a 69 6e 20 74 68 69 73 rbatim>..in this
0f10: 20 74 68 69 72 64 20 61 6e 64 20 66 69 6e 61 6c third and final
0f20: 20 63 61 6c 6c 20 74 68 65 20 74 68 72 65 73 68 call the thresh
0f30: 6f 6c 64 20 69 73 20 73 65 74 20 74 6f 20 73 74 old is set to st
0f40: 61 72 74 20 61 66 74 65 72 20 3c 62 3e 32 2c 30 art after <b>2,0
0f50: 34 38 20 56 65 72 74 69 63 65 73 3c 2f 62 3e 2e 48 Vertices</b>.
0f60: 3c 62 72 3e 3c 62 72 3e 0d 0a 41 73 20 73 68 6f <br><br>..As sho
0f70: 77 6e 20 62 79 20 74 68 65 20 66 69 67 75 72 65 wn by the figure
0f80: 2c 20 74 68 65 20 72 65 74 75 72 6e 65 64 20 72 , the returned r
0f90: 65 73 75 6c 74 20 69 73 20 6e 6f 77 20 61 20 63 esult is now a c
0fa0: 6f 6c 6c 65 63 74 69 6f 6e 20 63 6f 6e 74 61 69 ollection contai
0fb0: 6e 69 6e 67 20 6f 6e 6c 79 20 31 2c 32 30 30 2b ning only 1,200+
0fc0: 20 65 6c 65 6d 65 6e 74 61 72 79 20 70 61 72 74 elementary part
0fd0: 73 2e 0d 0a 3c 68 33 3e 53 68 6f 72 74 20 63 6f s...<h3>Short co
0fe0: 6e 63 6c 75 73 69 6f 6e 3c 2f 68 33 3e 0d 0a 3c nclusion</h3>..<
0ff0: 62 3e 53 54 5f 53 75 62 64 69 76 69 64 65 28 29 b>ST_Subdivide()
1000: 3c 2f 62 3e 20 69 73 20 76 65 72 79 20 63 61 70 </b> is very cap
1010: 61 62 6c 65 20 6f 66 20 73 75 62 64 69 76 69 64 able of subdivid
1020: 69 6e 67 20 61 20 68 75 67 65 2c 20 6e 61 73 74 ing a huge, nast
1030: 79 2c 20 47 65 6f 6d 65 74 72 79 20 69 6e 74 6f y, Geometry into
1040: 20 61 20 63 6f 6c 6c 65 63 74 69 6f 6e 20 6f 66 a collection of
1050: 20 73 6d 61 6c 6c 65 72 20 70 61 72 74 73 2c 20 smaller parts,
1060: 74 68 61 74 20 63 61 6e 20 62 65 20 68 61 6e 64 that can be hand
1070: 6c 65 64 20 69 6e 20 61 20 6d 6f 72 65 20 72 65 led in a more re
1080: 61 73 6f 6e 61 62 6c 65 20 6d 61 6e 6e 65 72 2e asonable manner.
1090: 3c 62 72 3e 0d 0a 41 6e 64 20 69 74 27 73 20 61 <br>..And it's a
10a0: 79 20 66 6c 65 78 69 62 6c 65 20 61 6e 64 20 65 y flexible and e
10b0: 61 73 79 20 74 6f 20 63 75 73 74 6f 6d 69 7a 65 asy to customize
10c0: 3b 20 79 6f 75 20 6a 75 73 74 20 68 61 76 65 20 ; you just have
10d0: 74 6f 20 73 65 74 20 61 6e 20 61 70 70 72 6f 70 to set an approp
10e0: 72 69 61 74 65 20 3c 62 3e 56 65 72 74 69 63 65 riate <b>Vertice
10f0: 73 3c 2f 62 3e 20 74 68 72 65 73 68 6f 6c 64 2e s</b> threshold.
1100: 0d 0a 3c 2f 74 64 3e 0d 0a 3c 74 64 3e 0d 0a 3c ..</td>..<td>..<
1110: 69 6d 67 20 73 72 63 3d 22 68 74 74 70 73 3a 2f img src="https:/
1120: 2f 77 77 77 2e 67 61 69 61 2d 67 69 73 2e 69 74 /www.gaia-gis.it
1130: 2f 67 61 69 61 2d 73 69 6e 73 2f 73 75 62 64 69 /gaia-sins/subdi
1140: 76 69 64 65 2f 73 75 62 32 30 34 38 2e 70 6e 67 vide/sub2048.png
1150: 22 20 61 6c 74 3d 22 6d 61 78 3d 32 30 34 38 22 " alt="max=2048"
1160: 3e 0d 0a 3c 2f 74 64 3e 0d 0a 3c 2f 74 72 3e 0d >..</td>..</tr>.
1170: 0a 3c 2f 74 61 62 6c 65 3e 0d 0a 3c 62 72 3e 0d .</table>..<br>.
1180: 0a 48 6f 77 65 76 65 72 2c 20 61 20 62 69 67 20 .However, a big
1190: 64 69 73 61 64 76 61 6e 74 61 67 65 20 73 68 6f disadvantage sho
11a0: 75 6c 64 20 62 65 20 61 6c 77 61 79 73 20 62 65 uld be always be
11b0: 20 63 6f 6e 73 69 64 65 72 65 64 20 77 68 65 6e considered when
11c0: 20 75 73 69 6e 67 20 74 68 65 20 6d 75 6c 74 69 using the multi
11d0: 2d 70 61 72 74 20 63 6f 6c 6c 65 63 74 69 6f 6e -part collection
11e0: 73 20 72 65 74 75 72 6e 65 64 20 62 79 20 3c 62 s returned by <b
11f0: 3e 53 54 5f 53 75 62 64 69 76 69 64 65 28 29 3c >ST_Subdivide()<
1200: 2f 62 3e 2e 3c 62 72 3e 0d 0a 41 74 20 6c 65 61 /b>.<br>..At lea
1210: 73 74 20 69 6e 20 74 68 65 20 63 61 73 65 20 6f st in the case o
1220: 66 20 3c 62 3e 4d 75 6c 74 69 50 6f 6c 79 67 6f f <b>MultiPolygo
1230: 6e 73 3c 2f 62 3e 2c 20 61 6e 79 20 63 6f 6c 6c ns</b>, any coll
1240: 65 63 74 69 6f 6e 20 72 65 74 75 72 6e 65 64 20 ection returned
1250: 62 79 20 53 54 5f 53 75 62 64 69 76 69 64 65 28 by ST_Subdivide(
1260: 29 20 69 73 20 69 6e 68 65 72 65 6e 74 6c 79 20 ) is inherently
1270: 69 6e 76 61 6c 69 64 2c 20 61 73 20 74 68 65 20 invalid, as the
1280: 66 6f 6c 6c 6f 77 69 6e 67 20 53 51 4c 20 71 75 following SQL qu
1290: 65 72 79 20 64 65 6d 6f 6e 73 74 72 61 74 65 73 ery demonstrates
12a0: 3a 0d 0a 3c 76 65 72 62 61 74 69 6d 3e 0d 0a 53 :..<verbatim>..S
12b0: 45 4c 45 43 54 20 53 54 5f 49 73 56 61 6c 69 64 ELECT ST_IsValid
12c0: 28 53 54 5f 53 75 62 64 69 76 69 64 65 28 67 65 (ST_Subdivide(ge
12d0: 6f 6d 65 74 72 79 29 29 20 46 52 4f 4d 20 74 75 ometry)) FROM tu
12e0: 73 63 61 6e 79 3b 0d 0a 2d 2d 2d 2d 2d 2d 2d 2d scany;..--------
12f0: 2d 0d 0a 30 0d 0a 3c 2f 76 65 72 62 61 74 69 6d -..0..</verbatim
1300: 3e 0d 0a 49 74 27 73 20 6e 6f 74 20 61 74 20 61 >..It's not at a
1310: 6c 6c 20 64 69 66 66 69 63 75 6c 74 20 74 6f 20 ll difficult to
1320: 75 6e 64 65 72 73 74 61 6e 64 20 77 68 79 20 74 understand why t
1330: 68 69 73 20 69 73 20 73 6f 2e 3c 62 72 3e 0d 0a his is so.<br>..
1340: 41 63 63 6f 72 64 69 6e 67 6c 79 20 74 6f 20 73 Accordingly to s
1350: 74 61 6e 64 61 72 64 20 3c 62 3e 4f 47 43 2f 53 tandard <b>OGC/S
1360: 46 53 3c 2f 62 3e 20 72 75 6c 65 73 3a 20 74 77 FS</b> rules: tw
1370: 6f 20 73 69 6e 67 6c 65 2d 70 61 72 74 20 50 6f o single-part Po
1380: 6c 79 67 6f 6e 73 2c 20 62 65 6c 6f 6e 67 69 6e lygons, belongin
1390: 67 20 74 6f 20 74 68 65 20 73 61 6d 65 20 4d 75 g to the same Mu
13a0: 6c 74 69 50 6f 6c 79 67 6f 6e 2c 20 61 72 65 20 ltiPolygon, are
13b0: 61 6c 77 61 79 73 20 66 6f 72 62 69 64 64 65 6e always forbidden
13c0: 20 74 6f 20 73 68 61 72 65 20 61 20 63 6f 6d 6d to share a comm
13d0: 6f 6e 20 62 6f 72 64 65 72 2e 3c 62 72 3e 0d 0a on border.<br>..
13e0: 4d 6f 72 65 20 70 72 65 63 69 73 65 6c 79 3a 20 More precisely:
13f0: 74 68 65 79 20 63 61 6e 20 6f 6e 6c 79 20 74 6f they can only to
1400: 75 63 68 20 6f 6e 20 73 70 65 63 69 66 69 63 20 uch on specific
1410: 70 6f 69 6e 74 28 73 29 2c 20 62 75 74 20 74 68 point(s), but th
1420: 65 79 20 63 61 6e 20 6e 65 76 65 72 20 73 68 61 ey can never sha
1430: 72 65 20 61 20 63 6f 6d 6d 6f 6e 20 62 6f 75 6e re a common boun
1440: 64 61 72 79 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 3c dary.<br><br>..<
1450: 74 61 62 6c 65 20 62 67 63 6f 6c 6f 72 3d 22 23 table bgcolor="#
1460: 66 66 64 30 64 30 22 20 63 65 6c 6c 73 70 61 63 ffd0d0" cellspac
1470: 69 6e 67 3d 22 38 22 20 63 65 6c 6c 70 61 64 64 ing="8" cellpadd
1480: 69 6e 67 3d 22 36 22 3e 0d 0a 3c 74 72 3e 3c 74 ing="6">..<tr><t
1490: 64 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 d align="center"
14a0: 3e 3c 68 33 3e 5b 26 69 65 78 63 6c 3b 26 69 65 ><h3>[¡&ie
14b0: 78 63 6c 3b 26 69 65 78 63 6c 3b 20 57 61 72 6e xcl;¡ Warn
14c0: 69 6e 67 20 21 21 21 5d 3c 2f 68 33 3e 3c 2f 74 ing !!!]</h3></t
14d0: 64 3e 3c 2f 74 72 3e 0d 0a 3c 74 72 3e 3c 74 64 d></tr>..<tr><td
14e0: 3e 3c 62 3e 4e 65 76 65 72 2c 20 65 76 65 72 2c ><b>Never, ever,
14f0: 20 70 61 73 73 20 73 75 63 68 20 61 20 47 65 6f pass such a Geo
1500: 6d 65 74 72 79 20 20 74 6f 20 61 6e 79 20 53 70 metry to any Sp
1510: 61 74 69 61 6c 20 6f 70 65 72 61 74 6f 72 20 73 atial operator s
1520: 75 63 68 20 61 73 20 53 54 5f 49 6e 74 65 72 73 uch as ST_Inters
1530: 65 63 74 73 2c 20 53 54 5f 54 6f 75 63 68 65 73 ects, ST_Touches
1540: 2c 20 53 54 5f 43 6f 76 65 72 73 20 65 74 63 2e , ST_Covers etc.
1550: 2e 3c 62 72 3e 3c 62 72 3e 0d 0a 54 68 69 73 20 .<br><br>..This
1560: 77 69 6c 6c 20 63 65 72 74 61 69 6e 6c 79 20 64 will certainly d
1570: 72 69 76 65 20 74 68 65 20 3c 62 3e 47 45 4f 53 rive the <b>GEOS
1580: 3c 2f 62 3e 20 6c 69 62 72 61 72 79 20 6e 75 74 </b> library nut
1590: 74 79 2e 3c 62 72 3e 0d 0a 49 6e 63 6f 72 72 65 ty.<br>..Incorre
15a0: 63 74 20 72 65 73 75 6c 74 73 20 6d 61 79 20 65 ct results may e
15b0: 61 73 69 6c 79 20 66 6f 6c 6c 6f 77 2e 3c 62 72 asily follow.<br
15c0: 3e 0d 0a 41 6e 64 20 69 6e 20 74 68 65 20 77 6f >..And in the wo
15d0: 72 73 74 20 63 61 73 65 20 73 6f 6d 65 20 75 6e rst case some un
15e0: 65 78 70 65 63 74 65 64 20 63 72 61 73 68 20 63 expected crash c
15f0: 6f 75 6c 64 20 65 76 65 6e 74 75 61 6c 6c 79 20 ould eventually
1600: 6f 63 63 75 72 2e 0d 0a 3c 68 33 3e 59 6f 75 20 occur...<h3>You
1610: 68 61 76 65 20 62 65 65 6e 20 77 61 72 6e 65 64 have been warned
1620: 20 21 21 21 3c 2f 68 33 3e 0d 0a 3c 2f 74 64 3e !!!</h3>..</td>
1630: 0d 0a 3c 2f 74 72 3e 0d 0a 3c 2f 74 61 62 6c 65 ..</tr>..</table
1640: 3e 0d 0a 3c 62 72 3e 3c 62 72 3e 0d 0a 3c 68 72 >..<br><br>..<hr
1650: 3e 0d 0a 3c 68 32 3e 41 64 76 61 6e 63 65 64 20 >..<h2>Advanced
1660: 53 61 6d 70 6c 65 73 3c 2f 68 32 3e 0d 0a 4e 6f Samples</h2>..No
1670: 77 20 77 65 27 6c 6c 20 67 6f 20 6f 6e 20 74 6f w we'll go on to
1680: 20 65 78 70 6c 6f 72 65 20 74 68 65 20 72 65 61 explore the rea
1690: 6c 20 65 66 66 65 63 74 69 76 65 6e 65 73 73 20 l effectiveness
16a0: 6f 66 20 3c 62 3e 53 54 5f 53 75 62 64 69 76 69 of <b>ST_Subdivi
16b0: 64 65 28 29 3c 2f 62 3e 20 66 6f 72 20 6f 6e 65 de()</b> for one
16c0: 20 6f 66 20 74 68 65 20 6d 6f 73 74 20 63 6f 6d of the most com
16d0: 6d 6f 6e 20 53 70 61 74 69 61 6c 20 50 72 6f 62 mon Spatial Prob
16e0: 6c 65 6d 73 3a 20 69 64 65 6e 74 69 66 79 69 6e lems: identifyin
16f0: 67 20 61 6c 6c 20 69 6e 74 65 72 73 65 63 74 69 g all intersecti
1700: 6f 6e 73 20 62 65 74 77 65 65 6e 20 61 20 64 61 ons between a da
1710: 74 61 73 65 74 20 6f 66 20 74 68 65 20 50 4f 49 taset of the POI
1720: 4e 54 20 74 79 70 65 20 61 6e 64 20 61 20 68 75 NT type and a hu
1730: 67 65 20 50 6f 6c 79 67 6f 6e 2f 4d 75 6c 74 69 ge Polygon/Multi
1740: 50 6f 6c 79 67 6f 6e 2e 3c 62 72 3e 3c 62 72 3e Polygon.<br><br>
1750: 0d 0a 44 75 72 69 6e 67 20 74 68 69 73 20 73 65 ..During this se
1760: 63 6f 6e 64 20 74 65 73 74 20 77 65 27 6c 6c 20 cond test we'll
1770: 75 73 65 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e use the followin
1780: 67 20 64 61 74 61 73 65 74 73 3a 0d 0a 3c 75 6c g datasets:..<ul
1790: 3e 0d 0a 3c 6c 69 3e 75 73 69 6e 67 2c 20 6f 6e >..<li>using, on
17a0: 63 65 20 61 67 61 69 6e 2c 20 74 68 65 20 73 61 ce again, the sa
17b0: 6d 65 20 61 64 6d 69 6e 69 73 74 72 61 74 69 76 me administrativ
17c0: 65 20 62 6f 75 6e 64 61 72 79 20 6f 66 20 54 75 e boundary of Tu
17d0: 73 63 61 6e 79 20 77 65 27 76 65 20 61 6c 72 65 scany we've alre
17e0: 61 64 79 20 75 73 65 64 20 62 65 66 6f 72 65 2e ady used before.
17f0: 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 66 6f 72 20 74 </li>..<li>for t
1800: 68 65 20 50 4f 49 4e 54 20 64 61 74 61 73 65 74 he POINT dataset
1810: 20 77 65 27 6c 6c 20 75 73 65 20 74 68 65 20 3c we'll use the <
1820: 62 3e 63 69 76 69 63 69 3c 2f 62 3e 20 53 68 61 b>civici</b> Sha
1830: 70 65 66 69 6c 65 20 28 3c 69 3e 48 6f 75 73 65 pefile (<i>House
1840: 20 4e 75 6d 62 65 72 73 3c 2f 69 3e 29 29 2c 20 Numbers</i>)),
1850: 61 6c 73 6f 20 66 72 65 65 6c 79 20 61 76 61 69 also freely avai
1860: 6c 61 62 6c 65 2c 20 61 6e 64 20 63 61 6e 20 62 lable, and can b
1870: 65 20 64 6f 77 6e 6c 6f 61 64 20 68 65 72 65 20 e download here
1880: 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f <a href="http://
1890: 77 77 77 35 30 32 2e 72 65 67 69 6f 6e 65 2e 74 www502.regione.t
18a0: 6f 73 63 61 6e 61 2e 69 74 2f 67 65 6f 73 63 6f oscana.it/geosco
18b0: 70 69 6f 2f 63 61 72 74 6f 74 65 63 61 2e 68 74 pio/cartoteca.ht
18c0: 6d 6c 22 3e 68 65 72 65 3c 2f 61 3e 20 28 73 65 ml">here</a> (se
18d0: 61 72 63 68 20 66 6f 72 20 3c 62 3e 47 72 61 66 arch for <b>Graf
18e0: 6f 20 53 74 72 61 64 61 6c 65 3c 2f 62 3e 20 2d o Stradale</b> -
18f0: 20 3c 69 3e 52 6f 61 64 20 4e 65 74 77 6f 72 6b <i>Road Network
1900: 3c 2f 69 3e 29 2e 3c 62 72 3e 0d 0a 54 68 69 73 </i>).<br>..This
1910: 20 74 6f 6f 20 69 73 20 61 20 68 75 67 65 20 64 too is a huge d
1920: 61 74 61 73 65 74 20 63 6f 6e 74 61 69 6e 69 6e ataset containin
1930: 67 20 61 62 6f 75 74 20 31 2e 35 20 6d 69 6c 6c g about 1.5 mill
1940: 69 6f 6e 20 70 6f 69 6e 74 73 2e 0d 0a 3c 2f 75 ion points...</u
1950: 6c 3e 0d 0a 3c 68 33 3e 41 20 66 69 72 73 74 20 l>..<h3>A first
1960: 73 69 6d 70 6c 65 20 61 74 74 65 6d 70 74 3c 2f simple attempt</
1970: 68 33 3e 0d 0a 3c 76 65 72 62 61 74 69 6d 3e 0d h3>..<verbatim>.
1980: 0a 53 45 4c 45 43 54 20 43 6f 75 6e 74 28 2a 29 .SELECT Count(*)
1990: 0d 0a 46 52 4f 4d 20 63 69 76 69 63 69 20 41 53 ..FROM civici AS
19a0: 20 63 0d 0a 4c 45 46 54 20 4a 4f 49 4e 20 74 75 c..LEFT JOIN tu
19b0: 73 63 61 6e 79 20 41 53 20 74 20 4f 4e 20 28 53 scany AS t ON (S
19c0: 54 5f 49 6e 74 65 72 73 65 63 74 73 28 63 2e 67 T_Intersects(c.g
19d0: 65 6f 6d 65 74 72 79 2c 20 74 2e 67 65 6f 6d 65 eometry, t.geome
19e0: 74 72 79 29 20 3d 20 31 29 3b 0d 0a 0d 0a 0d 0a try) = 1);......
19f0: 53 45 4c 45 43 54 20 43 6f 75 6e 74 28 2a 29 0d SELECT Count(*).
1a00: 0a 46 52 4f 4d 20 63 69 76 69 63 69 20 41 53 20 .FROM civici AS
1a10: 63 0d 0a 4c 45 46 54 20 4a 4f 49 4e 20 74 75 73 c..LEFT JOIN tus
1a20: 63 61 6e 79 20 41 53 20 74 20 4f 4e 20 28 53 54 cany AS t ON (ST
1a30: 5f 49 6e 74 65 72 73 65 63 74 73 28 63 2e 67 65 _Intersects(c.ge
1a40: 6f 6d 65 74 72 79 2c 20 74 2e 67 65 6f 6d 65 74 ometry, t.geomet
1a50: 72 79 29 20 3d 20 31 20 0d 0a 20 20 20 20 20 41 ry) = 1 .. A
1a60: 4e 44 20 63 2e 72 6f 77 69 64 20 49 4e 20 28 0d ND c.rowid IN (.
1a70: 0a 20 20 20 20 20 20 20 20 20 53 45 4c 45 43 54 . SELECT
1a80: 20 72 6f 77 69 64 20 46 52 4f 4d 20 53 70 61 74 rowid FROM Spat
1a90: 69 61 6c 49 6e 64 65 78 0d 0a 20 20 20 20 20 20 ialIndex..
1aa0: 20 20 20 57 48 45 52 45 20 66 5f 74 61 62 6c 65 WHERE f_table
1ab0: 5f 6e 61 6d 65 20 3d 20 27 63 69 76 69 63 69 27 _name = 'civici'
1ac0: 20 41 4e 44 20 73 65 61 72 63 68 5f 66 72 61 6d AND search_fram
1ad0: 65 20 3d 20 74 2e 67 65 6f 6d 65 74 72 79 29 29 e = t.geometry))
1ae0: 3b 0d 0a 3c 2f 76 65 72 62 61 74 69 6d 3e 0d 0a ;..</verbatim>..
1af0: 54 68 65 20 6f 6e 6c 79 20 64 69 66 66 65 72 65 The only differe
1b00: 6e 63 65 20 62 65 74 77 65 65 6e 20 74 68 65 20 nce between the
1b10: 74 77 6f 20 53 51 4c 20 71 75 65 72 69 65 73 20 two SQL queries
1b20: 69 73 20 69 6e 20 74 68 61 74 20 74 68 65 20 73 is in that the s
1b30: 65 63 6f 6e 64 20 6f 6e 65 20 65 78 70 6c 69 63 econd one explic
1b40: 69 74 6c 79 20 63 61 6c 6c 73 20 74 68 65 20 53 itly calls the S
1b50: 70 61 74 69 61 6c 20 49 6e 64 65 78 2e 3c 62 72 patial Index.<br
1b60: 3e 3c 62 72 3e 0d 0a 3c 62 3e 41 63 74 75 61 6c ><br>..<b>Actual
1b70: 20 66 69 6e 64 69 6e 67 73 3c 2f 62 3e 3a 0d 0a findings</b>:..
1b80: 3c 75 6c 3e 0d 0a 3c 6c 69 3e 49 20 77 61 73 20 <ul>..<li>I was
1b90: 66 6f 72 63 65 64 20 74 6f 20 70 72 65 6d 61 74 forced to premat
1ba0: 75 72 65 6c 79 20 61 62 6f 72 74 20 74 68 65 20 urely abort the
1bb0: 66 69 72 73 74 20 74 65 73 74 20 77 68 65 6e 20 first test when
1bc0: 49 20 64 69 73 63 6f 76 65 72 65 64 20 74 68 61 I discovered tha
1bd0: 74 2c 20 64 75 72 69 6e 67 20 74 68 65 20 66 69 t, during the fi
1be0: 72 73 74 20 68 61 6c 66 20 68 6f 75 72 2c 20 69 rst half hour, i
1bf0: 74 20 68 61 64 20 6d 61 64 65 20 6c 69 74 74 6c t had made littl
1c00: 65 20 70 72 6f 67 72 65 73 73 2e 3c 62 72 3e 0d e progress.<br>.
1c10: 0a 4d 79 20 65 73 74 69 6d 61 74 65 64 20 63 6f .My estimated co
1c20: 6e 63 6c 75 73 69 6f 6e 20 77 61 73 20 74 68 61 nclusion was tha
1c30: 74 20 62 65 74 77 65 65 6e 20 34 20 61 6e 64 20 t between 4 and
1c40: 36 20 68 6f 75 72 73 20 77 6f 75 6c 64 20 62 65 6 hours would be
1c50: 20 72 65 71 75 69 72 65 64 20 66 6f 72 20 63 6f required for co
1c60: 6d 70 6c 65 74 69 6f 6e 2e 3c 62 72 3e 0d 0a 44 mpletion.<br>..D
1c70: 65 66 69 6e 69 74 65 6c 79 20 74 68 69 73 20 69 efinitely this i
1c80: 73 6e 27 74 20 61 20 70 72 61 63 74 69 63 61 6c sn't a practical
1c90: 20 73 6f 6c 75 74 69 6f 6e 20 66 6f 72 20 6f 75 solution for ou
1ca0: 72 20 70 72 6f 62 6c 65 6d 2e 3c 2f 6c 69 3e 0d r problem.</li>.
1cb0: 0a 3c 6c 69 3e 74 68 65 20 73 65 63 6f 6e 64 20 .<li>the second
1cc0: 74 65 73 74 20 77 61 73 2c 20 69 66 20 70 6f 73 test was, if pos
1cd0: 73 69 62 6c 65 2c 20 65 76 65 6e 20 73 6c 6f 77 sible, even slow
1ce0: 65 72 20 74 68 61 6e 20 74 68 65 20 66 69 72 73 er than the firs
1cf0: 74 20 6f 6e 65 2e 3c 62 72 3e 0d 0a 41 6e 64 20 t one.<br>..And
1d00: 66 6f 72 20 76 65 72 79 20 67 6f 6f 64 20 72 65 for very good re
1d10: 61 73 6f 6e 73 2c 20 74 68 61 74 20 61 72 65 20 asons, that are
1d20: 65 61 73 79 20 74 6f 20 65 78 70 6c 61 69 6e 3b easy to explain;
1d30: 20 61 6c 6c 20 50 6f 69 6e 74 73 20 74 6f 20 62 all Points to b
1d40: 65 20 63 68 65 63 6b 65 64 20 66 61 6c 6c 20 69 e checked fall i
1d50: 6e 73 69 64 65 20 74 68 65 20 42 42 4f 58 20 6f nside the BBOX o
1d60: 66 20 54 75 73 63 61 6e 79 2e 3c 62 72 3e 0d 0a f Tuscany.<br>..
1d70: 53 6f 20 74 68 65 20 53 70 61 74 69 61 6c 20 49 So the Spatial I
1d80: 6e 64 65 78 20 69 73 6e 27 74 20 6f 66 20 61 6e ndex isn't of an
1d90: 79 20 70 6f 73 73 69 62 6c 65 20 68 65 6c 70 2e y possible help.
1da0: 3c 62 72 3e 0d 0a 41 6e 64 20 74 6f 20 6d 61 6b <br>..And to mak
1db0: 65 20 6d 61 74 74 65 72 73 20 77 6f 72 73 74 2c e matters worst,
1dc0: 20 71 75 65 72 79 69 6e 67 20 74 68 65 20 53 70 querying the Sp
1dd0: 61 74 69 61 6c 20 49 6e 64 65 78 20 69 6d 70 6f atial Index impo
1de0: 73 65 73 20 61 20 66 75 72 74 68 65 72 20 6f 76 ses a further ov
1df0: 65 72 68 65 61 64 2c 20 74 68 75 73 20 72 65 71 erhead, thus req
1e00: 75 69 72 69 6e 67 20 61 20 66 61 72 20 6c 6f 6e uiring a far lon
1e10: 67 65 72 20 74 69 6d 65 20 74 6f 20 61 63 68 69 ger time to achi
1e20: 65 76 65 20 61 62 73 6f 6c 75 74 65 6c 79 20 6e eve absolutely n
1e30: 6f 74 68 69 6e 67 2e 3c 2f 6c 69 3e 0d 0a 3c 6c othing.</li>..<l
1e40: 69 3e 3c 62 3e 53 68 6f 72 74 20 63 6f 6e 63 6c i><b>Short concl
1e50: 75 73 69 6f 6e 3c 2f 62 3e 3a 20 63 6f 6d 70 75 usion</b>: compu
1e60: 74 69 6e 67 20 6d 69 6c 6c 69 6f 6e 73 20 6f 66 ting millions of
1e70: 20 69 6e 74 65 72 73 65 63 74 69 6f 6e 73 20 62 intersections b
1e80: 65 74 77 65 65 6e 20 61 20 50 6f 69 6e 74 20 61 etween a Point a
1e90: 6e 64 20 61 20 50 6f 6c 79 67 6f 6e 2c 20 63 6f nd a Polygon, co
1ea0: 6e 74 61 69 6e 69 6e 67 20 68 75 6e 64 72 65 64 ntaining hundred
1eb0: 73 20 6f 66 20 74 68 6f 75 73 61 6e 64 73 20 6f s of thousands o
1ec0: 66 20 56 65 72 74 69 63 65 73 2c 20 69 73 20 61 f Vertices, is a
1ed0: 20 63 6f 6d 70 6c 65 78 20 63 6f 6d 70 75 74 61 complex computa
1ee0: 74 69 6f 6e 61 6c 20 70 72 6f 62 6c 65 6d 2e 3c tional problem.<
1ef0: 62 72 3e 20 0d 0a 52 65 71 75 69 72 69 6e 67 20 br> ..Requiring
1f00: 73 75 63 68 20 61 20 76 65 72 79 20 6c 6f 6e 67 such a very long
1f10: 20 74 69 6d 65 2c 20 6d 61 6b 65 73 20 73 75 63 time, makes suc
1f20: 68 20 61 20 73 6f 6c 75 74 69 6f 6e 20 61 62 73 h a solution abs
1f30: 6f 6c 75 74 65 6c 79 20 75 6e 70 72 61 63 74 69 olutely unpracti
1f40: 63 61 6c 2c 20 73 6f 20 61 20 6e 65 77 20 61 70 cal, so a new ap
1f50: 70 72 6f 63 68 20 74 6f 20 73 6f 6c 76 65 20 74 proch to solve t
1f60: 68 69 73 20 70 72 6f 62 6c 65 6d 20 69 73 20 6e his problem is n
1f70: 65 65 64 65 64 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 eeded.</li>..</u
1f80: 6c 3e 0d 0a 3c 68 33 3e 41 20 73 65 63 6f 6e 64 l>..<h3>A second
1f90: 20 61 74 74 65 6d 70 74 20 62 61 73 65 64 20 6f attempt based o
1fa0: 6e 20 53 54 5f 53 75 62 64 69 76 69 64 65 28 29 n ST_Subdivide()
1fb0: 20 61 6e 64 20 56 69 72 74 75 61 6c 45 6c 65 6d and VirtualElem
1fc0: 65 6e 74 61 72 79 3c 2f 68 33 3e 0d 0a 3c 76 65 entary</h3>..<ve
1fd0: 72 62 61 74 69 6d 3e 0d 0a 43 52 45 41 54 45 20 rbatim>..CREATE
1fe0: 54 41 42 4c 45 20 78 78 20 28 69 64 20 49 4e 54 TABLE xx (id INT
1ff0: 45 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59 EGER PRIMARY KEY
2000: 29 3b 0d 0a 53 45 4c 45 43 54 20 41 64 64 47 65 );..SELECT AddGe
2010: 6f 6d 65 74 72 79 43 6f 6c 75 6d 6e 28 27 78 78 ometryColumn('xx
2020: 27 2c 20 27 67 65 6f 6d 27 2c 20 33 30 30 33 2c ', 'geom', 3003,
2030: 20 27 4d 55 4c 54 49 50 4f 4c 59 47 4f 4e 27 2c 'MULTIPOLYGON',
2040: 20 27 58 59 27 29 3b 0d 0a 49 4e 53 45 52 54 20 'XY');..INSERT
2050: 49 4e 54 4f 20 78 78 20 56 41 4c 55 45 53 20 28 INTO xx VALUES (
2060: 31 2c 20 4e 55 4c 4c 29 3b 0d 0a 3c 2f 76 65 72 1, NULL);..</ver
2070: 62 61 74 69 6d 3e 0d 0a 57 65 27 6c 6c 20 73 74 batim>..We'll st
2080: 61 72 74 20 66 69 72 73 74 20 62 79 20 63 72 65 art first by cre
2090: 61 74 69 6e 67 20 61 20 63 6f 6e 76 65 6e 69 65 ating a convenie
20a0: 6e 63 65 20 54 61 62 6c 65 2c 20 77 68 69 63 68 nce Table, which
20b0: 20 77 69 6c 6c 20 73 74 6f 72 65 20 74 68 65 20 will store the
20c0: 72 65 73 75 6c 74 20 6f 66 20 53 54 5f 53 75 62 result of ST_Sub
20d0: 64 69 76 69 64 65 28 29 2e 3c 62 72 3e 0d 0a 54 divide().<br>..T
20e0: 68 69 73 20 69 73 20 61 20 76 65 72 79 20 73 69 his is a very si
20f0: 6d 70 6c 65 20 54 61 62 6c 65 3a 0d 0a 3c 75 6c mple Table:..<ul
2100: 3e 0d 0a 3c 6c 69 3e 69 74 20 68 61 73 20 6a 75 >..<li>it has ju
2110: 73 74 20 74 77 6f 20 63 6f 6c 75 6d 6e 73 2c 20 st two columns,
2120: 61 20 50 72 69 6d 61 72 79 20 4b 65 79 20 61 6e a Primary Key an
2130: 64 20 61 20 4d 75 6c 74 69 50 6f 6c 79 67 6f 6e d a MultiPolygon
2140: 20 47 65 6f 6d 65 74 72 79 2e 3c 2f 6c 69 3e 0d Geometry.</li>.
2150: 0a 3c 6c 69 3e 61 6e 64 20 77 69 6c 6c 20 73 74 .<li>and will st
2160: 6f 72 65 20 6f 6e 6c 79 20 61 20 73 69 6e 67 6c ore only a singl
2170: 65 20 72 6f 77 20 69 64 65 6e 74 69 66 69 65 64 e row identified
2180: 20 62 79 20 3c 62 3e 69 64 3d 31 3c 2f 62 3e 3c by <b>id=1</b><
2190: 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 0d 0a 3c 76 65 /li>..</ul>..<ve
21a0: 72 62 61 74 69 6d 3e 0d 0a 55 50 44 41 54 45 20 rbatim>..UPDATE
21b0: 78 78 20 53 45 54 20 67 65 6f 6d 20 3d 20 28 53 xx SET geom = (S
21c0: 45 4c 45 43 54 20 53 54 5f 53 75 62 64 69 76 69 ELECT ST_Subdivi
21d0: 64 65 28 67 65 6f 6d 65 74 72 79 2c 20 32 30 34 de(geometry, 204
21e0: 38 29 20 46 52 4f 4d 20 74 75 73 63 61 6e 79 29 8) FROM tuscany)
21f0: 20 57 48 45 52 45 20 69 64 20 3d 20 31 3b 0d 0a WHERE id = 1;..
2200: 53 45 4c 45 43 54 20 43 6f 75 6e 74 28 2a 29 0d SELECT Count(*).
2210: 0a 46 52 4f 4d 20 45 6c 65 6d 65 6e 74 61 72 79 .FROM Elementary
2220: 47 65 6f 6d 65 74 72 69 65 73 20 41 53 20 74 0d Geometries AS t.
2230: 0a 4a 4f 49 4e 20 63 69 76 69 63 69 20 41 53 20 .JOIN civici AS
2240: 63 20 4f 4e 20 28 53 54 5f 49 6e 74 65 72 73 65 c ON (ST_Interse
2250: 63 74 73 28 63 2e 67 65 6f 6d 65 74 72 79 2c 20 cts(c.geometry,
2260: 74 2e 67 65 6f 6d 65 74 72 79 29 20 3d 20 31 0d t.geometry) = 1.
2270: 0a 20 20 20 20 20 41 4e 44 20 63 2e 72 6f 77 69 . AND c.rowi
2280: 64 20 49 4e 20 28 0d 0a 20 20 20 20 20 20 20 20 d IN (..
2290: 20 53 45 4c 45 43 54 20 72 6f 77 69 64 20 46 52 SELECT rowid FR
22a0: 4f 4d 20 53 70 61 74 69 61 6c 49 6e 64 65 78 0d OM SpatialIndex.
22b0: 0a 20 20 20 20 20 20 20 20 20 57 48 45 52 45 20 . WHERE
22c0: 66 5f 74 61 62 6c 65 5f 6e 61 6d 65 20 3d 20 27 f_table_name = '
22d0: 63 69 76 69 63 69 27 20 41 4e 44 20 73 65 61 72 civici' AND sear
22e0: 63 68 5f 66 72 61 6d 65 20 3d 20 74 2e 67 65 6f ch_frame = t.geo
22f0: 6d 65 74 72 79 29 29 0d 0a 57 48 45 52 45 20 66 metry))..WHERE f
2300: 5f 74 61 62 6c 65 5f 6e 61 6d 65 20 3d 20 27 78 _table_name = 'x
2310: 78 27 20 41 4e 44 20 6f 72 69 67 69 6e 5f 72 6f x' AND origin_ro
2320: 77 69 64 20 3d 20 31 3b 0d 0a 2d 2d 2d 2d 2d 2d wid = 1;..------
2330: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0d 0a 31 34 38 30 ----------..1480
2340: 39 39 31 20 28 69 6e 20 33 38 2e 30 39 34 20 73 991 (in 38.094 s
2350: 65 63 6f 6e 64 73 29 0d 0a 0d 0a 0d 0a 55 50 44 econds)......UPD
2360: 41 54 45 20 78 78 20 53 45 54 20 67 65 6f 6d 20 ATE xx SET geom
2370: 3d 20 28 53 45 4c 45 43 54 20 53 54 5f 53 75 62 = (SELECT ST_Sub
2380: 64 69 76 69 64 65 28 67 65 6f 6d 65 74 72 79 2c divide(geometry,
2390: 20 35 31 32 29 20 46 52 4f 4d 20 74 75 73 63 61 512) FROM tusca
23a0: 6e 79 29 20 57 48 45 52 45 20 69 64 20 3d 20 31 ny) WHERE id = 1
23b0: 3b 0d 0a 53 45 4c 45 43 54 20 43 6f 75 6e 74 28 ;..SELECT Count(
23c0: 2a 29 0d 0a 46 52 4f 4d 20 45 6c 65 6d 65 6e 74 *)..FROM Element
23d0: 61 72 79 47 65 6f 6d 65 74 72 69 65 73 20 41 53 aryGeometries AS
23e0: 20 74 0d 0a 4a 4f 49 4e 20 63 69 76 69 63 69 20 t..JOIN civici
23f0: 41 53 20 63 20 4f 4e 20 28 53 54 5f 49 6e 74 65 AS c ON (ST_Inte
2400: 72 73 65 63 74 73 28 63 2e 67 65 6f 6d 65 74 72 rsects(c.geometr
2410: 79 2c 20 74 2e 67 65 6f 6d 65 74 72 79 29 20 3d y, t.geometry) =
2420: 20 31 0d 0a 20 20 20 20 20 41 4e 44 20 63 2e 72 1.. AND c.r
2430: 6f 77 69 64 20 49 4e 20 28 0d 0a 20 20 20 20 20 owid IN (..
2440: 20 20 20 20 53 45 4c 45 43 54 20 72 6f 77 69 64 SELECT rowid
2450: 20 46 52 4f 4d 20 53 70 61 74 69 61 6c 49 6e 64 FROM SpatialInd
2460: 65 78 0d 0a 20 20 20 20 20 20 20 20 20 57 48 45 ex.. WHE
2470: 52 45 20 66 5f 74 61 62 6c 65 5f 6e 61 6d 65 20 RE f_table_name
2480: 3d 20 27 63 69 76 69 63 69 27 20 41 4e 44 20 73 = 'civici' AND s
2490: 65 61 72 63 68 5f 66 72 61 6d 65 20 3d 20 74 2e earch_frame = t.
24a0: 67 65 6f 6d 65 74 72 79 29 29 0d 0a 57 48 45 52 geometry))..WHER
24b0: 45 20 66 5f 74 61 62 6c 65 5f 6e 61 6d 65 20 3d E f_table_name =
24c0: 20 27 78 78 27 20 41 4e 44 20 6f 72 69 67 69 6e 'xx' AND origin
24d0: 5f 72 6f 77 69 64 20 3d 20 31 3b 0d 0a 2d 2d 2d _rowid = 1;..---
24e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0d 0a 31 -------------..1
24f0: 34 38 30 39 39 31 20 28 69 6e 20 31 32 2e 36 31 480991 (in 12.61
2500: 37 20 73 65 63 6f 6e 64 73 29 0d 0a 0d 0a 0d 0a 7 seconds)......
2510: 55 50 44 41 54 45 20 78 78 20 53 45 54 20 67 65 UPDATE xx SET ge
2520: 6f 6d 20 3d 20 28 53 45 4c 45 43 54 20 53 54 5f om = (SELECT ST_
2530: 53 75 62 64 69 76 69 64 65 28 67 65 6f 6d 65 74 Subdivide(geomet
2540: 72 79 29 20 46 52 4f 4d 20 74 75 73 63 61 6e 79 ry) FROM tuscany
2550: 29 20 57 48 45 52 45 20 69 64 20 3d 20 31 3b 0d ) WHERE id = 1;.
2560: 0a 53 45 4c 45 43 54 20 43 6f 75 6e 74 28 2a 29 .SELECT Count(*)
2570: 0d 0a 46 52 4f 4d 20 45 6c 65 6d 65 6e 74 61 72 ..FROM Elementar
2580: 79 47 65 6f 6d 65 74 72 69 65 73 20 41 53 20 74 yGeometries AS t
2590: 0d 0a 4a 4f 49 4e 20 63 69 76 69 63 69 20 41 53 ..JOIN civici AS
25a0: 20 63 20 4f 4e 20 28 53 54 5f 49 6e 74 65 72 73 c ON (ST_Inters
25b0: 65 63 74 73 28 63 2e 67 65 6f 6d 65 74 72 79 2c ects(c.geometry,
25c0: 20 74 2e 67 65 6f 6d 65 74 72 79 29 20 3d 20 31 t.geometry) = 1
25d0: 0d 0a 20 20 20 20 20 41 4e 44 20 63 2e 72 6f 77 .. AND c.row
25e0: 69 64 20 49 4e 20 28 0d 0a 20 20 20 20 20 20 20 id IN (..
25f0: 20 20 53 45 4c 45 43 54 20 72 6f 77 69 64 20 46 SELECT rowid F
2600: 52 4f 4d 20 53 70 61 74 69 61 6c 49 6e 64 65 78 ROM SpatialIndex
2610: 0d 0a 20 20 20 20 20 20 20 20 20 57 48 45 52 45 .. WHERE
2620: 20 66 5f 74 61 62 6c 65 5f 6e 61 6d 65 20 3d 20 f_table_name =
2630: 27 63 69 76 69 63 69 27 20 41 4e 44 20 73 65 61 'civici' AND sea
2640: 72 63 68 5f 66 72 61 6d 65 20 3d 20 74 2e 67 65 rch_frame = t.ge
2650: 6f 6d 65 74 72 79 29 29 0d 0a 57 48 45 52 45 20 ometry))..WHERE
2660: 66 5f 74 61 62 6c 65 5f 6e 61 6d 65 20 3d 20 27 f_table_name = '
2670: 78 78 27 20 41 4e 44 20 6f 72 69 67 69 6e 5f 72 xx' AND origin_r
2680: 6f 77 69 64 20 3d 20 31 3b 0d 0a 2d 2d 2d 2d 2d owid = 1;..-----
2690: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0d 0a 31 34 38 -----------..148
26a0: 30 39 39 31 20 28 69 6e 20 39 2e 35 33 34 20 73 0991 (in 9.534 s
26b0: 65 63 6f 6e 64 73 29 0d 0a 3c 2f 76 65 72 62 61 econds)..</verba
26c0: 74 69 6d 3e 0d 0a 3c 62 3e 51 75 69 63 6b 20 65 tim>..<b>Quick e
26d0: 76 61 6c 75 61 74 69 6f 6e 3c 2f 62 3e 3a 0d 0a valuation</b>:..
26e0: 3c 75 6c 3e 0d 0a 3c 6c 69 3e 3c 62 3e 53 54 5f <ul>..<li><b>ST_
26f0: 53 75 62 64 69 76 69 64 65 3c 2f 62 3e 20 64 65 Subdivide</b> de
2700: 66 69 6e 69 74 65 6c 79 20 69 73 20 74 68 65 20 finitely is the
2710: 3c 62 3e 3c 69 3e 74 6f 6f 6c 20 6f 66 20 74 68 <b><i>tool of th
2720: 65 20 74 72 61 64 65 3c 2f 69 3e 3c 2f 62 3e 20 e trade</i></b>
2730: 77 65 20 77 65 72 65 20 73 65 61 72 63 68 69 6e we were searchin
2740: 67 20 66 6f 72 2e 3c 62 72 3e 0d 0a 49 74 20 65 g for.<br>..It e
2750: 66 66 65 63 74 69 76 65 6c 79 20 61 6c 6c 6f 77 ffectively allow
2760: 73 20 74 6f 20 72 65 73 6f 6c 76 65 20 61 20 63 s to resolve a c
2770: 6f 6d 70 75 74 61 74 69 6f 6e 61 6c 6c 79 20 63 omputationally c
2780: 6f 6d 70 6c 65 78 20 70 72 6f 62 6c 65 6d 20 69 omplex problem i
2790: 6e 20 61 20 73 75 72 70 72 69 73 69 6e 67 6c 79 n a surprisingly
27a0: 20 71 75 69 63 6b 20 74 69 6d 65 2e 3c 62 72 3e quick time.<br>
27b0: 0d 0a 46 72 6f 6d 20 6d 61 6e 79 20 6c 6f 6e 67 ..From many long
27c0: 20 68 6f 75 72 73 2c 20 74 6f 20 6a 75 73 74 20 hours, to just
27d0: 61 20 68 61 6e 64 66 75 6c 20 6f 66 20 73 65 63 a handful of sec
27e0: 6f 6e 64 73 2c 20 69 73 20 61 20 73 69 6e 67 75 onds, is a singu
27f0: 6c 61 72 6c 79 20 61 73 74 6f 6e 69 73 68 69 6e larly astonishin
2800: 67 20 69 6d 70 72 6f 76 65 6d 65 6e 74 2e 3c 62 g improvement.<b
2810: 72 3e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 73 75 62 r></li>..<li>sub
2820: 64 69 76 69 64 69 6e 67 20 74 68 65 20 69 6e 69 dividing the ini
2830: 74 69 61 6c 20 68 75 67 65 20 50 6f 6c 79 67 6f tial huge Polygo
2840: 6e 20 69 6e 74 6f 20 6d 61 6e 79 20 73 69 6d 70 n into many simp
2850: 6c 65 72 2f 73 6d 61 6c 6c 65 72 20 70 61 72 74 ler/smaller part
2860: 73 20 68 61 73 20 73 65 76 65 72 61 6c 20 62 65 s has several be
2870: 6e 65 66 69 63 69 61 6c 20 65 66 66 65 63 74 73 neficial effects
2880: 3a 0d 0a 3c 75 6c 3e 0d 0a 3c 6c 69 3e 74 68 65 :..<ul>..<li>the
2890: 20 74 69 6d 65 20 72 65 71 75 69 72 65 64 20 74 time required t
28a0: 6f 20 63 6f 6d 70 75 74 65 20 61 20 70 6f 69 6e o compute a poin
28b0: 74 2d 74 6f 2d 70 6f 6c 79 67 6f 6e 20 69 6e 74 t-to-polygon int
28c0: 65 72 73 65 63 74 69 6f 6e 20 71 75 69 63 6b 6c ersection quickl
28d0: 79 20 69 6e 63 72 65 61 73 65 73 20 77 69 74 68 y increases with
28e0: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 56 the number of V
28f0: 65 72 74 69 63 65 73 2e 3c 62 72 3e 0d 0a 53 6d ertices.<br>..Sm
2900: 61 6c 6c 65 72 20 70 6f 6c 79 67 6f 6e 73 20 61 aller polygons a
2910: 72 65 20 6f 62 76 69 6f 75 73 6c 79 20 73 77 69 re obviously swi
2920: 66 74 65 72 20 74 6f 20 62 65 20 65 76 61 6c 75 fter to be evalu
2930: 61 74 65 64 20 74 68 61 6e 20 62 69 67 67 65 72 ated than bigger
2940: 20 6f 6e 65 73 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 ones.</li>..<li
2950: 3e 73 6d 61 6c 6c 65 72 20 70 6f 6c 79 67 6f 6e >smaller polygon
2960: 73 20 63 61 6e 20 62 65 20 61 6e 20 65 66 66 69 s can be an effi
2970: 63 69 65 6e 74 20 53 70 61 74 69 61 6c 20 49 6e cient Spatial In
2980: 64 65 78 20 66 69 6c 74 65 72 2e 3c 2f 6c 69 3e dex filter.</li>
2990: 0d 0a 3c 2f 75 6c 3e 3c 2f 6c 69 3e 0d 0a 3c 6c ..</ul></li>..<l
29a0: 69 3e 75 73 69 6e 67 20 3c 62 3e 56 69 72 74 75 i>using <b>Virtu
29b0: 61 6c 45 6c 65 6d 65 6e 74 61 72 79 3c 2f 62 3e alElementary</b>
29c0: 2c 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 70 72 , in order to pr
29d0: 6f 63 65 73 73 20 61 6c 6c 20 73 75 62 2d 61 72 ocess all sub-ar
29e0: 65 61 73 20 6f 6e 65 20 62 79 20 6f 6e 65 2c 20 eas one by one,
29f0: 73 75 72 65 6c 79 20 69 6d 70 6f 73 65 73 20 66 surely imposes f
2a00: 75 72 74 68 65 72 20 63 6f 6d 70 6c 65 78 69 74 urther complexit
2a10: 79 20 74 6f 20 6f 75 72 20 53 51 4c 20 71 75 65 y to our SQL que
2a20: 72 69 65 73 2e 3c 62 72 3e 0d 0a 42 75 74 20 69 ries.<br>..But i
2a30: 6e 20 74 68 65 20 65 6e 64 2c 20 74 68 69 73 20 n the end, this
2a40: 6d 65 74 68 6f 64 20 70 72 6f 76 65 73 20 69 74 method proves it
2a50: 73 65 6c 66 20 74 6f 20 62 65 20 61 20 76 65 72 self to be a ver
2a60: 79 20 65 66 66 69 63 69 65 6e 74 20 6d 65 63 68 y efficient mech
2a70: 61 6e 69 73 6d 20 74 6f 20 72 65 73 6f 6c 76 65 anism to resolve
2a80: 20 74 68 69 73 20 63 6f 6d 70 6c 65 78 20 70 72 this complex pr
2a90: 6f 62 6c 65 6d 2e 3c 2f 6c 69 3e 0d 0a 3c 6c 69 oblem.</li>..<li
2aa0: 3e 3c 62 3e 4e 6f 74 65 3c 2f 62 3e 3a 20 53 70 ><b>Note</b>: Sp
2ab0: 61 74 69 61 4c 69 74 65 20 69 73 20 6e 6f 74 20 atiaLite is not
2ac0: 50 6f 73 74 47 49 53 2c 20 61 6e 64 20 53 51 4c PostGIS, and SQL
2ad0: 69 74 65 33 20 69 73 20 6e 6f 74 20 50 6f 73 74 ite3 is not Post
2ae0: 67 72 65 53 51 4c 3b 20 74 68 65 69 72 20 72 65 greSQL; their re
2af0: 73 70 65 63 74 69 76 65 20 69 6e 74 65 72 6e 61 spective interna
2b00: 6c 20 61 72 63 68 69 74 65 63 74 75 72 65 73 20 l architectures
2b10: 73 69 67 6e 69 66 69 63 61 6e 74 6c 79 20 64 69 significantly di
2b20: 66 66 65 72 20 69 6e 20 6d 61 6e 79 20 77 61 79 ffer in many way
2b30: 73 2e 3c 62 72 3e 0d 0a 4d 6f 72 65 20 73 70 65 s.<br>..More spe
2b40: 63 69 66 69 63 61 6c 6c 79 2c 20 53 51 4c 69 74 cifically, SQLit
2b50: 65 20 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 20 e is completely
2b60: 75 6e 61 62 6c 65 20 74 6f 20 73 75 70 70 6f 72 unable to suppor
2b70: 74 20 61 72 72 61 79 73 20 6f 72 20 6d 75 6c 74 t arrays or mult
2b80: 69 2d 72 6f 77 20 72 65 73 75 6c 74 73 2c 20 73 i-row results, s
2b90: 6f 20 75 73 69 6e 67 20 56 69 72 74 75 61 6c 45 o using VirtualE
2ba0: 6c 65 6d 65 6e 74 61 72 79 20 69 73 20 61 6e 20 lementary is an
2bb0: 61 62 73 6f 6c 75 74 65 6c 79 20 6e 65 63 65 73 absolutely neces
2bc0: 73 61 72 79 20 77 6f 72 6b 61 72 6f 75 6e 64 2e sary workaround.
2bd0: 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 0d 0a 3c 68 </li>..</ul>..<h
2be0: 33 3e 41 20 66 69 6e 61 6c 20 65 78 70 65 72 69 3>A final experi
2bf0: 6d 65 6e 74 61 6c 20 61 74 74 65 6d 70 74 20 62 mental attempt b
2c00: 61 73 65 64 20 6f 6e 20 61 20 70 75 72 65 20 53 ased on a pure S
2c10: 51 4c 20 61 70 70 72 6f 61 63 68 3c 2f 68 33 3e QL approach</h3>
2c20: 0d 0a 41 6e 6f 74 68 65 72 20 61 6c 74 65 72 6e ..Another altern
2c30: 61 74 69 76 65 20 6d 65 63 68 61 6e 69 73 6d 2c ative mechanism,
2c40: 20 62 61 73 65 64 20 6f 6e 20 70 75 72 65 20 53 based on pure S
2c50: 51 4c 20 61 6e 64 20 6e 6f 74 20 72 65 71 75 69 QL and not requi
2c60: 72 69 6e 67 20 74 68 65 20 75 73 65 20 6f 66 20 ring the use of
2c70: 45 6c 65 6d 65 6e 74 61 72 79 47 65 6f 6d 65 74 ElementaryGeomet
2c80: 72 69 65 73 20 6f 72 20 6f 66 20 61 20 63 6f 6e ries or of a con
2c90: 76 65 6e 69 65 6e 63 65 20 54 61 62 6c 65 20 69 venience Table i
2ca0: 73 3a 0d 0a 3c 76 65 72 62 61 74 69 6d 3e 0d 0a s:..<verbatim>..
2cb0: 57 49 54 48 20 52 45 43 55 52 53 49 56 45 20 6d WITH RECURSIVE m
2cc0: 61 67 69 63 28 6e 2c 20 67 65 6f 6d 29 20 41 53 agic(n, geom) AS
2cd0: 20 28 0d 0a 20 20 20 20 56 41 4c 55 45 53 28 31 (.. VALUES(1
2ce0: 2c 20 28 53 45 4c 45 43 54 20 53 54 5f 53 75 62 , (SELECT ST_Sub
2cf0: 64 69 76 69 64 65 28 67 65 6f 6d 65 74 72 79 2c divide(geometry,
2d00: 20 32 30 34 38 29 20 46 52 4f 4d 20 74 75 73 63 2048) FROM tusc
2d10: 61 6e 79 29 29 0d 0a 20 20 20 20 55 4e 49 4f 4e any)).. UNION
2d20: 20 41 4c 4c 0d 0a 20 20 20 20 53 45 4c 45 43 54 ALL.. SELECT
2d30: 20 6e 20 2b 20 31 2c 20 67 65 6f 6d 0d 0a 20 20 n + 1, geom..
2d40: 20 20 46 52 4f 4d 20 67 65 6f 6d 5f 69 6e 64 0d FROM geom_ind.
2d50: 0a 20 20 20 20 57 48 45 52 45 20 53 54 5f 47 65 . WHERE ST_Ge
2d60: 6f 6d 65 74 72 79 4e 28 67 65 6f 6d 2c 20 6e 29 ometryN(geom, n)
2d70: 20 49 53 20 4e 4f 54 20 4e 55 4c 4c 0d 0a 29 0d IS NOT NULL..).
2d80: 0a 53 45 4c 45 43 54 20 6e 2c 20 53 54 5f 47 65 .SELECT n, ST_Ge
2d90: 6f 6d 65 74 72 79 4e 28 67 65 6f 6d 2c 20 6e 29 ometryN(geom, n)
2da0: 20 46 52 4f 4d 20 6d 61 67 69 63 3b 0d 0a 3c 2f FROM magic;..</
2db0: 76 65 72 62 61 74 69 6d 3e 0d 0a 3c 75 6c 3e 0d verbatim>..<ul>.
2dc0: 0a 3c 6c 69 3e 77 65 20 73 69 6d 70 6c 79 20 68 .<li>we simply h
2dd0: 61 76 65 20 74 6f 20 77 72 69 74 65 20 61 20 3c ave to write a <
2de0: 62 3e 52 65 63 75 72 73 69 76 65 20 53 51 4c 20 b>Recursive SQL
2df0: 51 75 65 72 79 3c 2f 62 3e 20 69 6e 20 6f 72 64 Query</b> in ord
2e00: 65 72 20 74 6f 20 67 65 74 20 61 20 6d 75 6c 74 er to get a mult
2e10: 69 2d 72 6f 77 20 72 65 73 75 6c 74 73 65 74 2c i-row resultset,
2e20: 20 77 69 74 68 20 61 20 64 69 73 74 69 6e 63 74 with a distinct
2e30: 20 72 6f 77 20 66 6f 72 20 65 61 63 68 20 65 6c row for each el
2e40: 65 6d 65 6e 74 61 72 79 20 70 61 72 74 2e 3c 2f ementary part.</
2e50: 6c 69 3e 0d 0a 3c 6c 69 3e 69 74 20 65 66 66 65 li>..<li>it effe
2e60: 63 74 69 76 65 6c 79 20 77 6f 72 6b 73 2c 20 62 ctively works, b
2e70: 75 74 20 73 65 65 6d 73 20 74 6f 20 62 65 20 73 ut seems to be s
2e80: 6c 6f 77 65 72 20 74 68 61 6e 20 45 6c 65 6d 65 lower than Eleme
2e90: 6e 74 61 72 79 47 65 6f 6d 65 74 72 69 65 73 2e ntaryGeometries.
2ea0: 3c 2f 6c 69 3e 0d 0a 3c 6c 69 3e 61 6e 64 20 65 </li>..<li>and e
2eb0: 76 65 6e 20 6d 6f 72 65 20 72 65 6c 65 76 61 6e ven more relevan
2ec0: 74 2c 20 49 20 77 61 73 20 75 6e 61 62 6c 65 20 t, I was unable
2ed0: 74 6f 20 77 72 69 74 65 20 61 20 63 6f 6d 70 6c to write a compl
2ee0: 65 74 65 20 51 75 65 72 79 20 64 65 74 65 72 6d ete Query determ
2ef0: 69 6e 69 6e 67 20 61 6c 6c 20 69 6e 74 65 72 73 ining all inters
2f00: 65 63 74 69 6f 6e 73 20 62 65 74 77 65 65 6e 20 ections between
2f10: 50 6f 69 6e 74 73 20 61 6e 64 20 50 6f 6c 79 67 Points and Polyg
2f20: 6f 6e 73 20 69 6e 20 61 20 72 65 61 73 6f 6e 61 ons in a reasona
2f30: 62 6c 65 20 74 69 6d 65 2e 3c 62 72 3e 0d 0a 49 ble time.<br>..I
2f40: 20 73 75 73 70 65 63 74 20 74 68 61 74 20 74 68 suspect that th
2f50: 65 20 51 75 65 72 79 20 4f 70 74 69 6d 69 7a 65 e Query Optimize
2f60: 72 20 6f 66 20 53 51 4c 69 74 65 20 73 69 6d 70 r of SQLite simp
2f70: 6c 79 20 69 67 6e 6f 72 65 73 20 74 68 65 20 53 ly ignores the S
2f80: 70 61 74 69 61 6c 20 49 6e 64 65 78 2c 20 74 68 patial Index, th
2f90: 75 73 20 72 75 69 6e 69 6e 67 20 61 6e 79 20 61 us ruining any a
2fa0: 64 76 61 6e 74 61 67 65 20 74 68 61 74 20 74 68 dvantage that th
2fb0: 69 73 20 61 70 70 72 6f 61 63 68 20 77 6f 75 6c is approach woul
2fc0: 64 20 62 72 69 6e 67 2e 3c 62 72 3e 0d 0a 49 74 d bring.<br>..It
2fd0: 20 6d 61 79 20 77 65 6c 6c 20 62 65 2c 20 74 68 may well be, th
2fe0: 61 74 20 73 6f 6d 65 6f 6e 65 20 65 6c 73 65 20 at someone else
2ff0: 63 6f 75 6c 64 20 73 75 63 63 65 65 64 20 77 68 could succeed wh
3000: 65 72 65 20 49 20 66 61 69 6c 65 64 3b 20 61 6e ere I failed; an
3010: 79 20 66 75 72 74 68 65 72 20 74 68 69 72 64 2d y further third-
3020: 70 61 72 74 79 20 69 6e 76 65 73 74 69 67 61 74 party investigat
3030: 69 6f 6e 20 6f 6e 20 74 68 69 73 20 73 70 65 63 ion on this spec
3040: 69 66 69 63 20 61 72 65 61 20 77 6f 75 6c 64 20 ific area would
3050: 62 65 20 73 75 72 65 6c 79 20 77 65 6c 63 6f 6d be surely welcom
3060: 65 2e 3c 2f 6c 69 3e 0d 0a 3c 2f 75 6c 3e 0d 0a e.</li>..</ul>..
3070: 3c 62 72 3e 3c 62 72 3e 0d 0a 3c 68 72 3e 0d 0a <br><br>..<hr>..
3080: 3c 62 72 3e 3c 62 72 3e 0d 0a 3c 74 61 62 6c 65 <br><br>..<table
3090: 20 77 69 64 74 68 3d 22 31 30 30 25 22 3e 3c 74 width="100%"><t
30a0: 72 3e 0d 0a 3c 74 64 20 77 69 64 74 68 3d 22 33 r>..<td width="3
30b0: 33 25 22 20 61 6c 69 67 6e 3d 22 6c 65 66 74 22 3%" align="left"
30c0: 3e 3c 2f 74 64 3e 0d 0a 3c 74 64 20 61 6c 69 67 ></td>..<td alig
30d0: 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 61 20 68 72 n="center"><a hr
30e0: 65 66 3d 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e ef="https://www.
30f0: 67 61 69 61 2d 67 69 73 2e 69 74 2f 66 6f 73 73 gaia-gis.it/foss
3100: 69 6c 2f 6c 69 62 73 70 61 74 69 61 6c 69 74 65 il/libspatialite
3110: 2f 77 69 6b 69 3f 6e 61 6d 65 3d 34 2e 33 2e 30 /wiki?name=4.3.0
3120: 2b 64 6f 63 22 3e 62 61 63 6b 20 74 6f 20 69 6e +doc">back to in
3130: 64 65 78 3c 2f 61 3e 3c 2f 74 64 3e 0d 0a 3c 74 dex</a></td>..<t
3140: 64 20 77 69 64 74 68 3d 22 33 33 25 22 20 61 6c d width="33%" al
3150: 69 67 6e 3d 22 72 69 67 68 74 22 3e 3c 2f 74 64 ign="right"></td
3160: 3e 0d 0a 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e >..</tr></table>
3170: 0a 5a 20 63 33 39 36 34 39 30 34 61 65 37 33 62 .Z c3964904ae73b
3180: 32 34 36 36 30 62 35 65 35 33 33 62 65 36 35 39 24660b5e533be659
3190: 38 39 65 0a 89e.