Documentation Source Text

Hex Artifact Content
Login

Artifact 68128d8945dd0db83a01f458b9f877d90011a34e6114dbfa2a89cbdf175ee562:


0000: 3c 74 69 74 6c 65 3e 54 68 65 20 47 65 6f 70 6f  <title>The Geopo
0010: 6c 79 20 49 6e 74 65 72 66 61 63 65 20 54 6f 20  ly Interface To 
0020: 54 68 65 20 53 51 4c 69 74 65 20 52 2a 54 72 65  The SQLite R*Tre
0030: 65 20 4d 6f 64 75 6c 65 3c 2f 74 69 74 6c 65 3e  e Module</title>
0040: 0a 3c 74 63 6c 3e 68 64 5f 6b 65 79 77 6f 72 64  .<tcl>hd_keyword
0050: 73 20 7b 67 65 6f 70 6f 6c 79 7d 20 7b 47 65 6f  s {geopoly} {Geo
0060: 70 6f 6c 79 20 6d 6f 64 75 6c 65 7d 20 7b 47 65  poly module} {Ge
0070: 6f 70 6f 6c 79 20 65 78 74 65 6e 73 69 6f 6e 7d  opoly extension}
0080: 3c 2f 74 63 6c 3e 0a 3c 74 61 62 6c 65 5f 6f 66  </tcl>.<table_of
0090: 5f 63 6f 6e 74 65 6e 74 73 3e 0a 0a 3c 68 31 3e  _contents>..<h1>
00a0: 4f 76 65 72 76 69 65 77 3c 2f 68 31 3e 0a 0a 3c  Overview</h1>..<
00b0: 70 3e 0a 54 68 65 20 47 65 6f 70 6f 6c 79 20 6d  p>.The Geopoly m
00c0: 6f 64 75 6c 65 20 69 73 20 61 6e 20 61 6c 74 65  odule is an alte
00d0: 72 6e 61 74 69 76 65 20 69 6e 74 65 72 66 61 63  rnative interfac
00e0: 65 20 74 6f 20 74 68 65 20 5b 52 2d 54 72 65 65  e to the [R-Tree
00f0: 20 65 78 74 65 6e 73 69 6f 6e 5d 20 74 68 61 74   extension] that
0100: 20 75 73 65 73 0a 74 68 65 20 5b 68 74 74 70 3a   uses.the [http:
0110: 2f 2f 67 65 6f 6a 73 6f 6e 2e 6f 72 67 20 7c 20  //geojson.org | 
0120: 47 65 6f 4a 53 4f 4e 5d 20 6e 6f 74 61 74 69 6f  GeoJSON] notatio
0130: 6e 0a 28 5b 68 74 74 70 73 3a 2f 2f 74 6f 6f 6c  n.([https://tool
0140: 73 2e 69 65 74 66 2e 6f 72 67 2f 68 74 6d 6c 2f  s.ietf.org/html/
0150: 72 66 63 37 39 34 36 20 7c 20 52 46 43 2d 37 39  rfc7946 | RFC-79
0160: 34 36 5d 29 20 74 6f 20 64 65 73 63 72 69 62 65  46]) to describe
0170: 20 74 77 6f 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c   two-dimensional
0180: 0a 70 6f 6c 79 67 6f 6e 73 2e 20 20 47 65 6f 70  .polygons.  Geop
0190: 6f 6c 79 20 69 6e 63 6c 75 64 65 73 20 66 75 6e  oly includes fun
01a0: 63 74 69 6f 6e 73 20 66 6f 72 20 64 65 74 65 63  ctions for detec
01b0: 74 69 6e 67 20 77 68 65 6e 20 6f 6e 65 20 70 6f  ting when one po
01c0: 6c 79 67 6f 6e 20 69 73 0a 63 6f 6e 74 61 69 6e  lygon is.contain
01d0: 65 64 20 77 69 74 68 69 6e 20 6f 72 20 6f 76 65  ed within or ove
01e0: 72 6c 61 70 73 20 77 69 74 68 20 61 6e 6f 74 68  rlaps with anoth
01f0: 65 72 2c 20 66 6f 72 20 63 6f 6d 70 75 74 69 6e  er, for computin
0200: 67 20 74 68 65 0a 61 72 65 61 20 65 6e 63 6c 6f  g the.area enclo
0210: 73 65 64 20 62 79 20 61 20 70 6f 6c 79 67 6f 6e  sed by a polygon
0220: 2c 20 66 6f 72 20 64 6f 69 6e 67 20 6c 69 6e 65  , for doing line
0230: 61 72 20 74 72 61 6e 73 66 6f 72 6d 61 74 69 6f  ar transformatio
0240: 6e 73 20 6f 66 20 70 6f 6c 79 67 6f 6e 73 2c 0a  ns of polygons,.
0250: 66 6f 72 20 72 65 6e 64 65 72 69 6e 67 20 70 6f  for rendering po
0260: 6c 79 67 6f 6e 73 20 61 73 0a 5b 68 74 74 70 73  lygons as.[https
0270: 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e  ://en.wikipedia.
0280: 6f 72 67 2f 77 69 6b 69 2f 53 63 61 6c 61 62 6c  org/wiki/Scalabl
0290: 65 5f 56 65 63 74 6f 72 5f 47 72 61 70 68 69 63  e_Vector_Graphic
02a0: 73 20 7c 20 53 56 47 5d 2c 20 61 6e 64 20 6f 74  s | SVG], and ot
02b0: 68 65 72 0a 73 69 6d 69 6c 61 72 20 6f 70 65 72  her.similar oper
02c0: 61 74 69 6f 6e 73 2e 0a 0a 3c 70 3e 0a 54 68 65  ations...<p>.The
02d0: 20 73 6f 75 72 63 65 20 63 6f 64 65 20 66 6f 72   source code for
02e0: 20 47 65 6f 70 6f 6c 79 20 69 73 20 69 6e 63 6c   Geopoly is incl
02f0: 75 64 65 64 20 69 6e 20 74 68 65 20 5b 61 6d 61  uded in the [ama
0300: 6c 67 61 6d 61 74 69 6f 6e 5d 20 62 75 74 20 69  lgamation] but i
0310: 73 20 6e 6f 74 0a 69 6e 63 6c 75 64 65 64 20 69  s not.included i
0320: 6e 20 74 68 65 20 6c 69 62 72 61 72 79 20 75 6e  n the library un
0330: 6c 65 73 73 20 74 68 65 20 5b 2d 44 53 51 4c 49  less the [-DSQLI
0340: 54 45 5f 45 4e 41 42 4c 45 5f 47 45 4f 50 4f 4c  TE_ENABLE_GEOPOL
0350: 59 5d 20 63 6f 6d 70 69 6c 65 2d 74 69 6d 65 20  Y] compile-time 
0360: 6f 70 74 69 6f 6e 0a 69 73 20 75 73 65 64 2e 0a  option.is used..
0370: 0a 3c 70 3e 0a 47 65 6f 70 6f 6c 79 20 6f 70 65  .<p>.Geopoly ope
0380: 72 61 74 65 73 20 6f 6e 20 22 73 69 6d 70 6c 65  rates on "simple
0390: 22 20 70 6f 6c 79 67 6f 6e 73 20 2d 20 74 68 61  " polygons - tha
03a0: 74 20 69 73 2c 20 70 6f 6c 79 67 6f 6e 73 20 66  t is, polygons f
03b0: 6f 72 20 77 68 69 63 68 0a 74 68 65 20 62 6f 75  or which.the bou
03c0: 6e 64 61 72 79 20 64 6f 65 73 20 6e 6f 74 20 69  ndary does not i
03d0: 6e 74 65 72 73 65 63 74 20 69 74 73 65 6c 66 2e  ntersect itself.
03e0: 20 20 47 65 6f 70 6f 6c 79 20 74 68 75 73 20 65    Geopoly thus e
03f0: 78 74 65 6e 64 73 20 74 68 65 20 63 61 70 61 62  xtends the capab
0400: 69 6c 69 74 69 65 73 0a 6f 66 20 74 68 65 20 5b  ilities.of the [
0410: 52 2d 54 72 65 65 20 65 78 74 65 6e 73 69 6f 6e  R-Tree extension
0420: 5d 20 77 68 69 63 68 20 63 61 6e 20 6f 6e 6c 79  ] which can only
0430: 20 64 65 61 6c 20 77 69 74 68 20 72 65 63 74 61   deal with recta
0440: 6e 67 75 6c 61 72 20 61 72 65 61 73 2e 0a 4f 6e  ngular areas..On
0450: 20 74 68 65 20 6f 74 68 65 72 20 68 61 6e 64 2c   the other hand,
0460: 20 74 68 65 20 5b 52 2d 54 72 65 65 20 65 78 74   the [R-Tree ext
0470: 65 6e 73 69 6f 6e 5d 20 69 73 0a 61 62 6c 65 20  ension] is.able 
0480: 74 6f 20 68 61 6e 64 6c 65 20 62 65 74 77 65 65  to handle betwee
0490: 6e 20 31 20 61 6e 64 20 35 20 63 6f 6f 72 64 69  n 1 and 5 coordi
04a0: 6e 61 74 65 20 64 69 6d 65 6e 73 69 6f 6e 73 2c  nate dimensions,
04b0: 20 77 68 65 72 65 61 73 20 47 65 6f 70 6f 6c 79   whereas Geopoly
04c0: 20 69 73 20 72 65 73 74 72 69 63 74 65 64 0a 74   is restricted.t
04d0: 6f 20 32 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20  o 2-dimensional 
04e0: 73 68 61 70 65 73 20 6f 6e 6c 79 2e 0a 0a 3c 70  shapes only...<p
04f0: 3e 0a 45 61 63 68 20 70 6f 6c 79 67 6f 6e 20 69  >.Each polygon i
0500: 6e 20 74 68 65 20 47 65 6f 70 6f 6c 79 20 6d 6f  n the Geopoly mo
0510: 64 75 6c 65 20 63 61 6e 20 62 65 20 61 73 73 6f  dule can be asso
0520: 63 69 61 74 65 64 20 77 69 74 68 20 61 6e 20 61  ciated with an a
0530: 72 62 69 74 72 61 72 79 0a 6e 75 6d 62 65 72 20  rbitrary.number 
0540: 6f 66 20 61 75 78 69 6c 69 61 72 79 20 64 61 74  of auxiliary dat
0550: 61 20 66 69 65 6c 64 73 2e 0a 0a 3c 68 32 3e 47  a fields...<h2>G
0560: 65 6f 4a 53 4f 4e 3c 2f 68 32 3e 0a 0a 3c 70 3e  eoJSON</h2>..<p>
0570: 54 68 65 20 5b 68 74 74 70 73 3a 2f 2f 74 6f 6f  The [https://too
0580: 6c 73 2e 69 65 74 66 2e 6f 72 67 2f 68 74 6d 6c  ls.ietf.org/html
0590: 2f 72 66 63 37 39 34 36 7c 20 47 65 6f 4a 53 4f  /rfc7946| GeoJSO
05a0: 4e 20 73 74 61 6e 64 61 72 64 5d 20 69 73 20 73  N standard] is s
05b0: 79 6e 74 61 78 20 66 6f 72 0a 65 78 63 68 61 6e  yntax for.exchan
05c0: 67 69 6e 67 20 67 65 6f 73 70 61 74 69 61 6c 20  ging geospatial 
05d0: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 75 73 69 6e  information usin
05e0: 67 20 4a 53 4f 4e 2e 20 20 47 65 6f 4a 53 4f 4e  g JSON.  GeoJSON
05f0: 20 69 73 20 61 20 72 69 63 68 20 73 74 61 6e 64   is a rich stand
0600: 61 72 64 0a 74 68 61 74 20 63 61 6e 20 64 65 73  ard.that can des
0610: 63 72 69 62 65 20 6e 65 61 72 6c 79 20 61 6e 79  cribe nearly any
0620: 20 6b 69 6e 64 20 6f 66 20 67 65 6f 73 70 61 74   kind of geospat
0630: 69 61 6c 20 63 6f 6e 74 65 6e 74 2e 0a 0a 3c 70  ial content...<p
0640: 3e 54 68 65 20 47 65 6f 70 6f 6c 79 20 6d 6f 64  >The Geopoly mod
0650: 75 6c 65 20 6f 6e 6c 79 20 75 6e 64 65 72 73 74  ule only underst
0660: 61 6e 64 73 0a 61 20 73 6d 61 6c 6c 20 73 75 62  ands.a small sub
0670: 73 65 74 20 6f 66 20 47 65 6f 4a 53 4f 4e 2c 20  set of GeoJSON, 
0680: 62 75 74 20 61 20 63 72 69 74 69 63 61 6c 20 73  but a critical s
0690: 75 62 73 65 74 2e 20 20 0a 49 6e 20 70 61 72 74  ubset.  .In part
06a0: 69 63 75 6c 61 72 2c 20 47 65 6f 4a 53 4f 4e 20  icular, GeoJSON 
06b0: 75 6e 64 65 72 73 74 61 6e 64 73 0a 74 68 65 20  understands.the 
06c0: 4a 53 4f 4e 20 61 72 72 61 79 20 6f 66 20 76 65  JSON array of ve
06d0: 72 74 65 78 65 73 20 74 68 61 74 20 64 65 73 63  rtexes that desc
06e0: 72 69 62 65 73 20 61 20 73 69 6d 70 6c 65 20 70  ribes a simple p
06f0: 6f 6c 79 67 6f 6e 2e 0a 0a 3c 70 3e 41 20 70 6f  olygon...<p>A po
0700: 6c 79 67 6f 6e 20 69 73 20 64 65 66 69 6e 65 64  lygon is defined
0710: 20 62 79 20 69 74 73 20 76 65 72 74 65 78 65 73   by its vertexes
0720: 2e 0a 45 61 63 68 20 76 65 72 74 65 78 20 69 73  ..Each vertex is
0730: 20 61 20 4a 53 4f 4e 20 61 72 72 61 79 20 6f 66   a JSON array of
0740: 20 74 77 6f 20 6e 75 6d 65 72 69 63 20 76 61 6c   two numeric val
0750: 75 65 73 20 77 68 69 63 68 20 61 72 65 20 74 68  ues which are th
0760: 65 0a 58 20 61 6e 64 20 59 20 63 6f 6f 72 64 69  e.X and Y coordi
0770: 6e 61 74 65 73 20 6f 66 20 74 68 65 20 76 65 72  nates of the ver
0780: 74 65 78 2e 0a 41 20 70 6f 6c 79 67 6f 6e 20 69  tex..A polygon i
0790: 73 20 61 20 4a 53 4f 4e 20 61 72 72 61 79 20 6f  s a JSON array o
07a0: 66 20 61 74 20 6c 65 61 73 74 20 66 6f 75 72 20  f at least four 
07b0: 6f 66 20 74 68 65 73 65 20 76 65 72 74 65 78 65  of these vertexe
07c0: 73 2c 20 0a 61 6e 64 20 68 65 6e 63 65 20 69 73  s, .and hence is
07d0: 20 61 6e 20 61 72 72 61 79 20 6f 66 20 61 72 72   an array of arr
07e0: 61 79 73 2e 0a 54 68 65 20 66 69 72 73 74 20 61  ays..The first a
07f0: 6e 64 20 6c 61 73 74 20 76 65 72 74 65 78 20 69  nd last vertex i
0800: 6e 20 74 68 65 20 61 72 72 61 79 20 6d 75 73 74  n the array must
0810: 20 62 65 20 74 68 65 20 73 61 6d 65 2e 0a 54 68   be the same..Th
0820: 65 20 70 6f 6c 79 67 6f 6e 20 66 6f 6c 6c 6f 77  e polygon follow
0830: 73 20 74 68 65 20 72 69 67 68 74 2d 68 61 6e 64  s the right-hand
0840: 20 72 75 6c 65 3a 20 20 57 68 65 6e 20 74 72 61   rule:  When tra
0850: 63 69 6e 67 20 61 20 6c 69 6e 65 20 66 72 6f 6d  cing a line from
0860: 0a 6f 6e 65 20 76 65 72 74 65 78 20 74 6f 20 74  .one vertex to t
0870: 68 65 20 6e 65 78 74 2c 20 74 68 65 20 61 72 65  he next, the are
0880: 61 20 74 6f 20 74 68 65 20 72 69 67 68 74 20 6f  a to the right o
0890: 66 20 74 68 65 20 6c 69 6e 65 20 69 73 20 6f 75  f the line is ou
08a0: 74 73 69 64 65 0a 6f 66 20 74 68 65 20 70 6f 6c  tside.of the pol
08b0: 79 67 6f 6e 20 61 6e 64 20 74 68 65 20 61 72 65  ygon and the are
08c0: 61 20 74 6f 20 74 68 65 20 6c 65 66 74 20 69 73  a to the left is
08d0: 20 69 6e 73 69 64 65 20 74 68 65 20 70 6f 6c 79   inside the poly
08e0: 67 6f 6e 2e 0a 49 6e 20 6f 74 68 65 72 20 77 6f  gon..In other wo
08f0: 72 64 73 2c 20 74 68 65 20 6e 65 74 20 72 6f 74  rds, the net rot
0900: 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 76 65 72  ation of the ver
0910: 74 65 78 65 73 20 69 73 20 63 6f 75 6e 74 65 72  texes is counter
0920: 2d 63 6c 6f 63 6b 77 69 73 65 2e 0a 0a 3c 70 3e  -clockwise...<p>
0930: 0a 46 6f 72 20 65 78 61 6d 70 6c 65 2c 20 74 68  .For example, th
0940: 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 4a 53 4f 4e  e following JSON
0950: 20 64 65 73 63 72 69 62 65 73 20 61 6e 20 69 73   describes an is
0960: 6f 73 63 65 6c 65 73 20 74 72 69 61 6e 67 6c 65  osceles triangle
0970: 2c 20 73 69 74 74 69 6e 67 0a 6f 6e 20 74 68 65  , sitting.on the
0980: 20 58 20 61 78 69 73 20 61 6e 64 20 77 69 74 68   X axis and with
0990: 20 61 6e 20 61 72 65 61 20 6f 66 20 30 2e 35 3a   an area of 0.5:
09a0: 0a 0a 3c 63 6f 64 65 62 6c 6f 63 6b 3e 0a 26 23  ..<codeblock>.&#
09b0: 39 31 3b 26 23 39 31 3b 30 2c 30 5d 2c 26 23 39  91;&#91;0,0],&#9
09c0: 31 3b 31 2c 30 5d 2c 26 23 39 31 3b 30 2e 35 2c  1;1,0],&#91;0.5,
09d0: 31 5d 2c 26 23 39 31 3b 30 2c 30 5d 5d 0a 3c 2f  1],&#91;0,0]].</
09e0: 63 6f 64 65 62 6c 6f 63 6b 3e 0a 0a 3c 70 3e 0a  codeblock>..<p>.
09f0: 41 20 74 72 69 61 6e 67 6c 65 20 68 61 73 20 74  A triangle has t
0a00: 68 72 65 65 20 76 65 72 74 65 78 65 73 2c 20 62  hree vertexes, b
0a10: 75 74 20 74 68 65 20 47 65 6f 4a 53 4f 4e 20 64  ut the GeoJSON d
0a20: 65 73 63 72 69 70 74 69 6f 6e 20 6f 66 20 74 68  escription of th
0a30: 65 20 74 72 69 61 6e 67 6c 65 0a 68 61 73 20 34  e triangle.has 4
0a40: 20 76 65 72 74 65 78 65 73 20 62 65 63 61 75 73   vertexes becaus
0a50: 65 20 74 68 65 20 66 69 72 73 74 20 61 6e 64 20  e the first and 
0a60: 6c 61 73 74 20 76 65 72 74 65 78 20 61 72 65 20  last vertex are 
0a70: 64 75 70 6c 69 63 61 74 65 73 2e 0a 0a 3c 68 32  duplicates...<h2
0a80: 3e 42 69 6e 61 72 79 20 73 74 6f 72 61 67 65 20  >Binary storage 
0a90: 66 6f 72 6d 61 74 3c 2f 68 32 3e 0a 0a 3c 70 3e  format</h2>..<p>
0aa0: 0a 49 6e 74 65 72 6e 61 6c 6c 79 2c 20 47 65 6f  .Internally, Geo
0ab0: 70 6f 6c 79 20 73 74 6f 72 65 73 20 70 6f 6c 79  poly stores poly
0ac0: 67 6f 6e 73 20 69 6e 20 61 20 62 69 6e 61 72 79  gons in a binary
0ad0: 20 66 6f 72 6d 61 74 20 2d 20 61 6e 20 53 51 4c   format - an SQL
0ae0: 20 42 4c 4f 42 2e 0a 44 65 74 61 69 6c 73 20 6f   BLOB..Details o
0af0: 66 20 74 68 65 20 62 69 6e 61 72 79 20 66 6f 72  f the binary for
0b00: 6d 61 74 20 61 72 65 20 67 69 76 65 6e 20 62 65  mat are given be
0b10: 6c 6f 77 2e 0a 41 6c 6c 20 6f 66 20 74 68 65 20  low..All of the 
0b20: 47 65 6f 70 6f 6c 79 20 69 6e 74 65 72 66 61 63  Geopoly interfac
0b30: 65 73 20 61 72 65 20 61 62 6c 65 20 74 6f 20 61  es are able to a
0b40: 63 63 65 70 74 20 70 6f 6c 79 67 6f 6e 73 20 69  ccept polygons i
0b50: 6e 20 65 69 74 68 65 72 20 74 68 65 0a 47 65 6f  n either the.Geo
0b60: 4a 53 4f 4e 20 66 6f 72 6d 61 74 20 6f 72 20 69  JSON format or i
0b70: 6e 20 74 68 65 20 62 69 6e 61 72 79 20 66 6f 72  n the binary for
0b80: 6d 61 74 2e 0a 0a 3c 68 31 3e 55 73 69 6e 67 20  mat...<h1>Using 
0b90: 54 68 65 20 47 65 6f 70 6f 6c 79 20 45 78 74 65  The Geopoly Exte
0ba0: 6e 73 69 6f 6e 3c 2f 68 31 3e 0a 0a 3c 70 3e 0a  nsion</h1>..<p>.
0bb0: 41 20 67 65 6f 70 6f 6c 79 20 74 61 62 6c 65 20  A geopoly table 
0bc0: 69 73 20 63 72 65 61 74 65 64 20 61 73 20 66 6f  is created as fo
0bd0: 6c 6c 6f 77 73 3a 0a 0a 3c 63 6f 64 65 62 6c 6f  llows:..<codeblo
0be0: 63 6b 3e 0a 43 52 45 41 54 45 20 56 49 52 54 55  ck>.CREATE VIRTU
0bf0: 41 4c 20 54 41 42 4c 45 20 6e 65 77 74 61 62 20  AL TABLE newtab 
0c00: 55 53 49 4e 47 20 67 65 6f 70 6f 6c 79 28 61 2c  USING geopoly(a,
0c10: 62 2c 63 29 3b 0a 3c 2f 63 6f 64 65 62 6c 6f 63  b,c);.</codebloc
0c20: 6b 3e 0a 0a 3c 70 3e 0a 54 68 65 20 73 74 61 74  k>..<p>.The stat
0c30: 65 6d 65 6e 74 20 61 62 6f 76 65 20 63 72 65 61  ement above crea
0c40: 74 65 73 20 61 20 6e 65 77 20 67 65 6f 70 6f 6c  tes a new geopol
0c50: 79 20 74 61 62 6c 65 20 6e 61 6d 65 64 20 22 6e  y table named "n
0c60: 65 77 74 61 62 22 2e 0a 45 76 65 72 79 20 67 65  ewtab"..Every ge
0c70: 6f 70 6f 6c 79 20 74 61 62 6c 65 20 63 6f 6e 74  opoly table cont
0c80: 61 69 6e 73 20 61 20 62 75 69 6c 74 2d 69 6e 20  ains a built-in 
0c90: 69 6e 74 65 67 65 72 20 22 72 6f 77 69 64 22 20  integer "rowid" 
0ca0: 63 6f 6c 75 6d 6e 0a 61 6e 64 20 61 20 22 5f 73  column.and a "_s
0cb0: 68 61 70 65 22 20 63 6f 6c 75 6d 6e 20 74 68 61  hape" column tha
0cc0: 74 20 63 6f 6e 74 61 69 6e 73 0a 74 68 65 20 70  t contains.the p
0cd0: 6f 6c 79 67 6f 6e 20 61 73 73 6f 63 69 61 74 65  olygon associate
0ce0: 64 20 77 69 74 68 20 74 68 61 74 20 72 6f 77 20  d with that row 
0cf0: 6f 66 20 74 68 65 20 74 61 62 6c 65 2e 0a 54 68  of the table..Th
0d00: 65 20 65 78 61 6d 70 6c 65 20 61 62 6f 76 65 20  e example above 
0d10: 61 6c 73 6f 20 64 65 66 69 6e 65 73 20 74 68 72  also defines thr
0d20: 65 65 20 61 75 78 69 6c 69 61 72 79 20 64 61 74  ee auxiliary dat
0d30: 61 20 63 6f 6c 75 6d 6e 73 20 0a 6e 61 6d 65 64  a columns .named
0d40: 20 22 61 22 2c 20 22 62 22 2c 20 61 6e 64 20 22   "a", "b", and "
0d50: 63 22 20 74 68 61 74 20 63 61 6e 20 73 74 6f 72  c" that can stor
0d60: 65 20 77 68 61 74 65 76 65 72 20 61 64 64 69 74  e whatever addit
0d70: 69 6f 6e 61 6c 0a 69 6e 66 6f 72 6d 61 74 69 6f  ional.informatio
0d80: 6e 20 74 68 65 20 61 70 70 6c 69 63 61 74 69 6f  n the applicatio
0d90: 6e 20 6e 65 65 64 73 20 74 6f 20 61 73 73 6f 63  n needs to assoc
0da0: 69 61 74 65 0a 77 69 74 68 20 65 61 63 68 20 70  iate.with each p
0db0: 6f 6c 79 67 6f 6e 2e 20 20 49 66 20 74 68 65 72  olygon.  If ther
0dc0: 65 20 69 73 20 6e 6f 20 6e 65 65 64 20 74 6f 20  e is no need to 
0dd0: 73 74 6f 72 65 20 61 75 78 69 6c 69 61 72 79 0a  store auxiliary.
0de0: 69 6e 66 6f 72 6d 61 74 69 6f 6e 2c 20 74 68 65  information, the
0df0: 20 6c 69 73 74 20 6f 66 20 61 75 78 69 6c 69 61   list of auxilia
0e00: 72 79 20 63 6f 6c 75 6d 6e 73 20 63 61 6e 20 62  ry columns can b
0e10: 65 20 6f 6d 69 74 74 65 64 2e 0a 0a 3c 70 3e 0a  e omitted...<p>.
0e20: 53 74 6f 72 65 20 6e 65 77 20 70 6f 6c 79 67 6f  Store new polygo
0e30: 6e 73 20 69 6e 20 74 68 65 20 74 61 62 6c 65 20  ns in the table 
0e40: 75 73 69 6e 67 20 6f 72 64 69 6e 61 72 79 20 49  using ordinary I
0e50: 4e 53 45 52 54 20 73 74 61 74 65 6d 65 6e 74 73  NSERT statements
0e60: 3a 0a 0a 3c 63 6f 64 65 62 6c 6f 63 6b 3e 0a 49  :..<codeblock>.I
0e70: 4e 53 45 52 54 20 49 4e 54 4f 20 6e 65 77 74 61  NSERT INTO newta
0e80: 62 28 5f 73 68 61 70 65 29 20 56 41 4c 55 45 53  b(_shape) VALUES
0e90: 28 27 26 23 39 31 3b 26 23 39 31 3b 30 2c 30 5d  ('&#91;&#91;0,0]
0ea0: 2c 26 23 39 31 3b 31 2c 30 5d 2c 26 23 39 31 3b  ,&#91;1,0],&#91;
0eb0: 30 2e 35 2c 31 5d 2c 26 23 39 31 3b 30 2c 30 5d  0.5,1],&#91;0,0]
0ec0: 5d 27 29 3b 0a 3c 2f 63 6f 64 65 62 6c 6f 63 6b  ]');.</codeblock
0ed0: 3e 0a 0a 3c 70 3e 0a 55 50 44 41 54 45 20 61 6e  >..<p>.UPDATE an
0ee0: 64 20 44 45 4c 45 54 45 20 73 74 61 74 65 6d 65  d DELETE stateme
0ef0: 6e 74 73 20 77 6f 72 6b 20 73 69 6d 69 6c 61 72  nts work similar
0f00: 6c 79 2e 0a 0a 3c 68 32 3e 51 75 65 72 69 65 73  ly...<h2>Queries
0f10: 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 54 6f 20 71 75  </h2>..<p>.To qu
0f20: 65 72 79 20 74 68 65 20 67 65 6f 70 6f 6c 79 20  ery the geopoly 
0f30: 74 61 62 6c 65 20 75 73 69 6e 67 20 61 6e 20 69  table using an i
0f40: 6e 64 65 78 65 64 20 67 65 6f 73 70 61 74 69 61  ndexed geospatia
0f50: 6c 20 73 65 61 72 63 68 2c 20 0a 75 73 65 20 6f  l search, .use o
0f60: 6e 65 20 6f 66 20 74 68 65 20 66 75 6e 63 74 69  ne of the functi
0f70: 6f 6e 73 20 67 65 6f 70 6f 6c 79 5f 6f 76 65 72  ons geopoly_over
0f80: 6c 61 70 28 29 0a 6f 72 20 67 65 6f 70 6f 6c 79  lap().or geopoly
0f90: 5f 77 69 74 68 69 6e 28 29 20 61 73 20 61 20 62  _within() as a b
0fa0: 6f 6f 6c 65 61 6e 20 66 75 6e 63 74 69 6f 6e 20  oolean function 
0fb0: 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c 61  in the WHERE cla
0fc0: 75 73 65 2c 0a 77 69 74 68 20 74 68 65 20 22 5f  use,.with the "_
0fd0: 73 68 61 70 65 22 20 63 6f 6c 75 6d 6e 20 61 73  shape" column as
0fe0: 20 74 68 65 20 66 69 72 73 74 20 61 72 67 75 6d   the first argum
0ff0: 65 6e 74 20 74 6f 20 74 68 65 20 66 75 6e 63 74  ent to the funct
1000: 69 6f 6e 2e 0a 46 6f 72 20 65 78 61 6d 70 6c 65  ion..For example
1010: 3a 0a 0a 3c 63 6f 64 65 62 6c 6f 63 6b 3e 0a 53  :..<codeblock>.S
1020: 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 6e 65 77  ELECT * FROM new
1030: 74 61 62 20 57 48 45 52 45 20 67 65 6f 70 6f 6c  tab WHERE geopol
1040: 79 5f 6f 76 65 72 6c 61 70 28 5f 73 68 61 70 65  y_overlap(_shape
1050: 2c 20 24 71 75 65 72 79 5f 70 6f 6c 79 67 6f 6e  , $query_polygon
1060: 29 3b 0a 3c 2f 63 6f 64 65 62 6c 6f 63 6b 3e 0a  );.</codeblock>.
1070: 0a 3c 70 3e 0a 54 68 65 20 70 72 65 76 69 6f 75  .<p>.The previou
1080: 73 20 65 78 61 6d 70 6c 65 20 77 69 6c 6c 20 72  s example will r
1090: 65 74 75 72 6e 20 65 76 65 72 79 20 72 6f 77 20  eturn every row 
10a0: 66 6f 72 20 77 68 69 63 68 20 74 68 65 20 5f 73  for which the _s
10b0: 68 61 70 65 0a 6f 76 65 72 6c 61 70 73 20 74 68  hape.overlaps th
10c0: 65 20 70 6f 6c 79 67 6f 6e 20 69 6e 20 74 68 65  e polygon in the
10d0: 20 24 71 75 65 72 79 5f 70 6f 6c 79 67 6f 6e 20   $query_polygon 
10e0: 70 61 72 61 6d 65 74 65 72 2e 20 20 54 68 65 0a  parameter.  The.
10f0: 67 65 6f 70 6f 6c 79 5f 77 69 74 68 69 6e 28 29  geopoly_within()
1100: 20 66 75 6e 63 74 69 6f 6e 20 77 6f 72 6b 73 20   function works 
1110: 73 69 6d 69 6c 61 72 6c 79 2c 20 62 75 74 20 6f  similarly, but o
1120: 6e 6c 79 20 72 65 74 75 72 6e 73 20 72 6f 77 73  nly returns rows
1130: 20 66 6f 72 0a 77 68 69 63 68 20 74 68 65 20 5f   for.which the _
1140: 73 68 61 70 65 20 69 73 20 63 6f 6d 70 6c 65 74  shape is complet
1150: 65 6c 79 20 63 6f 6e 74 61 69 6e 65 64 20 77 69  ely contained wi
1160: 74 68 69 6e 20 24 71 75 65 72 79 5f 70 6f 6c 79  thin $query_poly
1170: 67 6f 6e 2e 0a 0a 3c 70 3e 0a 51 75 65 72 69 65  gon...<p>.Querie
1180: 73 20 28 61 6e 64 20 61 6c 73 6f 20 44 45 4c 45  s (and also DELE
1190: 54 45 20 61 6e 64 20 55 50 44 41 54 45 20 73 74  TE and UPDATE st
11a0: 61 74 65 6d 65 6e 74 73 29 20 69 6e 20 77 68 69  atements) in whi
11b0: 63 68 20 74 68 65 20 57 48 45 52 45 0a 63 6c 61  ch the WHERE.cla
11c0: 75 73 65 20 63 6f 6e 74 61 69 6e 73 20 61 20 62  use contains a b
11d0: 61 72 65 20 67 65 6f 70 6f 6c 79 5f 6f 76 65 72  are geopoly_over
11e0: 6c 61 70 28 29 20 6f 72 20 67 65 6f 70 6f 6c 79  lap() or geopoly
11f0: 5f 77 69 74 68 69 6e 28 29 20 66 75 6e 63 74 69  _within() functi
1200: 6f 6e 0a 6d 61 6b 65 20 75 73 65 20 6f 66 20 74  on.make use of t
1210: 68 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 52 2a  he underlying R*
1220: 54 72 65 65 20 64 61 74 61 20 73 74 72 75 63 74  Tree data struct
1230: 75 72 65 73 20 66 6f 72 20 61 20 66 61 73 74 20  ures for a fast 
1240: 6c 6f 6f 6b 75 70 20 74 68 61 74 0a 6f 6e 6c 79  lookup that.only
1250: 20 68 61 73 20 74 6f 20 65 78 61 6d 69 6e 65 20   has to examine 
1260: 61 20 73 75 62 73 65 74 20 6f 66 20 74 68 65 20  a subset of the 
1270: 72 6f 77 73 20 69 6e 20 74 68 65 20 74 61 62 6c  rows in the tabl
1280: 65 2e 20 20 54 68 65 20 6e 75 6d 62 65 72 20 6f  e.  The number o
1290: 66 0a 72 6f 77 73 20 65 78 61 6d 69 6e 65 73 20  f.rows examines 
12a0: 64 65 70 65 6e 64 73 2c 20 6f 66 20 63 6f 75 72  depends, of cour
12b0: 73 65 2c 20 6f 6e 20 74 68 65 20 73 69 7a 65 20  se, on the size 
12c0: 6f 66 20 74 68 65 20 24 71 75 65 72 79 5f 70 6f  of the $query_po
12d0: 6c 79 67 6f 6e 2e 0a 4c 61 72 67 65 20 24 71 75  lygon..Large $qu
12e0: 65 72 79 5f 70 6f 6c 79 67 6f 6e 73 20 77 69 6c  ery_polygons wil
12f0: 6c 20 6e 6f 72 6d 61 6c 6c 79 20 6e 65 65 64 20  l normally need 
1300: 74 6f 20 6c 6f 6f 6b 20 61 74 20 6d 6f 72 65 20  to look at more 
1310: 72 6f 77 73 20 74 68 61 6e 20 73 6d 61 6c 6c 0a  rows than small.
1320: 6f 6e 65 73 2e 0a 0a 3c 70 3e 0a 51 75 65 72 69  ones...<p>.Queri
1330: 65 73 20 61 67 61 69 6e 73 74 20 74 68 65 20 72  es against the r
1340: 6f 77 69 64 20 6f 66 20 61 20 67 65 6f 70 6f 6c  owid of a geopol
1350: 79 20 74 61 62 6c 65 20 61 72 65 20 61 6c 73 6f  y table are also
1360: 20 76 65 72 79 20 71 75 69 63 6b 2c 20 65 76 65   very quick, eve
1370: 6e 0a 66 6f 72 20 74 61 62 6c 65 73 20 77 69 74  n.for tables wit
1380: 68 20 61 20 76 61 73 74 20 6e 75 6d 62 65 72 20  h a vast number 
1390: 6f 66 20 72 6f 77 73 2e 0a 48 6f 77 65 76 65 72  of rows..However
13a0: 2c 20 6e 6f 6e 65 20 6f 66 20 74 68 65 20 61 75  , none of the au
13b0: 78 69 6c 69 61 72 79 20 64 61 74 61 20 63 6f 6c  xiliary data col
13c0: 75 6d 6e 73 20 61 72 65 20 69 6e 64 65 78 65 73  umns are indexes
13d0: 2c 20 61 6e 64 20 73 6f 20 71 75 65 72 69 65 73  , and so queries
13e0: 0a 61 67 61 69 6e 73 74 20 74 68 65 20 61 75 78  .against the aux
13f0: 69 6c 69 61 72 79 20 64 61 74 61 20 63 6f 6c 75  iliary data colu
1400: 6d 6e 73 20 77 69 6c 6c 20 69 6e 76 6f 6c 76 65  mns will involve
1410: 20 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63   a full table sc
1420: 61 6e 2e 0a 0a 3c 68 31 3e 53 70 65 63 69 61 6c  an...<h1>Special
1430: 20 46 75 6e 63 74 69 6f 6e 73 3c 2f 68 31 3e 0a   Functions</h1>.
1440: 0a 3c 70 3e 0a 54 68 65 20 67 65 6f 70 6f 6c 79  .<p>.The geopoly
1450: 20 6d 6f 64 75 6c 65 20 64 65 66 69 6e 65 73 20   module defines 
1460: 73 65 76 65 72 61 6c 20 6e 65 77 20 53 51 4c 20  several new SQL 
1470: 66 75 6e 63 74 69 6f 6e 73 20 74 68 61 74 20 61  functions that a
1480: 72 65 20 75 73 65 66 75 6c 20 66 6f 72 0a 64 65  re useful for.de
1490: 61 6c 69 6e 67 20 77 69 74 68 20 70 6f 6c 79 67  aling with polyg
14a0: 6f 6e 73 2e 20 20 41 6c 6c 20 70 6f 6c 79 67 6f  ons.  All polygo
14b0: 6e 20 61 72 67 75 6d 65 6e 74 73 20 74 6f 20 74  n arguments to t
14c0: 68 65 73 65 20 66 75 6e 63 74 69 6f 6e 73 20 63  hese functions c
14d0: 61 6e 20 62 65 0a 65 69 74 68 65 72 20 74 68 65  an be.either the
14e0: 20 47 65 6f 4a 53 4f 4e 20 66 6f 72 6d 61 74 20   GeoJSON format 
14f0: 6f 72 20 74 68 65 20 69 6e 74 65 72 6e 61 6c 20  or the internal 
1500: 62 69 6e 61 72 79 20 66 6f 72 6d 61 74 2e 0a 0a  binary format...
1510: 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74  <tcl>hd_fragment
1520: 20 67 6f 76 65 72 6c 61 70 20 67 65 6f 70 6f 6c   goverlap geopol
1530: 79 5f 6f 76 65 72 6c 61 70 3c 2f 74 63 6c 3e 0a  y_overlap</tcl>.
1540: 3c 68 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79 5f  <h2>The geopoly_
1550: 6f 76 65 72 6c 61 70 28 50 31 2c 50 32 29 20 46  overlap(P1,P2) F
1560: 75 6e 63 74 69 6f 6e 3c 2f 68 32 3e 0a 0a 3c 70  unction</h2>..<p
1570: 3e 0a 49 66 20 50 31 20 61 6e 64 20 50 32 20 61  >.If P1 and P2 a
1580: 72 65 20 62 6f 74 68 20 70 6f 6c 79 67 6f 6e 73  re both polygons
1590: 2c 20 74 68 65 6e 20 74 68 65 20 67 65 6f 70 6f  , then the geopo
15a0: 6c 79 5f 6f 76 65 72 6c 61 70 28 50 31 2c 50 32  ly_overlap(P1,P2
15b0: 29 20 66 75 6e 63 74 69 6f 6e 20 72 65 74 75 72  ) function retur
15c0: 6e 73 0a 61 20 6e 6f 6e 2d 7a 65 72 6f 20 69 6e  ns.a non-zero in
15d0: 74 65 67 65 72 20 69 66 20 74 68 65 72 65 20 69  teger if there i
15e0: 73 20 61 6e 79 20 6f 76 65 72 6c 61 70 20 62 65  s any overlap be
15f0: 74 77 65 65 6e 20 50 31 20 61 6e 64 20 50 32 2c  tween P1 and P2,
1600: 20 6f 72 20 69 74 20 72 65 74 75 72 6e 73 0a 7a   or it returns.z
1610: 65 72 6f 20 69 66 20 50 31 20 61 6e 64 20 50 32  ero if P1 and P2
1620: 20 63 6f 6d 70 6c 65 74 65 6c 79 20 64 69 73 6a   completely disj
1630: 6f 69 6e 74 2e 0a 49 66 20 65 69 74 68 65 72 20  oint..If either 
1640: 50 31 20 6f 72 20 50 32 20 69 73 20 6e 6f 74 20  P1 or P2 is not 
1650: 61 20 70 6f 6c 79 67 6f 6e 2c 20 74 68 69 73 20  a polygon, this 
1660: 72 6f 75 74 69 6e 65 20 72 65 74 75 72 6e 73 20  routine returns 
1670: 4e 55 4c 4c 2e 0a 0a 3c 70 3e 0a 54 68 65 20 67  NULL...<p>.The g
1680: 65 6f 70 6f 6c 79 5f 6f 76 65 72 6c 61 70 28 50  eopoly_overlap(P
1690: 31 2c 50 32 29 20 66 75 6e 63 74 69 6f 6e 20 69  1,P2) function i
16a0: 73 20 73 70 65 63 69 61 6c 20 69 6e 20 74 68 61  s special in tha
16b0: 74 20 74 68 65 20 67 65 6f 70 6f 6c 79 20 76 69  t the geopoly vi
16c0: 72 74 75 61 6c 0a 74 61 62 6c 65 20 6b 6e 6f 77  rtual.table know
16d0: 73 20 68 6f 77 20 74 6f 20 75 73 65 20 52 2a 54  s how to use R*T
16e0: 72 65 65 20 69 6e 64 65 78 65 73 20 74 6f 20 6f  ree indexes to o
16f0: 70 74 69 6d 69 7a 65 20 71 75 65 72 69 65 73 20  ptimize queries 
1700: 69 6e 20 77 68 69 63 68 20 74 68 65 20 0a 57 48  in which the .WH
1710: 45 52 45 20 63 6c 61 75 73 65 20 75 73 65 73 20  ERE clause uses 
1720: 67 65 6f 70 6f 6c 79 5f 6f 76 65 72 6c 61 70 28  geopoly_overlap(
1730: 29 20 61 73 20 61 20 62 6f 6f 6c 65 61 6e 20 66  ) as a boolean f
1740: 75 6e 63 74 69 6f 6e 2e 20 20 4f 6e 6c 79 20 74  unction.  Only t
1750: 68 65 0a 67 65 6f 70 6f 6c 79 5f 6f 76 65 72 6c  he.geopoly_overl
1760: 61 70 28 50 31 2c 50 32 29 20 61 6e 64 20 67 65  ap(P1,P2) and ge
1770: 6f 70 6f 6c 79 5f 77 69 74 68 69 6e 28 50 31 2c  opoly_within(P1,
1780: 50 32 29 20 66 75 6e 63 74 69 6f 6e 73 20 68 61  P2) functions ha
1790: 76 65 20 74 68 69 73 0a 63 61 70 61 62 69 6c 69  ve this.capabili
17a0: 74 79 2e 0a 0a 3c 74 63 6c 3e 68 64 5f 66 72 61  ty...<tcl>hd_fra
17b0: 67 6d 65 6e 74 20 67 77 69 74 68 69 6e 20 67 65  gment gwithin ge
17c0: 6f 70 6f 6c 79 5f 77 69 74 68 69 6e 3c 2f 74 63  opoly_within</tc
17d0: 6c 3e 0a 3c 68 32 3e 54 68 65 20 67 65 6f 70 6f  l>.<h2>The geopo
17e0: 6c 79 5f 77 69 74 68 69 6e 28 50 31 2c 50 32 29  ly_within(P1,P2)
17f0: 20 46 75 6e 63 74 69 6f 6e 3c 2f 68 32 3e 0a 0a   Function</h2>..
1800: 3c 70 3e 0a 49 66 20 50 31 20 61 6e 64 20 50 32  <p>.If P1 and P2
1810: 20 61 72 65 20 62 6f 74 68 20 70 6f 6c 79 67 6f   are both polygo
1820: 6e 73 2c 20 74 68 65 6e 20 74 68 65 20 67 65 6f  ns, then the geo
1830: 70 6f 6c 79 5f 77 69 74 68 69 6e 28 50 31 2c 50  poly_within(P1,P
1840: 32 29 20 66 75 6e 63 74 69 6f 6e 20 72 65 74 75  2) function retu
1850: 72 6e 73 0a 61 20 6e 6f 6e 2d 7a 65 72 6f 20 69  rns.a non-zero i
1860: 6e 74 65 67 65 72 20 69 66 20 50 32 20 69 73 20  nteger if P2 is 
1870: 63 6f 6d 70 6c 65 74 65 6c 79 20 63 6f 6e 74 61  completely conta
1880: 69 6e 65 64 20 77 69 74 68 69 6e 20 50 31 2c 20  ined within P1, 
1890: 6f 72 20 69 74 20 72 65 74 75 72 6e 73 20 7a 65  or it returns ze
18a0: 72 6f 0a 69 66 20 61 6e 79 20 70 61 72 74 20 6f  ro.if any part o
18b0: 66 20 50 32 20 69 73 20 6f 75 74 73 69 64 65 20  f P2 is outside 
18c0: 6f 66 20 50 31 2e 20 20 49 66 20 50 31 20 61 6e  of P1.  If P1 an
18d0: 64 20 50 32 20 61 72 65 20 74 68 65 20 73 61 6d  d P2 are the sam
18e0: 65 20 70 6f 6c 79 67 6f 6e 2c 20 74 68 69 73 20  e polygon, this 
18f0: 72 6f 75 74 69 6e 65 0a 72 65 74 75 72 6e 73 20  routine.returns 
1900: 6e 6f 6e 2d 7a 65 72 6f 2e 0a 49 66 20 65 69 74  non-zero..If eit
1910: 68 65 72 20 50 31 20 6f 72 20 50 32 20 69 73 20  her P1 or P2 is 
1920: 6e 6f 74 20 61 20 70 6f 6c 79 67 6f 6e 2c 20 74  not a polygon, t
1930: 68 69 73 20 72 6f 75 74 69 6e 65 20 72 65 74 75  his routine retu
1940: 72 6e 73 20 4e 55 4c 4c 2e 0a 0a 3c 70 3e 0a 54  rns NULL...<p>.T
1950: 68 65 20 67 65 6f 70 6f 6c 79 5f 77 69 74 68 69  he geopoly_withi
1960: 6e 28 50 31 2c 50 32 29 20 66 75 6e 63 74 69 6f  n(P1,P2) functio
1970: 6e 20 69 73 20 73 70 65 63 69 61 6c 20 69 6e 20  n is special in 
1980: 74 68 61 74 20 74 68 65 20 67 65 6f 70 6f 6c 79  that the geopoly
1990: 20 76 69 72 74 75 61 6c 0a 74 61 62 6c 65 20 6b   virtual.table k
19a0: 6e 6f 77 73 20 68 6f 77 20 74 6f 20 75 73 65 20  nows how to use 
19b0: 52 2a 54 72 65 65 20 69 6e 64 65 78 65 73 20 74  R*Tree indexes t
19c0: 6f 20 6f 70 74 69 6d 69 7a 65 20 71 75 65 72 69  o optimize queri
19d0: 65 73 20 69 6e 20 77 68 69 63 68 20 74 68 65 20  es in which the 
19e0: 0a 57 48 45 52 45 20 63 6c 61 75 73 65 20 75 73  .WHERE clause us
19f0: 65 73 20 67 65 6f 70 6f 6c 79 5f 77 69 74 68 69  es geopoly_withi
1a00: 6e 28 29 20 61 73 20 61 20 62 6f 6f 6c 65 61 6e  n() as a boolean
1a10: 20 66 75 6e 63 74 69 6f 6e 2e 20 20 4f 6e 6c 79   function.  Only
1a20: 20 74 68 65 0a 67 65 6f 70 6f 6c 79 5f 77 69 74   the.geopoly_wit
1a30: 68 69 6e 28 50 31 2c 50 32 29 20 61 6e 64 20 67  hin(P1,P2) and g
1a40: 65 6f 70 6f 6c 79 5f 6f 76 65 72 6c 61 70 28 50  eopoly_overlap(P
1a50: 31 2c 50 32 29 20 66 75 6e 63 74 69 6f 6e 73 20  1,P2) functions 
1a60: 68 61 76 65 20 74 68 69 73 0a 63 61 70 61 62 69  have this.capabi
1a70: 6c 69 74 79 2e 0a 0a 3c 74 63 6c 3e 68 64 5f 66  lity...<tcl>hd_f
1a80: 72 61 67 6d 65 6e 74 20 67 61 72 65 61 20 67 65  ragment garea ge
1a90: 6f 70 6f 6c 79 5f 61 72 65 61 3c 2f 74 63 6c 3e  opoly_area</tcl>
1aa0: 0a 3c 68 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79  .<h2>The geopoly
1ab0: 5f 61 72 65 61 28 50 29 20 46 75 6e 63 74 69 6f  _area(P) Functio
1ac0: 6e 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 49 66 20 50  n</h2>..<p>.If P
1ad0: 20 69 73 20 61 20 70 6f 6c 79 67 6f 6e 2c 20 74   is a polygon, t
1ae0: 68 65 6e 20 67 65 6f 70 6f 6c 79 5f 61 72 65 61  hen geopoly_area
1af0: 28 50 29 20 72 65 74 75 72 6e 73 20 74 68 65 20  (P) returns the 
1b00: 61 72 65 61 20 65 6e 63 6c 6f 73 65 64 20 62 79  area enclosed by
1b10: 0a 74 68 61 74 20 70 6f 6c 79 67 6f 6e 2e 20 20  .that polygon.  
1b20: 49 66 20 50 20 69 73 20 6e 6f 74 20 61 20 70 6f  If P is not a po
1b30: 6c 79 67 6f 6e 2c 20 67 65 6f 70 6f 6c 79 5f 61  lygon, geopoly_a
1b40: 72 65 61 28 50 29 20 72 65 74 75 72 6e 73 20 4e  rea(P) returns N
1b50: 55 4c 4c 2e 0a 0a 3c 74 63 6c 3e 68 64 5f 66 72  ULL...<tcl>hd_fr
1b60: 61 67 6d 65 6e 74 20 67 62 6c 6f 62 20 67 65 6f  agment gblob geo
1b70: 70 6f 6c 79 5f 62 6c 6f 62 3c 2f 74 63 6c 3e 0a  poly_blob</tcl>.
1b80: 3c 68 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79 5f  <h2>The geopoly_
1b90: 62 6c 6f 62 28 50 29 20 46 75 6e 63 74 69 6f 6e  blob(P) Function
1ba0: 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 49 66 20 50 20  </h2>..<p>.If P 
1bb0: 69 73 20 61 20 70 6f 6c 79 67 6f 6e 2c 20 74 68  is a polygon, th
1bc0: 65 6e 20 67 65 6f 70 6f 6c 79 5f 62 6c 6f 62 28  en geopoly_blob(
1bd0: 50 29 20 72 65 74 75 72 6e 73 20 74 68 65 20 62  P) returns the b
1be0: 69 6e 61 72 79 20 65 6e 63 6f 64 69 6e 67 0a 6f  inary encoding.o
1bf0: 66 20 74 68 61 74 20 70 6f 6c 79 67 6f 6e 20 61  f that polygon a
1c00: 73 20 61 20 42 4c 4f 42 2e 0a 49 66 20 50 20 69  s a BLOB..If P i
1c10: 73 20 6e 6f 74 20 61 20 70 6f 6c 79 67 6f 6e 2c  s not a polygon,
1c20: 20 67 65 6f 70 6f 6c 79 5f 62 6c 6f 62 28 50 29   geopoly_blob(P)
1c30: 20 72 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 0a   returns NULL...
1c40: 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74  <tcl>hd_fragment
1c50: 20 67 6a 73 6f 6e 20 67 65 6f 70 6f 6c 79 5f 6a   gjson geopoly_j
1c60: 73 6f 6e 3c 2f 74 63 6c 3e 0a 3c 68 32 3e 54 68  son</tcl>.<h2>Th
1c70: 65 20 67 65 6f 70 6f 6c 79 5f 6a 73 6f 6e 28 50  e geopoly_json(P
1c80: 29 20 46 75 6e 63 74 69 6f 6e 3c 2f 68 32 3e 0a  ) Function</h2>.
1c90: 0a 3c 70 3e 0a 49 66 20 50 20 69 73 20 61 20 70  .<p>.If P is a p
1ca0: 6f 6c 79 67 6f 6e 2c 20 74 68 65 6e 20 67 65 6f  olygon, then geo
1cb0: 70 6f 6c 79 5f 6a 73 6f 6e 28 50 29 20 72 65 74  poly_json(P) ret
1cc0: 75 72 6e 73 20 74 68 65 20 47 65 6f 4a 53 4f 4e  urns the GeoJSON
1cd0: 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e 0a   representation.
1ce0: 6f 66 20 74 68 61 74 20 70 6f 6c 79 67 6f 6e 20  of that polygon 
1cf0: 61 73 20 61 20 54 45 58 54 20 73 74 72 69 6e 67  as a TEXT string
1d00: 2e 0a 49 66 20 50 20 69 73 20 6e 6f 74 20 61 20  ..If P is not a 
1d10: 70 6f 6c 79 67 6f 6e 2c 20 67 65 6f 70 6f 6c 79  polygon, geopoly
1d20: 5f 6a 73 6f 6e 28 50 29 20 72 65 74 75 72 6e 73  _json(P) returns
1d30: 20 4e 55 4c 4c 2e 0a 0a 3c 74 63 6c 3e 68 64 5f   NULL...<tcl>hd_
1d40: 66 72 61 67 6d 65 6e 74 20 67 73 76 67 20 67 65  fragment gsvg ge
1d50: 6f 70 6f 6c 79 5f 73 76 67 3c 2f 74 63 6c 3e 0a  opoly_svg</tcl>.
1d60: 3c 68 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79 5f  <h2>The geopoly_
1d70: 73 76 67 28 50 2c 2e 2e 2e 29 20 46 75 6e 63 74  svg(P,...) Funct
1d80: 69 6f 6e 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 49 66  ion</h2>..<p>.If
1d90: 20 50 20 69 73 20 61 20 70 6f 6c 79 67 6f 6e 2c   P is a polygon,
1da0: 20 74 68 65 6e 20 67 65 6f 70 6f 6c 79 5f 73 76   then geopoly_sv
1db0: 67 28 50 2c 2e 2e 2e 29 20 72 65 74 75 72 6e 73  g(P,...) returns
1dc0: 20 61 20 74 65 78 74 20 73 74 72 69 6e 67 20 77   a text string w
1dd0: 68 69 63 68 20 69 73 20 61 0a 5b 68 74 74 70 73  hich is a.[https
1de0: 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e  ://en.wikipedia.
1df0: 6f 72 67 2f 77 69 6b 69 2f 53 63 61 6c 61 62 6c  org/wiki/Scalabl
1e00: 65 5f 56 65 63 74 6f 72 5f 47 72 61 70 68 69 63  e_Vector_Graphic
1e10: 73 7c 53 63 61 6c 61 62 6c 65 20 56 65 63 74 6f  s|Scalable Vecto
1e20: 72 20 47 72 61 70 68 69 63 73 20 28 53 56 47 29  r Graphics (SVG)
1e30: 5d 0a 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e  ].representation
1e40: 20 6f 66 20 74 68 61 74 20 70 6f 6c 79 67 6f 6e   of that polygon
1e50: 2e 20 20 49 66 20 74 68 65 72 65 20 69 73 20 6d  .  If there is m
1e60: 6f 72 65 20 6f 6e 65 20 61 72 67 75 6d 65 6e 74  ore one argument
1e70: 2c 20 74 68 65 6e 20 73 65 63 6f 6e 64 0a 61 6e  , then second.an
1e80: 64 20 73 75 62 73 65 71 75 65 6e 74 20 61 72 67  d subsequent arg
1e90: 75 6d 65 6e 74 73 20 61 72 65 20 61 64 64 65 64  uments are added
1ea0: 20 61 73 20 61 74 74 72 69 62 75 74 65 73 20 74   as attributes t
1eb0: 6f 20 65 61 63 68 20 53 56 47 20 67 6c 79 70 68  o each SVG glyph
1ec0: 2e 20 20 46 6f 72 20 65 78 61 6d 70 6c 65 3a 0a  .  For example:.
1ed0: 0a 3c 63 6f 64 65 62 6c 6f 63 6b 3e 0a 53 45 4c  .<codeblock>.SEL
1ee0: 45 43 54 20 67 65 6f 70 6f 6c 79 5f 73 76 67 28  ECT geopoly_svg(
1ef0: 24 70 6f 6c 79 67 6f 6e 2c 27 63 6c 61 73 73 3d  $polygon,'class=
1f00: 22 70 6f 6c 79 22 27 2c 27 73 74 79 6c 65 3d 22  "poly"','style="
1f10: 66 69 6c 6c 3a 62 6c 75 65 3b 22 27 29 3b 0a 3c  fill:blue;"');.<
1f20: 2f 63 6f 64 65 62 6c 6f 63 6b 3e 0a 0a 3c 70 3e  /codeblock>..<p>
1f30: 0a 49 66 20 50 20 69 73 20 6e 6f 74 20 61 20 70  .If P is not a p
1f40: 6f 6c 79 67 6f 6e 2c 20 67 65 6f 70 6f 6c 79 5f  olygon, geopoly_
1f50: 73 76 67 28 50 2c 2e 2e 2e 29 20 72 65 74 75 72  svg(P,...) retur
1f60: 6e 73 20 4e 55 4c 4c 2e 0a 0a 3c 70 3e 0a 4e 6f  ns NULL...<p>.No
1f70: 74 65 20 74 68 61 74 20 67 65 6f 70 6f 6c 79 20  te that geopoly 
1f80: 75 73 65 73 20 61 20 74 72 61 64 69 74 69 6f 6e  uses a tradition
1f90: 61 6c 20 72 69 67 68 74 2d 68 61 6e 64 65 64 20  al right-handed 
1fa0: 63 61 72 74 65 73 69 61 6e 20 63 6f 6f 72 64 69  cartesian coordi
1fb0: 6e 61 74 65 20 73 79 73 74 65 6d 0a 77 69 74 68  nate system.with
1fc0: 20 74 68 65 20 6f 72 69 67 69 6e 20 61 74 20 74   the origin at t
1fd0: 68 65 20 6c 6f 77 65 72 20 6c 65 66 74 2c 20 77  he lower left, w
1fe0: 68 65 72 65 61 73 20 53 56 47 20 75 73 65 73 20  hereas SVG uses 
1ff0: 61 20 6c 65 66 74 2d 68 61 6e 64 65 64 20 63 6f  a left-handed co
2000: 6f 72 64 69 6e 61 74 65 0a 73 79 73 74 65 6d 20  ordinate.system 
2010: 77 69 74 68 20 74 68 65 20 6f 72 69 67 69 6e 20  with the origin 
2020: 61 74 20 74 68 65 20 75 70 70 65 72 20 6c 65 66  at the upper lef
2030: 74 2e 20 20 54 68 65 20 67 65 6f 70 6f 6c 79 5f  t.  The geopoly_
2040: 73 76 67 28 29 20 72 6f 75 74 69 6e 65 20 6d 61  svg() routine ma
2050: 6b 65 73 20 6e 6f 0a 61 74 74 65 6d 70 74 20 74  kes no.attempt t
2060: 6f 20 74 72 61 6e 73 66 6f 72 6d 20 74 68 65 20  o transform the 
2070: 63 6f 6f 72 64 69 6e 61 74 65 20 73 79 73 74 65  coordinate syste
2080: 6d 2c 20 73 6f 20 74 68 65 20 64 69 73 70 6c 61  m, so the displa
2090: 79 65 64 20 69 6d 61 67 65 73 20 61 72 65 20 73  yed images are s
20a0: 68 6f 77 6e 0a 69 6e 20 6d 69 72 72 6f 72 20 69  hown.in mirror i
20b0: 6d 61 67 65 20 61 6e 64 20 72 6f 74 61 74 65 64  mage and rotated
20c0: 2e 20 20 49 66 20 74 68 61 74 20 69 73 20 75 6e  .  If that is un
20d0: 64 65 73 69 72 61 62 6c 65 2c 20 74 68 65 20 67  desirable, the g
20e0: 65 6f 70 6f 6c 79 5f 78 66 6f 72 6d 28 29 20 72  eopoly_xform() r
20f0: 6f 75 74 69 6e 65 0a 63 61 6e 20 62 65 20 75 73  outine.can be us
2100: 65 64 20 74 6f 20 74 72 61 6e 73 66 6f 72 6d 20  ed to transform 
2110: 74 68 65 20 6f 75 74 70 75 74 20 66 72 6f 6d 20  the output from 
2120: 63 61 72 74 65 73 69 61 6e 20 74 6f 20 53 56 47  cartesian to SVG
2130: 20 63 6f 6f 72 64 69 6e 61 74 65 73 20 70 72 69   coordinates pri
2140: 6f 72 20 74 6f 0a 70 61 73 73 69 6e 67 20 74 68  or to.passing th
2150: 65 20 70 6f 6c 79 67 6f 6e 73 20 69 6e 74 6f 20  e polygons into 
2160: 67 65 6f 70 6f 6c 79 5f 73 76 67 28 29 2e 0a 0a  geopoly_svg()...
2170: 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74  <tcl>hd_fragment
2180: 20 67 62 62 6f 78 20 67 65 6f 70 6f 6c 79 5f 62   gbbox geopoly_b
2190: 62 6f 78 20 67 65 6f 70 6f 6c 79 5f 67 72 6f 75  box geopoly_grou
21a0: 70 5f 62 62 6f 78 3c 2f 74 63 6c 3e 0a 3c 68 32  p_bbox</tcl>.<h2
21b0: 3e 54 68 65 20 67 65 6f 70 6f 6c 79 5f 62 62 6f  >The geopoly_bbo
21c0: 78 28 50 29 20 61 6e 64 20 67 65 6f 70 6f 6c 79  x(P) and geopoly
21d0: 5f 67 72 6f 75 70 5f 62 62 6f 78 28 50 29 20 46  _group_bbox(P) F
21e0: 75 6e 63 74 69 6f 6e 73 3c 2f 68 32 3e 0a 0a 3c  unctions</h2>..<
21f0: 70 3e 0a 49 66 20 50 20 69 73 20 61 20 70 6f 6c  p>.If P is a pol
2200: 79 67 6f 6e 2c 20 74 68 65 6e 20 67 65 6f 70 6f  ygon, then geopo
2210: 6c 79 5f 62 62 6f 78 28 50 29 20 72 65 74 75 72  ly_bbox(P) retur
2220: 6e 73 20 61 20 6e 65 77 20 70 6f 6c 79 67 6f 6e  ns a new polygon
2230: 20 74 68 61 74 20 69 73 0a 74 68 65 20 73 6d 61   that is.the sma
2240: 6c 6c 65 73 74 20 28 61 78 69 73 2d 61 6c 69 67  llest (axis-alig
2250: 6e 65 64 29 20 72 65 63 74 61 6e 67 6c 65 20 63  ned) rectangle c
2260: 6f 6d 70 6c 65 74 65 6c 79 20 65 6e 63 6c 6f 73  ompletely enclos
2270: 69 6e 67 20 50 2e 0a 49 66 20 50 20 69 73 20 6e  ing P..If P is n
2280: 6f 74 20 61 20 70 6f 6c 79 67 6f 6e 2c 20 67 65  ot a polygon, ge
2290: 6f 70 6f 6c 79 5f 62 62 6f 78 28 50 29 20 72 65  opoly_bbox(P) re
22a0: 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 0a 3c 70 3e  turns NULL...<p>
22b0: 0a 54 68 65 20 67 65 6f 70 6f 6c 79 5f 67 72 6f  .The geopoly_gro
22c0: 75 70 5f 62 62 6f 78 28 50 29 20 66 75 6e 63 74  up_bbox(P) funct
22d0: 69 6f 6e 20 69 73 20 61 6e 20 61 67 67 72 65 67  ion is an aggreg
22e0: 61 74 65 20 76 65 72 73 69 6f 6e 20 6f 66 20 67  ate version of g
22f0: 65 6f 70 6f 6c 79 5f 62 62 6f 78 28 50 29 2e 0a  eopoly_bbox(P)..
2300: 54 68 65 20 67 65 6f 70 6f 6c 79 5f 67 72 6f 75  The geopoly_grou
2310: 70 5f 62 62 6f 78 28 50 29 20 66 75 6e 63 74 69  p_bbox(P) functi
2320: 6f 6e 20 72 65 74 75 72 6e 73 20 74 68 65 20 73  on returns the s
2330: 6d 61 6c 6c 65 73 74 20 72 65 63 74 61 6e 67 6c  mallest rectangl
2340: 65 20 74 68 61 74 20 77 69 6c 6c 0a 65 6e 63 6c  e that will.encl
2350: 6f 73 65 20 61 6c 6c 20 50 20 76 61 6c 75 65 73  ose all P values
2360: 20 73 65 65 6e 20 64 75 72 69 6e 67 20 61 67 67   seen during agg
2370: 72 65 67 61 74 69 6f 6e 2e 0a 0a 3c 74 63 6c 3e  regation...<tcl>
2380: 68 64 5f 66 72 61 67 6d 65 6e 74 20 67 70 6f 69  hd_fragment gpoi
2390: 6e 74 20 67 65 6f 70 6f 6c 79 5f 63 6f 6e 73 74  nt geopoly_const
23a0: 61 69 6e 73 5f 70 6f 69 6e 74 3c 2f 74 63 6c 3e  ains_point</tcl>
23b0: 0a 3c 68 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79  .<h2>The geopoly
23c0: 5f 63 6f 6e 74 61 69 6e 73 5f 70 6f 69 6e 74 28  _contains_point(
23d0: 50 2c 58 2c 59 29 20 46 75 6e 63 74 69 6f 6e 3c  P,X,Y) Function<
23e0: 2f 68 32 3e 0a 0a 3c 70 3e 0a 49 66 20 50 20 69  /h2>..<p>.If P i
23f0: 73 20 61 20 70 6f 6c 79 67 6f 6e 2c 20 74 68 65  s a polygon, the
2400: 6e 20 67 65 6f 70 6f 6c 79 5f 63 6f 6e 74 61 69  n geopoly_contai
2410: 6e 73 5f 70 6f 69 6e 74 28 50 2c 58 2c 59 29 20  ns_point(P,X,Y) 
2420: 72 65 74 75 72 6e 73 20 61 20 0a 6e 6f 6e 2d 7a  returns a .non-z
2430: 65 72 6f 20 69 6e 74 65 67 65 72 20 69 66 20 61  ero integer if a
2440: 6e 64 20 6f 6e 6c 79 0a 69 66 20 74 68 65 20 63  nd only.if the c
2450: 6f 6f 72 64 69 6e 61 74 65 20 58 2c 59 20 69 73  oordinate X,Y is
2460: 20 69 6e 73 69 64 65 20 6f 72 20 6f 6e 20 74 68   inside or on th
2470: 65 20 62 6f 75 6e 64 61 72 79 20 6f 66 20 74 68  e boundary of th
2480: 65 20 70 6f 6c 79 67 6f 6e 20 50 2e 0a 49 66 20  e polygon P..If 
2490: 50 20 69 73 20 6e 6f 74 20 61 20 70 6f 6c 79 67  P is not a polyg
24a0: 6f 6e 2c 20 67 65 6f 70 6f 6c 79 5f 63 6f 6e 74  on, geopoly_cont
24b0: 61 69 6e 73 5f 70 6f 69 6e 74 28 50 2c 58 2c 59  ains_point(P,X,Y
24c0: 29 20 72 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a  ) returns NULL..
24d0: 0a 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e  .<tcl>hd_fragmen
24e0: 74 20 78 66 6f 72 6d 20 67 65 6f 70 6f 6c 79 5f  t xform geopoly_
24f0: 78 66 6f 72 6d 3c 2f 74 63 6c 3e 0a 3c 68 32 3e  xform</tcl>.<h2>
2500: 54 68 65 20 67 65 6f 70 6f 6c 79 5f 78 66 6f 72  The geopoly_xfor
2510: 6d 28 50 2c 41 2c 42 2c 43 2c 44 2c 45 2c 46 29  m(P,A,B,C,D,E,F)
2520: 20 46 75 6e 63 74 69 6f 6e 3c 2f 68 32 3e 0a 0a   Function</h2>..
2530: 3c 70 3e 0a 54 68 65 20 67 65 6f 70 6f 6c 79 5f  <p>.The geopoly_
2540: 78 66 6f 72 6d 28 50 2c 41 2c 42 2c 43 2c 44 2c  xform(P,A,B,C,D,
2550: 45 2c 46 29 20 66 75 6e 63 74 69 6f 6e 20 72 65  E,F) function re
2560: 74 75 72 6e 73 20 61 20 6e 65 77 20 70 6f 6c 79  turns a new poly
2570: 67 6f 6e 20 74 68 61 74 20 69 73 20 61 6e 0a 61  gon that is an.a
2580: 66 66 69 6e 65 20 74 72 61 6e 73 66 6f 72 6d 61  ffine transforma
2590: 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 6f 6c 79  tion of the poly
25a0: 67 6f 6e 20 50 20 61 6e 64 20 77 68 65 72 65 20  gon P and where 
25b0: 74 68 65 20 74 72 61 6e 73 66 6f 72 6d 61 74 69  the transformati
25c0: 6f 6e 0a 69 73 20 64 65 66 69 6e 65 64 20 62 79  on.is defined by
25d0: 20 76 61 6c 75 65 73 20 41 2c 42 2c 43 2c 44 2c   values A,B,C,D,
25e0: 45 2c 46 2e 20 49 66 20 50 20 69 73 20 6e 6f 74  E,F. If P is not
25f0: 20 61 20 76 61 6c 69 64 20 70 6f 6c 79 67 6f 6e   a valid polygon
2600: 2c 20 74 68 69 73 0a 72 6f 75 74 69 6e 65 20 72  , this.routine r
2610: 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 0a 3c 70  eturns NULL...<p
2620: 3e 0a 54 68 65 20 74 72 61 6e 73 66 6f 72 6d 61  >.The transforma
2630: 74 69 6f 6e 20 63 6f 6e 76 65 72 74 73 20 65 61  tion converts ea
2640: 63 68 20 76 65 72 74 65 78 20 6f 66 20 74 68 65  ch vertex of the
2650: 20 70 6f 6c 79 67 6f 6e 20 61 63 63 6f 72 64 69   polygon accordi
2660: 6e 67 20 74 6f 20 74 68 65 0a 66 6f 6c 6c 6f 77  ng to the.follow
2670: 69 6e 67 20 66 6f 72 6d 75 6c 61 3a 0a 0a 3c 63  ing formula:..<c
2680: 6f 64 65 62 6c 6f 63 6b 3e 0a 78 31 20 3d 20 41  odeblock>.x1 = A
2690: 2a 78 30 20 2b 20 42 2a 79 30 20 2b 20 45 0a 79  *x0 + B*y0 + E.y
26a0: 31 20 3d 20 43 2a 78 30 20 2b 20 44 2a 79 30 20  1 = C*x0 + D*y0 
26b0: 2b 20 46 0a 3c 2f 63 6f 64 65 62 6c 6f 63 6b 3e  + F.</codeblock>
26c0: 0a 0a 3c 70 3e 0a 53 6f 2c 20 66 6f 72 20 65 78  ..<p>.So, for ex
26d0: 61 6d 70 6c 65 2c 20 74 6f 20 6d 6f 76 65 20 61  ample, to move a
26e0: 20 70 6f 6c 79 67 6f 6e 20 62 79 20 73 6f 6d 65   polygon by some
26f0: 20 61 6d 6f 75 6e 74 20 44 58 2c 20 44 59 20 77   amount DX, DY w
2700: 69 74 68 6f 75 74 20 63 68 61 6e 67 69 6e 67 0a  ithout changing.
2710: 69 74 73 20 73 68 61 70 65 2c 20 75 73 65 3a 0a  its shape, use:.
2720: 0a 3c 63 6f 64 65 62 6c 6f 63 6b 3e 0a 67 65 6f  .<codeblock>.geo
2730: 70 6f 6c 79 5f 78 66 6f 72 6d 28 24 70 6f 6c 79  poly_xform($poly
2740: 67 6f 6e 2c 20 31 2c 20 30 2c 20 30 2c 20 31 2c  gon, 1, 0, 0, 1,
2750: 20 24 44 58 2c 20 24 44 59 29 0a 3c 2f 63 6f 64   $DX, $DY).</cod
2760: 65 62 6c 6f 63 6b 3e 0a 0a 3c 70 3e 0a 54 6f 20  eblock>..<p>.To 
2770: 72 6f 74 61 74 65 20 61 20 70 6f 6c 79 67 6f 6e  rotate a polygon
2780: 20 62 79 20 52 20 72 61 64 69 61 6e 73 20 61 72   by R radians ar
2790: 6f 75 6e 64 20 74 68 65 20 70 6f 69 6e 74 20 30  ound the point 0
27a0: 2c 20 30 3a 0a 0a 3c 63 6f 64 65 62 6c 6f 63 6b  , 0:..<codeblock
27b0: 3e 0a 67 65 6f 70 6f 6c 79 5f 78 66 6f 72 6d 28  >.geopoly_xform(
27c0: 24 70 6f 6c 79 67 6f 6e 2c 20 63 6f 73 28 24 52  $polygon, cos($R
27d0: 29 2c 20 73 69 6e 28 24 52 29 2c 20 2d 73 69 6e  ), sin($R), -sin
27e0: 28 24 52 29 2c 20 63 6f 73 28 24 52 29 2c 20 30  ($R), cos($R), 0
27f0: 2c 20 30 29 0a 3c 2f 63 6f 64 65 62 6c 6f 63 6b  , 0).</codeblock
2800: 3e 0a 0a 3c 70 3e 0a 4e 6f 74 65 20 74 68 61 74  >..<p>.Note that
2810: 20 61 20 74 72 61 6e 73 66 6f 72 6d 61 74 69 6f   a transformatio
2820: 6e 20 74 68 61 74 20 66 6c 69 70 73 20 74 68 65  n that flips the
2830: 20 70 6f 6c 79 67 6f 6e 20 6d 69 67 68 74 20 63   polygon might c
2840: 61 75 73 65 20 74 68 65 0a 6f 72 64 65 72 20 6f  ause the.order o
2850: 66 20 76 65 72 74 65 78 65 73 20 74 6f 20 62 65  f vertexes to be
2860: 20 72 65 76 65 72 73 65 64 2e 20 20 49 6e 20 6f   reversed.  In o
2870: 74 68 65 72 20 77 6f 72 64 73 2c 20 74 68 65 20  ther words, the 
2880: 74 72 61 6e 73 66 6f 72 6d 61 74 69 6f 6e 0a 6d  transformation.m
2890: 69 67 68 74 20 63 61 75 73 65 20 74 68 65 20 76  ight cause the v
28a0: 65 72 74 65 78 65 73 20 74 6f 20 63 69 72 63 75  ertexes to circu
28b0: 6c 61 74 65 20 69 6e 20 63 6c 6f 63 6b 77 69 73  late in clockwis
28c0: 65 20 6f 72 64 65 72 20 69 6e 73 74 65 61 64 20  e order instead 
28d0: 6f 66 0a 63 6f 75 6e 74 65 72 2d 63 6c 6f 63 6b  of.counter-clock
28e0: 77 69 73 65 2e 20 20 54 68 69 73 20 63 61 6e 20  wise.  This can 
28f0: 62 65 20 63 6f 72 72 65 63 74 65 64 20 62 79 20  be corrected by 
2900: 73 65 6e 64 69 6e 67 20 74 68 65 20 72 65 73 75  sending the resu
2910: 6c 74 0a 74 68 72 6f 75 67 68 20 74 68 65 20 5b  lt.through the [
2920: 67 65 6f 70 6f 6c 79 5f 63 63 77 28 29 5d 20 66  geopoly_ccw()] f
2930: 75 6e 63 74 69 6f 6e 20 61 66 74 65 72 20 74 72  unction after tr
2940: 61 6e 73 66 6f 72 6d 61 74 69 6f 6e 2e 0a 0a 0a  ansformation....
2950: 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74  <tcl>hd_fragment
2960: 20 72 65 67 70 6f 6c 79 20 67 65 6f 70 6f 6c 79   regpoly geopoly
2970: 5f 72 65 67 75 6c 61 72 3c 2f 74 63 6c 3e 0a 3c  _regular</tcl>.<
2980: 68 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79 5f 72  h2>The geopoly_r
2990: 65 67 75 6c 61 72 28 58 2c 59 2c 52 2c 4e 29 20  egular(X,Y,R,N) 
29a0: 46 75 6e 63 74 69 6f 6e 3c 2f 68 32 3e 0a 0a 3c  Function</h2>..<
29b0: 70 3e 0a 54 68 65 20 67 65 6f 70 6f 6c 79 5f 72  p>.The geopoly_r
29c0: 65 67 75 6c 61 72 28 58 2c 59 2c 52 2c 4e 29 20  egular(X,Y,R,N) 
29d0: 66 75 6e 63 74 69 6f 6e 20 72 65 74 75 72 6e 73  function returns
29e0: 20 61 20 63 6f 6e 76 65 78 2c 20 73 69 6d 70 6c   a convex, simpl
29f0: 65 2c 20 72 65 67 75 6c 61 72 2c 0a 65 71 75 69  e, regular,.equi
2a00: 6c 61 74 65 72 61 6c 2c 20 65 71 75 69 61 6e 67  lateral, equiang
2a10: 75 6c 61 72 20 70 6f 6c 79 67 6f 6e 20 77 69 74  ular polygon wit
2a20: 68 20 4e 20 73 69 64 65 73 2c 20 63 65 6e 74 65  h N sides, cente
2a30: 72 65 64 20 61 74 20 58 2c 59 2c 20 61 6e 64 20  red at X,Y, and 
2a40: 77 69 74 68 0a 61 20 63 69 72 63 75 6d 72 61 64  with.a circumrad
2a50: 69 75 73 20 6f 66 20 52 2e 20 20 4f 72 2c 20 69  ius of R.  Or, i
2a60: 66 20 52 20 69 73 20 6e 65 67 61 74 69 76 65 20  f R is negative 
2a70: 6f 72 20 69 66 20 4e 20 69 73 20 6c 65 73 73 20  or if N is less 
2a80: 74 68 61 6e 20 33 2c 20 74 68 65 0a 66 75 6e 63  than 3, the.func
2a90: 74 69 6f 6e 20 72 65 74 75 72 6e 73 20 4e 55 4c  tion returns NUL
2aa0: 4c 2e 20 20 54 68 65 20 4e 20 76 61 6c 75 65 20  L.  The N value 
2ab0: 69 73 20 63 61 70 70 65 64 20 61 74 20 31 30 30  is capped at 100
2ac0: 30 20 73 6f 20 74 68 61 74 20 74 68 65 20 72 6f  0 so that the ro
2ad0: 75 74 69 6e 65 0a 77 69 6c 6c 20 6e 65 76 65 72  utine.will never
2ae0: 20 72 65 6e 64 65 72 20 61 20 70 6f 6c 79 67 6f   render a polygo
2af0: 6e 20 77 69 74 68 20 6d 6f 72 65 20 74 68 61 6e  n with more than
2b00: 20 31 30 30 30 20 73 69 64 65 73 20 65 76 65 6e   1000 sides even
2b10: 20 69 66 20 74 68 65 20 4e 20 76 61 6c 75 65 0a   if the N value.
2b20: 69 73 20 6c 61 72 67 65 72 20 74 68 61 6e 20 31  is larger than 1
2b30: 30 30 30 2e 0a 0a 3c 70 3e 0a 41 73 20 61 6e 20  000...<p>.As an 
2b40: 65 78 61 6d 70 6c 65 2c 20 74 68 65 20 66 6f 6c  example, the fol
2b50: 6c 6f 77 69 6e 67 20 67 72 61 70 68 69 63 3a 0a  lowing graphic:.
2b60: 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 0a 3c 73  .<blockquote>.<s
2b70: 76 67 20 77 69 64 74 68 3d 22 36 30 30 22 20 68  vg width="600" h
2b80: 65 69 67 68 74 3d 22 33 30 30 22 20 73 74 79 6c  eight="300" styl
2b90: 65 3d 22 62 6f 72 64 65 72 3a 31 70 78 20 73 6f  e="border:1px so
2ba0: 6c 69 64 20 62 6c 61 63 6b 22 3e 0a 3c 70 6f 6c  lid black">.<pol
2bb0: 79 6c 69 6e 65 20 70 6f 69 6e 74 73 3d 22 31 34  yline points="14
2bc0: 30 2e 30 30 33 2c 31 30 30 20 38 30 2e 30 30 31  0.003,100 80.001
2bd0: 39 2c 31 33 34 2e 36 34 34 20 38 30 2e 30 30 31  9,134.644 80.001
2be0: 39 2c 36 35 2e 33 35 36 35 20 31 34 30 2e 30 30  9,65.3565 140.00
2bf0: 33 2c 31 30 30 22 20 73 74 79 6c 65 3d 22 66 69  3,100" style="fi
2c00: 6c 6c 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a 72  ll:none;stroke:r
2c10: 65 64 3b 73 74 72 6f 6b 65 2d 77 69 64 74 68 3a  ed;stroke-width:
2c20: 32 22 3e 3c 2f 70 6f 6c 79 6c 69 6e 65 3e 20 3c  2"></polyline> <
2c30: 74 65 78 74 20 78 3d 22 31 30 30 22 20 79 3d 22  text x="100" y="
2c40: 31 30 36 22 20 61 6c 69 67 6e 6d 65 6e 74 2d 62  106" alignment-b
2c50: 61 73 65 6c 69 6e 65 3d 22 63 65 6e 74 72 61 6c  aseline="central
2c60: 22 20 74 65 78 74 2d 61 6e 63 68 6f 72 3d 22 6d  " text-anchor="m
2c70: 69 64 64 6c 65 22 3e 33 3c 2f 74 65 78 74 3e 0a  iddle">3</text>.
2c80: 3c 70 6f 6c 79 6c 69 6e 65 20 70 6f 69 6e 74 73  <polyline points
2c90: 3d 22 32 34 30 2e 30 30 33 2c 31 30 30 20 32 30  ="240.003,100 20
2ca0: 30 2c 31 34 30 2e 30 30 33 20 31 35 39 2e 39 39  0,140.003 159.99
2cb0: 37 2c 31 30 30 20 32 30 30 2c 35 39 2e 39 39 37  7,100 200,59.997
2cc0: 33 20 32 34 30 2e 30 30 33 2c 31 30 30 22 20 73  3 240.003,100" s
2cd0: 74 79 6c 65 3d 22 66 69 6c 6c 3a 6e 6f 6e 65 3b  tyle="fill:none;
2ce0: 73 74 72 6f 6b 65 3a 6f 72 61 6e 67 65 3b 73 74  stroke:orange;st
2cf0: 72 6f 6b 65 2d 77 69 64 74 68 3a 32 22 3e 3c 2f  roke-width:2"></
2d00: 70 6f 6c 79 6c 69 6e 65 3e 20 3c 74 65 78 74 20  polyline> <text 
2d10: 78 3d 22 32 30 30 22 20 79 3d 22 31 30 36 22 20  x="200" y="106" 
2d20: 61 6c 69 67 6e 6d 65 6e 74 2d 62 61 73 65 6c 69  alignment-baseli
2d30: 6e 65 3d 22 63 65 6e 74 72 61 6c 22 20 74 65 78  ne="central" tex
2d40: 74 2d 61 6e 63 68 6f 72 3d 22 6d 69 64 64 6c 65  t-anchor="middle
2d50: 22 3e 34 3c 2f 74 65 78 74 3e 0a 3c 70 6f 6c 79  ">4</text>.<poly
2d60: 6c 69 6e 65 20 70 6f 69 6e 74 73 3d 22 33 34 30  line points="340
2d70: 2e 30 30 33 2c 31 30 30 20 33 31 32 2e 33 35 38  .003,100 312.358
2d80: 2c 31 33 38 2e 30 34 32 20 32 36 37 2e 36 33 37  ,138.042 267.637
2d90: 2c 31 32 33 2e 35 31 31 20 32 36 37 2e 36 33 37  ,123.511 267.637
2da0: 2c 37 36 2e 34 38 39 33 20 33 31 32 2e 33 35 38  ,76.4893 312.358
2db0: 2c 36 31 2e 39 35 38 33 20 33 34 30 2e 30 30 33  ,61.9583 340.003
2dc0: 2c 31 30 30 22 20 73 74 79 6c 65 3d 22 66 69 6c  ,100" style="fil
2dd0: 6c 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a 67 72  l:none;stroke:gr
2de0: 65 65 6e 3b 73 74 72 6f 6b 65 2d 77 69 64 74 68  een;stroke-width
2df0: 3a 32 22 3e 3c 2f 70 6f 6c 79 6c 69 6e 65 3e 20  :2"></polyline> 
2e00: 3c 74 65 78 74 20 78 3d 22 33 30 30 22 20 79 3d  <text x="300" y=
2e10: 22 31 30 36 22 20 61 6c 69 67 6e 6d 65 6e 74 2d  "106" alignment-
2e20: 62 61 73 65 6c 69 6e 65 3d 22 63 65 6e 74 72 61  baseline="centra
2e30: 6c 22 20 74 65 78 74 2d 61 6e 63 68 6f 72 3d 22  l" text-anchor="
2e40: 6d 69 64 64 6c 65 22 3e 35 3c 2f 74 65 78 74 3e  middle">5</text>
2e50: 0a 3c 70 6f 6c 79 6c 69 6e 65 20 70 6f 69 6e 74  .<polyline point
2e60: 73 3d 22 34 34 30 2e 30 30 33 2c 31 30 30 20 34  s="440.003,100 4
2e70: 31 39 2e 39 39 38 2c 31 33 34 2e 36 34 34 20 33  19.998,134.644 3
2e80: 38 30 2e 30 30 32 2c 31 33 34 2e 36 34 34 20 33  80.002,134.644 3
2e90: 35 39 2e 39 39 37 2c 31 30 30 20 33 38 30 2e 30  59.997,100 380.0
2ea0: 30 32 2c 36 35 2e 33 35 36 35 20 34 31 39 2e 39  02,65.3565 419.9
2eb0: 39 38 2c 36 35 2e 33 35 36 35 20 34 34 30 2e 30  98,65.3565 440.0
2ec0: 30 33 2c 31 30 30 22 20 73 74 79 6c 65 3d 22 66  03,100" style="f
2ed0: 69 6c 6c 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a  ill:none;stroke:
2ee0: 62 6c 75 65 3b 73 74 72 6f 6b 65 2d 77 69 64 74  blue;stroke-widt
2ef0: 68 3a 32 22 3e 3c 2f 70 6f 6c 79 6c 69 6e 65 3e  h:2"></polyline>
2f00: 20 3c 74 65 78 74 20 78 3d 22 34 30 30 22 20 79   <text x="400" y
2f10: 3d 22 31 30 36 22 20 61 6c 69 67 6e 6d 65 6e 74  ="106" alignment
2f20: 2d 62 61 73 65 6c 69 6e 65 3d 22 63 65 6e 74 72  -baseline="centr
2f30: 61 6c 22 20 74 65 78 74 2d 61 6e 63 68 6f 72 3d  al" text-anchor=
2f40: 22 6d 69 64 64 6c 65 22 3e 36 3c 2f 74 65 78 74  "middle">6</text
2f50: 3e 0a 3c 70 6f 6c 79 6c 69 6e 65 20 70 6f 69 6e  >.<polyline poin
2f60: 74 73 3d 22 35 34 30 2e 30 30 33 2c 31 30 30 20  ts="540.003,100 
2f70: 35 32 34 2e 39 34 2c 31 33 31 2e 32 37 36 20 34  524.94,131.276 4
2f80: 39 31 2e 31 30 31 2c 31 33 38 2e 39 39 35 20 34  91.101,138.995 4
2f90: 36 33 2e 39 35 39 2c 31 31 37 2e 33 35 33 20 34  63.959,117.353 4
2fa0: 36 33 2e 39 35 39 2c 38 32 2e 36 34 37 31 20 34  63.959,82.6471 4
2fb0: 39 31 2e 31 30 31 2c 36 31 2e 30 30 35 20 35 32  91.101,61.005 52
2fc0: 34 2e 39 34 2c 36 38 2e 37 32 34 33 20 35 34 30  4.94,68.7243 540
2fd0: 2e 30 30 33 2c 31 30 30 22 20 73 74 79 6c 65 3d  .003,100" style=
2fe0: 22 66 69 6c 6c 3a 6e 6f 6e 65 3b 73 74 72 6f 6b  "fill:none;strok
2ff0: 65 3a 70 75 72 70 6c 65 3b 73 74 72 6f 6b 65 2d  e:purple;stroke-
3000: 77 69 64 74 68 3a 32 22 3e 3c 2f 70 6f 6c 79 6c  width:2"></polyl
3010: 69 6e 65 3e 20 3c 74 65 78 74 20 78 3d 22 35 30  ine> <text x="50
3020: 30 22 20 79 3d 22 31 30 36 22 20 61 6c 69 67 6e  0" y="106" align
3030: 6d 65 6e 74 2d 62 61 73 65 6c 69 6e 65 3d 22 63  ment-baseline="c
3040: 65 6e 74 72 61 6c 22 20 74 65 78 74 2d 61 6e 63  entral" text-anc
3050: 68 6f 72 3d 22 6d 69 64 64 6c 65 22 3e 37 3c 2f  hor="middle">7</
3060: 74 65 78 74 3e 0a 3c 70 6f 6c 79 6c 69 6e 65 20  text>.<polyline 
3070: 70 6f 69 6e 74 73 3d 22 31 34 30 2e 30 30 33 2c  points="140.003,
3080: 32 30 30 20 31 32 38 2e 32 38 36 2c 32 32 38 2e  200 128.286,228.
3090: 32 38 36 20 31 30 30 2c 32 34 30 2e 30 30 33 20  286 100,240.003 
30a0: 37 31 2e 37 31 34 33 2c 32 32 38 2e 32 38 36 20  71.7143,228.286 
30b0: 35 39 2e 39 39 37 33 2c 32 30 30 20 37 31 2e 37  59.9973,200 71.7
30c0: 31 34 33 2c 31 37 31 2e 37 31 34 20 31 30 30 2c  143,171.714 100,
30d0: 31 35 39 2e 39 39 37 20 31 32 38 2e 32 38 36 2c  159.997 128.286,
30e0: 31 37 31 2e 37 31 34 20 31 34 30 2e 30 30 33 2c  171.714 140.003,
30f0: 32 30 30 22 20 73 74 79 6c 65 3d 22 66 69 6c 6c  200" style="fill
3100: 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a 72 65 64  :none;stroke:red
3110: 3b 73 74 72 6f 6b 65 2d 77 69 64 74 68 3a 32 22  ;stroke-width:2"
3120: 3e 3c 2f 70 6f 6c 79 6c 69 6e 65 3e 20 3c 74 65  ></polyline> <te
3130: 78 74 20 78 3d 22 31 30 30 22 20 79 3d 22 32 30  xt x="100" y="20
3140: 36 22 20 61 6c 69 67 6e 6d 65 6e 74 2d 62 61 73  6" alignment-bas
3150: 65 6c 69 6e 65 3d 22 63 65 6e 74 72 61 6c 22 20  eline="central" 
3160: 74 65 78 74 2d 61 6e 63 68 6f 72 3d 22 6d 69 64  text-anchor="mid
3170: 64 6c 65 22 3e 38 3c 2f 74 65 78 74 3e 0a 3c 70  dle">8</text>.<p
3180: 6f 6c 79 6c 69 6e 65 20 70 6f 69 6e 74 73 3d 22  olyline points="
3190: 32 34 30 2e 30 30 33 2c 32 30 30 20 32 33 32 2e  240.003,200 232.
31a0: 33 36 33 2c 32 32 33 2e 35 31 31 20 32 31 32 2e  363,223.511 212.
31b0: 33 35 38 2c 32 33 38 2e 30 34 32 20 31 38 37 2e  358,238.042 187.
31c0: 36 34 32 2c 32 33 38 2e 30 34 32 20 31 36 37 2e  642,238.042 167.
31d0: 36 33 37 2c 32 32 33 2e 35 31 31 20 31 35 39 2e  637,223.511 159.
31e0: 39 39 37 2c 32 30 30 20 31 36 37 2e 36 33 37 2c  997,200 167.637,
31f0: 31 37 36 2e 34 38 39 20 31 38 37 2e 36 34 32 2c  176.489 187.642,
3200: 31 36 31 2e 39 35 38 20 32 31 32 2e 33 35 38 2c  161.958 212.358,
3210: 31 36 31 2e 39 35 38 20 32 33 32 2e 33 36 33 2c  161.958 232.363,
3220: 31 37 36 2e 34 38 39 20 32 34 30 2e 30 30 33 2c  176.489 240.003,
3230: 32 30 30 22 20 73 74 79 6c 65 3d 22 66 69 6c 6c  200" style="fill
3240: 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a 6f 72 61  :none;stroke:ora
3250: 6e 67 65 3b 73 74 72 6f 6b 65 2d 77 69 64 74 68  nge;stroke-width
3260: 3a 32 22 3e 3c 2f 70 6f 6c 79 6c 69 6e 65 3e 20  :2"></polyline> 
3270: 3c 74 65 78 74 20 78 3d 22 32 30 30 22 20 79 3d  <text x="200" y=
3280: 22 32 30 36 22 20 61 6c 69 67 6e 6d 65 6e 74 2d  "206" alignment-
3290: 62 61 73 65 6c 69 6e 65 3d 22 63 65 6e 74 72 61  baseline="centra
32a0: 6c 22 20 74 65 78 74 2d 61 6e 63 68 6f 72 3d 22  l" text-anchor="
32b0: 6d 69 64 64 6c 65 22 3e 31 30 3c 2f 74 65 78 74  middle">10</text
32c0: 3e 0a 3c 70 6f 6c 79 6c 69 6e 65 20 70 6f 69 6e  >.<polyline poin
32d0: 74 73 3d 22 33 34 30 2e 30 30 33 2c 32 30 30 20  ts="340.003,200 
32e0: 33 33 34 2e 36 34 34 2c 32 31 39 2e 39 39 38 20  334.644,219.998 
32f0: 33 31 39 2e 39 39 38 2c 32 33 34 2e 36 34 34 20  319.998,234.644 
3300: 33 30 30 2c 32 34 30 2e 30 30 33 20 32 38 30 2e  300,240.003 280.
3310: 30 30 32 2c 32 33 34 2e 36 34 34 20 32 36 35 2e  002,234.644 265.
3320: 33 35 36 2c 32 31 39 2e 39 39 38 20 32 35 39 2e  356,219.998 259.
3330: 39 39 37 2c 32 30 30 20 32 36 35 2e 33 35 36 2c  997,200 265.356,
3340: 31 38 30 2e 30 30 32 20 32 38 30 2e 30 30 32 2c  180.002 280.002,
3350: 31 36 35 2e 33 35 36 20 33 30 30 2c 31 35 39 2e  165.356 300,159.
3360: 39 39 37 20 33 31 39 2e 39 39 38 2c 31 36 35 2e  997 319.998,165.
3370: 33 35 36 20 33 33 34 2e 36 34 34 2c 31 38 30 2e  356 334.644,180.
3380: 30 30 32 20 33 34 30 2e 30 30 33 2c 32 30 30 22  002 340.003,200"
3390: 20 73 74 79 6c 65 3d 22 66 69 6c 6c 3a 6e 6f 6e   style="fill:non
33a0: 65 3b 73 74 72 6f 6b 65 3a 67 72 65 65 6e 3b 73  e;stroke:green;s
33b0: 74 72 6f 6b 65 2d 77 69 64 74 68 3a 32 22 3e 3c  troke-width:2"><
33c0: 2f 70 6f 6c 79 6c 69 6e 65 3e 20 3c 74 65 78 74  /polyline> <text
33d0: 20 78 3d 22 33 30 30 22 20 79 3d 22 32 30 36 22   x="300" y="206"
33e0: 20 61 6c 69 67 6e 6d 65 6e 74 2d 62 61 73 65 6c   alignment-basel
33f0: 69 6e 65 3d 22 63 65 6e 74 72 61 6c 22 20 74 65  ine="central" te
3400: 78 74 2d 61 6e 63 68 6f 72 3d 22 6d 69 64 64 6c  xt-anchor="middl
3410: 65 22 3e 31 32 3c 2f 74 65 78 74 3e 0a 3c 70 6f  e">12</text>.<po
3420: 6c 79 6c 69 6e 65 20 70 6f 69 6e 74 73 3d 22 34  lyline points="4
3430: 34 30 2e 30 30 33 2c 32 30 30 20 34 33 36 2e 39  40.003,200 436.9
3440: 35 36 2c 32 31 35 2e 33 30 35 20 34 32 38 2e 32  56,215.305 428.2
3450: 38 36 2c 32 32 38 2e 32 38 36 20 34 31 35 2e 33  86,228.286 415.3
3460: 30 35 2c 32 33 36 2e 39 35 36 20 34 30 30 2c 32  05,236.956 400,2
3470: 34 30 2e 30 30 33 20 33 38 34 2e 36 39 35 2c 32  40.003 384.695,2
3480: 33 36 2e 39 35 36 20 33 37 31 2e 37 31 34 2c 32  36.956 371.714,2
3490: 32 38 2e 32 38 36 20 33 36 33 2e 30 34 34 2c 32  28.286 363.044,2
34a0: 31 35 2e 33 30 35 20 33 35 39 2e 39 39 37 2c 32  15.305 359.997,2
34b0: 30 30 20 33 36 33 2e 30 34 34 2c 31 38 34 2e 36  00 363.044,184.6
34c0: 39 35 20 33 37 31 2e 37 31 34 2c 31 37 31 2e 37  95 371.714,171.7
34d0: 31 34 20 33 38 34 2e 36 39 35 2c 31 36 33 2e 30  14 384.695,163.0
34e0: 34 34 20 34 30 30 2c 31 35 39 2e 39 39 37 20 34  44 400,159.997 4
34f0: 31 35 2e 33 30 35 2c 31 36 33 2e 30 34 34 20 34  15.305,163.044 4
3500: 32 38 2e 32 38 36 2c 31 37 31 2e 37 31 34 20 34  28.286,171.714 4
3510: 33 36 2e 39 35 36 2c 31 38 34 2e 36 39 35 20 34  36.956,184.695 4
3520: 34 30 2e 30 30 33 2c 32 30 30 22 20 73 74 79 6c  40.003,200" styl
3530: 65 3d 22 66 69 6c 6c 3a 6e 6f 6e 65 3b 73 74 72  e="fill:none;str
3540: 6f 6b 65 3a 62 6c 75 65 3b 73 74 72 6f 6b 65 2d  oke:blue;stroke-
3550: 77 69 64 74 68 3a 32 22 3e 3c 2f 70 6f 6c 79 6c  width:2"></polyl
3560: 69 6e 65 3e 20 3c 74 65 78 74 20 78 3d 22 34 30  ine> <text x="40
3570: 30 22 20 79 3d 22 32 30 36 22 20 61 6c 69 67 6e  0" y="206" align
3580: 6d 65 6e 74 2d 62 61 73 65 6c 69 6e 65 3d 22 63  ment-baseline="c
3590: 65 6e 74 72 61 6c 22 20 74 65 78 74 2d 61 6e 63  entral" text-anc
35a0: 68 6f 72 3d 22 6d 69 64 64 6c 65 22 3e 31 36 3c  hor="middle">16<
35b0: 2f 74 65 78 74 3e 0a 3c 70 6f 6c 79 6c 69 6e 65  /text>.<polyline
35c0: 20 70 6f 69 6e 74 73 3d 22 35 34 30 2e 30 30 33   points="540.003
35d0: 2c 32 30 30 20 35 33 38 2e 30 34 32 2c 32 31 32  ,200 538.042,212
35e0: 2e 33 35 38 20 35 33 32 2e 33 36 33 2c 32 32 33  .358 532.363,223
35f0: 2e 35 31 31 20 35 32 33 2e 35 31 31 2c 32 33 32  .511 523.511,232
3600: 2e 33 36 33 20 35 31 32 2e 33 35 38 2c 32 33 38  .363 512.358,238
3610: 2e 30 34 32 20 35 30 30 2c 32 34 30 2e 30 30 33  .042 500,240.003
3620: 20 34 38 37 2e 36 34 32 2c 32 33 38 2e 30 34 32   487.642,238.042
3630: 20 34 37 36 2e 34 38 39 2c 32 33 32 2e 33 36 33   476.489,232.363
3640: 20 34 36 37 2e 36 33 37 2c 32 32 33 2e 35 31 31   467.637,223.511
3650: 20 34 36 31 2e 39 35 38 2c 32 31 32 2e 33 35 38   461.958,212.358
3660: 20 34 35 39 2e 39 39 37 2c 32 30 30 20 34 36 31   459.997,200 461
3670: 2e 39 35 38 2c 31 38 37 2e 36 34 32 20 34 36 37  .958,187.642 467
3680: 2e 36 33 37 2c 31 37 36 2e 34 38 39 20 34 37 36  .637,176.489 476
3690: 2e 34 38 39 2c 31 36 37 2e 36 33 37 20 34 38 37  .489,167.637 487
36a0: 2e 36 34 32 2c 31 36 31 2e 39 35 38 20 35 30 30  .642,161.958 500
36b0: 2c 31 35 39 2e 39 39 37 20 35 31 32 2e 33 35 38  ,159.997 512.358
36c0: 2c 31 36 31 2e 39 35 38 20 35 32 33 2e 35 31 31  ,161.958 523.511
36d0: 2c 31 36 37 2e 36 33 37 20 35 33 32 2e 33 36 33  ,167.637 532.363
36e0: 2c 31 37 36 2e 34 38 39 20 35 33 38 2e 30 34 32  ,176.489 538.042
36f0: 2c 31 38 37 2e 36 34 32 20 35 34 30 2e 30 30 33  ,187.642 540.003
3700: 2c 32 30 30 22 20 73 74 79 6c 65 3d 22 66 69 6c  ,200" style="fil
3710: 6c 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a 70 75  l:none;stroke:pu
3720: 72 70 6c 65 3b 73 74 72 6f 6b 65 2d 77 69 64 74  rple;stroke-widt
3730: 68 3a 32 22 3e 3c 2f 70 6f 6c 79 6c 69 6e 65 3e  h:2"></polyline>
3740: 20 3c 74 65 78 74 20 78 3d 22 35 30 30 22 20 79   <text x="500" y
3750: 3d 22 32 30 36 22 20 61 6c 69 67 6e 6d 65 6e 74  ="206" alignment
3760: 2d 62 61 73 65 6c 69 6e 65 3d 22 63 65 6e 74 72  -baseline="centr
3770: 61 6c 22 20 74 65 78 74 2d 61 6e 63 68 6f 72 3d  al" text-anchor=
3780: 22 6d 69 64 64 6c 65 22 3e 32 30 3c 2f 74 65 78  "middle">20</tex
3790: 74 3e 0a 3c 2f 73 76 67 3e 0a 3c 2f 62 6c 6f 63  t>.</svg>.</bloc
37a0: 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e 57 61 73 20  kquote>..<p>Was 
37b0: 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 68 69  generated by thi
37c0: 73 20 73 63 72 69 70 74 3a 0a 0a 3c 63 6f 64 65  s script:..<code
37d0: 62 6c 6f 63 6b 3e 0a 53 45 4c 45 43 54 20 27 26  block>.SELECT '&
37e0: 6c 74 3b 73 76 67 20 77 69 64 74 68 3d 22 36 30  lt;svg width="60
37f0: 30 22 20 68 65 69 67 68 74 3d 22 33 30 30 22 3e  0" height="300">
3800: 27 3b 0a 57 49 54 48 20 74 31 28 78 2c 79 2c 6e  ';.WITH t1(x,y,n
3810: 2c 63 6f 6c 6f 72 29 20 41 53 20 28 56 41 4c 55  ,color) AS (VALU
3820: 45 53 0a 20 20 20 28 31 30 30 2c 31 30 30 2c 33  ES.   (100,100,3
3830: 2c 27 72 65 64 27 29 2c 0a 20 20 20 28 32 30 30  ,'red'),.   (200
3840: 2c 31 30 30 2c 34 2c 27 6f 72 61 6e 67 65 27 29  ,100,4,'orange')
3850: 2c 0a 20 20 20 28 33 30 30 2c 31 30 30 2c 35 2c  ,.   (300,100,5,
3860: 27 67 72 65 65 6e 27 29 2c 0a 20 20 20 28 34 30  'green'),.   (40
3870: 30 2c 31 30 30 2c 36 2c 27 62 6c 75 65 27 29 2c  0,100,6,'blue'),
3880: 0a 20 20 20 28 35 30 30 2c 31 30 30 2c 37 2c 27  .   (500,100,7,'
3890: 70 75 72 70 6c 65 27 29 2c 0a 20 20 20 28 31 30  purple'),.   (10
38a0: 30 2c 32 30 30 2c 38 2c 27 72 65 64 27 29 2c 0a  0,200,8,'red'),.
38b0: 20 20 20 28 32 30 30 2c 32 30 30 2c 31 30 2c 27     (200,200,10,'
38c0: 6f 72 61 6e 67 65 27 29 2c 0a 20 20 20 28 33 30  orange'),.   (30
38d0: 30 2c 32 30 30 2c 31 32 2c 27 67 72 65 65 6e 27  0,200,12,'green'
38e0: 29 2c 0a 20 20 20 28 34 30 30 2c 32 30 30 2c 31  ),.   (400,200,1
38f0: 36 2c 27 62 6c 75 65 27 29 2c 0a 20 20 20 28 35  6,'blue'),.   (5
3900: 30 30 2c 32 30 30 2c 32 30 2c 27 70 75 72 70 6c  00,200,20,'purpl
3910: 65 27 29 0a 29 0a 53 45 4c 45 43 54 0a 20 20 20  e').).SELECT.   
3920: 67 65 6f 70 6f 6c 79 5f 73 76 67 28 67 65 6f 70  geopoly_svg(geop
3930: 6f 6c 79 5f 72 65 67 75 6c 61 72 28 78 2c 79 2c  oly_regular(x,y,
3940: 34 30 2c 6e 29 2c 0a 20 20 20 20 20 20 20 20 70  40,n),.        p
3950: 72 69 6e 74 66 28 27 73 74 79 6c 65 3d 22 66 69  rintf('style="fi
3960: 6c 6c 3a 6e 6f 6e 65 3b 73 74 72 6f 6b 65 3a 25  ll:none;stroke:%
3970: 73 3b 73 74 72 6f 6b 65 2d 77 69 64 74 68 3a 32  s;stroke-width:2
3980: 22 27 2c 63 6f 6c 6f 72 29 29 0a 20 20 20 7c 7c  "',color)).   ||
3990: 20 70 72 69 6e 74 66 28 27 20 26 6c 74 3b 74 65   printf(' &lt;te
39a0: 78 74 20 78 3d 22 25 64 22 20 79 3d 22 25 64 22  xt x="%d" y="%d"
39b0: 20 61 6c 69 67 6e 6d 65 6e 74 2d 62 61 73 65 6c   alignment-basel
39c0: 69 6e 65 3d 22 63 65 6e 74 72 61 6c 22 20 74 65  ine="central" te
39d0: 78 74 2d 61 6e 63 68 6f 72 3d 22 6d 69 64 64 6c  xt-anchor="middl
39e0: 65 22 3e 25 64 26 6c 74 3b 2f 74 65 78 74 3e 27  e">%d&lt;/text>'
39f0: 2c 78 2c 79 2b 36 2c 6e 29 0a 20 20 46 52 4f 4d  ,x,y+6,n).  FROM
3a00: 20 74 31 3b 0a 53 45 4c 45 43 54 20 27 26 6c 74   t1;.SELECT '&lt
3a10: 3b 2f 73 76 67 3e 27 3b 0a 3c 2f 63 6f 64 65 62  ;/svg>';.</codeb
3a20: 6c 6f 63 6b 3e 0a 0a 3c 74 63 6c 3e 68 64 5f 66  lock>..<tcl>hd_f
3a30: 72 61 67 6d 65 6e 74 20 63 63 77 20 67 65 6f 70  ragment ccw geop
3a40: 6f 6c 79 5f 63 63 77 3c 2f 74 63 6c 3e 0a 3c 68  oly_ccw</tcl>.<h
3a50: 32 3e 54 68 65 20 67 65 6f 70 6f 6c 79 5f 63 63  2>The geopoly_cc
3a60: 77 28 4a 29 20 46 75 6e 63 74 69 6f 6e 3c 2f 68  w(J) Function</h
3a70: 32 3e 0a 0a 3c 70 3e 54 68 65 20 67 65 6f 70 6f  2>..<p>The geopo
3a80: 6c 79 5f 63 63 77 28 4a 29 20 66 75 6e 63 74 69  ly_ccw(J) functi
3a90: 6f 6e 20 72 65 74 75 72 6e 73 20 74 68 65 20 70  on returns the p
3aa0: 6f 6c 79 67 6f 6e 20 4a 20 77 69 74 68 20 63 6f  olygon J with co
3ab0: 75 6e 74 65 72 2d 63 6c 6f 63 6b 77 69 73 65 20  unter-clockwise 
3ac0: 28 43 43 57 29 20 72 6f 74 61 74 69 6f 6e 2e 0a  (CCW) rotation..
3ad0: 0a 3c 70 3e 0a 5b 68 74 74 70 73 3a 2f 2f 74 6f  .<p>.[https://to
3ae0: 6f 6c 73 2e 69 65 74 66 2e 6f 72 67 2f 68 74 6d  ols.ietf.org/htm
3af0: 6c 2f 72 66 63 37 39 34 36 20 7c 20 52 46 43 2d  l/rfc7946 | RFC-
3b00: 37 39 34 36 5d 20 72 65 71 75 69 72 65 73 20 74  7946] requires t
3b10: 68 61 74 20 70 6f 6c 79 67 6f 6e 73 20 75 73 65  hat polygons use
3b20: 20 43 43 57 20 72 6f 74 61 74 69 6f 6e 2e 0a 42   CCW rotation..B
3b30: 75 74 20 74 68 65 20 73 70 65 63 20 61 6c 73 6f  ut the spec also
3b40: 20 6f 62 73 65 72 76 65 73 20 74 68 61 74 20 6d   observes that m
3b50: 61 6e 79 20 6c 65 67 61 63 79 20 47 65 6f 4a 53  any legacy GeoJS
3b60: 4f 4e 20 66 69 6c 65 73 20 64 6f 20 6e 6f 74 20  ON files do not 
3b70: 66 6f 6c 6c 6f 77 69 6e 67 20 74 68 65 20 73 70  following the sp
3b80: 65 63 20 61 6e 64 0a 63 6f 6e 74 61 69 6e 20 70  ec and.contain p
3b90: 6f 6c 79 67 6f 6e 73 20 77 69 74 68 20 63 6c 6f  olygons with clo
3ba0: 63 6b 77 69 73 65 20 28 43 57 29 20 72 6f 74 61  ckwise (CW) rota
3bb0: 74 69 6f 6e 2e 20 20 54 68 65 20 67 65 6f 70 6f  tion.  The geopo
3bc0: 6c 79 5f 63 63 77 28 29 20 66 75 6e 63 74 69 6f  ly_ccw() functio
3bd0: 6e 20 69 73 20 75 73 65 66 75 6c 20 66 6f 72 0a  n is useful for.
3be0: 61 70 70 6c 69 63 61 74 69 6f 6e 73 20 74 68 61  applications tha
3bf0: 74 20 61 72 65 20 72 65 61 64 69 6e 67 20 6c 65  t are reading le
3c00: 67 61 63 79 20 47 65 6f 4a 53 4f 4e 20 73 63 72  gacy GeoJSON scr
3c10: 69 70 74 73 2e 20 20 49 66 20 74 68 65 20 69 6e  ipts.  If the in
3c20: 70 75 74 20 74 6f 20 67 65 6f 70 6f 6c 79 5f 63  put to geopoly_c
3c30: 63 77 28 29 20 69 73 0a 61 20 63 6f 72 72 65 63  cw() is.a correc
3c40: 74 6c 79 2d 66 6f 72 6d 61 74 74 65 64 20 70 6f  tly-formatted po
3c50: 6c 79 67 6f 6e 2c 20 74 68 65 6e 20 6e 6f 20 63  lygon, then no c
3c60: 68 61 6e 67 65 73 20 61 72 65 20 6d 61 64 65 2e  hanges are made.
3c70: 20 20 48 6f 77 65 76 65 72 2c 20 69 66 20 74 68    However, if th
3c80: 65 20 63 69 72 63 75 6c 61 74 69 6f 6e 20 6f 66  e circulation of
3c90: 0a 74 68 65 20 69 6e 70 75 74 20 70 6f 6c 79 67  .the input polyg
3ca0: 6f 6e 20 69 73 20 62 61 63 6b 77 61 72 64 73 2c  on is backwards,
3cb0: 20 74 68 65 6e 20 67 65 6f 70 6f 6c 79 5f 63 63   then geopoly_cc
3cc0: 77 28 29 20 72 65 76 65 72 73 65 73 20 74 68 65  w() reverses the
3cd0: 20 63 69 72 63 75 6c 61 74 69 6f 6e 20 6f 72 64   circulation ord
3ce0: 65 72 20 73 6f 20 74 68 61 74 0a 69 74 20 63 6f  er so that.it co
3cf0: 6e 66 6f 72 6d 73 20 74 6f 20 74 68 65 20 73 70  nforms to the sp
3d00: 65 63 20 61 6e 64 20 73 6f 20 74 68 61 74 20 69  ec and so that i
3d10: 74 20 77 69 6c 6c 20 77 6f 72 6b 20 63 6f 72 72  t will work corr
3d20: 65 63 74 6c 79 20 77 69 74 68 20 74 68 65 20 47  ectly with the G
3d30: 65 6f 70 6f 6c 79 20 6d 6f 64 75 6c 65 2e 0a 0a  eopoly module...
3d40: 0a 0a 3c 68 31 3e 49 6d 70 6c 65 6d 65 6e 74 61  ..<h1>Implementa
3d50: 74 69 6f 6e 20 44 65 74 61 69 6c 73 3c 2f 68 31  tion Details</h1
3d60: 3e 0a 0a 3c 70 3e 54 68 65 20 67 65 6f 70 6f 6c  >..<p>The geopol
3d70: 79 20 6d 6f 64 75 6c 65 20 69 73 20 61 6e 20 65  y module is an e
3d80: 78 74 65 6e 73 69 6f 6e 20 74 6f 20 74 68 65 20  xtension to the 
3d90: 5b 52 2d 54 72 65 65 20 65 78 74 65 6e 73 69 6f  [R-Tree extensio
3da0: 6e 5d 2e 20 20 47 65 6f 70 6f 6c 79 0a 75 73 65  n].  Geopoly.use
3db0: 73 20 74 68 65 20 73 61 6d 65 20 75 6e 64 65 72  s the same under
3dc0: 6c 79 69 6e 67 20 6c 6f 67 69 63 20 61 6e 64 20  lying logic and 
3dd0: 73 68 61 64 6f 77 20 74 61 62 6c 65 73 20 61 73  shadow tables as
3de0: 20 74 68 65 20 5b 52 2d 54 72 65 65 20 65 78 74   the [R-Tree ext
3df0: 65 6e 73 69 6f 6e 5d 2e 0a 47 65 6f 70 6f 6c 79  ension]..Geopoly
3e00: 20 6d 65 72 65 6c 79 20 70 72 65 73 65 6e 74 73   merely presents
3e10: 20 61 20 64 69 66 66 65 72 65 6e 74 20 69 6e 74   a different int
3e20: 65 72 66 61 63 65 2c 20 61 6e 64 20 70 72 6f 76  erface, and prov
3e30: 69 64 65 73 20 73 6f 6d 65 20 65 78 74 72 61 20  ides some extra 
3e40: 6c 6f 67 69 63 0a 74 6f 20 63 6f 6d 70 75 74 65  logic.to compute
3e50: 20 70 6f 6c 79 67 6f 6e 20 64 65 63 6f 64 69 6e   polygon decodin
3e60: 67 2c 20 6f 76 65 72 6c 61 70 2c 20 61 6e 64 20  g, overlap, and 
3e70: 63 6f 6e 74 61 69 6e 6d 65 6e 74 2e 0a 0a 3c 68  containment...<h
3e80: 32 3e 42 69 6e 61 72 79 20 45 6e 63 6f 64 69 6e  2>Binary Encodin
3e90: 67 20 6f 66 20 50 6f 6c 79 67 6f 6e 73 3c 2f 68  g of Polygons</h
3ea0: 32 3e 0a 0a 3c 70 3e 0a 47 65 6f 70 6f 6c 79 20  2>..<p>.Geopoly 
3eb0: 73 74 6f 72 65 73 20 61 6c 6c 20 70 6f 6c 79 67  stores all polyg
3ec0: 6f 6e 73 20 69 6e 74 65 72 6e 61 6c 6c 79 20 75  ons internally u
3ed0: 73 69 6e 67 20 61 20 62 69 6e 61 72 79 20 66 6f  sing a binary fo
3ee0: 72 6d 61 74 2e 20 20 41 20 62 69 6e 61 72 79 0a  rmat.  A binary.
3ef0: 70 6f 6c 79 67 6f 6e 20 63 6f 6e 73 69 73 74 73  polygon consists
3f00: 20 6f 66 20 61 20 34 2d 62 79 74 65 20 68 65 61   of a 4-byte hea
3f10: 64 65 72 20 66 6f 6c 6c 6f 77 69 6e 67 20 62 79  der following by
3f20: 20 61 6e 20 61 72 72 61 79 20 6f 66 20 63 6f 6f   an array of coo
3f30: 72 64 69 6e 61 74 65 0a 70 61 69 72 73 20 69 6e  rdinate.pairs in
3f40: 20 77 68 69 63 68 20 65 61 63 68 20 64 69 6d 65   which each dime
3f50: 6e 73 69 6f 6e 20 6f 66 20 65 61 63 68 20 63 6f  nsion of each co
3f60: 6f 72 64 69 6e 61 74 65 20 69 73 20 61 20 33 32  ordinate is a 32
3f70: 2d 62 69 74 20 66 6c 6f 61 74 69 6e 67 20 70 6f  -bit floating po
3f80: 69 6e 74 0a 6e 75 6d 62 65 72 2e 0a 0a 3c 70 3e  int.number...<p>
3f90: 0a 54 68 65 20 66 69 72 73 74 20 62 79 74 65 20  .The first byte 
3fa0: 6f 66 20 74 68 65 20 68 65 61 64 65 72 20 69 73  of the header is
3fb0: 20 61 20 66 6c 61 67 20 62 79 74 65 2e 20 20 54   a flag byte.  T
3fc0: 68 65 20 6c 65 61 73 74 20 73 69 67 6e 69 66 69  he least signifi
3fd0: 63 61 6e 74 20 62 69 74 0a 6f 66 20 74 68 65 20  cant bit.of the 
3fe0: 66 6c 61 67 20 62 79 74 65 20 64 65 74 65 72 6d  flag byte determ
3ff0: 69 6e 65 73 20 77 68 65 74 68 65 72 20 74 68 65  ines whether the
4000: 20 63 6f 6f 72 64 69 6e 61 74 65 20 70 61 69 72   coordinate pair
4010: 73 20 74 68 61 74 20 66 6f 6c 6c 6f 77 20 74 68  s that follow th
4020: 65 0a 68 65 61 64 65 72 20 61 72 65 20 73 74 6f  e.header are sto
4030: 72 65 64 20 62 69 67 2d 65 6e 64 69 61 6e 20 6f  red big-endian o
4040: 72 20 6c 69 74 74 6c 65 2d 65 6e 64 69 61 6e 2e  r little-endian.
4050: 20 20 41 20 76 61 6c 75 65 20 6f 66 20 30 20 66    A value of 0 f
4060: 6f 72 20 74 68 65 20 6c 65 61 73 74 0a 73 69 67  or the least.sig
4070: 6e 69 66 69 63 61 6e 74 20 62 69 74 20 6d 65 61  nificant bit mea
4080: 6e 73 20 62 69 67 2d 65 6e 64 69 61 6e 20 61 6e  ns big-endian an
4090: 64 20 61 20 76 61 6c 75 65 20 6f 66 20 31 20 6d  d a value of 1 m
40a0: 65 61 6e 73 20 6c 69 74 74 6c 65 20 65 6e 64 69  eans little endi
40b0: 61 6e 2e 0a 4f 74 68 65 72 20 62 69 74 73 20 6f  an..Other bits o
40c0: 66 20 74 68 65 20 66 69 72 73 74 20 62 79 74 65  f the first byte
40d0: 20 69 6e 20 74 68 65 20 68 65 61 64 65 72 20 61   in the header a
40e0: 72 65 20 72 65 73 65 72 76 65 64 20 66 6f 72 20  re reserved for 
40f0: 66 75 74 75 72 65 20 65 78 70 61 6e 73 69 6f 6e  future expansion
4100: 2e 0a 0a 3c 70 3e 0a 54 68 65 20 6e 65 78 74 20  ...<p>.The next 
4110: 74 68 72 65 65 20 62 79 74 65 73 20 69 6e 20 74  three bytes in t
4120: 68 65 20 68 65 61 64 65 72 20 72 65 63 6f 72 64  he header record
4130: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 76   the number of v
4140: 65 72 74 65 78 65 73 20 69 6e 20 74 68 65 20 70  ertexes in the p
4150: 6f 6c 79 67 6f 6e 0a 61 73 20 61 20 62 69 67 2d  olygon.as a big-
4160: 65 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 2e 20  endian integer. 
4170: 20 54 68 75 73 20 74 68 65 72 65 20 69 73 20 61   Thus there is a
4180: 6e 20 75 70 70 65 72 20 62 6f 75 6e 64 20 6f 66  n upper bound of
4190: 20 61 62 6f 75 74 20 31 36 20 6d 69 6c 6c 69 6f   about 16 millio
41a0: 6e 0a 76 65 72 74 65 78 65 73 20 70 65 72 20 70  n.vertexes per p
41b0: 6f 6c 79 67 6f 6e 2e 0a 0a 3c 70 3e 0a 46 6f 6c  olygon...<p>.Fol
41c0: 6c 6f 77 69 6e 67 20 74 68 65 20 68 65 61 64 65  lowing the heade
41d0: 72 20 69 73 20 74 68 65 20 61 72 72 61 79 20 6f  r is the array o
41e0: 66 20 63 6f 6f 72 64 69 6e 61 74 65 20 70 61 69  f coordinate pai
41f0: 72 73 2e 20 20 45 61 63 68 20 63 6f 6f 72 64 69  rs.  Each coordi
4200: 6e 61 74 65 20 69 73 0a 61 20 33 32 2d 62 69 74  nate is.a 32-bit
4210: 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69 6e 74 20   floating point 
4220: 6e 75 6d 62 65 72 2e 20 20 54 68 65 20 75 73 65  number.  The use
4230: 20 6f 66 20 33 32 2d 62 69 74 20 66 6c 6f 61 74   of 32-bit float
4240: 69 6e 67 20 70 6f 69 6e 74 20 76 61 6c 75 65 73  ing point values
4250: 20 66 6f 72 0a 63 6f 6f 72 64 69 6e 61 74 65 73   for.coordinates
4260: 20 6d 65 61 6e 73 20 74 68 61 74 20 61 6e 79 20   means that any 
4270: 70 6f 69 6e 74 20 6f 6e 20 74 68 65 20 65 61 72  point on the ear
4280: 74 68 27 73 20 73 75 72 66 61 63 65 20 63 61 6e  th's surface can
4290: 20 62 65 20 6d 61 70 70 65 64 20 77 69 74 68 0a   be mapped with.
42a0: 61 20 72 65 73 6f 6c 75 74 69 6f 6e 20 6f 66 20  a resolution of 
42b0: 61 70 70 72 6f 78 69 6d 61 74 65 6c 79 20 32 2e  approximately 2.
42c0: 35 20 6d 65 74 65 72 73 2e 20 20 48 69 67 68 65  5 meters.  Highe
42d0: 72 20 72 65 73 6f 6c 75 74 69 6f 6e 73 20 61 72  r resolutions ar
42e0: 65 20 6f 66 20 63 6f 75 72 73 65 0a 70 6f 73 73  e of course.poss
42f0: 69 62 6c 65 20 69 66 20 74 68 65 20 6d 61 70 20  ible if the map 
4300: 69 73 20 72 65 73 74 72 69 63 74 65 64 20 74 6f  is restricted to
4310: 20 61 20 73 69 6e 67 6c 65 20 63 6f 6e 74 69 6e   a single contin
4320: 65 6e 74 20 6f 72 20 63 6f 75 6e 74 72 79 2e 0a  ent or country..
4330: 4e 6f 74 65 20 74 68 61 74 20 74 68 65 20 72 65  Note that the re
4340: 73 6f 6c 75 74 69 6f 6e 20 6f 66 20 63 6f 6f 72  solution of coor
4350: 64 69 6e 61 74 65 73 20 69 6e 20 74 68 65 20 67  dinates in the g
4360: 65 6f 70 6f 6c 79 20 6d 6f 64 75 6c 65 20 69 73  eopoly module is
4370: 20 73 69 6d 69 6c 61 72 0a 69 6e 20 6d 61 67 6e   similar.in magn
4380: 69 74 75 64 65 20 74 6f 20 64 61 69 6c 79 20 6d  itude to daily m
4390: 6f 76 65 6d 65 6e 74 20 6f 66 20 70 6f 69 6e 74  ovement of point
43a0: 73 20 6f 6e 20 74 68 65 20 65 61 72 74 68 27 73  s on the earth's
43b0: 20 73 75 72 66 61 63 65 20 64 75 65 20 74 6f 0a   surface due to.
43c0: 74 69 64 61 6c 20 66 6f 72 63 65 73 2e 0a 0a 3c  tidal forces...<
43d0: 70 3e 0a 54 68 65 20 6c 69 73 74 20 6f 66 20 63  p>.The list of c
43e0: 6f 6f 72 64 69 6e 61 74 65 73 20 69 6e 20 74 68  oordinates in th
43f0: 65 20 62 69 6e 61 72 79 20 66 6f 72 6d 61 74 20  e binary format 
4400: 63 6f 6e 74 61 69 6e 73 20 6e 6f 20 72 65 64 75  contains no redu
4410: 6e 64 61 6e 63 79 2e 20 20 0a 54 68 65 20 6c 61  ndancy.  .The la
4420: 73 74 20 63 6f 6f 72 64 69 6e 61 74 65 20 69 73  st coordinate is
4430: 20 6e 6f 74 20 61 20 72 65 70 65 61 74 20 6f 66   not a repeat of
4440: 20 74 68 65 20 66 69 72 73 74 20 61 73 20 69 74   the first as it
4450: 20 69 73 20 77 69 74 68 20 47 65 6f 4a 53 4f 4e   is with GeoJSON
4460: 2e 20 20 0a 48 65 6e 63 65 2c 20 74 68 65 72 65  .  .Hence, there
4470: 20 69 73 20 61 6c 77 61 79 73 20 6f 6e 65 20 66   is always one f
4480: 65 77 65 72 20 63 6f 6f 72 64 69 6e 61 74 65 20  ewer coordinate 
4490: 70 61 69 72 20 69 6e 20 74 68 65 20 62 69 6e 61  pair in the bina
44a0: 72 79 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f  ry representatio
44b0: 6e 20 6f 66 0a 61 20 70 6f 6c 79 67 6f 6e 20 63  n of.a polygon c
44c0: 6f 6d 70 61 72 65 64 20 74 6f 20 74 68 65 20 47  ompared to the G
44d0: 65 6f 4a 53 4f 4e 20 72 65 70 72 65 73 65 6e 74  eoJSON represent
44e0: 61 74 69 6f 6e 2e 0a 0a 3c 68 32 3e 53 68 61 64  ation...<h2>Shad
44f0: 6f 77 20 54 61 62 6c 65 73 3c 2f 68 32 3e 0a 0a  ow Tables</h2>..
4500: 3c 70 3e 0a 54 68 65 20 67 65 6f 70 6f 6c 79 20  <p>.The geopoly 
4510: 6d 6f 64 75 6c 65 20 69 73 20 62 75 69 6c 74 20  module is built 
4520: 6f 6e 20 74 6f 70 20 6f 66 20 74 68 65 20 5b 52  on top of the [R
4530: 2d 54 72 65 65 20 65 78 74 65 6e 73 69 6f 6e 5d  -Tree extension]
4540: 20 61 6e 64 20 75 73 65 73 20 74 68 65 0a 73 61   and uses the.sa
4550: 6d 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 73 68  me underlying sh
4560: 61 64 6f 77 20 74 61 62 6c 65 73 20 61 6e 64 20  adow tables and 
4570: 61 6c 67 6f 72 69 74 68 6d 73 2e 20 20 46 6f 72  algorithms.  For
4580: 20 69 6e 64 65 78 69 6e 67 20 70 75 72 70 6f 73   indexing purpos
4590: 65 73 2c 20 65 61 63 68 0a 70 6f 6c 79 67 6f 6e  es, each.polygon
45a0: 20 69 73 20 72 65 70 72 65 73 65 6e 74 65 64 20   is represented 
45b0: 69 6e 20 74 68 65 20 73 68 61 64 6f 77 20 74 61  in the shadow ta
45c0: 62 6c 65 73 20 61 73 20 61 20 72 65 63 74 61 6e  bles as a rectan
45d0: 67 75 6c 61 72 20 62 6f 75 6e 64 69 6e 67 20 62  gular bounding b
45e0: 6f 78 2e 0a 54 68 65 20 75 6e 64 65 72 6c 79 69  ox..The underlyi
45f0: 6e 67 20 52 2d 54 72 65 65 20 69 6d 70 6c 65 6d  ng R-Tree implem
4600: 65 6e 74 61 74 69 6f 6e 20 75 73 65 73 20 62 6f  entation uses bo
4610: 75 6e 64 69 6e 67 20 62 6f 78 65 73 20 74 6f 20  unding boxes to 
4620: 6c 69 6d 69 74 20 74 68 65 20 73 65 61 72 63 68  limit the search
4630: 0a 73 70 61 63 65 2e 20 20 54 68 65 6e 20 74 68  .space.  Then th
4640: 65 20 67 65 6f 70 6c 6f 79 5f 6f 76 65 72 6c 61  e geoploy_overla
4650: 70 28 29 20 61 6e 64 2f 6f 72 20 67 65 6f 70 6f  p() and/or geopo
4660: 6c 79 5f 77 69 74 68 69 6e 28 29 20 72 6f 75 74  ly_within() rout
4670: 69 6e 65 73 20 66 75 72 74 68 65 72 0a 72 65 66  ines further.ref
4680: 69 6e 65 20 74 68 65 20 73 65 61 72 63 68 20 74  ine the search t
4690: 6f 20 74 68 65 20 65 78 61 63 74 20 61 6e 73 77  o the exact answ
46a0: 65 72 2e 0a                                      er..