{"version":3,"sources":["../../index.ts"],"sourcesContent":["// http://en.wikipedia.org/wiki/Delaunay_triangulation\n// https://github.com/ironwallaby/delaunay\nimport { FeatureCollection, Point, Polygon } from \"geojson\";\nimport { featureCollection, polygon } from \"@turf/helpers\";\n\ninterface Pt {\n  x: number;\n  y: number;\n  z?: number;\n  __sentinel?: boolean;\n}\ninterface Vertice {\n  x: number;\n  y: number;\n}\n\n/**\n * Takes a set of {@link Point|points} and creates a\n * [Triangulated Irregular Network](http://en.wikipedia.org/wiki/Triangulated_irregular_network),\n * or a TIN for short, returned as a collection of Polygons. These are often used\n * for developing elevation contour maps or stepped heat visualizations.\n *\n * If an optional z-value property is provided then it is added as properties called `a`, `b`,\n * and `c` representing its value at each of the points that represent the corners of the\n * triangle.\n *\n * @function\n * @param {FeatureCollection<Point>} points input points\n * @param {String} [z] name of the property from which to pull z values\n * This is optional: if not given, then there will be no extra data added to the derived triangles.\n * @returns {FeatureCollection<Polygon>} TIN output\n * @example\n * // generate some random point data\n * var points = turf.randomPoint(30, {bbox: [50, 30, 70, 50]});\n *\n * // add a random property to each point between 0 and 9\n * for (var i = 0; i < points.features.length; i++) {\n *   points.features[i].properties.z = ~~(Math.random() * 9);\n * }\n * var tin = turf.tin(points, 'z');\n *\n * //addToMap\n * var addToMap = [tin, points]\n * for (var i = 0; i < tin.features.length; i++) {\n *   var properties  = tin.features[i].properties;\n *   properties.fill = '#' + properties.a + properties.b + properties.c;\n * }\n */\nfunction tin(\n  points: FeatureCollection<Point, any>,\n  z?: string\n): FeatureCollection<Polygon> {\n  // break down points\n  let isPointZ = false;\n  return featureCollection(\n    triangulate(\n      points.features.map((p) => {\n        const point: Pt = {\n          x: p.geometry.coordinates[0],\n          y: p.geometry.coordinates[1],\n        };\n        if (z) {\n          point.z = p.properties[z];\n        } else if (p.geometry.coordinates.length === 3) {\n          isPointZ = true;\n          point.z = p.geometry.coordinates[2];\n        }\n        return point;\n      })\n    ).map((triangle: any) => {\n      const a = [triangle.a.x, triangle.a.y];\n      const b = [triangle.b.x, triangle.b.y];\n      const c = [triangle.c.x, triangle.c.y];\n      let properties = {};\n\n      // Add z coordinates to triangle points if user passed\n      // them in that way otherwise add it as a property.\n      if (isPointZ) {\n        a.push(triangle.a.z);\n        b.push(triangle.b.z);\n        c.push(triangle.c.z);\n      } else {\n        properties = {\n          a: triangle.a.z,\n          b: triangle.b.z,\n          c: triangle.c.z,\n        };\n      }\n\n      return polygon([[a, b, c, a]], properties);\n    })\n  );\n}\n\nclass Triangle {\n  public a: Pt;\n  public b: Pt;\n  public c: Pt;\n  public x: number;\n  public y: number;\n  public r: number;\n\n  constructor(a: Pt, b: Pt, c: Pt) {\n    this.a = a;\n    this.b = b;\n    this.c = c;\n\n    const A = b.x - a.x;\n    const B = b.y - a.y;\n    const C = c.x - a.x;\n    const D = c.y - a.y;\n    const E = A * (a.x + b.x) + B * (a.y + b.y);\n    const F = C * (a.x + c.x) + D * (a.y + c.y);\n    const G = 2 * (A * (c.y - b.y) - B * (c.x - b.x));\n    let dx;\n    let dy;\n\n    // If the points of the triangle are collinear, then just find the\n    // extremes and use the midpoint as the center of the circumcircle.\n    this.x = (D * E - B * F) / G;\n    this.y = (A * F - C * E) / G;\n    dx = this.x - a.x;\n    dy = this.y - a.y;\n    this.r = dx * dx + dy * dy;\n  }\n}\n\nfunction byX(a: Pt, b: Pt) {\n  return b.x - a.x;\n}\n\nfunction dedup(edges: number[]) {\n  let j = edges.length;\n  let a;\n  let b;\n  let i;\n  let m;\n  let n;\n\n  outer: while (j) {\n    b = edges[--j];\n    a = edges[--j];\n    i = j;\n    while (i) {\n      n = edges[--i];\n      m = edges[--i];\n      if ((a === m && b === n) || (a === n && b === m)) {\n        edges.splice(j, 2);\n        edges.splice(i, 2);\n        j -= 2;\n        continue outer;\n      }\n    }\n  }\n}\n\nfunction triangulate(vertices: Vertice[]) {\n  // Bail if there aren't enough vertices to form any triangles.\n  if (vertices.length < 3) {\n    return [];\n  }\n\n  // Ensure the vertex array is in order of descending X coordinate\n  // (which is needed to ensure a subquadratic runtime), and then find\n  // the bounding box around the points.\n  vertices.sort(byX);\n\n  let i = vertices.length - 1;\n  const xmin = vertices[i].x;\n  const xmax = vertices[0].x;\n  let ymin = vertices[i].y;\n  let ymax = ymin;\n  const epsilon = 1e-12;\n\n  let a;\n  let b;\n  let c;\n  let A;\n  let B;\n  let G;\n\n  while (i--) {\n    if (vertices[i].y < ymin) {\n      ymin = vertices[i].y;\n    }\n    if (vertices[i].y > ymax) {\n      ymax = vertices[i].y;\n    }\n  }\n\n  // Find a supertriangle, which is a triangle that surrounds all the\n  // vertices. This is used like something of a sentinel value to remove\n  // cases in the main algorithm, and is removed before we return any\n  // results.\n\n  // Once found, put it in the \"open\" list. (The \"open\" list is for\n  // triangles who may still need to be considered; the \"closed\" list is\n  // for triangles which do not.)\n  let dx = xmax - xmin;\n  let dy = ymax - ymin;\n  const dmax = dx > dy ? dx : dy;\n  const xmid = (xmax + xmin) * 0.5;\n  const ymid = (ymax + ymin) * 0.5;\n  const open = [\n    new Triangle(\n      {\n        __sentinel: true,\n        x: xmid - 20 * dmax,\n        y: ymid - dmax,\n      },\n      {\n        __sentinel: true,\n        x: xmid,\n        y: ymid + 20 * dmax,\n      },\n      {\n        __sentinel: true,\n        x: xmid + 20 * dmax,\n        y: ymid - dmax,\n      }\n    ),\n  ];\n  const closed = [];\n  const edges: any = [];\n  let j;\n\n  // Incrementally add each vertex to the mesh.\n  i = vertices.length;\n  while (i--) {\n    // For each open triangle, check to see if the current point is\n    // inside it's circumcircle. If it is, remove the triangle and add\n    // it's edges to an edge list.\n    edges.length = 0;\n    j = open.length;\n    while (j--) {\n      // If this point is to the right of this triangle's circumcircle,\n      // then this triangle should never get checked again. Remove it\n      // from the open list, add it to the closed list, and skip.\n      dx = vertices[i].x - open[j].x;\n      if (dx > 0 && dx * dx > open[j].r) {\n        closed.push(open[j]);\n        open.splice(j, 1);\n        continue;\n      }\n\n      // If not, skip this triangle.\n      dy = vertices[i].y - open[j].y;\n      if (dx * dx + dy * dy > open[j].r) {\n        continue;\n      }\n\n      // Remove the triangle and add it's edges to the edge list.\n      edges.push(\n        open[j].a,\n        open[j].b,\n        open[j].b,\n        open[j].c,\n        open[j].c,\n        open[j].a\n      );\n      open.splice(j, 1);\n    }\n\n    // Remove any doubled edges.\n    dedup(edges);\n\n    // Add a new triangle for each edge.\n    j = edges.length;\n    while (j) {\n      b = edges[--j];\n      a = edges[--j];\n      c = vertices[i];\n      // Avoid adding colinear triangles (which have error-prone\n      // circumcircles)\n      A = b.x - a.x;\n      B = b.y - a.y;\n      G = 2 * (A * (c.y - b.y) - B * (c.x - b.x));\n      if (Math.abs(G) > epsilon) {\n        open.push(new Triangle(a, b, c));\n      }\n    }\n  }\n\n  // Copy any remaining open triangles to the closed list, and then\n  // remove any triangles that share a vertex with the supertriangle.\n  Array.prototype.push.apply(closed, open);\n\n  i = closed.length;\n  while (i--) {\n    if (\n      closed[i].a.__sentinel ||\n      closed[i].b.__sentinel ||\n      closed[i].c.__sentinel\n    ) {\n      closed.splice(i, 1);\n    }\n  }\n\n  return closed;\n}\n\nexport { Pt, Vertice, tin };\nexport default tin;\n"],"mappings":";AAGA,SAAS,mBAAmB,eAAe;AA6C3C,SAAS,IACP,QACA,GAC4B;AAE5B,MAAI,WAAW;AACf,SAAO;AAAA,IACL;AAAA,MACE,OAAO,SAAS,IAAI,CAAC,MAAM;AACzB,cAAM,QAAY;AAAA,UAChB,GAAG,EAAE,SAAS,YAAY,CAAC;AAAA,UAC3B,GAAG,EAAE,SAAS,YAAY,CAAC;AAAA,QAC7B;AACA,YAAI,GAAG;AACL,gBAAM,IAAI,EAAE,WAAW,CAAC;AAAA,QAC1B,WAAW,EAAE,SAAS,YAAY,WAAW,GAAG;AAC9C,qBAAW;AACX,gBAAM,IAAI,EAAE,SAAS,YAAY,CAAC;AAAA,QACpC;AACA,eAAO;AAAA,MACT,CAAC;AAAA,IACH,EAAE,IAAI,CAAC,aAAkB;AACvB,YAAM,IAAI,CAAC,SAAS,EAAE,GAAG,SAAS,EAAE,CAAC;AACrC,YAAM,IAAI,CAAC,SAAS,EAAE,GAAG,SAAS,EAAE,CAAC;AACrC,YAAM,IAAI,CAAC,SAAS,EAAE,GAAG,SAAS,EAAE,CAAC;AACrC,UAAI,aAAa,CAAC;AAIlB,UAAI,UAAU;AACZ,UAAE,KAAK,SAAS,EAAE,CAAC;AACnB,UAAE,KAAK,SAAS,EAAE,CAAC;AACnB,UAAE,KAAK,SAAS,EAAE,CAAC;AAAA,MACrB,OAAO;AACL,qBAAa;AAAA,UACX,GAAG,SAAS,EAAE;AAAA,UACd,GAAG,SAAS,EAAE;AAAA,UACd,GAAG,SAAS,EAAE;AAAA,QAChB;AAAA,MACF;AAEA,aAAO,QAAQ,CAAC,CAAC,GAAG,GAAG,GAAG,CAAC,CAAC,GAAG,UAAU;AAAA,IAC3C,CAAC;AAAA,EACH;AACF;AAEA,IAAM,WAAN,MAAe;AAAA,EAQb,YAAY,GAAO,GAAO,GAAO;AAC/B,SAAK,IAAI;AACT,SAAK,IAAI;AACT,SAAK,IAAI;AAET,UAAM,IAAI,EAAE,IAAI,EAAE;AAClB,UAAM,IAAI,EAAE,IAAI,EAAE;AAClB,UAAM,IAAI,EAAE,IAAI,EAAE;AAClB,UAAM,IAAI,EAAE,IAAI,EAAE;AAClB,UAAM,IAAI,KAAK,EAAE,IAAI,EAAE,KAAK,KAAK,EAAE,IAAI,EAAE;AACzC,UAAM,IAAI,KAAK,EAAE,IAAI,EAAE,KAAK,KAAK,EAAE,IAAI,EAAE;AACzC,UAAM,IAAI,KAAK,KAAK,EAAE,IAAI,EAAE,KAAK,KAAK,EAAE,IAAI,EAAE;AAC9C,QAAI;AACJ,QAAI;AAIJ,SAAK,KAAK,IAAI,IAAI,IAAI,KAAK;AAC3B,SAAK,KAAK,IAAI,IAAI,IAAI,KAAK;AAC3B,SAAK,KAAK,IAAI,EAAE;AAChB,SAAK,KAAK,IAAI,EAAE;AAChB,SAAK,IAAI,KAAK,KAAK,KAAK;AAAA,EAC1B;AACF;AAEA,SAAS,IAAI,GAAO,GAAO;AACzB,SAAO,EAAE,IAAI,EAAE;AACjB;AAEA,SAAS,MAAM,OAAiB;AAC9B,MAAI,IAAI,MAAM;AACd,MAAI;AACJ,MAAI;AACJ,MAAI;AACJ,MAAI;AACJ,MAAI;AAEJ,QAAO,QAAO,GAAG;AACf,QAAI,MAAM,EAAE,CAAC;AACb,QAAI,MAAM,EAAE,CAAC;AACb,QAAI;AACJ,WAAO,GAAG;AACR,UAAI,MAAM,EAAE,CAAC;AACb,UAAI,MAAM,EAAE,CAAC;AACb,UAAK,MAAM,KAAK,MAAM,KAAO,MAAM,KAAK,MAAM,GAAI;AAChD,cAAM,OAAO,GAAG,CAAC;AACjB,cAAM,OAAO,GAAG,CAAC;AACjB,aAAK;AACL,iBAAS;AAAA,MACX;AAAA,IACF;AAAA,EACF;AACF;AAEA,SAAS,YAAY,UAAqB;AAExC,MAAI,SAAS,SAAS,GAAG;AACvB,WAAO,CAAC;AAAA,EACV;AAKA,WAAS,KAAK,GAAG;AAEjB,MAAI,IAAI,SAAS,SAAS;AAC1B,QAAM,OAAO,SAAS,CAAC,EAAE;AACzB,QAAM,OAAO,SAAS,CAAC,EAAE;AACzB,MAAI,OAAO,SAAS,CAAC,EAAE;AACvB,MAAI,OAAO;AACX,QAAM,UAAU;AAEhB,MAAI;AACJ,MAAI;AACJ,MAAI;AACJ,MAAI;AACJ,MAAI;AACJ,MAAI;AAEJ,SAAO,KAAK;AACV,QAAI,SAAS,CAAC,EAAE,IAAI,MAAM;AACxB,aAAO,SAAS,CAAC,EAAE;AAAA,IACrB;AACA,QAAI,SAAS,CAAC,EAAE,IAAI,MAAM;AACxB,aAAO,SAAS,CAAC,EAAE;AAAA,IACrB;AAAA,EACF;AAUA,MAAI,KAAK,OAAO;AAChB,MAAI,KAAK,OAAO;AAChB,QAAM,OAAO,KAAK,KAAK,KAAK;AAC5B,QAAM,QAAQ,OAAO,QAAQ;AAC7B,QAAM,QAAQ,OAAO,QAAQ;AAC7B,QAAM,OAAO;AAAA,IACX,IAAI;AAAA,MACF;AAAA,QACE,YAAY;AAAA,QACZ,GAAG,OAAO,KAAK;AAAA,QACf,GAAG,OAAO;AAAA,MACZ;AAAA,MACA;AAAA,QACE,YAAY;AAAA,QACZ,GAAG;AAAA,QACH,GAAG,OAAO,KAAK;AAAA,MACjB;AAAA,MACA;AAAA,QACE,YAAY;AAAA,QACZ,GAAG,OAAO,KAAK;AAAA,QACf,GAAG,OAAO;AAAA,MACZ;AAAA,IACF;AAAA,EACF;AACA,QAAM,SAAS,CAAC;AAChB,QAAM,QAAa,CAAC;AACpB,MAAI;AAGJ,MAAI,SAAS;AACb,SAAO,KAAK;AAIV,UAAM,SAAS;AACf,QAAI,KAAK;AACT,WAAO,KAAK;AAIV,WAAK,SAAS,CAAC,EAAE,IAAI,KAAK,CAAC,EAAE;AAC7B,UAAI,KAAK,KAAK,KAAK,KAAK,KAAK,CAAC,EAAE,GAAG;AACjC,eAAO,KAAK,KAAK,CAAC,CAAC;AACnB,aAAK,OAAO,GAAG,CAAC;AAChB;AAAA,MACF;AAGA,WAAK,SAAS,CAAC,EAAE,IAAI,KAAK,CAAC,EAAE;AAC7B,UAAI,KAAK,KAAK,KAAK,KAAK,KAAK,CAAC,EAAE,GAAG;AACjC;AAAA,MACF;AAGA,YAAM;AAAA,QACJ,KAAK,CAAC,EAAE;AAAA,QACR,KAAK,CAAC,EAAE;AAAA,QACR,KAAK,CAAC,EAAE;AAAA,QACR,KAAK,CAAC,EAAE;AAAA,QACR,KAAK,CAAC,EAAE;AAAA,QACR,KAAK,CAAC,EAAE;AAAA,MACV;AACA,WAAK,OAAO,GAAG,CAAC;AAAA,IAClB;AAGA,UAAM,KAAK;AAGX,QAAI,MAAM;AACV,WAAO,GAAG;AACR,UAAI,MAAM,EAAE,CAAC;AACb,UAAI,MAAM,EAAE,CAAC;AACb,UAAI,SAAS,CAAC;AAGd,UAAI,EAAE,IAAI,EAAE;AACZ,UAAI,EAAE,IAAI,EAAE;AACZ,UAAI,KAAK,KAAK,EAAE,IAAI,EAAE,KAAK,KAAK,EAAE,IAAI,EAAE;AACxC,UAAI,KAAK,IAAI,CAAC,IAAI,SAAS;AACzB,aAAK,KAAK,IAAI,SAAS,GAAG,GAAG,CAAC,CAAC;AAAA,MACjC;AAAA,IACF;AAAA,EACF;AAIA,QAAM,UAAU,KAAK,MAAM,QAAQ,IAAI;AAEvC,MAAI,OAAO;AACX,SAAO,KAAK;AACV,QACE,OAAO,CAAC,EAAE,EAAE,cACZ,OAAO,CAAC,EAAE,EAAE,cACZ,OAAO,CAAC,EAAE,EAAE,YACZ;AACA,aAAO,OAAO,GAAG,CAAC;AAAA,IACpB;AAAA,EACF;AAEA,SAAO;AACT;AAGA,IAAO,mBAAQ;","names":[]}