"use strict";Object.defineProperty(exports, "__esModule", {value: true});// index.ts
var _helpers = require('@turf/helpers');

// lib/util.ts
var _booleanpointinpolygon = require('@turf/boolean-point-in-polygon');

function mathSign(x) {
  return (x > 0) - (x < 0) || +x;
}
function orientationIndex(p1, p2, q) {
  const dx1 = p2[0] - p1[0], dy1 = p2[1] - p1[1], dx2 = q[0] - p2[0], dy2 = q[1] - p2[1];
  return mathSign(dx1 * dy2 - dx2 * dy1);
}
function envelopeIsEqual(env1, env2) {
  const envX1 = env1.geometry.coordinates[0].map((c) => c[0]), envY1 = env1.geometry.coordinates[0].map((c) => c[1]), envX2 = env2.geometry.coordinates[0].map((c) => c[0]), envY2 = env2.geometry.coordinates[0].map((c) => c[1]);
  return Math.max.apply(null, envX1) === Math.max.apply(null, envX2) && Math.max.apply(null, envY1) === Math.max.apply(null, envY2) && Math.min.apply(null, envX1) === Math.min.apply(null, envX2) && Math.min.apply(null, envY1) === Math.min.apply(null, envY2);
}
function envelopeContains(self, env) {
  return env.geometry.coordinates[0].every(
    (c) => _booleanpointinpolygon.booleanPointInPolygon.call(void 0, _helpers.point.call(void 0, c), self)
  );
}
function coordinatesEqual(coord1, coord2) {
  return coord1[0] === coord2[0] && coord1[1] === coord2[1];
}

// lib/Node.ts
var Node = class _Node {
  static buildId(coordinates) {
    return coordinates.join(",");
  }
  constructor(coordinates) {
    this.id = _Node.buildId(coordinates);
    this.coordinates = coordinates;
    this.innerEdges = [];
    this.outerEdges = [];
    this.outerEdgesSorted = false;
  }
  removeInnerEdge(edge) {
    this.innerEdges = this.innerEdges.filter((e) => e.from.id !== edge.from.id);
  }
  removeOuterEdge(edge) {
    this.outerEdges = this.outerEdges.filter((e) => e.to.id !== edge.to.id);
  }
  /**
   * Outer edges are stored CCW order.
   *
   * @memberof Node
   * @param {Edge} edge - Edge to add as an outerEdge.
   */
  addOuterEdge(edge) {
    this.outerEdges.push(edge);
    this.outerEdgesSorted = false;
  }
  /**
   * Sorts outer edges in CCW way.
   *
   * @memberof Node
   * @private
   */
  sortOuterEdges() {
    if (!this.outerEdgesSorted) {
      this.outerEdges.sort((a, b) => {
        const aNode = a.to, bNode = b.to;
        if (aNode.coordinates[0] - this.coordinates[0] >= 0 && bNode.coordinates[0] - this.coordinates[0] < 0)
          return 1;
        if (aNode.coordinates[0] - this.coordinates[0] < 0 && bNode.coordinates[0] - this.coordinates[0] >= 0)
          return -1;
        if (aNode.coordinates[0] - this.coordinates[0] === 0 && bNode.coordinates[0] - this.coordinates[0] === 0) {
          if (aNode.coordinates[1] - this.coordinates[1] >= 0 || bNode.coordinates[1] - this.coordinates[1] >= 0)
            return aNode.coordinates[1] - bNode.coordinates[1];
          return bNode.coordinates[1] - aNode.coordinates[1];
        }
        const det = orientationIndex(
          this.coordinates,
          aNode.coordinates,
          bNode.coordinates
        );
        if (det < 0)
          return 1;
        if (det > 0)
          return -1;
        const d1 = Math.pow(aNode.coordinates[0] - this.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - this.coordinates[1], 2), d2 = Math.pow(bNode.coordinates[0] - this.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - this.coordinates[1], 2);
        return d1 - d2;
      });
      this.outerEdgesSorted = true;
    }
  }
  /**
   * Retrieves outer edges.
   *
   * They are sorted if they aren't in the CCW order.
   *
   * @memberof Node
   * @returns {Edge[]} - List of outer edges sorted in a CCW order.
   */
  getOuterEdges() {
    this.sortOuterEdges();
    return this.outerEdges;
  }
  getOuterEdge(i) {
    this.sortOuterEdges();
    return this.outerEdges[i];
  }
  addInnerEdge(edge) {
    this.innerEdges.push(edge);
  }
};

// lib/Edge.ts

var Edge = class _Edge {
  /**
   * Creates or get the symetric Edge.
   *
   * @returns {Edge} - Symetric Edge.
   */
  getSymetric() {
    if (!this.symetric) {
      this.symetric = new _Edge(this.to, this.from);
      this.symetric.symetric = this;
    }
    return this.symetric;
  }
  /**
   * @param {Node} from - start node of the Edge
   * @param {Node} to - end node of the edge
   */
  constructor(from, to) {
    this.from = from;
    this.to = to;
    this.next = void 0;
    this.label = void 0;
    this.symetric = void 0;
    this.ring = void 0;
    this.from.addOuterEdge(this);
    this.to.addInnerEdge(this);
  }
  /**
   * Removes edge from from and to nodes.
   */
  deleteEdge() {
    this.from.removeOuterEdge(this);
    this.to.removeInnerEdge(this);
  }
  /**
   * Compares Edge equallity.
   *
   * An edge is equal to another, if the from and to nodes are the same.
   *
   * @param {Edge} edge - Another Edge
   * @returns {boolean} - True if Edges are equal, False otherwise
   */
  isEqual(edge) {
    return this.from.id === edge.from.id && this.to.id === edge.to.id;
  }
  toString() {
    return `Edge { ${this.from.id} -> ${this.to.id} }`;
  }
  /**
   * Returns a LineString representation of the Edge
   *
   * @returns {Feature<LineString>} - LineString representation of the Edge
   */
  toLineString() {
    return _helpers.lineString.call(void 0, [this.from.coordinates, this.to.coordinates]);
  }
  /**
   * Comparator of two edges.
   *
   * Implementation of geos::planargraph::DirectedEdge::compareTo.
   *
   * @param {Edge} edge - Another edge to compare with this one
   * @returns {number} -1 if this Edge has a greater angle with the positive x-axis than b,
   *          0 if the Edges are colinear,
   *          1 otherwise
   */
  compareTo(edge) {
    return orientationIndex(
      edge.from.coordinates,
      edge.to.coordinates,
      this.to.coordinates
    );
  }
};

// lib/EdgeRing.ts

var _envelope = require('@turf/envelope');

var EdgeRing = class {
  constructor() {
    this.edges = [];
    this.polygon = void 0;
    this.envelope = void 0;
  }
  /**
   * Add an edge to the ring, inserting it in the last position.
   *
   * @memberof EdgeRing
   * @param {Edge} edge - Edge to be inserted
   */
  push(edge) {
    this.edges.push(edge);
    this.polygon = this.envelope = void 0;
  }
  /**
   * Get Edge.
   *
   * @memberof EdgeRing
   * @param {number} i - Index
   * @returns {Edge} - Edge in the i position
   */
  get(i) {
    return this.edges[i];
  }
  /**
   * Getter of length property.
   *
   * @memberof EdgeRing
   * @returns {number} - Length of the edge ring.
   */
  get length() {
    return this.edges.length;
  }
  /**
   * Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.
   *
   * @memberof EdgeRing
   * @param {Function} f - The same function to be passed to Array.prototype.forEach
   */
  forEach(f) {
    this.edges.forEach(f);
  }
  /**
   * Similar to Array.prototype.map for the list of Edges in the EdgeRing.
   *
   * @memberof EdgeRing
   * @param {Function} f - The same function to be passed to Array.prototype.map
   * @returns {Array} - The mapped values in the function
   */
  map(f) {
    return this.edges.map(f);
  }
  /**
   * Similar to Array.prototype.some for the list of Edges in the EdgeRing.
   *
   * @memberof EdgeRing
   * @param {Function} f - The same function to be passed to Array.prototype.some
   * @returns {boolean} - True if an Edge check the condition
   */
  some(f) {
    return this.edges.some(f);
  }
  /**
   * Check if the ring is valid in geomtry terms.
   *
   * A ring must have either 0 or 4 or more points. The first and the last must be
   * equal (in 2D)
   * geos::geom::LinearRing::validateConstruction
   *
   * @memberof EdgeRing
   * @returns {boolean} - Validity of the EdgeRing
   */
  isValid() {
    return true;
  }
  /**
   * Tests whether this ring is a hole.
   *
   * A ring is a hole if it is oriented counter-clockwise.
   * Similar implementation of geos::algorithm::CGAlgorithms::isCCW
   *
   * @memberof EdgeRing
   * @returns {boolean} - true: if it is a hole
   */
  isHole() {
    const hiIndex = this.edges.reduce((high, edge, i) => {
      if (edge.from.coordinates[1] > this.edges[high].from.coordinates[1])
        high = i;
      return high;
    }, 0), iPrev = (hiIndex === 0 ? this.length : hiIndex) - 1, iNext = (hiIndex + 1) % this.length, disc = orientationIndex(
      this.edges[iPrev].from.coordinates,
      this.edges[hiIndex].from.coordinates,
      this.edges[iNext].from.coordinates
    );
    if (disc === 0)
      return this.edges[iPrev].from.coordinates[0] > this.edges[iNext].from.coordinates[0];
    return disc > 0;
  }
  /**
   * Creates a MultiPoint representing the EdgeRing (discarts edges directions).
   *
   * @memberof EdgeRing
   * @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing
   */
  toMultiPoint() {
    return _helpers.multiPoint.call(void 0, this.edges.map((edge) => edge.from.coordinates));
  }
  /**
   * Creates a Polygon representing the EdgeRing.
   *
   * @memberof EdgeRing
   * @returns {Feature<Polygon>} - Polygon representation of the Edge Ring
   */
  toPolygon() {
    if (this.polygon)
      return this.polygon;
    const coordinates = this.edges.map((edge) => edge.from.coordinates);
    coordinates.push(this.edges[0].from.coordinates);
    return this.polygon = _helpers.polygon.call(void 0, [coordinates]);
  }
  /**
   * Calculates the envelope of the EdgeRing.
   *
   * @memberof EdgeRing
   * @returns {Feature<Polygon>} - envelope
   */
  getEnvelope() {
    if (this.envelope)
      return this.envelope;
    return this.envelope = _envelope.envelope.call(void 0, this.toPolygon());
  }
  /**
   * `geos::operation::polygonize::EdgeRing::findEdgeRingContaining`
   *
   * @param {EdgeRing} testEdgeRing - EdgeRing to look in the list
   * @param {EdgeRing[]} shellList - List of EdgeRing in which to search
   *
   * @returns {EdgeRing} - EdgeRing which contains the testEdgeRing
   */
  static findEdgeRingContaining(testEdgeRing, shellList) {
    const testEnvelope = testEdgeRing.getEnvelope();
    let minEnvelope, minShell;
    shellList.forEach((shell) => {
      const tryEnvelope = shell.getEnvelope();
      if (minShell)
        minEnvelope = minShell.getEnvelope();
      if (envelopeIsEqual(tryEnvelope, testEnvelope))
        return;
      if (envelopeContains(tryEnvelope, testEnvelope)) {
        const testEdgeRingCoordinates = testEdgeRing.map(
          (edge) => edge.from.coordinates
        );
        let testPoint;
        for (const pt of testEdgeRingCoordinates) {
          if (!shell.some((edge) => coordinatesEqual(pt, edge.from.coordinates))) {
            testPoint = pt;
          }
        }
        if (testPoint && shell.inside(_helpers.point.call(void 0, testPoint))) {
          if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
            minShell = shell;
        }
      }
    });
    return minShell;
  }
  /**
   * Checks if the point is inside the edgeRing
   *
   * @param {Feature<Point>} pt - Point to check if it is inside the edgeRing
   * @returns {boolean} - True if it is inside, False otherwise
   */
  inside(pt) {
    return _booleanpointinpolygon.booleanPointInPolygon.call(void 0, pt, this.toPolygon());
  }
};

// lib/Graph.ts
var _meta = require('@turf/meta');
var _invariant = require('@turf/invariant');
function validateGeoJson(geoJson) {
  if (!geoJson)
    throw new Error("No geojson passed");
  if (geoJson.type !== "FeatureCollection" && geoJson.type !== "GeometryCollection" && geoJson.type !== "MultiLineString" && geoJson.type !== "LineString" && geoJson.type !== "Feature")
    throw new Error(
      `Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`
    );
}
var Graph = class _Graph {
  /**
   * Creates a graph from a GeoJSON.
   *
   * @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index
   * @returns {Graph} - The newly created graph
   * @throws {Error} if geoJson is invalid.
   */
  static fromGeoJson(geoJson) {
    validateGeoJson(geoJson);
    const graph = new _Graph();
    _meta.flattenEach.call(void 0, geoJson, (feature) => {
      _invariant.featureOf.call(void 0, feature, "LineString", "Graph::fromGeoJson");
      _meta.coordReduce.call(void 0, feature, (prev, cur) => {
        if (prev) {
          const start = graph.getNode(prev), end = graph.getNode(cur);
          graph.addEdge(start, end);
        }
        return cur;
      });
    });
    return graph;
  }
  /**
   * Creates or get a Node.
   *
   * @param {number[]} coordinates - Coordinates of the node
   * @returns {Node} - The created or stored node
   */
  getNode(coordinates) {
    const id = Node.buildId(coordinates);
    let node = this.nodes[id];
    if (!node)
      node = this.nodes[id] = new Node(coordinates);
    return node;
  }
  /**
   * Adds an Edge and its symetricall.
   *
   * Edges are added symetrically, i.e.: we also add its symetric
   *
   * @param {Node} from - Node which starts the Edge
   * @param {Node} to - Node which ends the Edge
   */
  addEdge(from, to) {
    const edge = new Edge(from, to), symetricEdge = edge.getSymetric();
    this.edges.push(edge);
    this.edges.push(symetricEdge);
  }
  constructor() {
    this.edges = [];
    this.nodes = {};
  }
  /**
   * Removes Dangle Nodes (nodes with grade 1).
   */
  deleteDangles() {
    Object.keys(this.nodes).map((id) => this.nodes[id]).forEach((node) => this._removeIfDangle(node));
  }
  /**
   * Check if node is dangle, if so, remove it.
   *
   * It calls itself recursively, removing a dangling node might cause another dangling node
   *
   * @param {Node} node - Node to check if it's a dangle
   */
  _removeIfDangle(node) {
    if (node.innerEdges.length <= 1) {
      const outerNodes = node.getOuterEdges().map((e) => e.to);
      this.removeNode(node);
      outerNodes.forEach((n) => this._removeIfDangle(n));
    }
  }
  /**
   * Delete cut-edges (bridge edges).
   *
   * The graph will be traversed, all the edges will be labeled according the ring
   * in which they are. (The label is a number incremented by 1). Edges with the same
   * label are cut-edges.
   */
  deleteCutEdges() {
    this._computeNextCWEdges();
    this._findLabeledEdgeRings();
    this.edges.forEach((edge) => {
      if (edge.label === edge.symetric.label) {
        this.removeEdge(edge.symetric);
        this.removeEdge(edge);
      }
    });
  }
  /**
   * Set the `next` property of each Edge.
   *
   * The graph will be transversed in a CW form, so, we set the next of the symetrical edge as the previous one.
   * OuterEdges are sorted CCW.
   *
   * @param {Node} [node] - If no node is passed, the function calls itself for every node in the Graph
   */
  _computeNextCWEdges(node) {
    if (typeof node === "undefined") {
      Object.keys(this.nodes).forEach(
        (id) => this._computeNextCWEdges(this.nodes[id])
      );
    } else {
      node.getOuterEdges().forEach((edge, i) => {
        node.getOuterEdge(
          (i === 0 ? node.getOuterEdges().length : i) - 1
        ).symetric.next = edge;
      });
    }
  }
  /**
   * Computes the next edge pointers going CCW around the given node, for the given edgering label.
   *
   * This algorithm has the effect of converting maximal edgerings into minimal edgerings
   *
   * XXX: method literally transcribed from `geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges`,
   * could be written in a more javascript way.
   *
   * @param {Node} node - Node
   * @param {number} label - Ring's label
   */
  _computeNextCCWEdges(node, label) {
    const edges = node.getOuterEdges();
    let firstOutDE, prevInDE;
    for (let i = edges.length - 1; i >= 0; --i) {
      let de = edges[i], sym = de.symetric, outDE, inDE;
      if (de.label === label)
        outDE = de;
      if (sym.label === label)
        inDE = sym;
      if (!outDE || !inDE)
        continue;
      if (inDE)
        prevInDE = inDE;
      if (outDE) {
        if (prevInDE) {
          prevInDE.next = outDE;
          prevInDE = void 0;
        }
        if (!firstOutDE)
          firstOutDE = outDE;
      }
    }
    if (prevInDE)
      prevInDE.next = firstOutDE;
  }
  /**
   * Finds rings and labels edges according to which rings are.
   *
   * The label is a number which is increased for each ring.
   *
   * @returns {Edge[]} edges that start rings
   */
  _findLabeledEdgeRings() {
    const edgeRingStarts = [];
    let label = 0;
    this.edges.forEach((edge) => {
      if (edge.label >= 0)
        return;
      edgeRingStarts.push(edge);
      let e = edge;
      do {
        e.label = label;
        e = e.next;
      } while (!edge.isEqual(e));
      label++;
    });
    return edgeRingStarts;
  }
  /**
   * Computes the EdgeRings formed by the edges in this graph.
   *
   * @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.
   */
  getEdgeRings() {
    this._computeNextCWEdges();
    this.edges.forEach((edge) => {
      edge.label = void 0;
    });
    this._findLabeledEdgeRings().forEach((edge) => {
      this._findIntersectionNodes(edge).forEach((node) => {
        this._computeNextCCWEdges(node, edge.label);
      });
    });
    const edgeRingList = [];
    this.edges.forEach((edge) => {
      if (edge.ring)
        return;
      edgeRingList.push(this._findEdgeRing(edge));
    });
    return edgeRingList;
  }
  /**
   * Find all nodes in a Maxima EdgeRing which are self-intersection nodes.
   *
   * @param {Node} startEdge - Start Edge of the Ring
   * @returns {Node[]} - intersection nodes
   */
  _findIntersectionNodes(startEdge) {
    const intersectionNodes = [];
    let edge = startEdge;
    do {
      let degree = 0;
      edge.from.getOuterEdges().forEach((e) => {
        if (e.label === startEdge.label)
          ++degree;
      });
      if (degree > 1)
        intersectionNodes.push(edge.from);
      edge = edge.next;
    } while (!startEdge.isEqual(edge));
    return intersectionNodes;
  }
  /**
   * Get the edge-ring which starts from the provided Edge.
   *
   * @param {Edge} startEdge - starting edge of the edge ring
   * @returns {EdgeRing} - EdgeRing which start Edge is the provided one.
   */
  _findEdgeRing(startEdge) {
    let edge = startEdge;
    const edgeRing = new EdgeRing();
    do {
      edgeRing.push(edge);
      edge.ring = edgeRing;
      edge = edge.next;
    } while (!startEdge.isEqual(edge));
    return edgeRing;
  }
  /**
   * Removes a node from the Graph.
   *
   * It also removes edges asociated to that node
   * @param {Node} node - Node to be removed
   */
  removeNode(node) {
    node.getOuterEdges().forEach((edge) => this.removeEdge(edge));
    node.innerEdges.forEach((edge) => this.removeEdge(edge));
    delete this.nodes[node.id];
  }
  /**
   * Remove edge from the graph and deletes the edge.
   *
   * @param {Edge} edge - Edge to be removed
   */
  removeEdge(edge) {
    this.edges = this.edges.filter((e) => !e.isEqual(edge));
    edge.deleteEdge();
  }
};

// index.ts
function polygonize(geoJson) {
  const graph = Graph.fromGeoJson(geoJson);
  graph.deleteDangles();
  graph.deleteCutEdges();
  const holes = [], shells = [];
  graph.getEdgeRings().filter((edgeRing) => edgeRing.isValid()).forEach((edgeRing) => {
    if (edgeRing.isHole())
      holes.push(edgeRing);
    else
      shells.push(edgeRing);
  });
  holes.forEach((hole) => {
    if (EdgeRing.findEdgeRingContaining(hole, shells))
      shells.push(hole);
  });
  return _helpers.featureCollection.call(void 0, shells.map((shell) => shell.toPolygon()));
}
var turf_polygonize_default = polygonize;



exports.default = turf_polygonize_default; exports.polygonize = polygonize;
//# sourceMappingURL=index.cjs.map