graphs-and-paths - npm Package Compare versions

Comparing version 0.2.0 to 0.2.1

dist/graph.d.ts

@@ -75,2 +75,21 @@ import { Edge, EdgeId, EdgePoint, Location, Node, NodeId, Path, SimpleEdge, SimpleNode } from "./types";
     static advanceAlongLocations(locations: Location[], distance: number): Location[];
+    /**
+     * Returns a new path obtained by truncating the given path by the provided distance. That is,
+     * the start point of the path moves forward, and any nodes and edges that it passes are
+     * dropped. Throws an error if distance is negative.
+     *
+     * @param path A path.
+     * @param distance A distance to travel along the path.
+     * @returns The remaining portion of `path` after traveling `distance` along it.
+     */
+    static advanceAlongPath(path: Path, distance: number): Path;
+    /**
+     * Returns the path obtained when advancing the given path all the way to the end.
+     */
+    private static getFinishedPath(path);
+    /**
+     * Removes zero-length segments at the start and end of the path caused by the ambiguity of
+     * representing a Node location with an EdgePoint.
+     */
+    private static canonicalizePath(path);
     private constructor(nodesById, edgesById, mesh?);
@@ -126,2 +145,7 @@ /**
     /**
+     * Returns the Cartesian coordinates of the point a certain distance along an edge. Does not
+     * throw on out-of-bounds distances. Instead negative distances return the start of the edge
+     * and distances greater than the length return the end of the edge. This is to avoid unexpected
+     * behavior due to floating-point imprecision issues.
+     *
      * @param edgePoint A point specified as a certain distance along an edge.
@@ -135,4 +159,5 @@ * @return The Cartesian coordinates of the given point.
      * single edge, where the removed nodes are converted into inner locations of the new edge. In
-     * particular, the new graph will have no nodes of degree 2. This may significantly increase
-     * the speed of certain calculations, such as [[getShortestPath]].
+     * particular, the new graph will have no nodes of degree 2 except for nodes with only one edge
+     * connecting to themselves. This may significantly increase the speed of certain calculations,
+     * such as [[getShortestPath]].
      *
@@ -165,12 +190,2 @@ * A newly created edge will have the lowest ID of the edges which were combined to form it,
     /**
-     * Returns a new path obtained by truncating the given path by the provided distance. That is,
-     * the start point of the path moves forward, and any nodes and edges that it passes are
-     * dropped. Throws an error if distance is negative.
-     *
-     * @param path A path.
-     * @param distance A distance to travel along the path.
-     * @returns The remaining portion of `path` after traveling `distance` along it.
-     */
-    advanceAlongPath(path: Path, distance: number): Path;
-    /**
      * Does preprocessing to enable [[getClosestPoint]] by creating a spatial index for mesh of
@@ -177,0 +192,0 @@ * points along the graph.

dist/graph.js

 "use strict";
+var __assign = (this && this.__assign) || Object.assign || function(t) {
+    for (var s, i = 1, n = arguments.length; i < n; i++) {
+        s = arguments[i];
+        for (var p in s) if (Object.prototype.hasOwnProperty.call(s, p))
+            t[p] = s[p];
+    }
+    return t;
+};
 var Heap = require("heap");
@@ -149,2 +157,117 @@ var rbush = require("rbush");
     /**
+     * Returns a new path obtained by truncating the given path by the provided distance. That is,
+     * the start point of the path moves forward, and any nodes and edges that it passes are
+     * dropped. Throws an error if distance is negative.
+     *
+     * @param path A path.
+     * @param distance A distance to travel along the path.
+     * @returns The remaining portion of `path` after traveling `distance` along it.
+     */
+    Graph.advanceAlongPath = function (path, distance) {
+        var start = path.start, end = path.end, orientedEdges = path.orientedEdges, nodes = path.nodes, locations = path.locations, length = path.length;
+        if (distance === 0) {
+            return path;
+        }
+        else if (distance >= length) {
+            return Graph.getFinishedPath(path);
+        }
+        else if (distance < 0) {
+            throw new Error("Cannot advance path by a negative distance");
+        }
+        else {
+            var _a = orientedEdges[0], startEdge = _a.edge, isStartEdgeForward = _a.isForward;
+            var orientedStartDistance = isStartEdgeForward
+                ? start.distance
+                : startEdge.length - start.distance;
+            var distanceRemaining = distance + orientedStartDistance;
+            var edgeIndex = 0;
+            while (distanceRemaining >= orientedEdges[edgeIndex].edge.length) {
+                distanceRemaining -= orientedEdges[edgeIndex].edge.length;
+                edgeIndex++;
+                if (edgeIndex >= orientedEdges.length) {
+                    // Only possible through floating-point imprecision because of earlier check
+                    // against total distance. I'm not even sure this case is possible, but better
+                    // safe than sorry.
+                    return Graph.getFinishedPath(path);
+                }
+            }
+            var newStartEdge = orientedEdges[edgeIndex];
+            var distanceDownEdge = newStartEdge.isForward
+                ? distanceRemaining
+                : newStartEdge.edge.length - distanceRemaining;
+            return {
+                start: { edgeId: newStartEdge.edge.id, distance: distanceDownEdge },
+                end: end,
+                orientedEdges: orientedEdges.slice(edgeIndex),
+                nodes: nodes.slice(edgeIndex),
+                locations: Graph.advanceAlongLocations(locations, distance),
+                length: length - distance,
+            };
+        }
+    };
+    /**
+     * Returns the path obtained when advancing the given path all the way to the end.
+     */
+    Graph.getFinishedPath = function (path) {
+        var end = path.end, orientedEdges = path.orientedEdges, locations = path.locations;
+        return {
+            start: end,
+            end: end,
+            orientedEdges: [Utils.last(orientedEdges)],
+            nodes: [],
+            locations: [Utils.last(locations)],
+            length: 0,
+        };
+    };
+    /**
+     * Removes zero-length segments at the start and end of the path caused by the ambiguity of
+     * representing a Node location with an EdgePoint.
+     */
+    Graph.canonicalizePath = function (path) {
+        var start = path.start, end = path.end, orientedEdges = path.orientedEdges, nodes = path.nodes;
+        if (start === end) {
+            return path;
+        }
+        var firstEdge = orientedEdges[0];
+        var lastEdge = Utils.last(orientedEdges);
+        var firstEdgeIsTrivial = (firstEdge.isForward && start.distance >= firstEdge.edge.length)
+            || (!firstEdge.isForward && start.distance <= 0);
+        var lastEdgeIsTrivial = (lastEdge.isForward && end.distance <= 0)
+            || (!lastEdge.isForward && end.distance >= lastEdge.edge.length);
+        if (firstEdgeIsTrivial && lastEdgeIsTrivial && nodes.length === 1) {
+            return __assign({}, path, { start: end, end: end, nodes: [], orientedEdges: [Utils.last(orientedEdges)] });
+        }
+        else if (firstEdgeIsTrivial || lastEdgeIsTrivial) {
+            var newStart = (function () {
+                if (firstEdgeIsTrivial) {
+                    var secondEdge = orientedEdges[1];
+                    return {
+                        edgeId: secondEdge.edge.id,
+                        distance: secondEdge.isForward ? 0 : secondEdge.edge.length,
+                    };
+                }
+                else {
+                    return start;
+                }
+            })();
+            var newEnd = (function () {
+                if (lastEdgeIsTrivial) {
+                    var secondLastEdge = orientedEdges[orientedEdges.length - 2];
+                    return {
+                        edgeId: secondLastEdge.edge.id,
+                        distance: secondLastEdge.isForward ? secondLastEdge.edge.length : 0,
+                    };
+                }
+                else {
+                    return end;
+                }
+            })();
+            var slice = function (xs) { return xs.slice(firstEdgeIsTrivial ? 1 : 0, lastEdgeIsTrivial ? xs.length - 1 : xs.length); };
+            return __assign({}, path, { start: newStart, end: newEnd, orientedEdges: slice(orientedEdges), nodes: slice(nodes) });
+        }
+        else {
+            return path;
+        }
+    };
+    /**
      * @returns All the nodes present in this graph, in the order that they were originally provided
@@ -227,2 +350,7 @@ *          to [[Graph.create]].
     /**
+     * Returns the Cartesian coordinates of the point a certain distance along an edge. Does not
+     * throw on out-of-bounds distances. Instead negative distances return the start of the edge
+     * and distances greater than the length return the end of the edge. This is to avoid unexpected
+     * behavior due to floating-point imprecision issues.
+     *
      * @param edgePoint A point specified as a certain distance along an edge.
@@ -250,4 +378,5 @@ * @return The Cartesian coordinates of the given point.
      * single edge, where the removed nodes are converted into inner locations of the new edge. In
-     * particular, the new graph will have no nodes of degree 2. This may significantly increase
-     * the speed of certain calculations, such as [[getShortestPath]].
+     * particular, the new graph will have no nodes of degree 2 except for nodes with only one edge
+     * connecting to themselves. This may significantly increase the speed of certain calculations,
+     * such as [[getShortestPath]].
      *
@@ -368,3 +497,3 @@ * A newly created edge will have the lowest ID of the edges which were combined to form it,
             if (currentNodeId == null) {
-                return { value: this_1.reconstructPath(start, end, cameFrom, endEdgeIsForward, endDistanceFromStart) };
+                return { value: Graph.canonicalizePath(this_1.reconstructPath(start, end, cameFrom, endEdgeIsForward, endDistanceFromStart)) };
             }
@@ -412,54 +541,2 @@ else {
     /**
-     * Returns a new path obtained by truncating the given path by the provided distance. That is,
-     * the start point of the path moves forward, and any nodes and edges that it passes are
-     * dropped. Throws an error if distance is negative.
-     *
-     * @param path A path.
-     * @param distance A distance to travel along the path.
-     * @returns The remaining portion of `path` after traveling `distance` along it.
-     */
-    Graph.prototype.advanceAlongPath = function (path, distance) {
-        var start = path.start, end = path.end, orientedEdges = path.orientedEdges, nodes = path.nodes, locations = path.locations, length = path.length;
-        if (distance === 0) {
-            return path;
-        }
-        else if (distance >= path.length) {
-            return {
-                start: end,
-                end: end,
-                orientedEdges: [Utils.last(orientedEdges)],
-                nodes: [],
-                locations: [Utils.last(path.locations)],
-                length: 0,
-            };
-        }
-        else if (distance < 0) {
-            throw new Error("Cannot advance path by a negative distance");
-        }
-        else {
-            var _a = orientedEdges[0], startEdge = _a.edge, isStartEdgeForward = _a.isForward;
-            var orientedStartDistance = isStartEdgeForward
-                ? start.distance
-                : startEdge.length - start.distance;
-            var distanceRemaining = distance + orientedStartDistance;
-            var edgeIndex = 0;
-            while (distanceRemaining > orientedEdges[edgeIndex].edge.length) {
-                distanceRemaining -= orientedEdges[edgeIndex].edge.length;
-                edgeIndex++;
-            }
-            var newStartEdge = orientedEdges[edgeIndex];
-            var distanceDownEdge = newStartEdge.isForward
-                ? distanceRemaining
-                : newStartEdge.edge.length - distanceRemaining;
-            return {
-                start: { edgeId: newStartEdge.edge.id, distance: distanceDownEdge },
-                end: end,
-                orientedEdges: orientedEdges.slice(edgeIndex),
-                nodes: nodes.slice(edgeIndex),
-                locations: Graph.advanceAlongLocations(locations, distance),
-                length: length - distance,
-            };
-        }
-    };
-    /**
      * Does preprocessing to enable [[getClosestPoint]] by creating a spatial index for mesh of
@@ -466,0 +543,0 @@ * points along the graph.

package.json

 {
   "name": "graphs-and-paths",
-  "version": "0.2.0",
+  "version": "0.2.1",
   "description": "Tools for graphs representing 2-D spatial points and links between them.",
@@ -45,3 +45,3 @@ "main": "dist/index.js",
     "jest": "^18.0.0",
-    "tslint": "^4.1.1",
+    "tslint": "^4.3.1",
     "typedoc": "^0.5.3",
@@ -48,0 +48,0 @@ "typedoc-default-themes": "0.4.0",

README.md

 # Graphs and Paths
 
-Tools for graphs representing 2-D spatial points and links between them. [View the demo here](https://dphilipson.github.io/graphs-and-paths-demo).
+Tools for graphs representing 2-D spatial points and links between them.
 
 [![Build Status](https://travis-ci.org/dphilipson/graphs-and-paths.svg?branch=develop)](https://travis-ci.org/dphilipson/graphs-and-paths)
 
+## Demo
+
+[View the demo](https://dphilipson.github.io/graphs-and-paths-demo).
+
 ## Installation
@@ -8,0 +12,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

92934

increased by7.89%

Lines of code

1400

increased by7.03%

Number of lines in readme file

58

increased by7.41%

No dependency changes