Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@turf/polygonize

Package Overview
Dependencies
Maintainers
4
Versions
36
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@turf/polygonize - npm Package Compare versions

Comparing version 5.1.2 to 5.1.5

main.es.js

819

lib/polygonize.js

@@ -7,11 +7,13 @@ import booleanPointInPolygon from '@turf/boolean-point-in-polygon';

/** Returns the direction of the point q relative to the vector p1 -> p2.
/**
* Returns the direction of the point q relative to the vector p1 -> p2.
*
* Implementation of geos::algorithm::CGAlgorithm::orientationIndex()
* (same as geos::algorithm::CGAlgorithm::computeOrientation())
*
* @param {Number[]} p1 - the origin point of the vector
* @param {Number[]} p2 - the final point of the vector
* @param {Number[]} q - the point to compute the direction to
* @param {number[]} p1 - the origin point of the vector
* @param {number[]} p2 - the final point of the vector
* @param {number[]} q - the point to compute the direction to
*
* @returns {Number} - 1 if q is ccw (left) from p1->p2,
* @returns {number} - 1 if q is ccw (left) from p1->p2,
* -1 if q is cw (right) from p1->p2,

@@ -21,11 +23,13 @@ * 0 if q is colinear with p1->p2

function orientationIndex(p1, p2, q) {
var dx1 = p2[0] - p1[0],
dy1 = p2[1] - p1[1],
dx2 = q[0] - p2[0],
dy2 = q[1] - p2[1];
var dx1 = p2[0] - p1[0],
dy1 = p2[1] - p1[1],
dx2 = q[0] - p2[0],
dy2 = q[1] - p2[1];
return Math.sign(dx1 * dy2 - dx2 * dy1);
return Math.sign(dx1 * dy2 - dx2 * dy1);
}
/** Checks if two envelopes are equal.
/**
* Checks if two envelopes are equal.
*
* The function assumes that the arguments are envelopes, i.e.: Rectangular polygon

@@ -35,11 +39,11 @@ *

* @param {Feature<Polygon>} env2 - Envelope
* @returns {Boolean} - True if the envelopes are equal
* @returns {boolean} - True if the envelopes are equal
*/
function envelopeIsEqual(env1, env2) {
var envX1 = env1.geometry.coordinates.map(function (c) { return c[0]; }),
envY1 = env1.geometry.coordinates.map(function (c) { return c[1]; }),
envX2 = env2.geometry.coordinates.map(function (c) { return c[0]; }),
envY2 = env2.geometry.coordinates.map(function (c) { return c[1]; });
var envX1 = env1.geometry.coordinates.map(function (c) { return c[0]; }),
envY1 = env1.geometry.coordinates.map(function (c) { return c[1]; }),
envX2 = env2.geometry.coordinates.map(function (c) { return c[0]; }),
envY2 = env2.geometry.coordinates.map(function (c) { return c[1]; });
return Math.max(null, envX1) === Math.max(null, envX2) &&
return Math.max(null, envX1) === Math.max(null, envX2) &&
Math.max(null, envY1) === Math.max(null, envY2) &&

@@ -50,3 +54,5 @@ Math.min(null, envX1) === Math.min(null, envX2) &&

/** Check if a envelope is contained in other one.
/**
* Check if a envelope is contained in other one.
*
* The function assumes that the arguments are envelopes, i.e.: Convex polygon

@@ -58,151 +64,170 @@ * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,

* @param {Feature<Polygon>} env - Envelope
* @returns {Boolean} - True if env is contained in self
* @returns {boolean} - True if env is contained in self
*/
function envelopeContains(self, env) {
return env.geometry.coordinates[0].every(function (c) { return booleanPointInPolygon(point(c), self); });
return env.geometry.coordinates[0].every(function (c) { return booleanPointInPolygon(point(c), self); });
}
/** Checks if two coordinates are equal.
/**
* Checks if two coordinates are equal.
*
* @param {Number[]} coord1 - First coordinate
* @param {Number[]} coord2 - Second coordinate
* @returns {Boolean} - True if coordinates are equal
* @param {number[]} coord1 - First coordinate
* @param {number[]} coord2 - Second coordinate
* @returns {boolean} - True if coordinates are equal
*/
function coordinatesEqual(coord1, coord2) {
return coord1[0] === coord2[0] && coord1[1] === coord2[1];
return coord1[0] === coord2[0] && coord1[1] === coord2[1];
}
/**
* Node
*/
var Node = function Node(coordinates) {
this.id = Node.buildId(coordinates);
this.coordinates = coordinates; //< {Number[]}
this.innerEdges = []; //< {Edge[]}
this.id = Node.buildId(coordinates);
this.coordinates = coordinates; //< {Number[]}
this.innerEdges = []; //< {Edge[]}
// We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
this.outerEdges = []; //< {Edge[]}
this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
// We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
this.outerEdges = []; //< {Edge[]}
this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
};
Node.buildId = function buildId (coordinates) {
return coordinates.join(',');
return coordinates.join(',');
};
Node.prototype.removeInnerEdge = function removeInnerEdge (edge) {
this.innerEdges = this.innerEdges.filter(function (e) { return e.from.id !== edge.from.id; });
this.innerEdges = this.innerEdges.filter(function (e) { return e.from.id !== edge.from.id; });
};
Node.prototype.removeOuterEdge = function removeOuterEdge (edge) {
this.outerEdges = this.outerEdges.filter(function (e) { return e.to.id !== edge.to.id; });
this.outerEdges = this.outerEdges.filter(function (e) { return e.to.id !== edge.to.id; });
};
/** Outer edges are stored CCW order.
/**
* Outer edges are stored CCW order.
*
* @memberof Node
* @param {Edge} edge - Edge to add as an outerEdge.
*/
Node.prototype.addOuterEdge = function addOuterEdge (edge) {
this.outerEdges.push(edge);
this.outerEdgesSorted = false;
this.outerEdges.push(edge);
this.outerEdgesSorted = false;
};
/** Sorts outer edges in CCW way.
/**
* Sorts outer edges in CCW way.
*
* @memberof Node
* @private
*/
Node.prototype.sortOuterEdges = function sortOuterEdges () {
var this$1 = this;
var this$1 = this;
if (!this.outerEdgesSorted) {
//this.outerEdges.sort((a, b) => a.compareTo(b));
// Using this comparator in order to be deterministic
this.outerEdges.sort(function (a, b) {
var aNode = a.to,
bNode = b.to;
if (!this.outerEdgesSorted) {
//this.outerEdges.sort((a, b) => a.compareTo(b));
// Using this comparator in order to be deterministic
this.outerEdges.sort(function (a, b) {
var aNode = a.to,
bNode = b.to;
if (aNode.coordinates[0] - this$1.coordinates[0] >= 0 && bNode.coordinates[0] - this$1.coordinates[0] < 0)
{ return 1; }
if (aNode.coordinates[0] - this$1.coordinates[0] < 0 && bNode.coordinates[0] - this$1.coordinates[0] >= 0)
{ return -1; }
if (aNode.coordinates[0] - this$1.coordinates[0] >= 0 && bNode.coordinates[0] - this$1.coordinates[0] < 0)
{ return 1; }
if (aNode.coordinates[0] - this$1.coordinates[0] < 0 && bNode.coordinates[0] - this$1.coordinates[0] >= 0)
{ return -1; }
if (aNode.coordinates[0] - this$1.coordinates[0] === 0 && bNode.coordinates[0] - this$1.coordinates[0] === 0) {
if (aNode.coordinates[1] - this$1.coordinates[1] >= 0 || bNode.coordinates[1] - this$1.coordinates[1] >= 0)
{ return aNode.coordinates[1] - bNode.coordinates[1]; }
return bNode.coordinates[1] - aNode.coordinates[1];
}
if (aNode.coordinates[0] - this$1.coordinates[0] === 0 && bNode.coordinates[0] - this$1.coordinates[0] === 0) {
if (aNode.coordinates[1] - this$1.coordinates[1] >= 0 || bNode.coordinates[1] - this$1.coordinates[1] >= 0)
{ return aNode.coordinates[1] - bNode.coordinates[1]; }
return bNode.coordinates[1] - aNode.coordinates[1];
}
var det = orientationIndex(this$1.coordinates, aNode.coordinates, bNode.coordinates);
if (det < 0)
{ return 1; }
if (det > 0)
{ return -1; }
var det = orientationIndex(this$1.coordinates, aNode.coordinates, bNode.coordinates);
if (det < 0)
{ return 1; }
if (det > 0)
{ return -1; }
var d1 = Math.pow(aNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - this$1.coordinates[1], 2),
d2 = Math.pow(bNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - this$1.coordinates[1], 2);
var d1 = Math.pow(aNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - this$1.coordinates[1], 2),
d2 = Math.pow(bNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - this$1.coordinates[1], 2);
return d1 - d2;
});
this.outerEdgesSorted = true;
}
return d1 - d2;
});
this.outerEdgesSorted = true;
}
};
/** Retrieves outer edges.
/**
* 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.
*/
Node.prototype.getOuterEdges = function getOuterEdges () {
this.sortOuterEdges();
return this.outerEdges;
this.sortOuterEdges();
return this.outerEdges;
};
Node.prototype.getOuterEdge = function getOuterEdge (i) {
this.sortOuterEdges();
return this.outerEdges[i];
this.sortOuterEdges();
return this.outerEdges[i];
};
Node.prototype.addInnerEdge = function addInnerEdge (edge) {
this.innerEdges.push(edge);
this.innerEdges.push(edge);
};
/** This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge
/**
* This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge
*/
var Edge = function Edge(from, to) {
this.from = from; //< start
this.to = to; //< End
this.from = from; //< start
this.to = to; //< End
this.next = undefined; //< The edge to be computed after
this.label = undefined; //< Used in order to detect Cut Edges (Bridges)
this.symetric = undefined; //< The symetric edge of this
this.ring = undefined; //< EdgeRing in which the Edge is
this.next = undefined; //< The edge to be computed after
this.label = undefined; //< Used in order to detect Cut Edges (Bridges)
this.symetric = undefined; //< The symetric edge of this
this.ring = undefined; //< EdgeRing in which the Edge is
this.from.addOuterEdge(this);
this.to.addInnerEdge(this);
this.from.addOuterEdge(this);
this.to.addInnerEdge(this);
};
/** Removes edge from from and to nodes.
/**
* Removes edge from from and to nodes.
*/
Edge.prototype.getSymetric = function getSymetric () {
if (!this.symetric) {
this.symetric = new Edge(this.to, this.from);
this.symetric.symetric = this;
}
if (!this.symetric) {
this.symetric = new Edge(this.to, this.from);
this.symetric.symetric = this;
}
return this.symetric;
return this.symetric;
};
Edge.prototype.deleteEdge = function deleteEdge () {
this.from.removeOuterEdge(this);
this.to.removeInnerEdge(this);
this.from.removeOuterEdge(this);
this.to.removeInnerEdge(this);
};
/** Compares Edge equallity.
/**
* 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
* @returns {boolean} - True if Edges are equal, False otherwise
*/
Edge.prototype.isEqual = function isEqual (edge) {
return this.from.id === edge.from.id && this.to.id === edge.to.id;
return this.from.id === edge.from.id && this.to.id === edge.to.id;
};
Edge.prototype.toString = function toString () {
return ("Edge { " + (this.from.id) + " -> " + (this.to.id) + " }");
return ("Edge { " + (this.from.id) + " -> " + (this.to.id) + " }");
};
/** Returns a LineString representation of the Edge
/**
* Returns a LineString representation of the Edge
*

@@ -212,18 +237,22 @@ * @returns {Feature<LineString>} - LineString representation of the Edge

Edge.prototype.toLineString = function toLineString () {
return lineString([this.from.coordinates, this.to.coordinates]);
return lineString([this.from.coordinates, this.to.coordinates]);
};
/** Comparator of two edges.
/**
* 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
* @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
*/
Edge.prototype.compareTo = function compareTo (edge) {
return orientationIndex(edge.from.coordinates, edge.to.coordinates, this.to.coordinates);
return orientationIndex(edge.from.coordinates, edge.to.coordinates, this.to.coordinates);
};
/** Ring of edges which form a polygon.
/**
* Ring of edges which form a polygon.
*
* The ring may be either an outer shell or a hole.

@@ -234,5 +263,5 @@ *

var EdgeRing = function EdgeRing() {
this.edges = [];
this.polygon = undefined; //< Caches Polygon representation
this.envelope = undefined; //< Caches Envelope representation
this.edges = [];
this.polygon = undefined; //< Caches Polygon representation
this.envelope = undefined; //< Caches Envelope representation
};

@@ -242,40 +271,50 @@

/** Add an edge to the ring, inserting it in the last position.
/**
* Add an edge to the ring, inserting it in the last position.
*
* @memberof EdgeRing
* @param {Edge} edge - Edge to be inserted
*/
EdgeRing.prototype.push = function push (edge) {
// Emulate Array getter ([]) behaviour
this[this.edges.length] = edge;
this.edges.push(edge);
this.polygon = this.envelope = undefined;
// Emulate Array getter ([]) behaviour
this[this.edges.length] = edge;
this.edges.push(edge);
this.polygon = this.envelope = undefined;
};
/** Get Edge.
/**
* Get Edge.
*
* @param {Number} i - Index
* @memberof EdgeRing
* @param {number} i - Index
* @returns {Edge} - Edge in the i position
*/
EdgeRing.prototype.get = function get (i) {
return this.edges[i];
return this.edges[i];
};
/** Getter of length property.
/**
* Getter of length property.
*
* @returns {Number} - Length of the edge ring.
* @memberof EdgeRing
* @returns {number} - Length of the edge ring.
*/
prototypeAccessors.length.get = function () {
return this.edges.length;
return this.edges.length;
};
/** Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.
/**
* 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
*/
EdgeRing.prototype.forEach = function forEach (f) {
this.edges.forEach(f);
this.edges.forEach(f);
};
/** Similar to Array.prototype.map for the list of Edges in the EdgeRing.
/**
* 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

@@ -285,15 +324,19 @@ * @returns {Array} - The mapped values in the function

EdgeRing.prototype.map = function map (f) {
return this.edges.map(f);
return this.edges.map(f);
};
/** Similar to Array.prototype.some for the list of Edges in the EdgeRing.
/**
* 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
* @returns {boolean} - True if an Edge check the condition
*/
EdgeRing.prototype.some = function some (f) {
return this.edges.some(f);
return this.edges.some(f);
};
/** Check if the ring is valid in geomtry terms.
/**
* 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

@@ -303,58 +346,72 @@ * equal (in 2D)

*
* @returns {Boolean} - Validity of the EdgeRing
* @memberof EdgeRing
* @returns {boolean} - Validity of the EdgeRing
*/
EdgeRing.prototype.isValid = function isValid () {
// TODO: stub
return true;
// TODO: stub
return true;
};
/** Tests whether this ring is a hole.
/**
* 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
* @returns {Boolean} - true: if it is a hole
*
* @memberof EdgeRing
* @returns {boolean} - true: if it is a hole
*/
EdgeRing.prototype.isHole = function isHole () {
var this$1 = this;
var this$1 = this;
// XXX: Assuming Ring is valid
// Find highest point
var hiIndex = this.edges.reduce(function (high, edge, i) {
if (edge.from.coordinates[1] > this$1.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);
// XXX: Assuming Ring is valid
// Find highest point
var hiIndex = this.edges.reduce(function (high, edge, i) {
if (edge.from.coordinates[1] > this$1.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;
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).
/**
* Creates a MultiPoint representing the EdgeRing (discarts edges directions).
*
* @memberof EdgeRing
* @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing
*/
EdgeRing.prototype.toMultiPoint = function toMultiPoint () {
return multiPoint(this.edges.map(function (edge) { return edge.from.coordinates; }));
return multiPoint(this.edges.map(function (edge) { return edge.from.coordinates; }));
};
/** Creates a Polygon representing the EdgeRing.
/**
* Creates a Polygon representing the EdgeRing.
*
* @memberof EdgeRing
* @returns {Feature<Polygon>} - Polygon representation of the Edge Ring
*/
EdgeRing.prototype.toPolygon = function toPolygon () {
if (this.polygon)
{ return this.polygon; }
var coordinates = this.edges.map(function (edge) { return edge.from.coordinates; });
coordinates.push(this.edges[0].from.coordinates);
return (this.polygon = polygon([coordinates]));
if (this.polygon)
{ return this.polygon; }
var coordinates = this.edges.map(function (edge) { return edge.from.coordinates; });
coordinates.push(this.edges[0].from.coordinates);
return (this.polygon = polygon([coordinates]));
};
/** Calculates the envelope of the EdgeRing.
/**
* Calculates the envelope of the EdgeRing.
*
* @memberof EdgeRing
* @returns {Feature<Polygon>} - envelope
*/
EdgeRing.prototype.getEnvelope = function getEnvelope () {
if (this.envelope)
{ return this.envelope; }
return (this.envelope = envelope(this.toPolygon()));
if (this.envelope)
{ return this.envelope; }
return (this.envelope = envelope(this.toPolygon()));
};

@@ -371,37 +428,38 @@

EdgeRing.findEdgeRingContaining = function findEdgeRingContaining (testEdgeRing, shellList) {
var testEnvelope = testEdgeRing.getEnvelope();
var testEnvelope = testEdgeRing.getEnvelope();
var minEnvelope,
minShell;
shellList.forEach(function (shell) {
var tryEnvelope = shell.getEnvelope();
var minEnvelope,
minShell;
shellList.forEach(function (shell) {
var tryEnvelope = shell.getEnvelope();
if (minShell)
{ minEnvelope = minShell.getEnvelope(); }
if (minShell)
{ minEnvelope = minShell.getEnvelope(); }
// the hole envelope cannot equal the shell envelope
if (envelopeIsEqual(tryEnvelope, testEnvelope))
{ return; }
// the hole envelope cannot equal the shell envelope
if (envelopeIsEqual(tryEnvelope, testEnvelope))
{ return; }
if (envelopeContains(tryEnvelope, testEnvelope)) {
var testPoint = testEdgeRing.map(function (edge) { return edge.from.coordinates; })
.find(function (pt) { return !shell.some(function (edge) { return coordinatesEqual(pt, edge.from.coordinates); }); });
if (envelopeContains(tryEnvelope, testEnvelope)) {
var testPoint = testEdgeRing.map(function (edge) { return edge.from.coordinates; })
.find(function (pt) { return !shell.some(function (edge) { return coordinatesEqual(pt, edge.from.coordinates); }); });
if (testPoint && shell.inside(point(testPoint))) {
if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
{ minShell = shell; }
}
}
});
if (testPoint && shell.inside(point(testPoint))) {
if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
{ minShell = shell; }
}
}
});
return minShell;
return minShell;
};
/** Checks if the point is inside the edgeRing
/**
* Checks if the point is inside the edgeRing
*
* @param {Feature<Point>} point - Point to check if it is inside the edgeRing
* @returns {Boolean} - True if it is inside, False otherwise
* @param {Feature<Point>} pt - Point to check if it is inside the edgeRing
* @returns {boolean} - True if it is inside, False otherwise
*/
EdgeRing.prototype.inside = function inside (point$$1) {
return booleanPointInPolygon(point$$1, this.toPolygon());
EdgeRing.prototype.inside = function inside (pt) {
return booleanPointInPolygon(pt, this.toPolygon());
};

@@ -411,12 +469,13 @@

/** Validates the geoJson.
/**
* Validates the geoJson.
*
* @param {Geojson} geoJson - input geoJson.
* @param {GeoJSON} geoJson - input geoJson.
* @throws {Error} if geoJson is invalid.
*/
function validateGeoJson(geoJson) {
if (!geoJson)
{ throw new Error('No geojson passed'); }
if (!geoJson)
{ throw new Error('No geojson passed'); }
if (geoJson.type !== 'FeatureCollection' &&
if (geoJson.type !== 'FeatureCollection' &&
geoJson.type !== 'GeometryCollection' &&

@@ -426,8 +485,8 @@ geoJson.type !== 'MultiLineString' &&

geoJson.type !== 'Feature'
)
{ throw new Error(("Invalid input type '" + (geoJson.type) + "'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature")); }
)
{ throw new Error(("Invalid input type '" + (geoJson.type) + "'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature")); }
}
/** Represents a planar graph of edges and nodes that can be used to compute a
* polygonization.
/**
* Represents a planar graph of edges and nodes that can be used to compute a polygonization.
*

@@ -441,46 +500,50 @@ * Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,

var Graph = function Graph() {
this.edges = []; //< {Edge[]} dirEdges
this.edges = []; //< {Edge[]} dirEdges
// The key is the `id` of the Node (ie: coordinates.join(','))
this.nodes = {};
// The key is the `id` of the Node (ie: coordinates.join(','))
this.nodes = {};
};
/** Removes Dangle Nodes (nodes with grade 1).
/**
* Removes Dangle Nodes (nodes with grade 1).
*/
Graph.fromGeoJson = function fromGeoJson (geoJson) {
validateGeoJson(geoJson);
validateGeoJson(geoJson);
var graph = new Graph();
flattenEach(geoJson, function (feature) {
featureOf(feature, 'LineString', 'Graph::fromGeoJson');
// When a LineString if formed by many segments, split them
coordReduce(feature, function (prev, cur) {
if (prev) {
var start = graph.getNode(prev),
end = graph.getNode(cur);
var graph = new Graph();
flattenEach(geoJson, function (feature) {
featureOf(feature, 'LineString', 'Graph::fromGeoJson');
// When a LineString if formed by many segments, split them
coordReduce(feature, function (prev, cur) {
if (prev) {
var start = graph.getNode(prev),
end = graph.getNode(cur);
graph.addEdge(start, end);
}
return cur;
graph.addEdge(start, end);
}
return cur;
});
});
});
return graph;
return graph;
};
/** Creates or get a Node.
/**
* Creates or get a Node.
*
* @param {Number[]} coordinates - Coordinates of the node
* @param {number[]} coordinates - Coordinates of the node
* @returns {Node} - The created or stored node
*/
Graph.prototype.getNode = function getNode (coordinates) {
var id = Node.buildId(coordinates);
var node = this.nodes[id];
if (!node)
{ node = this.nodes[id] = new Node(coordinates); }
var id = Node.buildId(coordinates);
var node = this.nodes[id];
if (!node)
{ node = this.nodes[id] = new Node(coordinates); }
return node;
return node;
};
/** Adds an Edge and its symetricall.
/**
* Adds an Edge and its symetricall.
*
* Edges are added symetrically, i.e.: we also add its symetric

@@ -492,18 +555,20 @@ *

Graph.prototype.addEdge = function addEdge (from, to) {
var edge = new Edge(from, to),
symetricEdge = edge.getSymetric();
var edge = new Edge(from, to),
symetricEdge = edge.getSymetric();
this.edges.push(edge);
this.edges.push(symetricEdge);
this.edges.push(edge);
this.edges.push(symetricEdge);
};
Graph.prototype.deleteDangles = function deleteDangles () {
var this$1 = this;
var this$1 = this;
Object.keys(this.nodes)
.map(function (id) { return this$1.nodes[id]; })
.forEach(function (node) { return this$1._removeIfDangle(node); });
Object.keys(this.nodes)
.map(function (id) { return this$1.nodes[id]; })
.forEach(function (node) { return this$1._removeIfDangle(node); });
};
/** Check if node is dangle, if so, remove it.
/**
* Check if node is dangle, if so, remove it.
*
* It calls itself recursively, removing a dangling node might cause another dangling node

@@ -514,13 +579,14 @@ *

Graph.prototype._removeIfDangle = function _removeIfDangle (node) {
var this$1 = this;
var this$1 = this;
// As edges are directed and symetrical, we count only innerEdges
if (node.innerEdges.length <= 1) {
var outerNodes = node.getOuterEdges().map(function (e) { return e.to; });
this.removeNode(node);
outerNodes.forEach(function (n) { return this$1._removeIfDangle(n); });
}
// As edges are directed and symetrical, we count only innerEdges
if (node.innerEdges.length <= 1) {
var outerNodes = node.getOuterEdges().map(function (e) { return e.to; });
this.removeNode(node);
outerNodes.forEach(function (n) { return this$1._removeIfDangle(n); });
}
};
/** Delete cut-edges (bridge edges).
/**
* Delete cut-edges (bridge edges).
*

@@ -532,17 +598,19 @@ * The graph will be traversed, all the edges will be labeled according the ring

Graph.prototype.deleteCutEdges = function deleteCutEdges () {
var this$1 = this;
var this$1 = this;
this._computeNextCWEdges();
this._findLabeledEdgeRings();
this._computeNextCWEdges();
this._findLabeledEdgeRings();
// Cut-edges (bridges) are edges where both edges have the same label
this.edges.forEach(function (edge) {
if (edge.label === edge.symetric.label) {
this$1.removeEdge(edge.symetric);
this$1.removeEdge(edge);
}
});
// Cut-edges (bridges) are edges where both edges have the same label
this.edges.forEach(function (edge) {
if (edge.label === edge.symetric.label) {
this$1.removeEdge(edge.symetric);
this$1.removeEdge(edge);
}
});
};
/** Set the `next` property of each 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.

@@ -554,15 +622,17 @@ * OuterEdges are sorted CCW.

Graph.prototype._computeNextCWEdges = function _computeNextCWEdges (node) {
var this$1 = this;
var this$1 = this;
if (typeof node === 'undefined') {
Object.keys(this.nodes)
.forEach(function (id) { return this$1._computeNextCWEdges(this$1.nodes[id]); });
} else {
node.getOuterEdges().forEach(function (edge, i) {
node.getOuterEdge((i === 0 ? node.getOuterEdges().length : i) - 1).symetric.next = edge;
});
}
if (typeof node === 'undefined') {
Object.keys(this.nodes)
.forEach(function (id) { return this$1._computeNextCWEdges(this$1.nodes[id]); });
} else {
node.getOuterEdges().forEach(function (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.
/**
* 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

@@ -574,44 +644,46 @@ *

* @param {Node} node - Node
* @param {Number} label - Ring's label
* @param {number} label - Ring's label
*/
Graph.prototype._computeNextCCWEdges = function _computeNextCCWEdges (node, label) {
var edges = node.getOuterEdges();
var firstOutDE,
prevInDE;
var edges = node.getOuterEdges();
var firstOutDE,
prevInDE;
for (var i = edges.length - 1; i >= 0; --i) {
var de = edges[i],
sym = de.symetric,
outDE = (void 0),
inDE = (void 0);
for (var i = edges.length - 1; i >= 0; --i) {
var de = edges[i],
sym = de.symetric,
outDE = (void 0),
inDE = (void 0);
if (de.label === label)
{ outDE = de; }
if (de.label === label)
{ outDE = de; }
if (sym.label === label)
{ inDE = sym; }
if (sym.label === label)
{ inDE = sym; }
if (!outDE || !inDE) // This edge is not in edgering
{ continue; }
if (!outDE || !inDE) // This edge is not in edgering
{ continue; }
if (inDE)
{ prevInDE = inDE; }
if (inDE)
{ prevInDE = inDE; }
if (outDE) {
if (prevInDE) {
prevInDE.next = outDE;
prevInDE = undefined;
}
if (outDE) {
if (prevInDE) {
prevInDE.next = outDE;
prevInDE = undefined;
}
if (!firstOutDE)
{ firstOutDE = outDE; }
if (!firstOutDE)
{ firstOutDE = outDE; }
}
}
}
if (prevInDE)
{ prevInDE.next = firstOutDE; }
if (prevInDE)
{ prevInDE.next = firstOutDE; }
};
/** Finds rings and labels edges according to which rings are.
/**
* Finds rings and labels edges according to which rings are.
*
* The label is a number which is increased for each ring.

@@ -622,23 +694,24 @@ *

Graph.prototype._findLabeledEdgeRings = function _findLabeledEdgeRings () {
var edgeRingStarts = [];
var label = 0;
this.edges.forEach(function (edge) {
if (edge.label >= 0)
{ return; }
var edgeRingStarts = [];
var label = 0;
this.edges.forEach(function (edge) {
if (edge.label >= 0)
{ return; }
edgeRingStarts.push(edge);
edgeRingStarts.push(edge);
var e = edge;
do {
e.label = label;
e = e.next;
} while (!edge.isEqual(e));
var e = edge;
do {
e.label = label;
e = e.next;
} while (!edge.isEqual(e));
label++;
});
label++;
});
return edgeRingStarts;
return edgeRingStarts;
};
/** Computes the EdgeRings formed by the edges in this graph.
/**
* Computes the EdgeRings formed by the edges in this graph.
*

@@ -648,31 +721,32 @@ * @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.

Graph.prototype.getEdgeRings = function getEdgeRings () {
var this$1 = this;
var this$1 = this;
this._computeNextCWEdges();
this._computeNextCWEdges();
// Clear labels
this.edges.forEach(function (edge) {
edge.label = undefined;
});
// Clear labels
this.edges.forEach(function (edge) {
edge.label = undefined;
});
this._findLabeledEdgeRings().forEach(function (edge) {
// convertMaximalToMinimalEdgeRings
this$1._findIntersectionNodes(edge).forEach(function (node) {
this$1._computeNextCCWEdges(node, edge.label);
this._findLabeledEdgeRings().forEach(function (edge) {
// convertMaximalToMinimalEdgeRings
this$1._findIntersectionNodes(edge).forEach(function (node) {
this$1._computeNextCCWEdges(node, edge.label);
});
});
});
var edgeRingList = [];
var edgeRingList = [];
// find all edgerings
this.edges.forEach(function (edge) {
if (edge.ring)
{ return; }
edgeRingList.push(this$1._findEdgeRing(edge));
});
// find all edgerings
this.edges.forEach(function (edge) {
if (edge.ring)
{ return; }
edgeRingList.push(this$1._findEdgeRing(edge));
});
return edgeRingList;
return edgeRingList;
};
/** Find all nodes in a Maxima EdgeRing which are self-intersection nodes.
/**
* Find all nodes in a Maxima EdgeRing which are self-intersection nodes.
*

@@ -683,26 +757,27 @@ * @param {Node} startEdge - Start Edge of the Ring

Graph.prototype._findIntersectionNodes = function _findIntersectionNodes (startEdge) {
var intersectionNodes = [];
var edge = startEdge;
var loop = function () {
// getDegree
var degree = 0;
edge.from.getOuterEdges().forEach(function (e) {
if (e.label === startEdge.label)
{ ++degree; }
});
var intersectionNodes = [];
var edge = startEdge;
var loop = function () {
// getDegree
var degree = 0;
edge.from.getOuterEdges().forEach(function (e) {
if (e.label === startEdge.label)
{ ++degree; }
});
if (degree > 1)
{ intersectionNodes.push(edge.from); }
if (degree > 1)
{ intersectionNodes.push(edge.from); }
edge = edge.next;
};
edge = edge.next;
};
do {
loop();
} while (!startEdge.isEqual(edge));
do {
loop();
} while (!startEdge.isEqual(edge));
return intersectionNodes;
return intersectionNodes;
};
/** Get the edge-ring which starts from the provided Edge.
/**
* Get the edge-ring which starts from the provided Edge.
*

@@ -713,15 +788,16 @@ * @param {Edge} startEdge - starting edge of the edge ring

Graph.prototype._findEdgeRing = function _findEdgeRing (startEdge) {
var edge = startEdge;
var edgeRing = new EdgeRing();
var edge = startEdge;
var edgeRing = new EdgeRing();
do {
edgeRing.push(edge);
edge.ring = edgeRing;
edge = edge.next;
} while (!startEdge.isEqual(edge));
do {
edgeRing.push(edge);
edge.ring = edgeRing;
edge = edge.next;
} while (!startEdge.isEqual(edge));
return edgeRing;
return edgeRing;
};
/** Removes a node from the Graph.
/**
* Removes a node from the Graph.
*

@@ -732,10 +808,11 @@ * It also removes edges asociated to that node

Graph.prototype.removeNode = function removeNode (node) {
var this$1 = this;
var this$1 = this;
node.getOuterEdges().forEach(function (edge) { return this$1.removeEdge(edge); });
node.innerEdges.forEach(function (edge) { return this$1.removeEdge(edge); });
delete this.nodes[node.id];
node.getOuterEdges().forEach(function (edge) { return this$1.removeEdge(edge); });
node.innerEdges.forEach(function (edge) { return this$1.removeEdge(edge); });
delete this.nodes[node.id];
};
/** Remove edge from the graph and deletes the edge.
/**
* Remove edge from the graph and deletes the edge.
*

@@ -745,4 +822,4 @@ * @param {Edge} edge - Edge to be removed

Graph.prototype.removeEdge = function removeEdge (edge) {
this.edges = this.edges.filter(function (e) { return !e.isEqual(edge); });
edge.deleteEdge();
this.edges = this.edges.filter(function (e) { return !e.isEqual(edge); });
edge.deleteEdge();
};

@@ -769,33 +846,33 @@

function polygonize(geoJson) {
var graph = Graph.fromGeoJson(geoJson);
var graph = Graph.fromGeoJson(geoJson);
// 1. Remove dangle node
graph.deleteDangles();
// 1. Remove dangle node
graph.deleteDangles();
// 2. Remove cut-edges (bridge edges)
graph.deleteCutEdges();
// 2. Remove cut-edges (bridge edges)
graph.deleteCutEdges();
// 3. Get all holes and shells
var holes = [],
shells = [];
// 3. Get all holes and shells
var holes = [],
shells = [];
graph.getEdgeRings()
.filter(function (edgeRing) { return edgeRing.isValid(); })
.forEach(function (edgeRing) {
if (edgeRing.isHole())
{ holes.push(edgeRing); }
else
{ shells.push(edgeRing); }
graph.getEdgeRings()
.filter(function (edgeRing) { return edgeRing.isValid(); })
.forEach(function (edgeRing) {
if (edgeRing.isHole())
{ holes.push(edgeRing); }
else
{ shells.push(edgeRing); }
});
// 4. Assign Holes to Shells
holes.forEach(function (hole) {
if (EdgeRing.findEdgeRingContaining(hole, shells))
{ shells.push(hole); }
});
// 4. Assign Holes to Shells
holes.forEach(function (hole) {
if (EdgeRing.findEdgeRingContaining(hole, shells))
{ shells.push(hole); }
});
// 5. EdgeRings to Polygons
return featureCollection(shells.map(function (shell) { return shell.toPolygon(); }));
// 5. EdgeRings to Polygons
return featureCollection(shells.map(function (shell) { return shell.toPolygon(); }));
}
export default polygonize;

132

lib/polygonize/Edge.js
import {lineString} from '@turf/helpers';
import {orientationIndex} from './util';
/** This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge
/**
* This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge
*/
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;
/**
* 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;
}
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; //< start
this.to = to; //< End
/**
* @param {Node} from - start node of the Edge
* @param {Node} to - end node of the edge
*/
constructor(from, to) {
this.from = from; //< start
this.to = to; //< End
this.next = undefined; //< The edge to be computed after
this.label = undefined; //< Used in order to detect Cut Edges (Bridges)
this.symetric = undefined; //< The symetric edge of this
this.ring = undefined; //< EdgeRing in which the Edge is
this.next = undefined; //< The edge to be computed after
this.label = undefined; //< Used in order to detect Cut Edges (Bridges)
this.symetric = undefined; //< The symetric edge of this
this.ring = undefined; //< EdgeRing in which the Edge is
this.from.addOuterEdge(this);
this.to.addInnerEdge(this);
}
this.from.addOuterEdge(this);
this.to.addInnerEdge(this);
}
/**
* Removes edge from from and to nodes.
*/
deleteEdge() {
this.from.removeOuterEdge(this);
this.to.removeInnerEdge(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;
}
/** 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} }`;
}
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 lineString([this.from.coordinates, this.to.coordinates]);
}
/** Returns a LineString representation of the Edge
*
* @returns {Feature<LineString>} - LineString representation of the Edge
*/
toLineString() {
return lineString([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);
}
/**
* 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);
}
}
export default Edge;

317

lib/polygonize/EdgeRing.js

@@ -6,3 +6,5 @@ import {orientationIndex, envelopeIsEqual, envelopeContains, coordinatesEqual} from './util';

/** Ring of edges which form a polygon.
/**
* Ring of edges which form a polygon.
*
* The ring may be either an outer shell or a hole.

@@ -13,170 +15,199 @@ *

class EdgeRing {
constructor() {
this.edges = [];
this.polygon = undefined; //< Caches Polygon representation
this.envelope = undefined; //< Caches Envelope representation
}
constructor() {
this.edges = [];
this.polygon = undefined; //< Caches Polygon representation
this.envelope = undefined; //< Caches Envelope representation
}
/** Add an edge to the ring, inserting it in the last position.
*
* @param {Edge} edge - Edge to be inserted
*/
push(edge) {
/**
* Add an edge to the ring, inserting it in the last position.
*
* @memberof EdgeRing
* @param {Edge} edge - Edge to be inserted
*/
push(edge) {
// Emulate Array getter ([]) behaviour
this[this.edges.length] = edge;
this.edges.push(edge);
this.polygon = this.envelope = undefined;
}
this[this.edges.length] = edge;
this.edges.push(edge);
this.polygon = this.envelope = undefined;
}
/** Get Edge.
*
* @param {Number} i - Index
* @returns {Edge} - Edge in the i position
*/
get(i) {
return this.edges[i];
}
/**
* 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.
*
* @returns {Number} - Length of the edge ring.
*/
get length() {
return this.edges.length;
}
/**
* 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.
*
* @param {Function} f - The same function to be passed to Array.prototype.forEach
*/
forEach(f) {
this.edges.forEach(f);
}
/**
* 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.
*
* @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.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.
*
* @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);
}
/**
* 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
*
* @returns {Boolean} - Validity of the EdgeRing
*/
isValid() {
/**
* 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() {
// TODO: stub
return true;
}
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
* @returns {Boolean} - true: if it is a hole
*/
isHole() {
/**
* 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() {
// XXX: Assuming Ring is valid
// Find highest point
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);
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;
}
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).
* @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing
*/
toMultiPoint() {
return multiPoint(this.edges.map(edge => edge.from.coordinates));
}
/**
* Creates a MultiPoint representing the EdgeRing (discarts edges directions).
*
* @memberof EdgeRing
* @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing
*/
toMultiPoint() {
return multiPoint(this.edges.map(edge => edge.from.coordinates));
}
/** Creates a Polygon representing the 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 = polygon([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 = polygon([coordinates]));
}
/** Calculates the envelope of the EdgeRing.
* @returns {Feature<Polygon>} - envelope
*/
getEnvelope() {
if (this.envelope)
return this.envelope;
return (this.envelope = envelope(this.toPolygon()));
}
/**
* Calculates the envelope of the EdgeRing.
*
* @memberof EdgeRing
* @returns {Feature<Polygon>} - envelope
*/
getEnvelope() {
if (this.envelope)
return this.envelope;
return (this.envelope = envelope(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();
/**
* `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();
let minEnvelope,
minShell;
shellList.forEach(shell => {
const tryEnvelope = shell.getEnvelope();
if (minShell)
minEnvelope = minShell.getEnvelope();
if (minShell)
minEnvelope = minShell.getEnvelope();
// the hole envelope cannot equal the shell envelope
if (envelopeIsEqual(tryEnvelope, testEnvelope))
return;
// the hole envelope cannot equal the shell envelope
if (envelopeIsEqual(tryEnvelope, testEnvelope))
return;
if (envelopeContains(tryEnvelope, testEnvelope)) {
const testPoint = testEdgeRing.map(edge => edge.from.coordinates)
.find(pt => !shell.some(edge => coordinatesEqual(pt, edge.from.coordinates)));
if (envelopeContains(tryEnvelope, testEnvelope)) {
const testPoint = testEdgeRing.map(edge => edge.from.coordinates)
.find(pt => !shell.some(edge => coordinatesEqual(pt, edge.from.coordinates)));
if (testPoint && shell.inside(point(testPoint))) {
if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
minShell = shell;
}
}
});
if (testPoint && shell.inside(point(testPoint))) {
if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
minShell = shell;
}
}
});
return minShell;
}
return minShell;
}
/** Checks if the point is inside the edgeRing
*
* @param {Feature<Point>} point - Point to check if it is inside the edgeRing
* @returns {Boolean} - True if it is inside, False otherwise
*/
inside(point) {
return booleanPointInPolygon(point, this.toPolygon());
}
/**
* 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(pt, this.toPolygon());
}
}
export default EdgeRing;

516

lib/polygonize/Graph.js

@@ -7,12 +7,13 @@ import Node from './Node';

/** Validates the geoJson.
/**
* Validates the geoJson.
*
* @param {Geojson} geoJson - input geoJson.
* @param {GeoJSON} geoJson - input geoJson.
* @throws {Error} if geoJson is invalid.
*/
function validateGeoJson(geoJson) {
if (!geoJson)
throw new Error('No geojson passed');
if (!geoJson)
throw new Error('No geojson passed');
if (geoJson.type !== 'FeatureCollection' &&
if (geoJson.type !== 'FeatureCollection' &&
geoJson.type !== 'GeometryCollection' &&

@@ -22,8 +23,8 @@ geoJson.type !== 'MultiLineString' &&

geoJson.type !== 'Feature'
)
throw new Error(`Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`);
)
throw new Error(`Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`);
}
/** Represents a planar graph of edges and nodes that can be used to compute a
* polygonization.
/**
* Represents a planar graph of edges and nodes that can be used to compute a polygonization.
*

@@ -37,291 +38,310 @@ * Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,

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);
/**
* 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();
flattenEach(geoJson, feature => {
featureOf(feature, 'LineString', 'Graph::fromGeoJson');
// When a LineString if formed by many segments, split them
coordReduce(feature, (prev, cur) => {
if (prev) {
const start = graph.getNode(prev),
end = graph.getNode(cur);
const graph = new Graph();
flattenEach(geoJson, feature => {
featureOf(feature, 'LineString', 'Graph::fromGeoJson');
// When a LineString if formed by many segments, split them
coordReduce(feature, (prev, cur) => {
if (prev) {
const start = graph.getNode(prev),
end = graph.getNode(cur);
graph.addEdge(start, end);
}
return cur;
});
});
graph.addEdge(start, end);
}
return cur;
});
});
return graph;
}
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);
/**
* 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;
}
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();
/**
* 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);
}
this.edges.push(edge);
this.edges.push(symetricEdge);
}
constructor() {
this.edges = []; //< {Edge[]} dirEdges
constructor() {
this.edges = []; //< {Edge[]} dirEdges
// The key is the `id` of the Node (ie: coordinates.join(','))
this.nodes = {};
}
// The key is the `id` of the Node (ie: coordinates.join(','))
this.nodes = {};
}
/** Removes Dangle Nodes (nodes with grade 1).
*/
deleteDangles() {
Object.keys(this.nodes)
.map(id => this.nodes[id])
.forEach(node => this._removeIfDangle(node));
}
/**
* 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) {
/**
* 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) {
// As edges are directed and symetrical, we count only innerEdges
if (node.innerEdges.length <= 1) {
const outerNodes = node.getOuterEdges().map(e => e.to);
this.removeNode(node);
outerNodes.forEach(n => this._removeIfDangle(n));
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();
/**
* 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();
// Cut-edges (bridges) are edges where both edges have the same label
this.edges.forEach(edge => {
if (edge.label === edge.symetric.label) {
this.removeEdge(edge.symetric);
this.removeEdge(edge);
}
});
}
// Cut-edges (bridges) are edges where both edges have the same label
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;
});
/**
* 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;
/**
* 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;
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 (de.label === label)
outDE = de;
if (sym.label === label)
inDE = sym;
if (sym.label === label)
inDE = sym;
if (!outDE || !inDE) // This edge is not in edgering
continue;
if (!outDE || !inDE) // This edge is not in edgering
continue;
if (inDE)
prevInDE = inDE;
if (inDE)
prevInDE = inDE;
if (outDE) {
if (prevInDE) {
prevInDE.next = outDE;
prevInDE = undefined;
if (outDE) {
if (prevInDE) {
prevInDE.next = outDE;
prevInDE = undefined;
}
if (!firstOutDE)
firstOutDE = outDE;
}
}
if (!firstOutDE)
firstOutDE = outDE;
}
if (prevInDE)
prevInDE.next = firstOutDE;
}
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;
/** 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);
edgeRingStarts.push(edge);
let e = edge;
do {
e.label = label;
e = e.next;
} while (!edge.isEqual(e));
let e = edge;
do {
e.label = label;
e = e.next;
} while (!edge.isEqual(e));
label++;
});
label++;
});
return edgeRingStarts;
}
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();
/** Computes the EdgeRings formed by the edges in this graph.
*
* @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.
*/
getEdgeRings() {
this._computeNextCWEdges();
// Clear labels
this.edges.forEach(edge => {
edge.label = undefined;
});
// Clear labels
this.edges.forEach(edge => {
edge.label = undefined;
});
this._findLabeledEdgeRings().forEach(edge => {
// convertMaximalToMinimalEdgeRings
this._findIntersectionNodes(edge).forEach(node => {
this._computeNextCCWEdges(node, edge.label);
});
});
this._findLabeledEdgeRings().forEach(edge => {
// convertMaximalToMinimalEdgeRings
this._findIntersectionNodes(edge).forEach(node => {
this._computeNextCCWEdges(node, edge.label);
});
});
const edgeRingList = [];
const edgeRingList = [];
// find all edgerings
this.edges.forEach(edge => {
if (edge.ring)
return;
edgeRingList.push(this._findEdgeRing(edge));
});
// find all edgerings
this.edges.forEach(edge => {
if (edge.ring)
return;
edgeRingList.push(this._findEdgeRing(edge));
});
return edgeRingList;
}
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 {
// getDegree
let degree = 0;
edge.from.getOuterEdges().forEach(e => {
if (e.label === startEdge.label)
++degree;
});
/** 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 {
// getDegree
let degree = 0;
edge.from.getOuterEdges().forEach(e => {
if (e.label === startEdge.label)
++degree;
});
if (degree > 1)
intersectionNodes.push(edge.from);
if (degree > 1)
intersectionNodes.push(edge.from);
edge = edge.next;
} while (!startEdge.isEqual(edge));
edge = edge.next;
} while (!startEdge.isEqual(edge));
return intersectionNodes;
}
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();
/** 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));
do {
edgeRing.push(edge);
edge.ring = edgeRing;
edge = edge.next;
} while (!startEdge.isEqual(edge));
return edgeRing;
}
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];
}
/** 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();
}
/**
* 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();
}
}
export default Graph;

46

lib/polygonize/index.js

@@ -24,33 +24,33 @@ import Graph from './Graph';

function polygonize(geoJson) {
const graph = Graph.fromGeoJson(geoJson);
const graph = Graph.fromGeoJson(geoJson);
// 1. Remove dangle node
graph.deleteDangles();
// 1. Remove dangle node
graph.deleteDangles();
// 2. Remove cut-edges (bridge edges)
graph.deleteCutEdges();
// 2. Remove cut-edges (bridge edges)
graph.deleteCutEdges();
// 3. Get all holes and shells
const holes = [],
shells = [];
// 3. Get all holes and shells
const holes = [],
shells = [];
graph.getEdgeRings()
.filter(edgeRing => edgeRing.isValid())
.forEach(edgeRing => {
if (edgeRing.isHole())
holes.push(edgeRing);
else
shells.push(edgeRing);
graph.getEdgeRings()
.filter(edgeRing => edgeRing.isValid())
.forEach(edgeRing => {
if (edgeRing.isHole())
holes.push(edgeRing);
else
shells.push(edgeRing);
});
// 4. Assign Holes to Shells
holes.forEach(hole => {
if (EdgeRing.findEdgeRingContaining(hole, shells))
shells.push(hole);
});
// 4. Assign Holes to Shells
holes.forEach(hole => {
if (EdgeRing.findEdgeRingContaining(hole, shells))
shells.push(hole);
});
// 5. EdgeRings to Polygons
return featureCollection(shells.map(shell => shell.toPolygon()));
// 5. EdgeRings to Polygons
return featureCollection(shells.map(shell => shell.toPolygon()));
}
export default polygonize;

151

lib/polygonize/Node.js
import {orientationIndex} from './util';
/**
* Node
*/
class Node {
static buildId(coordinates) {
return coordinates.join(',');
}
static buildId(coordinates) {
return coordinates.join(',');
}
constructor(coordinates) {
this.id = Node.buildId(coordinates);
this.coordinates = coordinates; //< {Number[]}
this.innerEdges = []; //< {Edge[]}
constructor(coordinates) {
this.id = Node.buildId(coordinates);
this.coordinates = coordinates; //< {Number[]}
this.innerEdges = []; //< {Edge[]}
// We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
this.outerEdges = []; //< {Edge[]}
this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
}
// We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
this.outerEdges = []; //< {Edge[]}
this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
}
removeInnerEdge(edge) {
this.innerEdges = this.innerEdges.filter(e => e.from.id !== edge.from.id);
}
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);
}
removeOuterEdge(edge) {
this.outerEdges = this.outerEdges.filter(e => e.to.id !== edge.to.id);
}
/** Outer edges are stored CCW order.
* @param {Edge} edge - Edge to add as an outerEdge.
*/
addOuterEdge(edge) {
this.outerEdges.push(edge);
this.outerEdgesSorted = false;
}
/**
* 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.
* @private
*/
sortOuterEdges() {
if (!this.outerEdgesSorted) {
//this.outerEdges.sort((a, b) => a.compareTo(b));
// Using this comparator in order to be deterministic
this.outerEdges.sort((a, b) => {
const aNode = a.to,
bNode = b.to;
/**
* Sorts outer edges in CCW way.
*
* @memberof Node
* @private
*/
sortOuterEdges() {
if (!this.outerEdgesSorted) {
//this.outerEdges.sort((a, b) => a.compareTo(b));
// Using this comparator in order to be deterministic
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)
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];
}
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 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);
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;
return d1 - d2;
});
this.outerEdgesSorted = true;
}
}
}
/** Retrieves outer edges.
* They are sorted if they aren't in the CCW order.
* @returns {Edge[]} - List of outer edges sorted in a CCW order.
*/
getOuterEdges() {
this.sortOuterEdges();
return this.outerEdges;
}
/**
* 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];
}
getOuterEdge(i) {
this.sortOuterEdges();
return this.outerEdges[i];
}
addInnerEdge(edge) {
this.innerEdges.push(edge);
}
addInnerEdge(edge) {
this.innerEdges.push(edge);
}
}
export default Node;

65

lib/polygonize/util.js
import booleanPointInPolygon from '@turf/boolean-point-in-polygon';
import {point} from '@turf/helpers';
/** Returns the direction of the point q relative to the vector p1 -> p2.
/**
* Returns the direction of the point q relative to the vector p1 -> p2.
*
* Implementation of geos::algorithm::CGAlgorithm::orientationIndex()
* (same as geos::algorithm::CGAlgorithm::computeOrientation())
*
* @param {Number[]} p1 - the origin point of the vector
* @param {Number[]} p2 - the final point of the vector
* @param {Number[]} q - the point to compute the direction to
* @param {number[]} p1 - the origin point of the vector
* @param {number[]} p2 - the final point of the vector
* @param {number[]} q - the point to compute the direction to
*
* @returns {Number} - 1 if q is ccw (left) from p1->p2,
* @returns {number} - 1 if q is ccw (left) from p1->p2,
* -1 if q is cw (right) from p1->p2,

@@ -17,11 +19,13 @@ * 0 if q is colinear with p1->p2

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];
const dx1 = p2[0] - p1[0],
dy1 = p2[1] - p1[1],
dx2 = q[0] - p2[0],
dy2 = q[1] - p2[1];
return Math.sign(dx1 * dy2 - dx2 * dy1);
return Math.sign(dx1 * dy2 - dx2 * dy1);
}
/** Checks if two envelopes are equal.
/**
* Checks if two envelopes are equal.
*
* The function assumes that the arguments are envelopes, i.e.: Rectangular polygon

@@ -31,11 +35,11 @@ *

* @param {Feature<Polygon>} env2 - Envelope
* @returns {Boolean} - True if the envelopes are equal
* @returns {boolean} - True if the envelopes are equal
*/
function envelopeIsEqual(env1, env2) {
const envX1 = env1.geometry.coordinates.map(c => c[0]),
envY1 = env1.geometry.coordinates.map(c => c[1]),
envX2 = env2.geometry.coordinates.map(c => c[0]),
envY2 = env2.geometry.coordinates.map(c => c[1]);
const envX1 = env1.geometry.coordinates.map(c => c[0]),
envY1 = env1.geometry.coordinates.map(c => c[1]),
envX2 = env2.geometry.coordinates.map(c => c[0]),
envY2 = env2.geometry.coordinates.map(c => c[1]);
return Math.max(null, envX1) === Math.max(null, envX2) &&
return Math.max(null, envX1) === Math.max(null, envX2) &&
Math.max(null, envY1) === Math.max(null, envY2) &&

@@ -46,3 +50,5 @@ Math.min(null, envX1) === Math.min(null, envX2) &&

/** Check if a envelope is contained in other one.
/**
* Check if a envelope is contained in other one.
*
* The function assumes that the arguments are envelopes, i.e.: Convex polygon

@@ -54,23 +60,24 @@ * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,

* @param {Feature<Polygon>} env - Envelope
* @returns {Boolean} - True if env is contained in self
* @returns {boolean} - True if env is contained in self
*/
function envelopeContains(self, env) {
return env.geometry.coordinates[0].every(c => booleanPointInPolygon(point(c), self));
return env.geometry.coordinates[0].every(c => booleanPointInPolygon(point(c), self));
}
/** Checks if two coordinates are equal.
/**
* Checks if two coordinates are equal.
*
* @param {Number[]} coord1 - First coordinate
* @param {Number[]} coord2 - Second coordinate
* @returns {Boolean} - True if coordinates are equal
* @param {number[]} coord1 - First coordinate
* @param {number[]} coord2 - Second coordinate
* @returns {boolean} - True if coordinates are equal
*/
function coordinatesEqual(coord1, coord2) {
return coord1[0] === coord2[0] && coord1[1] === coord2[1];
return coord1[0] === coord2[0] && coord1[1] === coord2[1];
}
export {
orientationIndex,
envelopeIsEqual,
envelopeContains,
coordinatesEqual
orientationIndex,
envelopeIsEqual,
envelopeContains,
coordinatesEqual
};

819

main.js

@@ -11,11 +11,13 @@ 'use strict';

/** Returns the direction of the point q relative to the vector p1 -> p2.
/**
* Returns the direction of the point q relative to the vector p1 -> p2.
*
* Implementation of geos::algorithm::CGAlgorithm::orientationIndex()
* (same as geos::algorithm::CGAlgorithm::computeOrientation())
*
* @param {Number[]} p1 - the origin point of the vector
* @param {Number[]} p2 - the final point of the vector
* @param {Number[]} q - the point to compute the direction to
* @param {number[]} p1 - the origin point of the vector
* @param {number[]} p2 - the final point of the vector
* @param {number[]} q - the point to compute the direction to
*
* @returns {Number} - 1 if q is ccw (left) from p1->p2,
* @returns {number} - 1 if q is ccw (left) from p1->p2,
* -1 if q is cw (right) from p1->p2,

@@ -25,11 +27,13 @@ * 0 if q is colinear with p1->p2

function orientationIndex(p1, p2, q) {
var dx1 = p2[0] - p1[0],
dy1 = p2[1] - p1[1],
dx2 = q[0] - p2[0],
dy2 = q[1] - p2[1];
var dx1 = p2[0] - p1[0],
dy1 = p2[1] - p1[1],
dx2 = q[0] - p2[0],
dy2 = q[1] - p2[1];
return Math.sign(dx1 * dy2 - dx2 * dy1);
return Math.sign(dx1 * dy2 - dx2 * dy1);
}
/** Checks if two envelopes are equal.
/**
* Checks if two envelopes are equal.
*
* The function assumes that the arguments are envelopes, i.e.: Rectangular polygon

@@ -39,11 +43,11 @@ *

* @param {Feature<Polygon>} env2 - Envelope
* @returns {Boolean} - True if the envelopes are equal
* @returns {boolean} - True if the envelopes are equal
*/
function envelopeIsEqual(env1, env2) {
var envX1 = env1.geometry.coordinates.map(function (c) { return c[0]; }),
envY1 = env1.geometry.coordinates.map(function (c) { return c[1]; }),
envX2 = env2.geometry.coordinates.map(function (c) { return c[0]; }),
envY2 = env2.geometry.coordinates.map(function (c) { return c[1]; });
var envX1 = env1.geometry.coordinates.map(function (c) { return c[0]; }),
envY1 = env1.geometry.coordinates.map(function (c) { return c[1]; }),
envX2 = env2.geometry.coordinates.map(function (c) { return c[0]; }),
envY2 = env2.geometry.coordinates.map(function (c) { return c[1]; });
return Math.max(null, envX1) === Math.max(null, envX2) &&
return Math.max(null, envX1) === Math.max(null, envX2) &&
Math.max(null, envY1) === Math.max(null, envY2) &&

@@ -54,3 +58,5 @@ Math.min(null, envX1) === Math.min(null, envX2) &&

/** Check if a envelope is contained in other one.
/**
* Check if a envelope is contained in other one.
*
* The function assumes that the arguments are envelopes, i.e.: Convex polygon

@@ -62,151 +68,170 @@ * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,

* @param {Feature<Polygon>} env - Envelope
* @returns {Boolean} - True if env is contained in self
* @returns {boolean} - True if env is contained in self
*/
function envelopeContains(self, env) {
return env.geometry.coordinates[0].every(function (c) { return booleanPointInPolygon(helpers.point(c), self); });
return env.geometry.coordinates[0].every(function (c) { return booleanPointInPolygon(helpers.point(c), self); });
}
/** Checks if two coordinates are equal.
/**
* Checks if two coordinates are equal.
*
* @param {Number[]} coord1 - First coordinate
* @param {Number[]} coord2 - Second coordinate
* @returns {Boolean} - True if coordinates are equal
* @param {number[]} coord1 - First coordinate
* @param {number[]} coord2 - Second coordinate
* @returns {boolean} - True if coordinates are equal
*/
function coordinatesEqual(coord1, coord2) {
return coord1[0] === coord2[0] && coord1[1] === coord2[1];
return coord1[0] === coord2[0] && coord1[1] === coord2[1];
}
/**
* Node
*/
var Node = function Node(coordinates) {
this.id = Node.buildId(coordinates);
this.coordinates = coordinates; //< {Number[]}
this.innerEdges = []; //< {Edge[]}
this.id = Node.buildId(coordinates);
this.coordinates = coordinates; //< {Number[]}
this.innerEdges = []; //< {Edge[]}
// We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
this.outerEdges = []; //< {Edge[]}
this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
// We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
this.outerEdges = []; //< {Edge[]}
this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
};
Node.buildId = function buildId (coordinates) {
return coordinates.join(',');
return coordinates.join(',');
};
Node.prototype.removeInnerEdge = function removeInnerEdge (edge) {
this.innerEdges = this.innerEdges.filter(function (e) { return e.from.id !== edge.from.id; });
this.innerEdges = this.innerEdges.filter(function (e) { return e.from.id !== edge.from.id; });
};
Node.prototype.removeOuterEdge = function removeOuterEdge (edge) {
this.outerEdges = this.outerEdges.filter(function (e) { return e.to.id !== edge.to.id; });
this.outerEdges = this.outerEdges.filter(function (e) { return e.to.id !== edge.to.id; });
};
/** Outer edges are stored CCW order.
/**
* Outer edges are stored CCW order.
*
* @memberof Node
* @param {Edge} edge - Edge to add as an outerEdge.
*/
Node.prototype.addOuterEdge = function addOuterEdge (edge) {
this.outerEdges.push(edge);
this.outerEdgesSorted = false;
this.outerEdges.push(edge);
this.outerEdgesSorted = false;
};
/** Sorts outer edges in CCW way.
/**
* Sorts outer edges in CCW way.
*
* @memberof Node
* @private
*/
Node.prototype.sortOuterEdges = function sortOuterEdges () {
var this$1 = this;
var this$1 = this;
if (!this.outerEdgesSorted) {
//this.outerEdges.sort((a, b) => a.compareTo(b));
// Using this comparator in order to be deterministic
this.outerEdges.sort(function (a, b) {
var aNode = a.to,
bNode = b.to;
if (!this.outerEdgesSorted) {
//this.outerEdges.sort((a, b) => a.compareTo(b));
// Using this comparator in order to be deterministic
this.outerEdges.sort(function (a, b) {
var aNode = a.to,
bNode = b.to;
if (aNode.coordinates[0] - this$1.coordinates[0] >= 0 && bNode.coordinates[0] - this$1.coordinates[0] < 0)
{ return 1; }
if (aNode.coordinates[0] - this$1.coordinates[0] < 0 && bNode.coordinates[0] - this$1.coordinates[0] >= 0)
{ return -1; }
if (aNode.coordinates[0] - this$1.coordinates[0] >= 0 && bNode.coordinates[0] - this$1.coordinates[0] < 0)
{ return 1; }
if (aNode.coordinates[0] - this$1.coordinates[0] < 0 && bNode.coordinates[0] - this$1.coordinates[0] >= 0)
{ return -1; }
if (aNode.coordinates[0] - this$1.coordinates[0] === 0 && bNode.coordinates[0] - this$1.coordinates[0] === 0) {
if (aNode.coordinates[1] - this$1.coordinates[1] >= 0 || bNode.coordinates[1] - this$1.coordinates[1] >= 0)
{ return aNode.coordinates[1] - bNode.coordinates[1]; }
return bNode.coordinates[1] - aNode.coordinates[1];
}
if (aNode.coordinates[0] - this$1.coordinates[0] === 0 && bNode.coordinates[0] - this$1.coordinates[0] === 0) {
if (aNode.coordinates[1] - this$1.coordinates[1] >= 0 || bNode.coordinates[1] - this$1.coordinates[1] >= 0)
{ return aNode.coordinates[1] - bNode.coordinates[1]; }
return bNode.coordinates[1] - aNode.coordinates[1];
}
var det = orientationIndex(this$1.coordinates, aNode.coordinates, bNode.coordinates);
if (det < 0)
{ return 1; }
if (det > 0)
{ return -1; }
var det = orientationIndex(this$1.coordinates, aNode.coordinates, bNode.coordinates);
if (det < 0)
{ return 1; }
if (det > 0)
{ return -1; }
var d1 = Math.pow(aNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - this$1.coordinates[1], 2),
d2 = Math.pow(bNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - this$1.coordinates[1], 2);
var d1 = Math.pow(aNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - this$1.coordinates[1], 2),
d2 = Math.pow(bNode.coordinates[0] - this$1.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - this$1.coordinates[1], 2);
return d1 - d2;
});
this.outerEdgesSorted = true;
}
return d1 - d2;
});
this.outerEdgesSorted = true;
}
};
/** Retrieves outer edges.
/**
* 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.
*/
Node.prototype.getOuterEdges = function getOuterEdges () {
this.sortOuterEdges();
return this.outerEdges;
this.sortOuterEdges();
return this.outerEdges;
};
Node.prototype.getOuterEdge = function getOuterEdge (i) {
this.sortOuterEdges();
return this.outerEdges[i];
this.sortOuterEdges();
return this.outerEdges[i];
};
Node.prototype.addInnerEdge = function addInnerEdge (edge) {
this.innerEdges.push(edge);
this.innerEdges.push(edge);
};
/** This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge
/**
* This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge
*/
var Edge = function Edge(from, to) {
this.from = from; //< start
this.to = to; //< End
this.from = from; //< start
this.to = to; //< End
this.next = undefined; //< The edge to be computed after
this.label = undefined; //< Used in order to detect Cut Edges (Bridges)
this.symetric = undefined; //< The symetric edge of this
this.ring = undefined; //< EdgeRing in which the Edge is
this.next = undefined; //< The edge to be computed after
this.label = undefined; //< Used in order to detect Cut Edges (Bridges)
this.symetric = undefined; //< The symetric edge of this
this.ring = undefined; //< EdgeRing in which the Edge is
this.from.addOuterEdge(this);
this.to.addInnerEdge(this);
this.from.addOuterEdge(this);
this.to.addInnerEdge(this);
};
/** Removes edge from from and to nodes.
/**
* Removes edge from from and to nodes.
*/
Edge.prototype.getSymetric = function getSymetric () {
if (!this.symetric) {
this.symetric = new Edge(this.to, this.from);
this.symetric.symetric = this;
}
if (!this.symetric) {
this.symetric = new Edge(this.to, this.from);
this.symetric.symetric = this;
}
return this.symetric;
return this.symetric;
};
Edge.prototype.deleteEdge = function deleteEdge () {
this.from.removeOuterEdge(this);
this.to.removeInnerEdge(this);
this.from.removeOuterEdge(this);
this.to.removeInnerEdge(this);
};
/** Compares Edge equallity.
/**
* 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
* @returns {boolean} - True if Edges are equal, False otherwise
*/
Edge.prototype.isEqual = function isEqual (edge) {
return this.from.id === edge.from.id && this.to.id === edge.to.id;
return this.from.id === edge.from.id && this.to.id === edge.to.id;
};
Edge.prototype.toString = function toString () {
return ("Edge { " + (this.from.id) + " -> " + (this.to.id) + " }");
return ("Edge { " + (this.from.id) + " -> " + (this.to.id) + " }");
};
/** Returns a LineString representation of the Edge
/**
* Returns a LineString representation of the Edge
*

@@ -216,18 +241,22 @@ * @returns {Feature<LineString>} - LineString representation of the Edge

Edge.prototype.toLineString = function toLineString () {
return helpers.lineString([this.from.coordinates, this.to.coordinates]);
return helpers.lineString([this.from.coordinates, this.to.coordinates]);
};
/** Comparator of two edges.
/**
* 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
* @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
*/
Edge.prototype.compareTo = function compareTo (edge) {
return orientationIndex(edge.from.coordinates, edge.to.coordinates, this.to.coordinates);
return orientationIndex(edge.from.coordinates, edge.to.coordinates, this.to.coordinates);
};
/** Ring of edges which form a polygon.
/**
* Ring of edges which form a polygon.
*
* The ring may be either an outer shell or a hole.

@@ -238,5 +267,5 @@ *

var EdgeRing = function EdgeRing() {
this.edges = [];
this.polygon = undefined; //< Caches Polygon representation
this.envelope = undefined; //< Caches Envelope representation
this.edges = [];
this.polygon = undefined; //< Caches Polygon representation
this.envelope = undefined; //< Caches Envelope representation
};

@@ -246,40 +275,50 @@

/** Add an edge to the ring, inserting it in the last position.
/**
* Add an edge to the ring, inserting it in the last position.
*
* @memberof EdgeRing
* @param {Edge} edge - Edge to be inserted
*/
EdgeRing.prototype.push = function push (edge) {
// Emulate Array getter ([]) behaviour
this[this.edges.length] = edge;
this.edges.push(edge);
this.polygon = this.envelope = undefined;
// Emulate Array getter ([]) behaviour
this[this.edges.length] = edge;
this.edges.push(edge);
this.polygon = this.envelope = undefined;
};
/** Get Edge.
/**
* Get Edge.
*
* @param {Number} i - Index
* @memberof EdgeRing
* @param {number} i - Index
* @returns {Edge} - Edge in the i position
*/
EdgeRing.prototype.get = function get (i) {
return this.edges[i];
return this.edges[i];
};
/** Getter of length property.
/**
* Getter of length property.
*
* @returns {Number} - Length of the edge ring.
* @memberof EdgeRing
* @returns {number} - Length of the edge ring.
*/
prototypeAccessors.length.get = function () {
return this.edges.length;
return this.edges.length;
};
/** Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.
/**
* 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
*/
EdgeRing.prototype.forEach = function forEach (f) {
this.edges.forEach(f);
this.edges.forEach(f);
};
/** Similar to Array.prototype.map for the list of Edges in the EdgeRing.
/**
* 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

@@ -289,15 +328,19 @@ * @returns {Array} - The mapped values in the function

EdgeRing.prototype.map = function map (f) {
return this.edges.map(f);
return this.edges.map(f);
};
/** Similar to Array.prototype.some for the list of Edges in the EdgeRing.
/**
* 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
* @returns {boolean} - True if an Edge check the condition
*/
EdgeRing.prototype.some = function some (f) {
return this.edges.some(f);
return this.edges.some(f);
};
/** Check if the ring is valid in geomtry terms.
/**
* 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

@@ -307,58 +350,72 @@ * equal (in 2D)

*
* @returns {Boolean} - Validity of the EdgeRing
* @memberof EdgeRing
* @returns {boolean} - Validity of the EdgeRing
*/
EdgeRing.prototype.isValid = function isValid () {
// TODO: stub
return true;
// TODO: stub
return true;
};
/** Tests whether this ring is a hole.
/**
* 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
* @returns {Boolean} - true: if it is a hole
*
* @memberof EdgeRing
* @returns {boolean} - true: if it is a hole
*/
EdgeRing.prototype.isHole = function isHole () {
var this$1 = this;
var this$1 = this;
// XXX: Assuming Ring is valid
// Find highest point
var hiIndex = this.edges.reduce(function (high, edge, i) {
if (edge.from.coordinates[1] > this$1.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);
// XXX: Assuming Ring is valid
// Find highest point
var hiIndex = this.edges.reduce(function (high, edge, i) {
if (edge.from.coordinates[1] > this$1.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;
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).
/**
* Creates a MultiPoint representing the EdgeRing (discarts edges directions).
*
* @memberof EdgeRing
* @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing
*/
EdgeRing.prototype.toMultiPoint = function toMultiPoint () {
return helpers.multiPoint(this.edges.map(function (edge) { return edge.from.coordinates; }));
return helpers.multiPoint(this.edges.map(function (edge) { return edge.from.coordinates; }));
};
/** Creates a Polygon representing the EdgeRing.
/**
* Creates a Polygon representing the EdgeRing.
*
* @memberof EdgeRing
* @returns {Feature<Polygon>} - Polygon representation of the Edge Ring
*/
EdgeRing.prototype.toPolygon = function toPolygon () {
if (this.polygon)
{ return this.polygon; }
var coordinates = this.edges.map(function (edge) { return edge.from.coordinates; });
coordinates.push(this.edges[0].from.coordinates);
return (this.polygon = helpers.polygon([coordinates]));
if (this.polygon)
{ return this.polygon; }
var coordinates = this.edges.map(function (edge) { return edge.from.coordinates; });
coordinates.push(this.edges[0].from.coordinates);
return (this.polygon = helpers.polygon([coordinates]));
};
/** Calculates the envelope of the EdgeRing.
/**
* Calculates the envelope of the EdgeRing.
*
* @memberof EdgeRing
* @returns {Feature<Polygon>} - envelope
*/
EdgeRing.prototype.getEnvelope = function getEnvelope () {
if (this.envelope)
{ return this.envelope; }
return (this.envelope = envelope(this.toPolygon()));
if (this.envelope)
{ return this.envelope; }
return (this.envelope = envelope(this.toPolygon()));
};

@@ -375,37 +432,38 @@

EdgeRing.findEdgeRingContaining = function findEdgeRingContaining (testEdgeRing, shellList) {
var testEnvelope = testEdgeRing.getEnvelope();
var testEnvelope = testEdgeRing.getEnvelope();
var minEnvelope,
minShell;
shellList.forEach(function (shell) {
var tryEnvelope = shell.getEnvelope();
var minEnvelope,
minShell;
shellList.forEach(function (shell) {
var tryEnvelope = shell.getEnvelope();
if (minShell)
{ minEnvelope = minShell.getEnvelope(); }
if (minShell)
{ minEnvelope = minShell.getEnvelope(); }
// the hole envelope cannot equal the shell envelope
if (envelopeIsEqual(tryEnvelope, testEnvelope))
{ return; }
// the hole envelope cannot equal the shell envelope
if (envelopeIsEqual(tryEnvelope, testEnvelope))
{ return; }
if (envelopeContains(tryEnvelope, testEnvelope)) {
var testPoint = testEdgeRing.map(function (edge) { return edge.from.coordinates; })
.find(function (pt) { return !shell.some(function (edge) { return coordinatesEqual(pt, edge.from.coordinates); }); });
if (envelopeContains(tryEnvelope, testEnvelope)) {
var testPoint = testEdgeRing.map(function (edge) { return edge.from.coordinates; })
.find(function (pt) { return !shell.some(function (edge) { return coordinatesEqual(pt, edge.from.coordinates); }); });
if (testPoint && shell.inside(helpers.point(testPoint))) {
if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
{ minShell = shell; }
}
}
});
if (testPoint && shell.inside(helpers.point(testPoint))) {
if (!minShell || envelopeContains(minEnvelope, tryEnvelope))
{ minShell = shell; }
}
}
});
return minShell;
return minShell;
};
/** Checks if the point is inside the edgeRing
/**
* Checks if the point is inside the edgeRing
*
* @param {Feature<Point>} point - Point to check if it is inside the edgeRing
* @returns {Boolean} - True if it is inside, False otherwise
* @param {Feature<Point>} pt - Point to check if it is inside the edgeRing
* @returns {boolean} - True if it is inside, False otherwise
*/
EdgeRing.prototype.inside = function inside (point$$1) {
return booleanPointInPolygon(point$$1, this.toPolygon());
EdgeRing.prototype.inside = function inside (pt) {
return booleanPointInPolygon(pt, this.toPolygon());
};

@@ -415,12 +473,13 @@

/** Validates the geoJson.
/**
* Validates the geoJson.
*
* @param {Geojson} geoJson - input geoJson.
* @param {GeoJSON} geoJson - input geoJson.
* @throws {Error} if geoJson is invalid.
*/
function validateGeoJson(geoJson) {
if (!geoJson)
{ throw new Error('No geojson passed'); }
if (!geoJson)
{ throw new Error('No geojson passed'); }
if (geoJson.type !== 'FeatureCollection' &&
if (geoJson.type !== 'FeatureCollection' &&
geoJson.type !== 'GeometryCollection' &&

@@ -430,8 +489,8 @@ geoJson.type !== 'MultiLineString' &&

geoJson.type !== 'Feature'
)
{ throw new Error(("Invalid input type '" + (geoJson.type) + "'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature")); }
)
{ throw new Error(("Invalid input type '" + (geoJson.type) + "'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature")); }
}
/** Represents a planar graph of edges and nodes that can be used to compute a
* polygonization.
/**
* Represents a planar graph of edges and nodes that can be used to compute a polygonization.
*

@@ -445,46 +504,50 @@ * Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,

var Graph = function Graph() {
this.edges = []; //< {Edge[]} dirEdges
this.edges = []; //< {Edge[]} dirEdges
// The key is the `id` of the Node (ie: coordinates.join(','))
this.nodes = {};
// The key is the `id` of the Node (ie: coordinates.join(','))
this.nodes = {};
};
/** Removes Dangle Nodes (nodes with grade 1).
/**
* Removes Dangle Nodes (nodes with grade 1).
*/
Graph.fromGeoJson = function fromGeoJson (geoJson) {
validateGeoJson(geoJson);
validateGeoJson(geoJson);
var graph = new Graph();
meta.flattenEach(geoJson, function (feature) {
invariant.featureOf(feature, 'LineString', 'Graph::fromGeoJson');
// When a LineString if formed by many segments, split them
meta.coordReduce(feature, function (prev, cur) {
if (prev) {
var start = graph.getNode(prev),
end = graph.getNode(cur);
var graph = new Graph();
meta.flattenEach(geoJson, function (feature) {
invariant.featureOf(feature, 'LineString', 'Graph::fromGeoJson');
// When a LineString if formed by many segments, split them
meta.coordReduce(feature, function (prev, cur) {
if (prev) {
var start = graph.getNode(prev),
end = graph.getNode(cur);
graph.addEdge(start, end);
}
return cur;
graph.addEdge(start, end);
}
return cur;
});
});
});
return graph;
return graph;
};
/** Creates or get a Node.
/**
* Creates or get a Node.
*
* @param {Number[]} coordinates - Coordinates of the node
* @param {number[]} coordinates - Coordinates of the node
* @returns {Node} - The created or stored node
*/
Graph.prototype.getNode = function getNode (coordinates) {
var id = Node.buildId(coordinates);
var node = this.nodes[id];
if (!node)
{ node = this.nodes[id] = new Node(coordinates); }
var id = Node.buildId(coordinates);
var node = this.nodes[id];
if (!node)
{ node = this.nodes[id] = new Node(coordinates); }
return node;
return node;
};
/** Adds an Edge and its symetricall.
/**
* Adds an Edge and its symetricall.
*
* Edges are added symetrically, i.e.: we also add its symetric

@@ -496,18 +559,20 @@ *

Graph.prototype.addEdge = function addEdge (from, to) {
var edge = new Edge(from, to),
symetricEdge = edge.getSymetric();
var edge = new Edge(from, to),
symetricEdge = edge.getSymetric();
this.edges.push(edge);
this.edges.push(symetricEdge);
this.edges.push(edge);
this.edges.push(symetricEdge);
};
Graph.prototype.deleteDangles = function deleteDangles () {
var this$1 = this;
var this$1 = this;
Object.keys(this.nodes)
.map(function (id) { return this$1.nodes[id]; })
.forEach(function (node) { return this$1._removeIfDangle(node); });
Object.keys(this.nodes)
.map(function (id) { return this$1.nodes[id]; })
.forEach(function (node) { return this$1._removeIfDangle(node); });
};
/** Check if node is dangle, if so, remove it.
/**
* Check if node is dangle, if so, remove it.
*
* It calls itself recursively, removing a dangling node might cause another dangling node

@@ -518,13 +583,14 @@ *

Graph.prototype._removeIfDangle = function _removeIfDangle (node) {
var this$1 = this;
var this$1 = this;
// As edges are directed and symetrical, we count only innerEdges
if (node.innerEdges.length <= 1) {
var outerNodes = node.getOuterEdges().map(function (e) { return e.to; });
this.removeNode(node);
outerNodes.forEach(function (n) { return this$1._removeIfDangle(n); });
}
// As edges are directed and symetrical, we count only innerEdges
if (node.innerEdges.length <= 1) {
var outerNodes = node.getOuterEdges().map(function (e) { return e.to; });
this.removeNode(node);
outerNodes.forEach(function (n) { return this$1._removeIfDangle(n); });
}
};
/** Delete cut-edges (bridge edges).
/**
* Delete cut-edges (bridge edges).
*

@@ -536,17 +602,19 @@ * The graph will be traversed, all the edges will be labeled according the ring

Graph.prototype.deleteCutEdges = function deleteCutEdges () {
var this$1 = this;
var this$1 = this;
this._computeNextCWEdges();
this._findLabeledEdgeRings();
this._computeNextCWEdges();
this._findLabeledEdgeRings();
// Cut-edges (bridges) are edges where both edges have the same label
this.edges.forEach(function (edge) {
if (edge.label === edge.symetric.label) {
this$1.removeEdge(edge.symetric);
this$1.removeEdge(edge);
}
});
// Cut-edges (bridges) are edges where both edges have the same label
this.edges.forEach(function (edge) {
if (edge.label === edge.symetric.label) {
this$1.removeEdge(edge.symetric);
this$1.removeEdge(edge);
}
});
};
/** Set the `next` property of each 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.

@@ -558,15 +626,17 @@ * OuterEdges are sorted CCW.

Graph.prototype._computeNextCWEdges = function _computeNextCWEdges (node) {
var this$1 = this;
var this$1 = this;
if (typeof node === 'undefined') {
Object.keys(this.nodes)
.forEach(function (id) { return this$1._computeNextCWEdges(this$1.nodes[id]); });
} else {
node.getOuterEdges().forEach(function (edge, i) {
node.getOuterEdge((i === 0 ? node.getOuterEdges().length : i) - 1).symetric.next = edge;
});
}
if (typeof node === 'undefined') {
Object.keys(this.nodes)
.forEach(function (id) { return this$1._computeNextCWEdges(this$1.nodes[id]); });
} else {
node.getOuterEdges().forEach(function (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.
/**
* 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

@@ -578,44 +648,46 @@ *

* @param {Node} node - Node
* @param {Number} label - Ring's label
* @param {number} label - Ring's label
*/
Graph.prototype._computeNextCCWEdges = function _computeNextCCWEdges (node, label) {
var edges = node.getOuterEdges();
var firstOutDE,
prevInDE;
var edges = node.getOuterEdges();
var firstOutDE,
prevInDE;
for (var i = edges.length - 1; i >= 0; --i) {
var de = edges[i],
sym = de.symetric,
outDE = (void 0),
inDE = (void 0);
for (var i = edges.length - 1; i >= 0; --i) {
var de = edges[i],
sym = de.symetric,
outDE = (void 0),
inDE = (void 0);
if (de.label === label)
{ outDE = de; }
if (de.label === label)
{ outDE = de; }
if (sym.label === label)
{ inDE = sym; }
if (sym.label === label)
{ inDE = sym; }
if (!outDE || !inDE) // This edge is not in edgering
{ continue; }
if (!outDE || !inDE) // This edge is not in edgering
{ continue; }
if (inDE)
{ prevInDE = inDE; }
if (inDE)
{ prevInDE = inDE; }
if (outDE) {
if (prevInDE) {
prevInDE.next = outDE;
prevInDE = undefined;
}
if (outDE) {
if (prevInDE) {
prevInDE.next = outDE;
prevInDE = undefined;
}
if (!firstOutDE)
{ firstOutDE = outDE; }
if (!firstOutDE)
{ firstOutDE = outDE; }
}
}
}
if (prevInDE)
{ prevInDE.next = firstOutDE; }
if (prevInDE)
{ prevInDE.next = firstOutDE; }
};
/** Finds rings and labels edges according to which rings are.
/**
* Finds rings and labels edges according to which rings are.
*
* The label is a number which is increased for each ring.

@@ -626,23 +698,24 @@ *

Graph.prototype._findLabeledEdgeRings = function _findLabeledEdgeRings () {
var edgeRingStarts = [];
var label = 0;
this.edges.forEach(function (edge) {
if (edge.label >= 0)
{ return; }
var edgeRingStarts = [];
var label = 0;
this.edges.forEach(function (edge) {
if (edge.label >= 0)
{ return; }
edgeRingStarts.push(edge);
edgeRingStarts.push(edge);
var e = edge;
do {
e.label = label;
e = e.next;
} while (!edge.isEqual(e));
var e = edge;
do {
e.label = label;
e = e.next;
} while (!edge.isEqual(e));
label++;
});
label++;
});
return edgeRingStarts;
return edgeRingStarts;
};
/** Computes the EdgeRings formed by the edges in this graph.
/**
* Computes the EdgeRings formed by the edges in this graph.
*

@@ -652,31 +725,32 @@ * @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.

Graph.prototype.getEdgeRings = function getEdgeRings () {
var this$1 = this;
var this$1 = this;
this._computeNextCWEdges();
this._computeNextCWEdges();
// Clear labels
this.edges.forEach(function (edge) {
edge.label = undefined;
});
// Clear labels
this.edges.forEach(function (edge) {
edge.label = undefined;
});
this._findLabeledEdgeRings().forEach(function (edge) {
// convertMaximalToMinimalEdgeRings
this$1._findIntersectionNodes(edge).forEach(function (node) {
this$1._computeNextCCWEdges(node, edge.label);
this._findLabeledEdgeRings().forEach(function (edge) {
// convertMaximalToMinimalEdgeRings
this$1._findIntersectionNodes(edge).forEach(function (node) {
this$1._computeNextCCWEdges(node, edge.label);
});
});
});
var edgeRingList = [];
var edgeRingList = [];
// find all edgerings
this.edges.forEach(function (edge) {
if (edge.ring)
{ return; }
edgeRingList.push(this$1._findEdgeRing(edge));
});
// find all edgerings
this.edges.forEach(function (edge) {
if (edge.ring)
{ return; }
edgeRingList.push(this$1._findEdgeRing(edge));
});
return edgeRingList;
return edgeRingList;
};
/** Find all nodes in a Maxima EdgeRing which are self-intersection nodes.
/**
* Find all nodes in a Maxima EdgeRing which are self-intersection nodes.
*

@@ -687,26 +761,27 @@ * @param {Node} startEdge - Start Edge of the Ring

Graph.prototype._findIntersectionNodes = function _findIntersectionNodes (startEdge) {
var intersectionNodes = [];
var edge = startEdge;
var loop = function () {
// getDegree
var degree = 0;
edge.from.getOuterEdges().forEach(function (e) {
if (e.label === startEdge.label)
{ ++degree; }
});
var intersectionNodes = [];
var edge = startEdge;
var loop = function () {
// getDegree
var degree = 0;
edge.from.getOuterEdges().forEach(function (e) {
if (e.label === startEdge.label)
{ ++degree; }
});
if (degree > 1)
{ intersectionNodes.push(edge.from); }
if (degree > 1)
{ intersectionNodes.push(edge.from); }
edge = edge.next;
};
edge = edge.next;
};
do {
loop();
} while (!startEdge.isEqual(edge));
do {
loop();
} while (!startEdge.isEqual(edge));
return intersectionNodes;
return intersectionNodes;
};
/** Get the edge-ring which starts from the provided Edge.
/**
* Get the edge-ring which starts from the provided Edge.
*

@@ -717,15 +792,16 @@ * @param {Edge} startEdge - starting edge of the edge ring

Graph.prototype._findEdgeRing = function _findEdgeRing (startEdge) {
var edge = startEdge;
var edgeRing = new EdgeRing();
var edge = startEdge;
var edgeRing = new EdgeRing();
do {
edgeRing.push(edge);
edge.ring = edgeRing;
edge = edge.next;
} while (!startEdge.isEqual(edge));
do {
edgeRing.push(edge);
edge.ring = edgeRing;
edge = edge.next;
} while (!startEdge.isEqual(edge));
return edgeRing;
return edgeRing;
};
/** Removes a node from the Graph.
/**
* Removes a node from the Graph.
*

@@ -736,10 +812,11 @@ * It also removes edges asociated to that node

Graph.prototype.removeNode = function removeNode (node) {
var this$1 = this;
var this$1 = this;
node.getOuterEdges().forEach(function (edge) { return this$1.removeEdge(edge); });
node.innerEdges.forEach(function (edge) { return this$1.removeEdge(edge); });
delete this.nodes[node.id];
node.getOuterEdges().forEach(function (edge) { return this$1.removeEdge(edge); });
node.innerEdges.forEach(function (edge) { return this$1.removeEdge(edge); });
delete this.nodes[node.id];
};
/** Remove edge from the graph and deletes the edge.
/**
* Remove edge from the graph and deletes the edge.
*

@@ -749,4 +826,4 @@ * @param {Edge} edge - Edge to be removed

Graph.prototype.removeEdge = function removeEdge (edge) {
this.edges = this.edges.filter(function (e) { return !e.isEqual(edge); });
edge.deleteEdge();
this.edges = this.edges.filter(function (e) { return !e.isEqual(edge); });
edge.deleteEdge();
};

@@ -773,31 +850,31 @@

function polygonize$1(geoJson) {
var graph = Graph.fromGeoJson(geoJson);
var graph = Graph.fromGeoJson(geoJson);
// 1. Remove dangle node
graph.deleteDangles();
// 1. Remove dangle node
graph.deleteDangles();
// 2. Remove cut-edges (bridge edges)
graph.deleteCutEdges();
// 2. Remove cut-edges (bridge edges)
graph.deleteCutEdges();
// 3. Get all holes and shells
var holes = [],
shells = [];
// 3. Get all holes and shells
var holes = [],
shells = [];
graph.getEdgeRings()
.filter(function (edgeRing) { return edgeRing.isValid(); })
.forEach(function (edgeRing) {
if (edgeRing.isHole())
{ holes.push(edgeRing); }
else
{ shells.push(edgeRing); }
graph.getEdgeRings()
.filter(function (edgeRing) { return edgeRing.isValid(); })
.forEach(function (edgeRing) {
if (edgeRing.isHole())
{ holes.push(edgeRing); }
else
{ shells.push(edgeRing); }
});
// 4. Assign Holes to Shells
holes.forEach(function (hole) {
if (EdgeRing.findEdgeRingContaining(hole, shells))
{ shells.push(hole); }
});
// 4. Assign Holes to Shells
holes.forEach(function (hole) {
if (EdgeRing.findEdgeRingContaining(hole, shells))
{ shells.push(hole); }
});
// 5. EdgeRings to Polygons
return helpers.featureCollection(shells.map(function (shell) { return shell.toPolygon(); }));
// 5. EdgeRings to Polygons
return helpers.featureCollection(shells.map(function (shell) { return shell.toPolygon(); }));
}

@@ -804,0 +881,0 @@

18

package.json
{
"name": "@turf/polygonize",
"version": "5.1.2",
"version": "5.1.5",
"description": "turf polygonize module",
"main": "main.js",
"module": "main.mjs",
"module": "main.es.js",
"types": "index.d.ts",

@@ -12,4 +12,4 @@ "files": [

"main.js",
"main.mjs",
"lib"
"lib",
"main.es.js"
],

@@ -52,7 +52,7 @@ "scripts": {

"dependencies": {
"@turf/boolean-point-in-polygon": "^5.1.0",
"@turf/envelope": "^5.1.0",
"@turf/helpers": "^5.1.0",
"@turf/invariant": "^5.1.0",
"@turf/meta": "^5.1.0"
"@turf/boolean-point-in-polygon": "^5.1.5",
"@turf/envelope": "^5.1.5",
"@turf/helpers": "^5.1.5",
"@turf/invariant": "^5.1.5",
"@turf/meta": "^5.1.5"
},

@@ -59,0 +59,0 @@ "@std/esm": {

main.mjs
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc