finds the route between two points/rectangles (`from`, `to`) implementing A* algorithm rectangles get rect points assigned by getRectPoints()
437097
function findRoute(from, to, map, opt) {

        var precision = opt.precision;

        // Get grid for this route.

        var sourceAnchor, targetAnchor;

        if (from instanceof g.Rect) { // `from` is sourceBBox
            sourceAnchor = round(getSourceAnchor(this, opt).clone(), precision);
        } else {
            sourceAnchor = round(from.clone(), precision);
        }

        if (to instanceof g.Rect) { // `to` is targetBBox
            targetAnchor = round(getTargetAnchor(this, opt).clone(), precision);
        } else {
            targetAnchor = round(to.clone(), precision);
        }

        var grid = getGrid(opt.step, sourceAnchor, targetAnchor);

        // Get pathfinding points.

        var start, end; // aligned with grid by definition
        var startPoints, endPoints; // assumed to be aligned with grid already

        // set of points we start pathfinding from
        if (from instanceof g.Rect) { // `from` is sourceBBox
            start = sourceAnchor;
            startPoints = getRectPoints(start, from, opt.startDirections, grid, opt);

        } else {
            start = sourceAnchor;
            startPoints = [start];
        }

        // set of points we want the pathfinding to finish at
        if (to instanceof g.Rect) { // `to` is targetBBox
            end = targetAnchor;
            endPoints = getRectPoints(targetAnchor, to, opt.endDirections, grid, opt);

        } else {
            end = targetAnchor;
            endPoints = [end];
        }

        // take into account only accessible rect points (those not under obstacles)
        startPoints = startPoints.filter(map.isPointAccessible, map);
        endPoints = endPoints.filter(map.isPointAccessible, map);

        // Check that there is an accessible route point on both sides.
        // Otherwise, use fallbackRoute().
        if (startPoints.length > 0 && endPoints.length > 0) {

            // The set of tentative points to be evaluated, initially containing the start points.
            // Rounded to nearest integer for simplicity.
            var openSet = new SortedSet();
            // Keeps reference to actual points for given elements of the open set.
            var points = {};
            // Keeps reference to a point that is immediate predecessor of given element.
            var parents = {};
            // Cost from start to a point along best known path.
            var costs = {};

            for (var i = 0, n = startPoints.length; i < n; i++) {
                // startPoint is assumed to be aligned already
                var startPoint = startPoints[i];

                var key = getKey(startPoint);

                openSet.add(key, estimateCost(startPoint, endPoints));
                points[key] = startPoint;
                costs[key] = 0;
            }

            var previousRouteDirectionAngle = opt.previousDirectionAngle; // undefined for first route
            var isPathBeginning = (previousRouteDirectionAngle === undefined);

            // directions
            var direction, directionChange;
            var directions = opt.directions;
            getGridOffsets(directions, grid, opt);

            var numDirections = directions.length;

            var endPointsKeys = util.toArray(endPoints).reduce(function(res, endPoint) {
                // endPoint is assumed to be aligned already

                var key = getKey(endPoint);
                res.push(key);
                return res;
            }, []);

            // main route finding loop
            var loopsRemaining = opt.maximumLoops;
            while (!openSet.isEmpty() && loopsRemaining > 0) {

                // remove current from the open list
                var currentKey = openSet.pop();
                var currentPoint = points[currentKey];
                var currentParent = parents[currentKey];
                var currentCost = costs[currentKey];

                var isRouteBeginning = (currentParent === undefined); // undefined for route starts
                var isStart = currentPoint.equals(start); // (is source anchor or `from` point) = can leave in any direction

                var previousDirectionAngle;
                if (!isRouteBeginning) previousDirectionAngle = getDirectionAngle(currentParent, currentPoint, numDirections, grid, opt); // a vertex on the route
                else if (!isPathBeginning) previousDirectionAngle = previousRouteDirectionAngle; // beginning of route on the path
                else if (!isStart) previousDirectionAngle = getDirectionAngle(start, currentPoint, numDirections, grid, opt); // beginning of path, start rect point
                else previousDirectionAngle = null; // beginning of path, source anchor or `from` point

                // check if we reached any endpoint
                if (endPointsKeys.indexOf(currentKey) >= 0) {
                    opt.previousDirectionAngle = previousDirectionAngle;
                    return reconstructRoute(parents, points, currentPoint, start, end, grid, opt);
                }

                // go over all possible directions and find neighbors
                for (i = 0; i < numDirections; i++) {
                    direction = directions[i];

                    var directionAngle = direction.angle;
                    directionChange = getDirectionChange(previousDirectionAngle, directionAngle);

                    // if the direction changed rapidly, don't use this point
                    // any direction is allowed for starting points
                    if (!(isPathBeginning && isStart) && directionChange > opt.maxAllowedDirectionChange) continue;

                    var neighborPoint = align(currentPoint.clone().offset(direction.gridOffsetX, direction.gridOffsetY), grid, precision);
                    var neighborKey = getKey(neighborPoint);

                    // Closed points from the openSet were already evaluated.
                    if (openSet.isClose(neighborKey) || !map.isPointAccessible(neighborPoint)) continue;

                    // We can only enter end points at an acceptable angle.
                    if (endPointsKeys.indexOf(neighborKey) >= 0) { // neighbor is an end point

                        var isNeighborEnd = neighborPoint.equals(end); // (is target anchor or `to` point) = can be entered in any direction

                        if (!isNeighborEnd) {
                            var endDirectionAngle = getDirectionAngle(neighborPoint, end, numDirections, grid, opt);
                            var endDirectionChange = getDirectionChange(directionAngle, endDirectionAngle);

                            if (endDirectionChange > opt.maxAllowedDirectionChange) continue;
                        }
                    }

                    // The current direction is ok.

                    var neighborCost = direction.cost;
                    var neighborPenalty = isStart ? 0 : opt.penalties[directionChange]; // no penalties for start point
                    var costFromStart = currentCost + neighborCost + neighborPenalty;

                    if (!openSet.isOpen(neighborKey) || (costFromStart < costs[neighborKey])) {
                        // neighbor point has not been processed yet
                        // or the cost of the path from start is lower than previously calculated

                        points[neighborKey] = neighborPoint;
                        parents[neighborKey] = currentPoint;
                        costs[neighborKey] = costFromStart;
                        openSet.add(neighborKey, costFromStart + estimateCost(neighborPoint, endPoints));
                    }
                }

                loopsRemaining--;
            }
        }

        // no route found (`to` point either wasn't accessible or finding route took
        // way too much calculation)
        return opt.fallbackRoute.call(this, start, end, opt);
    }
974500
public static RectL getBounds(final RectL pIn,
                                  final long pCenterX, final long pCenterY, final double pDegrees,
                                  final RectL pReuse) {
        final RectL out = pReuse != null ? pReuse : new RectL();
        if (pDegrees == 0) { // optimization
            out.top = pIn.top;
            out.left = pIn.left;
            out.bottom = pIn.bottom;
            out.right = pIn.right;
            return out;
        }
        final double radians = pDegrees * Math.PI / 180.;
        final double cos = Math.cos(radians);
        final double sin = Math.sin(radians);
        long inputX;
        long inputY;
        long outputX;
        long outputY;
        inputX = pIn.left; // corner 1
        inputY = pIn.top;
        outputX = getRotatedX(inputX, inputY, pCenterX, pCenterY, cos, sin);
        outputY = getRotatedY(inputX, inputY, pCenterX, pCenterY, cos, sin);
        out.top = out.bottom = outputY;
        out.left = out.right = outputX;
        inputX = pIn.right; // corner 2
        inputY = pIn.top;
        outputX = getRotatedX(inputX, inputY, pCenterX, pCenterY, cos, sin);
        outputY = getRotatedY(inputX, inputY, pCenterX, pCenterY, cos, sin);
        if (out.top > outputY) {
            out.top = outputY;
        }
        if (out.bottom < outputY) {
            out.bottom = outputY;
        }
        if (out.left > outputX) {
            out.left = outputX;
        }
        if (out.right < outputX) {
            out.right = outputX;
        }
        inputX = pIn.right; // corner 3
        inputY = pIn.bottom;
        outputX = getRotatedX(inputX, inputY, pCenterX, pCenterY, cos, sin);
        outputY = getRotatedY(inputX, inputY, pCenterX, pCenterY, cos, sin);
        if (out.top > outputY) {
            out.top = outputY;
        }
        if (out.bottom < outputY) {
            out.bottom = outputY;
        }
        if (out.left > outputX) {
            out.left = outputX;
        }
        if (out.right < outputX) {
            out.right = outputX;
        }
        inputX = pIn.left; // corner 4
        inputY = pIn.bottom;
        outputX = getRotatedX(inputX, inputY, pCenterX, pCenterY, cos, sin);
        outputY = getRotatedY(inputX, inputY, pCenterX, pCenterY, cos, sin);
        if (out.top > outputY) {
            out.top = outputY;
        }
        if (out.bottom < outputY) {
            out.bottom = outputY;
        }
        if (out.left > outputX) {
            out.left = outputX;
        }
        if (out.right < outputX) {
            out.right = outputX;
        }
        return out;
    }
653610
function reconstructRoute(parents, points, tailPoint, from, to, grid, opt) {

        var route = [];

        var prevDiff = normalizePoint(to.difference(tailPoint));

        // tailPoint is assumed to be aligned already
        var currentKey = getKey(tailPoint);
        var parent = parents[currentKey];

        var point;
        while (parent) {

            // point is assumed to be aligned already
            point = points[currentKey];

            var diff = normalizePoint(point.difference(parent));
            if (!diff.equals(prevDiff)) {
                route.unshift(point);
                prevDiff = diff;
            }

            // parent is assumed to be aligned already
            currentKey = getKey(parent);
            parent = parents[currentKey];
        }

        // leadPoint is assumed to be aligned already
        var leadPoint = points[currentKey];

        var fromDiff = normalizePoint(leadPoint.difference(from));
        if (!fromDiff.equals(prevDiff)) {
            route.unshift(leadPoint);
        }

        return route;
    }
1045303
function getClosestPoints( simplex ){

        // see http://www.codezealot.org/archives/153
        // for algorithm details

        // we know that the position of the last point
        // is very close to the previous. (by nature of the distance test)
        // this won't give great results for the closest
        // points algorithm, so let's use the previous two
        var len = simplex.length
            ,last = simplex[ len - 2 ]
            ,prev = simplex[ len - 3 ]
            ,scratch = Physics.scratchpad()
            ,A = scratch.vector().clone( last.pt )
            // L = B - A
            ,L = scratch.vector().clone( prev.pt ).vsub( A )
            ,lambdaB
            ,lambdaA
            ;

        if ( L.equals(Physics.vector.zero) ){

            // oh.. it's a zero vector. So A and B are both the closest.
            // just use one of them
            return scratch.done({

                a: last.a,
                b: last.b
            });
        }

        lambdaB = - L.dot( A ) / L.normSq();
        lambdaA = 1 - lambdaB;

        if ( lambdaA <= 0 ){
            // woops.. that means the closest simplex point
            // isn't on the line it's point B itself
            return scratch.done({
                a: prev.a,
                b: prev.b
            });
        } else if ( lambdaB <= 0 ){
            // vice versa
            return scratch.done({
                a: last.a,
                b: last.b
            });
        }

        // guess we'd better do the math now...
        return scratch.done({
            // a closest = lambdaA * Aa + lambdaB * Ba
            a: A.clone( last.a ).mult( lambdaA ).vadd( L.clone( prev.a ).mult( lambdaB ) ).values(),
            // b closest = lambdaA * Ab + lambdaB * Bb
            b: A.clone( last.b ).mult( lambdaA ).vadd( L.clone( prev.b ).mult( lambdaB ) ).values()
        });
    }
1085919
def get_route(self, name):
        '''
        '''
        for route in self.routes:
            if route.name == name:
                return route
        for child in self.routes:
            route = child.get_route(name)
            if route:
                return route
288434
function _getInterPath(points) {
  var path = [];
  Util.each(points, function (point, index) {
    var subPath = index === 0 ? ['M', point.x, point.y] : ['L', point.x, point.y];
    path.push(subPath);
  });
  return path;
}
1076322
function getRoute(node) {
	var id = "";

	var parent = node.parentNode;
	var index = -1;

	if(!parent) {
		return {id:"0"};
	}

	var child = parent.firstChild;
	while(child) {
		index++;
		if(child === node) {
			break;
		}
		child = child.nextSibling;
	}

	// ARG!

	var parentInfo = parent.nodeType === 9 ? {id:""} :
		getCachedInfo(parent) || getRoute(parent);

	var parentId = parentInfo.id;

	id = (parentId ? parentId + SEPARATOR : "") + index;

	var routeInfo = {
		id: id,
		branch: getBranch(index, node, parentInfo.branch)
	};
	cache(node, routeInfo);

	return routeInfo;
}
1255806
function computePathBoundingBox(path) {

            var points = [];
            var iterator = function (c, p0, p1, p2) {
                if (c === 'L') {
                    points.push(p0);
                    points.push(p1);
                }
                else if (c === 'Q') {
                    var bound = computeQuadraticBezierBoundingBox(p0, p1, p2);

                    points.push(bound);
                    points.push({
                        x: bound.x + bound.width,
                        y: bound.y + bound.height
                    });
                }
            };

            if (arguments.length === 1) {
                pathIterator(path, function (c, p0, p1, p2) {
                    if (c === 'L') {
                        points.push(p0);
                        points.push(p1);
                    }
                    else if (c === 'Q') {
                        var bound = computeQuadraticBezierBoundingBox(p0, p1, p2);

                        points.push(bound);
                        points.push({
                            x: bound.x + bound.width,
                            y: bound.y + bound.height
                        });
                    }
                });
            }
            else {
                for (var i = 0, l = arguments.length; i < l; i++) {
                    pathIterator(arguments[i], iterator);
                }
            }

            return computeBoundingBox(points);
        }
1186029
def _get_segments(self):
        
        points = list(self.points)
        segments = [[]]
        lastWasOffCurve = False
        firstIsMove = points[0].type == "move"
        for point in points:
            segments[-1].append(point)
            if point.type != "offcurve":
                segments.append([])
            lastWasOffCurve = point.type == "offcurve"
        if len(segments[-1]) == 0:
            del segments[-1]
        if lastWasOffCurve and firstIsMove:
            # ignore trailing off curves
            del segments[-1]
        if lastWasOffCurve and not firstIsMove:
            segment = segments.pop(-1)
            segment.extend(segments[0])
            del segments[0]
            segments.append(segment)
        if not lastWasOffCurve and not firstIsMove:
            segment = segments.pop(0)
            segments.append(segment)
        # wrap into segments
        wrapped = []
        for points in segments:
            s = self.segmentClass()
            s._setPoints(points)
            self._setContourInSegment(s)
            wrapped.append(s)
        return wrapped
719940
def path_get_destination(p: tcod.path.AStar) -> Tuple[int, int]:
    
    x = ffi.new("int *")
    y = ffi.new("int *")
    lib.TCOD_path_get_destination(p._path_c, x, y)
    return x[0], y[0]
426591
private static function getRelativePath($from, $to)
    {
        $from = explode('/', $from);
        $to = explode('/', $to);
        $relPath = $to;

        foreach ($from as $depth => $dir) {
            // find first non-matching dir
            if (isset($to[$depth]) && $dir === $to[$depth]) {
                // ignore this directory
                array_shift($relPath);
            } else {
                // get number of remaining dirs to $from
                $remaining = count($from) - $depth;
                if ($remaining > 1) {
                    // add traversals up to first matching dir
                    $padLength = (count($relPath) + $remaining - 1) * -1;
                    $relPath = array_pad($relPath, $padLength, '..');
                    break;
                } else {
                    $relPath[0] = './'.$relPath[0];
                }
            }
        }

        return implode('/', $relPath);
    }
324513
function() {

            var segments = this.segments;
            var numSegments = segments.length;
            if (numSegments === 0) return null; // if segments is an empty array

            var bbox;
            for (var i = 0; i < numSegments; i++) {

                var segment = segments[i];
                if (segment.isVisible) {
                    var segmentBBox = segment.bbox();
                    bbox = bbox ? bbox.union(segmentBBox) : segmentBBox;
                }
            }

            if (bbox) return bbox;

            // if the path has only invisible elements, return end point of last segment
            var lastSegment = segments[numSegments - 1];
            return new Rect(lastSegment.end.x, lastSegment.end.y, 0, 0);
        }
709095
def path(self, goal):
        
        if goal == self.name:
            return [self]

        if goal not in self.routes:
            raise ValueError("Unknown '{0}'".format(goal))

        obj = self
        path = [obj]
        while True:
            obj = obj.routes[goal].direction
            path.append(obj)
            if obj.name == goal:
                break
        return path
1266944
function (from, to) {

		var toPath = this.getPlotLinePath(to),
			path = this.getPlotLinePath(from);
			
		if (path && toPath) {
			path.push(
				toPath[4],
				toPath[5],
				toPath[1],
				toPath[2]
			);
		} else { // outside the axis area
			path = null;
		}
		
		return path;
	}
1145409
protected Result<PortalResult> getPortalPoints(long from, Poly fromPoly, MeshTile fromTile, long to, Poly toPoly,
            MeshTile toTile, int fromType, int toType) {
        float[] left = new float[3];
        float[] right = new float[3];
        // Find the link that points to the 'to' polygon.
        Link link = null;
        for (int i = fromPoly.firstLink; i != NavMesh.DT_NULL_LINK; i = fromTile.links.get(i).next) {
            if (fromTile.links.get(i).ref == to) {
                link = fromTile.links.get(i);
                break;
            }
        }
        if (link == null) {
            return Result.invalidParam("No link found");
        }

        // Handle off-mesh connections.
        if (fromPoly.getType() == Poly.DT_POLYTYPE_OFFMESH_CONNECTION) {
            // Find link that points to first vertex.
            for (int i = fromPoly.firstLink; i != NavMesh.DT_NULL_LINK; i = fromTile.links.get(i).next) {
                if (fromTile.links.get(i).ref == to) {
                    int v = fromTile.links.get(i).edge;
                    System.arraycopy(fromTile.data.verts, fromPoly.verts[v] * 3, left, 0, 3);
                    System.arraycopy(fromTile.data.verts, fromPoly.verts[v] * 3, right, 0, 3);
                    return Result.success(new PortalResult(left, right, fromType, toType));
                }
            }
            return Result.invalidParam("Invalid offmesh from connection");
        }

        if (toPoly.getType() == Poly.DT_POLYTYPE_OFFMESH_CONNECTION) {
            for (int i = toPoly.firstLink; i != NavMesh.DT_NULL_LINK; i = toTile.links.get(i).next) {
                if (toTile.links.get(i).ref == from) {
                    int v = toTile.links.get(i).edge;
                    System.arraycopy(toTile.data.verts, toPoly.verts[v] * 3, left, 0, 3);
                    System.arraycopy(toTile.data.verts, toPoly.verts[v] * 3, right, 0, 3);
                    return Result.success(new PortalResult(left, right, fromType, toType));
                }
            }
            return Result.invalidParam("Invalid offmesh to connection");
        }

        // Find portal vertices.
        int v0 = fromPoly.verts[link.edge];
        int v1 = fromPoly.verts[(link.edge + 1) % fromPoly.vertCount];
        System.arraycopy(fromTile.data.verts, v0 * 3, left, 0, 3);
        System.arraycopy(fromTile.data.verts, v1 * 3, right, 0, 3);

        // If the link is at tile boundary, dtClamp the vertices to
        // the link width.
        if (link.side != 0xff) {
            // Unpack portal limits.
            if (link.bmin != 0 || link.bmax != 255) {
                float s = 1.0f / 255.0f;
                float tmin = link.bmin * s;
                float tmax = link.bmax * s;
                left = vLerp(fromTile.data.verts, v0 * 3, v1 * 3, tmin);
                right = vLerp(fromTile.data.verts, v0 * 3, v1 * 3, tmax);
            }
        }

        return Result.success(new PortalResult(left, right, fromType, toType));
    }
545780
function getDivergenceIndexes(currentPath, newPath, routes) {
        // find where path differs
        var divergenceIndex // the index at which the paths diverge
        for(var n=0; n<currentPath.length; n++) {
            if(currentPath[n] !== newPath[n]) {
                divergenceIndex = n
                break;
            }
        }
        if(divergenceIndex === undefined && newPath.length > currentPath.length) {
            divergenceIndex = currentPath.length
        }

        if(divergenceIndex === undefined)
            return undefined

        return routeAndCorrectedPathIndexes(routes, divergenceIndex)
    }
926913
function lineRectangleIntersection(line, rect) {
  const intersections = [];

  Object.keys(rect).forEach(function(side) {
    const segment = rect[side];
    const intersection = line.intersectLine(segment);

    if (intersection) {
      intersections.push(intersection);
    }
  });

  return intersections;
}