LevelbossMike · July 29, 2022 14:15
diff --git a/README.md b/README.md
diff --git a/demo.html b/demo.html
 <!DOCTYPE html>
 <html lang="en">
    <head>
        <title>Orthogonal Connector Router</title>
        <script>
            window.OrthogonalConnector=function(){function t(t,s){return{x:t,y:s}}class s{constructor(t,s,e,o){this.left=t,this.top=s,this.width=e,this.height=o}static get empty(){return new s(0,0,0,0)}static fromRect(t){return new s(t.left,t.top,t.width,t.height)}static fromLTRB(t,e,o,n){return new s(t,e,o-t,n-e)}contains(t){return t.x>=this.left&&t.x<=this.right&&t.y>=this.top&&t.y<=this.bottom}inflate(t,e){return s.fromLTRB(this.left-t,this.top-e,this.right+t,this.bottom+e)}intersects(t){let s=this.left,e=this.top,o=this.width,n=this.height,r=t.left,i=t.top,h=t.width,c=t.height;return r<s+o&&s<r+h&&i<e+n&&e<i+c}union(t){const e=[this.left,this.right,t.left,t.right],o=[this.top,this.bottom,t.top,t.bottom];return s.fromLTRB(Math.min(...e),Math.min(...o),Math.max(...e),Math.max(...o))}get center(){return{x:this.left+this.width/2,y:this.top+this.height/2}}get right(){return this.left+this.width}get bottom(){return this.top+this.height}get location(){return t(this.left,this.top)}get northEast(){return{x:this.right,y:this.top}}get southEast(){return{x:this.right,y:this.bottom}}get southWest(){return{x:this.left,y:this.bottom}}get northWest(){return{x:this.left,y:this.top}}get east(){return t(this.right,this.center.y)}get north(){return t(this.center.x,this.top)}get south(){return t(this.center.x,this.bottom)}get west(){return t(this.left,this.center.y)}get size(){return{width:this.width,height:this.height}}}class e{constructor(t){this.data=t,this.distance=Number.MAX_SAFE_INTEGER,this.shortestPath=[],this.adjacentNodes=new Map}}class o{constructor(){this.index={}}add(t){const{x:s,y:o}=t,n=s.toString(),r=o.toString();n in this.index||(this.index[n]={}),r in this.index[n]||(this.index[n][r]=new e(t))}getLowestDistanceNode(t){let s=null,e=Number.MAX_SAFE_INTEGER;for(const o of t){const t=o.distance;t<e&&(e=t,s=o)}return s}inferPathDirection(t){return 0==t.shortestPath.length?null:this.directionOfNodes(t.shortestPath[t.shortestPath.length-1],t)}calculateShortestPathFromSource(t,s){s.distance=0;const e=new Set,o=new Set;for(o.add(s);0!=o.size;){const t=this.getLowestDistanceNode(o);o.delete(t);for(const[s,n]of t.adjacentNodes)e.has(s)||(this.calculateMinimumDistance(s,n,t),o.add(s));e.add(t)}return t}calculateMinimumDistance(t,s,e){const o=e.distance,n=this.inferPathDirection(e),r=this.directionOfNodes(e,t),i=n&&r&&n!=r?Math.pow(s+1,2):0;if(o+s+i<t.distance){t.distance=o+s+i;const n=[...e.shortestPath];n.push(e),t.shortestPath=n}}directionOf(t,s){return t.x===s.x?"h":t.y===s.y?"v":null}directionOfNodes(t,s){return this.directionOf(t.data,s.data)}connect(t,s){const e=this.get(t),o=this.get(s);if(!e||!o)throw new Error("A point was not found");e.adjacentNodes.set(o,function(t,s){return Math.sqrt(Math.pow(s.x-t.x,2)+Math.pow(s.y-t.y,2))}(t,s))}has(t){const{x:s,y:e}=t,o=s.toString(),n=e.toString();return o in this.index&&n in this.index[o]}get(t){const{x:s,y:e}=t,o=s.toString(),n=e.toString();return o in this.index&&n in this.index[o]?this.index[o][n]:null}}function n(e){const o=s.fromRect(e.shape);switch(e.side){case"bottom":return t(o.left+o.width*e.distance,o.bottom);case"top":return t(o.left+o.width*e.distance,o.top);case"left":return t(o.left,o.top+o.height*e.distance);case"right":return t(o.right,o.top+o.height*e.distance)}}function r(s,e){const{x:o,y:r}=n(s);switch(s.side){case"top":return t(o,r-e);case"right":return t(o+e,r);case"bottom":return t(o,r+e);case"left":return t(o-e,r)}}function i(t){return"top"==t||"bottom"==t}function h(s,e){const o=[];for(const[t,e]of s.data){const n=0==t,r=t==s.rows-1;for(const[t,i]of e){const e=0==t,h=t==s.columns-1,c=n&&h,a=r&&h,u=r&&e;e&&n||c||a||u?o.push(i.northWest,i.northEast,i.southWest,i.southEast):n?o.push(i.northWest,i.north,i.northEast):r?o.push(i.southEast,i.south,i.southWest):e?o.push(i.northWest,i.west,i.southWest):h?o.push(i.northEast,i.east,i.southEast):o.push(i.northWest,i.north,i.northEast,i.east,i.southEast,i.south,i.southWest,i.west,i.center)}}return function(s){const e=[],o=new Map;s.forEach(t=>{const{x:s,y:e}=t;let n=o.get(e)||o.set(e,[]).get(e);n.indexOf(s)<0&&n.push(s)});for(const[s,n]of o)for(const o of n)e.push(t(o,s));return e}(o).filter(t=>!(t=>e.filter(s=>s.contains(t)).length>0)(t))}function c(t,s,e){const o=t.get(s),n=t.get(e);if(!o)throw new Error(`Origin node {${s.x},${s.y}} not found`);if(!n)throw new Error(`Origin node {${s.x},${s.y}} not found`);return t.calculateShortestPathFromSource(t,o),n.shortestPath.map(t=>t.data)}function a(t,s,e){const o=t.x===s.x&&s.x===e.x,n=t.y===s.y&&s.y===e.y,r=t.y===s.y,i=t.x===s.x,h=s.y===e.y,c=s.x===e.x;if(o||n)return"none";if(!i&&!r||!c&&!h)return"unknown";if(r&&c)return e.y>s.y?"s":"n";if(i&&h)return e.x>s.x?"e":"w";throw new Error("Nope")}class u{constructor(){this._rows=0,this._cols=0,this.data=new Map}set(t,s,e){this._rows=Math.max(this.rows,t+1),this._cols=Math.max(this.columns,s+1),(this.data.get(t)||this.data.set(t,new Map).get(t)).set(s,e)}get(t,s){const e=this.data.get(t);return e&&e.get(s)||null}rectangles(){const t=[];for(const[s,e]of this.data)for(const[s,o]of e)t.push(o);return t}get columns(){return this._cols}get rows(){return this._rows}}class f{static route(e){const{pointA:f,pointB:d,globalBoundsMargin:l}=e,g=[],p=[],m=[],x=i(f.side),w=i(d.side),y=n(f),b=n(d),M=s.fromRect(f.shape),E=s.fromRect(d.shape),R=s.fromRect(e.globalBounds);let S=e.shapeMargin,N=M.inflate(S,S),B=E.inflate(S,S);N.intersects(B)&&(S=0,N=M,B=E);const O=N.union(B).inflate(l,l),P=s.fromLTRB(Math.max(O.left,R.left),Math.max(O.top,R.top),Math.min(O.right,R.right),Math.min(O.bottom,R.bottom));for(const t of[N,B])p.push(t.left),p.push(t.right),m.push(t.top),m.push(t.bottom);(x?p:m).push(x?y.x:y.y),(w?p:m).push(w?b.x:b.y);for(const s of[f,d]){const e=n(s),o=(s,o)=>g.push(t(e.x+s,e.y+o));switch(s.side){case"top":o(0,-S);break;case"right":o(S,0);break;case"bottom":o(0,S);break;case"left":o(-S,0)}}p.sort((t,s)=>t-s),m.sort((t,s)=>t-s);const L=function(t,e,o){const n=new u;t.sort((t,s)=>t-s),e.sort((t,s)=>t-s);let r=o.left,i=o.top,h=0,c=0;for(const a of e){for(const e of t)n.set(c,h++,s.fromLTRB(r,i,e,a)),r=e;n.set(c,h,s.fromLTRB(r,i,o.right,a)),r=o.left,i=a,h=0,c++}r=o.left;for(const e of t)n.set(c,h++,s.fromLTRB(r,i,e,o.bottom)),r=e;return n.set(c,h,s.fromLTRB(r,i,o.right,o.bottom)),n}(p,m,P),T=h(L,[N,B]);g.push(...T);const{graph:W,connections:_}=function(s){const e=[],n=[],r=new o,i=[];s.forEach(t=>{const{x:s,y:o}=t;e.indexOf(s)<0&&e.push(s),n.indexOf(o)<0&&n.push(o),r.add(t)}),e.sort((t,s)=>t-s),n.sort((t,s)=>t-s);const h=t=>r.has(t);for(let s=0;s<n.length;s++)for(let o=0;o<e.length;o++){const c=t(e[o],n[s]);if(h(c)){if(o>0){const a=t(e[o-1],n[s]);h(a)&&(r.connect(a,c),r.connect(c,a),i.push({a:a,b:c}))}if(s>0){const a=t(e[o],n[s-1]);h(a)&&(r.connect(a,c),r.connect(c,a),i.push({a:a,b:c}))}}}return{graph:r,connections:i}}(g),A=r(f,S),D=r(d,S),k=n(f),F=n(d);return this.byproduct.spots=g,this.byproduct.vRulers=p,this.byproduct.hRulers=m,this.byproduct.grid=L.rectangles(),this.byproduct.connections=_,c(W,A,D).length>0?function(t){if(t.length<=2)return t;const s=[t[0]];for(let e=1;e<t.length;e++){const o=t[e];if(e===t.length-1){s.push(o);break}"none"!==a(t[e-1],o,t[e+1])&&s.push(o)}return s}([k,...c(W,A,D),F]):[]}}return f.byproduct={hRulers:[],vRulers:[],spots:[],grid:[],connections:[]},f}();
        </script>
    </head>
 <body>
    <canvas id="canvas" width="500" height="500"></canvas>
    <script>

        const shapeA = {left: 50,  top: 50,  width: 100, height: 100};
        const shapeB = {left: 200, top: 200, width: 50,  height: 100};
        const path = OrthogonalConnector.route({
            pointA: {shape: shapeA, side: 'bottom', distance: 0.5},
            pointB: {shape: shapeB, side: 'right',  distance: 0.5},
            shapeMargin: 10,
            globalBoundsMargin: 10,
            globalBounds: {left: 0, top: 0, width: 500, height: 500},
        });

        // Draw shapes and path
        const context = document.getElementById('canvas').getContext('2d');
        const {x, y} = path.shift();

        // Draw shapes
        context.strokeRect(shapeA.left, shapeA.top, shapeA.width, shapeA.height);
        context.strokeRect(shapeB.left, shapeB.top, shapeB.width, shapeB.height);

        // Draw path
        context.beginPath();
        context.moveTo(x, y); path.forEach(({x, y}) => context.lineTo(x, y));
        context.stroke();

    </script>
 </body>
 </html>
diff --git a/ortho-connector.ts b/ortho-connector.ts
 /**
 * Orthogonal Connector Router
 *   - Given two rectangles and their connection points, returns the path for an orthogonal connector.
 *
 * https://jose.page
 * 2020
 */

 type BasicCardinalPoint = 'n' | 'e' | 's' | 'w';
 type Direction = 'v' | 'h';
 type Side = 'top' | 'right' | 'bottom' | 'left';
 type BendDirection = BasicCardinalPoint | 'unknown' | 'none';

 /**
 * A point in space
 */
 interface Point {
    x: number;
    y: number;
 }

 /**
 * A size tuple
 */
 interface Size {
    width: number;
    height: number;
 }

 /**
 * A line between two points
 */
 interface Line{
    a: Point;
    b: Point;
 }

 /**
 * Represents a Rectangle by location and size
 */
 interface Rect extends Size{
    left: number;
    top: number;
 }

 /**
 * Represents a connection point on a routing request
 */
 interface ConnectorPoint {
    shape: Rect;
    side: Side;
    distance: number;
 }

 /**
 * Byproduct data emitted by the routing algorithm
 */
 interface OrthogonalConnectorByproduct{
    hRulers: number[];
    vRulers: number[];
    spots: Point[];
    grid: Rectangle[];
    connections: Line[];
 }

 /**
 * Routing request data
 */
 interface OrthogonalConnectorOpts {
    pointA: ConnectorPoint;
    pointB: ConnectorPoint;
    shapeMargin: number;
    globalBoundsMargin: number;
    globalBounds: Rect;
 }

 /**
 * Utility Point creator
 * @param x
 * @param y
 */
 function makePt(x: number, y: number): Point {
    return {x, y};
 }

 /**
 * Computes distance between two points
 * @param a
 * @param b
 */
 function distance(a: Point, b: Point): number{
    return Math.sqrt(Math.pow(b.x - a.x, 2) + Math.pow(b.y - a.y, 2));
 }

 /**
 * Abstracts a Rectangle and adds geometric utilities
 */
 class Rectangle{

    static get empty(): Rectangle{
        return new Rectangle(0, 0, 0, 0);
    }

    static fromRect(r: Rect): Rectangle{
        return new Rectangle(r.left, r.top, r.width, r.height);
    }

    static fromLTRB(left: number, top: number, right: number, bottom: number): Rectangle{
        return new Rectangle(left, top, right - left, bottom - top);
    }

    constructor(readonly left: number, readonly top:number, readonly width: number, readonly height: number){}

    contains(p: Point): boolean{
        return p.x >= this.left && p.x <= this.right && p.y >= this.top && p.y <= this.bottom;
    }

    inflate(horizontal: number, vertical: number): Rectangle{
        return Rectangle.fromLTRB(this.left - horizontal, this.top - vertical, this.right + horizontal, this.bottom + vertical);
    }

    intersects(rectangle: Rectangle): boolean{
        let thisX = this.left;
        let thisY = this.top;
        let thisW = this.width;
        let thisH = this.height;
        let rectX = rectangle.left;
        let rectY = rectangle.top;
        let rectW = rectangle.width;
        let rectH = rectangle.height;
        return (rectX < thisX + thisW) && (thisX < (rectX + rectW)) && (rectY < thisY + thisH) && (thisY < rectY + rectH);
    }

    union(r: Rectangle): Rectangle{
        const x = [this.left, this.right, r.left, r.right];
        const y = [this.top, this.bottom, r.top, r.bottom];
        return Rectangle.fromLTRB(
            Math.min(...x), Math.min(...y),
            Math.max(...x), Math.max(...y)
        );
    }

    get center(): Point{
        return {
            x: this.left + this.width / 2,
            y: this.top + this.height / 2
        };
    }

    get right(): number{
        return this.left + this.width;
    }

    get bottom(): number{
        return this.top + this.height;
    }

    get location(): Point{
        return makePt(this.left, this.top);
    }

    get northEast(): Point{
        return {x: this.right, y: this.top};
    }

    get southEast(): Point{
        return {x: this.right, y: this.bottom};
    }

    get southWest(): Point{
        return {x: this.left, y: this.bottom};
    }

    get northWest(): Point{
        return {x: this.left, y: this.top};
    }

    get east(): Point{
        return makePt(this.right, this.center.y);
    }

    get north(): Point{
        return makePt(this.center.x, this.top);
    }

    get south(): Point{
        return makePt(this.center.x, this.bottom);
    }

    get west(): Point{
        return makePt(this.left, this.center.y);
    }

    get size(): Size{
        return {width: this.width, height: this.height};
    }
 }

 /**
 * Represents a node in a graph, whose data is a Point
 */
 class PointNode{
    public distance = Number.MAX_SAFE_INTEGER;
    public shortestPath: PointNode[] = [];
    public adjacentNodes: Map<PointNode, number> = new Map();
    constructor(public data: Point){}
 }

 /***
 * Represents a Graph of Point nodes
 */
 class PointGraph{

    private index: {[x: string]: {[y: string]: PointNode}} = {};

    add(p: Point){
        const {x, y} = p;
        const xs = x.toString(), ys = y.toString();

        if(!(xs in this.index)) {
            this.index[xs] = {}
        }
        if(!(ys in this.index[xs])){
            this.index[xs][ys] = new PointNode(p);
        }
    }

    private getLowestDistanceNode(unsettledNodes: Set<PointNode>): PointNode{
        let lowestDistanceNode: PointNode | null = null;
        let lowestDistance = Number.MAX_SAFE_INTEGER;
        for(const node of unsettledNodes){
            const nodeDistance = node.distance;
            if(nodeDistance < lowestDistance) {
                lowestDistance = nodeDistance;
                lowestDistanceNode = node;
            }
        }
        return lowestDistanceNode!;
    }

    private inferPathDirection(node: PointNode): Direction | null{
        if(node.shortestPath.length == 0) {
            return null;
        }

        return this.directionOfNodes(node.shortestPath[node.shortestPath.length - 1], node);
    }

    calculateShortestPathFromSource(graph: PointGraph, source: PointNode): PointGraph {
        source.distance = 0;

        const settledNodes: Set<PointNode> = new Set();
        const unsettledNodes: Set<PointNode> = new Set();

        unsettledNodes.add(source);

        while (unsettledNodes.size != 0){
            const currentNode = this.getLowestDistanceNode(unsettledNodes);
            unsettledNodes.delete(currentNode);

            for(const [adjacentNode, edgeWeight] of currentNode.adjacentNodes){
                if(!settledNodes.has(adjacentNode)) {
                    this.calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
                    unsettledNodes.add(adjacentNode);
                }

            }
            settledNodes.add(currentNode);
        }

        return graph;

    }

    private calculateMinimumDistance(evaluationNode: PointNode, edgeWeigh: number, sourceNode: PointNode){
        const sourceDistance = sourceNode.distance;
        const comingDirection = this.inferPathDirection(sourceNode);
        const goingDirection = this.directionOfNodes(sourceNode, evaluationNode);
        const changingDirection = comingDirection && goingDirection && comingDirection != goingDirection;
        const extraWeigh = changingDirection ? Math.pow(edgeWeigh + 1, 2) : 0;

        if(sourceDistance + edgeWeigh + extraWeigh < evaluationNode.distance) {
            evaluationNode.distance  = sourceDistance + edgeWeigh + extraWeigh;
            const shortestPath: PointNode[] = [...sourceNode.shortestPath];
            shortestPath.push(sourceNode);
            evaluationNode.shortestPath = shortestPath;
        }
    }

    private directionOf(a: Point, b: Point): Direction | null{
        if(a.x === b.x) {
            return 'h';
        }else if(a.y === b.y){
            return 'v';
        }else{
            return null;
        }
    }

    private directionOfNodes(a: PointNode, b: PointNode): Direction | null{
        return this.directionOf(a.data, b.data);
    }

    connect(a: Point, b: Point){
        const nodeA = this.get(a);
        const nodeB = this.get(b);

        if(!nodeA || !nodeB) {
            throw new Error(`A point was not found`);
        }

        nodeA.adjacentNodes.set(nodeB, distance(a, b));
    }

    has(p: Point): boolean{
        const {x, y} = p;
        const xs = x.toString(), ys = y.toString();
        return xs in this.index && ys in this.index[xs];
    }

    get(p: Point): PointNode | null{
        const {x, y} = p;
        const xs = x.toString(), ys = y.toString();

        if(xs in this.index && ys in this.index[xs]) {
            return this.index[xs][ys];
        }

        return null;
    }

 }

 /**
 * Gets the actual point of the connector based on the distance parameter
 * @param p
 */
 function computePt(p: ConnectorPoint): Point{
    const b = Rectangle.fromRect(p.shape);
    switch(p.side){
        case "bottom": return makePt(b.left + b.width * p.distance, b.bottom);
        case "top": return makePt(b.left + b.width * p.distance, b.top);
        case "left": return makePt(b.left, b.top + b.height * p.distance);
        case "right": return makePt(b.right, b.top + b.height * p.distance);
    }
 }

 /**
 * Extrudes the connector point by margin depending on it's side
 * @param cp
 * @param margin
 */
 function extrudeCp(cp: ConnectorPoint, margin: number): Point{
    const {x, y} = computePt(cp);
    switch (cp.side){
        case "top": return makePt(x, y - margin);
        case "right": return makePt(x + margin, y);
        case "bottom": return makePt(x, y + margin);
        case "left": return makePt(x - margin, y);
    }
 }

 /**
 * Returns flag indicating if the side belongs on a vertical axis
 * @param side
 */
 function isVerticalSide(side: Side): boolean{
    return side == "top" || side == "bottom";
 }

 /**
 * Creates a grid of rectangles from the specified set of rulers, contained on the specified bounds
 * @param verticals
 * @param horizontals
 * @param bounds
 */
 function rulersToGrid(verticals: number[], horizontals: number[], bounds: Rectangle): Grid{

    const result: Grid = new Grid;

    verticals.sort((a, b) => a - b);
    horizontals.sort((a, b) => a - b);

    let lastX = bounds.left;
    let lastY = bounds.top;
    let column = 0;
    let row = 0;

    for(const y of horizontals){
        for(const x of verticals){
            result.set(row, column++, Rectangle.fromLTRB(lastX, lastY, x, y));
            lastX = x;
        }

        // Last cell of the row
        result.set(row, column, Rectangle.fromLTRB(lastX, lastY, bounds.right, y));
        lastX = bounds.left;
        lastY = y;
        column = 0;
        row++;
    }

    lastX = bounds.left;

    // Last fow of cells
    for(const x of verticals) {
        result.set(row, column++, Rectangle.fromLTRB(lastX, lastY, x, bounds.bottom));
        lastX = x;
    }

    // Last cell of last row
    result.set(row, column, Rectangle.fromLTRB(lastX, lastY, bounds.right, bounds.bottom));

    return result;

 }

 /**
 * Returns an array without repeated points
 * @param points
 */
 function reducePoints(points: Point[]): Point[]{

    const result: Point[] = [];
    const map = new Map<number, number[]>();

    points.forEach(p => {
        const {x, y} = p;
        let arr: number[] = map.get(y) || map.set(y, []).get(y)!;

        if(arr.indexOf(x) < 0) {
            arr.push(x);
        }
    });

    for(const [y, xs] of map){
        for(const x of xs){
            result.push(makePt(x, y));
        }
    }

    return result;

 }

 /**
 * Returns a set of spots generated from the grid, avoiding colliding spots with specified obstacles
 * @param grid
 * @param obstacles
 */
 function gridToSpots(grid: Grid, obstacles: Rectangle[]): Point[]{

    const obstacleCollision = (p: Point) => obstacles.filter(o => o.contains(p)).length > 0;

    const gridPoints: Point[] = [];

    for(const [row, data] of grid.data){

        const firstRow = row == 0;
        const lastRow =  row == grid.rows - 1;

        for(const [col, r] of data){

            const firstCol = col == 0;
            const lastCol = col == grid.columns - 1;
            const nw = firstCol && firstRow;
            const ne = firstRow && lastCol;
            const se = lastRow && lastCol;
            const sw = lastRow && firstCol;

            if(nw || ne || se || sw) {
                gridPoints.push(r.northWest, r.northEast, r.southWest, r.southEast);
            }else if(firstRow){
                gridPoints.push(r.northWest, r.north, r.northEast);
            }else if(lastRow){
                gridPoints.push(r.southEast, r.south, r.southWest);
            }else if(firstCol){
                gridPoints.push(r.northWest, r.west, r.southWest);
            }else if(lastCol){
                gridPoints.push(r.northEast, r.east, r.southEast);
            }else{
                gridPoints.push(
                    r.northWest, r.north, r.northEast, r.east,
                    r.southEast, r.south, r.southWest, r.west, r.center);
            }

        }
    }

    // for(const r of grid) {
    //     gridPoints.push(
    //         r.northWest, r.north, r.northEast, r.east,
    //         r.southEast, r.south, r.southWest, r.west, r.center);
    // }

    // Reduce repeated points and filter out those who touch shapes
    return reducePoints(gridPoints).filter(p => !obstacleCollision(p));
 }

 /**
 * Creates a graph connecting the specified points orthogonally
 * @param spots
 */
 function createGraph(spots: Point[]): {graph: PointGraph, connections: Line[]} {
    const hotXs: number[] = [];
    const hotYs: number[] = [];
    const graph = new PointGraph();
    const connections: Line[] = [];

    spots.forEach(p => {
        const {x, y} = p;
        if(hotXs.indexOf(x) < 0) hotXs.push(x);
        if(hotYs.indexOf(y) < 0) hotYs.push(y);
        graph.add(p);
    });

    hotXs.sort((a, b) => a - b);
    hotYs.sort((a, b) => a - b);

    const inHotIndex = (p: Point): boolean => graph.has(p);

    for(let i = 0; i < hotYs.length; i++){
        for(let j = 0; j < hotXs.length; j++) {
            const b = makePt(hotXs[j], hotYs[i]);

            if(!inHotIndex(b)) continue;

            if(j > 0) {
                const a = makePt(hotXs[j - 1], hotYs[i]);

                if(inHotIndex(a)) {
                    graph.connect(a, b);
                    graph.connect(b, a);
                    connections.push({a, b});
                }
            }

            if(i > 0) {
                const a = makePt(hotXs[j], hotYs[i - 1]);

                if(inHotIndex(a)) {
                    graph.connect(a, b);
                    graph.connect(b, a);
                    connections.push({a, b});
                }
            }

        }
    }

    return {graph, connections};
 }

 /**
 * Solves the shotest path for the origin-destination path of the graph
 * @param graph
 * @param origin
 * @param destination
 */
 function shortestPath(graph: PointGraph, origin: Point, destination: Point): Point[]{

    const originNode = graph.get(origin);
    const destinationNode = graph.get(destination);

    if(!originNode){
        throw new Error(`Origin node {${origin.x},${origin.y}} not found`);
    }

    if(!destinationNode){
        throw new Error(`Origin node {${origin.x},${origin.y}} not found`);
    }

    graph.calculateShortestPathFromSource(graph, originNode);

    return destinationNode.shortestPath.map(n => n.data);

 }

 /**
 * Given two segments represented by 3 points,
 * determines if the second segment bends on an orthogonal direction or not, and which.
 *
 * @param a
 * @param b
 * @param c
 * @return Bend direction, unknown if not orthogonal or 'none' if straight line
 */
 function getBend(a: Point, b: Point, c: Point): BendDirection {

    const equalX = a.x === b.x && b.x === c.x;
    const equalY = a.y === b.y && b.y === c.y;
    const segment1Horizontal = a.y === b.y;
    const segment1Vertical = a.x === b.x;
    const segment2Horizontal = b.y === c.y;
    const segment2Vertical = b.x === c.x;

    if( equalX || equalY ) {
        return 'none';
    }

    if(
        !(segment1Vertical || segment1Horizontal) ||
        !(segment2Vertical || segment2Horizontal)
    ) {
        return 'unknown';
    }

    if(segment1Horizontal && segment2Vertical) {
        return c.y > b.y ? 's' : 'n';

    }else if(segment1Vertical && segment2Horizontal) {
        return c.x > b.x ? 'e' : 'w';
    }

    throw new Error('Nope');

 }

 /**
 * Simplifies the path by removing unnecessary points, based on orthogonal pathways
 * @param points
 */
 function simplifyPath(points: Point[]): Point[]{

    if(points.length <= 2){
        return points;
    }

    const r: Point[] = [points[0]];
    for(let i = 1; i < points.length; i++){
        const cur = points[i];

        if(i === (points.length - 1)) {
            r.push(cur);
            break;
        }

        const prev = points[i - 1];
        const next = points[i + 1];
        const bend = getBend(prev, cur, next);

        if(bend !== 'none') {
            r.push(cur);
        }

    }
    return r;
 }

 /**
 * Helps create the grid portion of the algorithm
 */
 class Grid{

    private _rows = 0;
    private _cols = 0;

    readonly data: Map<number, Map<number, Rectangle>> = new Map();

    constructor(){}

    set(row: number, column: number, rectangle: Rectangle){
        this._rows = Math.max(this.rows, row + 1);
        this._cols = Math.max(this.columns, column + 1);

        const rowMap: Map<number, Rectangle> = this.data.get(row) || this.data.set(row, new Map()).get(row)!;

        rowMap.set(column, rectangle);
    }

    get(row: number, column: number): Rectangle | null{
        const rowMap = this.data.get(row);

        if(rowMap) {
            return rowMap.get(column) || null;
        }

        return null;

    }

    rectangles(): Rectangle[]{
        const r: Rectangle[] = [];

        for(const [_, data] of this.data){
            for(const[_, rect] of data){
                r.push(rect);
            }
        }

        return r;
    }

    get columns(): number{
        return this._cols;
    }

    get rows(): number{
        return this._rows;
    }
 }

 /**
 * Main logic wrapped in a class to hold a space for potential future functionallity
 */
 export class OrthogonalConnector{

    static readonly byproduct: OrthogonalConnectorByproduct = {
        hRulers: [],
        vRulers: [],
        spots: [],
        grid: [],
        connections: [],
    };

    static route(opts: OrthogonalConnectorOpts): Point[]{

        const {pointA, pointB, globalBoundsMargin} = opts;
        const spots: Point[] = [];
        const verticals: number[] = [];
        const horizontals: number[] = [];
        const sideA = pointA.side, sideAVertical = isVerticalSide(sideA);
        const sideB = pointB.side, sideBVertical = isVerticalSide(sideB);
        const originA = computePt(pointA);
        const originB = computePt(pointB);
        const shapeA = Rectangle.fromRect(pointA.shape);
        const shapeB = Rectangle.fromRect(pointB.shape);
        const bigBounds = Rectangle.fromRect(opts.globalBounds);
        let shapeMargin = opts.shapeMargin;
        let inflatedA = shapeA.inflate(shapeMargin, shapeMargin);
        let inflatedB = shapeB.inflate(shapeMargin, shapeMargin);

        // Check bounding boxes collision
        if(inflatedA.intersects(inflatedB)){
            shapeMargin = 0;
            inflatedA = shapeA;
            inflatedB = shapeB;
        }

        const inflatedBounds = inflatedA.union(inflatedB).inflate(globalBoundsMargin, globalBoundsMargin);

        // Curated bounds to stick to
        const bounds = Rectangle.fromLTRB(
            Math.max(inflatedBounds.left, bigBounds.left),
            Math.max(inflatedBounds.top, bigBounds.top),
            Math.min(inflatedBounds.right, bigBounds.right),
            Math.min(inflatedBounds.bottom, bigBounds.bottom)
        );

        // Add edges to rulers
        for(const b of [inflatedA, inflatedB]){
            verticals.push(b.left);
            verticals.push(b.right);
            horizontals.push(b.top);
            horizontals.push(b.bottom);
        }

        // Rulers at origins of shapes
        (sideAVertical ? verticals : horizontals).push(sideAVertical ? originA.x : originA.y);
        (sideBVertical ? verticals : horizontals).push(sideBVertical ? originB.x : originB.y);

        // Points of shape antennas
        for(const connectorPt of [pointA, pointB]){
            const p = computePt(connectorPt);
            const add = (dx: number, dy: number) => spots.push(makePt(p.x + dx, p.y + dy));

            switch (connectorPt.side) {
                case "top":     add(0, -shapeMargin);   break;
                case "right":   add(shapeMargin, 0);    break;
                case "bottom":  add(0, shapeMargin);    break;
                case "left":    add(-shapeMargin, 0);   break;
            }
        }

        // Sort rulers
        verticals.sort((a, b) => a - b);
        horizontals.sort((a, b) => a - b);

        // Create grid
        const grid = rulersToGrid(verticals, horizontals, bounds);
        const gridPoints = gridToSpots(grid, [inflatedA, inflatedB]);

        // Add to spots
        spots.push(...gridPoints);

        // Create graph
        const {graph, connections} = createGraph(spots);

        // Origin and destination by extruding antennas
        const origin = extrudeCp(pointA, shapeMargin);
        const destination = extrudeCp(pointB, shapeMargin);

        const start = computePt(pointA);
        const end = computePt(pointB);

        this.byproduct.spots = spots;
        this.byproduct.vRulers = verticals;
        this.byproduct.hRulers = horizontals;
        this.byproduct.grid = grid.rectangles();
        this.byproduct.connections = connections;

        const path = shortestPath(graph, origin, destination);

        if(path.length > 0) {
            return simplifyPath([start, ...shortestPath(graph, origin, destination), end]);
        }else{
            return [];
        }
    }
 }
Property	Type	Description
pointA	ConnectorPoint	Origin point of connector
pointB	ConnectorPoint	Destination point of connector
shapeMargin	number	Margin around shapes for routing
globalBoundsMargin	number	Margin that routing expands
globalBounds	Rect	Defines confinement bounds
Property	Type	Description
shape	Rect	Bounds of shape representing the point
side	top,right,bottom,left	Side where the connector departs/arrives
distance	number	From 0 to 1, to calculate the connector departure/arrival relative to the edge this point represents
Property	Type	Description
left	number	Left coordinate of rectangle
top	number	Top coordinate of rectangle
width	number	Width of rectangle
height	number	Height of rectangle
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<title>Orthogonal Connector Router</title>
	<script>
	window.OrthogonalConnector=function(){function t(t,s){return{x:t,y:s}}class s{constructor(t,s,e,o){this.left=t,this.top=s,this.width=e,this.height=o}static get empty(){return new s(0,0,0,0)}static fromRect(t){return new s(t.left,t.top,t.width,t.height)}static fromLTRB(t,e,o,n){return new s(t,e,o-t,n-e)}contains(t){return t.x>=this.left&&t.x<=this.right&&t.y>=this.top&&t.y<=this.bottom}inflate(t,e){return s.fromLTRB(this.left-t,this.top-e,this.right+t,this.bottom+e)}intersects(t){let s=this.left,e=this.top,o=this.width,n=this.height,r=t.left,i=t.top,h=t.width,c=t.height;return r<s+o&&s<r+h&&i<e+n&&e<i+c}union(t){const e=[this.left,this.right,t.left,t.right],o=[this.top,this.bottom,t.top,t.bottom];return s.fromLTRB(Math.min(...e),Math.min(...o),Math.max(...e),Math.max(...o))}get center(){return{x:this.left+this.width/2,y:this.top+this.height/2}}get right(){return this.left+this.width}get bottom(){return this.top+this.height}get location(){return t(this.left,this.top)}get northEast(){return{x:this.right,y:this.top}}get southEast(){return{x:this.right,y:this.bottom}}get southWest(){return{x:this.left,y:this.bottom}}get northWest(){return{x:this.left,y:this.top}}get east(){return t(this.right,this.center.y)}get north(){return t(this.center.x,this.top)}get south(){return t(this.center.x,this.bottom)}get west(){return t(this.left,this.center.y)}get size(){return{width:this.width,height:this.height}}}class e{constructor(t){this.data=t,this.distance=Number.MAX_SAFE_INTEGER,this.shortestPath=[],this.adjacentNodes=new Map}}class o{constructor(){this.index={}}add(t){const{x:s,y:o}=t,n=s.toString(),r=o.toString();n in this.index\|\|(this.index[n]={}),r in this.index[n]\|\|(this.index[n][r]=new e(t))}getLowestDistanceNode(t){let s=null,e=Number.MAX_SAFE_INTEGER;for(const o of t){const t=o.distance;t<e&&(e=t,s=o)}return s}inferPathDirection(t){return 0==t.shortestPath.length?null:this.directionOfNodes(t.shortestPath[t.shortestPath.length-1],t)}calculateShortestPathFromSource(t,s){s.distance=0;const e=new Set,o=new Set;for(o.add(s);0!=o.size;){const t=this.getLowestDistanceNode(o);o.delete(t);for(const[s,n]of t.adjacentNodes)e.has(s)\|\|(this.calculateMinimumDistance(s,n,t),o.add(s));e.add(t)}return t}calculateMinimumDistance(t,s,e){const o=e.distance,n=this.inferPathDirection(e),r=this.directionOfNodes(e,t),i=n&&r&&n!=r?Math.pow(s+1,2):0;if(o+s+i<t.distance){t.distance=o+s+i;const n=[...e.shortestPath];n.push(e),t.shortestPath=n}}directionOf(t,s){return t.x===s.x?"h":t.y===s.y?"v":null}directionOfNodes(t,s){return this.directionOf(t.data,s.data)}connect(t,s){const e=this.get(t),o=this.get(s);if(!e\|\|!o)throw new Error("A point was not found");e.adjacentNodes.set(o,function(t,s){return Math.sqrt(Math.pow(s.x-t.x,2)+Math.pow(s.y-t.y,2))}(t,s))}has(t){const{x:s,y:e}=t,o=s.toString(),n=e.toString();return o in this.index&&n in this.index[o]}get(t){const{x:s,y:e}=t,o=s.toString(),n=e.toString();return o in this.index&&n in this.index[o]?this.index[o][n]:null}}function n(e){const o=s.fromRect(e.shape);switch(e.side){case"bottom":return t(o.left+o.widthe.distance,o.bottom);case"top":return t(o.left+o.widthe.distance,o.top);case"left":return t(o.left,o.top+o.heighte.distance);case"right":return t(o.right,o.top+o.heighte.distance)}}function r(s,e){const{x:o,y:r}=n(s);switch(s.side){case"top":return t(o,r-e);case"right":return t(o+e,r);case"bottom":return t(o,r+e);case"left":return t(o-e,r)}}function i(t){return"top"==t\|\|"bottom"==t}function h(s,e){const o=[];for(const[t,e]of s.data){const n=0==t,r=t==s.rows-1;for(const[t,i]of e){const e=0==t,h=t==s.columns-1,c=n&&h,a=r&&h,u=r&&e;e&&n\|\|c\|\|a\|\|u?o.push(i.northWest,i.northEast,i.southWest,i.southEast):n?o.push(i.northWest,i.north,i.northEast):r?o.push(i.southEast,i.south,i.southWest):e?o.push(i.northWest,i.west,i.southWest):h?o.push(i.northEast,i.east,i.southEast):o.push(i.northWest,i.north,i.northEast,i.east,i.southEast,i.south,i.southWest,i.west,i.center)}}return function(s){const e=[],o=new Map;s.forEach(t=>{const{x:s,y:e}=t;let n=o.get(e)\|\|o.set(e,[]).get(e);n.indexOf(s)<0&&n.push(s)});for(const[s,n]of o)for(const o of n)e.push(t(o,s));return e}(o).filter(t=>!(t=>e.filter(s=>s.contains(t)).length>0)(t))}function c(t,s,e){const o=t.get(s),n=t.get(e);if(!o)throw new Error(`Origin node {${s.x},${s.y}} not found`);if(!n)throw new Error(`Origin node {${s.x},${s.y}} not found`);return t.calculateShortestPathFromSource(t,o),n.shortestPath.map(t=>t.data)}function a(t,s,e){const o=t.x===s.x&&s.x===e.x,n=t.y===s.y&&s.y===e.y,r=t.y===s.y,i=t.x===s.x,h=s.y===e.y,c=s.x===e.x;if(o\|\|n)return"none";if(!i&&!r\|\|!c&&!h)return"unknown";if(r&&c)return e.y>s.y?"s":"n";if(i&&h)return e.x>s.x?"e":"w";throw new Error("Nope")}class u{constructor(){this._rows=0,this._cols=0,this.data=new Map}set(t,s,e){this._rows=Math.max(this.rows,t+1),this._cols=Math.max(this.columns,s+1),(this.data.get(t)\|\|this.data.set(t,new Map).get(t)).set(s,e)}get(t,s){const e=this.data.get(t);return e&&e.get(s)\|\|null}rectangles(){const t=[];for(const[s,e]of this.data)for(const[s,o]of e)t.push(o);return t}get columns(){return this._cols}get rows(){return this._rows}}class f{static route(e){const{pointA:f,pointB:d,globalBoundsMargin:l}=e,g=[],p=[],m=[],x=i(f.side),w=i(d.side),y=n(f),b=n(d),M=s.fromRect(f.shape),E=s.fromRect(d.shape),R=s.fromRect(e.globalBounds);let S=e.shapeMargin,N=M.inflate(S,S),B=E.inflate(S,S);N.intersects(B)&&(S=0,N=M,B=E);const O=N.union(B).inflate(l,l),P=s.fromLTRB(Math.max(O.left,R.left),Math.max(O.top,R.top),Math.min(O.right,R.right),Math.min(O.bottom,R.bottom));for(const t of[N,B])p.push(t.left),p.push(t.right),m.push(t.top),m.push(t.bottom);(x?p:m).push(x?y.x:y.y),(w?p:m).push(w?b.x:b.y);for(const s of[f,d]){const e=n(s),o=(s,o)=>g.push(t(e.x+s,e.y+o));switch(s.side){case"top":o(0,-S);break;case"right":o(S,0);break;case"bottom":o(0,S);break;case"left":o(-S,0)}}p.sort((t,s)=>t-s),m.sort((t,s)=>t-s);const L=function(t,e,o){const n=new u;t.sort((t,s)=>t-s),e.sort((t,s)=>t-s);let r=o.left,i=o.top,h=0,c=0;for(const a of e){for(const e of t)n.set(c,h++,s.fromLTRB(r,i,e,a)),r=e;n.set(c,h,s.fromLTRB(r,i,o.right,a)),r=o.left,i=a,h=0,c++}r=o.left;for(const e of t)n.set(c,h++,s.fromLTRB(r,i,e,o.bottom)),r=e;return n.set(c,h,s.fromLTRB(r,i,o.right,o.bottom)),n}(p,m,P),T=h(L,[N,B]);g.push(...T);const{graph:W,connections:_}=function(s){const e=[],n=[],r=new o,i=[];s.forEach(t=>{const{x:s,y:o}=t;e.indexOf(s)<0&&e.push(s),n.indexOf(o)<0&&n.push(o),r.add(t)}),e.sort((t,s)=>t-s),n.sort((t,s)=>t-s);const h=t=>r.has(t);for(let s=0;s<n.length;s++)for(let o=0;o<e.length;o++){const c=t(e[o],n[s]);if(h(c)){if(o>0){const a=t(e[o-1],n[s]);h(a)&&(r.connect(a,c),r.connect(c,a),i.push({a:a,b:c}))}if(s>0){const a=t(e[o],n[s-1]);h(a)&&(r.connect(a,c),r.connect(c,a),i.push({a:a,b:c}))}}}return{graph:r,connections:i}}(g),A=r(f,S),D=r(d,S),k=n(f),F=n(d);return this.byproduct.spots=g,this.byproduct.vRulers=p,this.byproduct.hRulers=m,this.byproduct.grid=L.rectangles(),this.byproduct.connections=_,c(W,A,D).length>0?function(t){if(t.length<=2)return t;const s=[t[0]];for(let e=1;e<t.length;e++){const o=t[e];if(e===t.length-1){s.push(o);break}"none"!==a(t[e-1],o,t[e+1])&&s.push(o)}return s}([k,...c(W,A,D),F]):[]}}return f.byproduct={hRulers:[],vRulers:[],spots:[],grid:[],connections:[]},f}();
	</script>
	</head>
	<body>
	<canvas id="canvas" width="500" height="500"></canvas>
	<script>

	const shapeA = {left: 50, top: 50, width: 100, height: 100};
	const shapeB = {left: 200, top: 200, width: 50, height: 100};
	const path = OrthogonalConnector.route({
	pointA: {shape: shapeA, side: 'bottom', distance: 0.5},
	pointB: {shape: shapeB, side: 'right', distance: 0.5},
	shapeMargin: 10,
	globalBoundsMargin: 10,
	globalBounds: {left: 0, top: 0, width: 500, height: 500},
	});

	// Draw shapes and path
	const context = document.getElementById('canvas').getContext('2d');
	const {x, y} = path.shift();

	// Draw shapes
	context.strokeRect(shapeA.left, shapeA.top, shapeA.width, shapeA.height);
	context.strokeRect(shapeB.left, shapeB.top, shapeB.width, shapeB.height);

	// Draw path
	context.beginPath();
	context.moveTo(x, y); path.forEach(({x, y}) => context.lineTo(x, y));
	context.stroke();

	</script>
	</body>
	</html>
	/**
	* Orthogonal Connector Router
	* - Given two rectangles and their connection points, returns the path for an orthogonal connector.
	*
	* https://jose.page
	* 2020
	*/

	type BasicCardinalPoint = 'n' \| 'e' \| 's' \| 'w';
	type Direction = 'v' \| 'h';
	type Side = 'top' \| 'right' \| 'bottom' \| 'left';
	type BendDirection = BasicCardinalPoint \| 'unknown' \| 'none';

	/**
	* A point in space
	*/
	interface Point {
	x: number;
	y: number;
	}

	/**
	* A size tuple
	*/
	interface Size {
	width: number;
	height: number;
	}

	/**
	* A line between two points
	*/
	interface Line{
	a: Point;
	b: Point;
	}

	/**
	* Represents a Rectangle by location and size
	*/
	interface Rect extends Size{
	left: number;
	top: number;
	}

	/**
	* Represents a connection point on a routing request
	*/
	interface ConnectorPoint {
	shape: Rect;
	side: Side;
	distance: number;
	}

	/**
	* Byproduct data emitted by the routing algorithm
	*/
	interface OrthogonalConnectorByproduct{
	hRulers: number[];
	vRulers: number[];
	spots: Point[];
	grid: Rectangle[];
	connections: Line[];
	}

	/**
	* Routing request data
	*/
	interface OrthogonalConnectorOpts {
	pointA: ConnectorPoint;
	pointB: ConnectorPoint;
	shapeMargin: number;
	globalBoundsMargin: number;
	globalBounds: Rect;
	}

	/**
	* Utility Point creator
	* @param x
	* @param y
	*/
	function makePt(x: number, y: number): Point {
	return {x, y};
	}

	/**
	* Computes distance between two points
	* @param a
	* @param b
	*/
	function distance(a: Point, b: Point): number{
	return Math.sqrt(Math.pow(b.x - a.x, 2) + Math.pow(b.y - a.y, 2));
	}

	/**
	* Abstracts a Rectangle and adds geometric utilities
	*/
	class Rectangle{

	static get empty(): Rectangle{
	return new Rectangle(0, 0, 0, 0);
	}

	static fromRect(r: Rect): Rectangle{
	return new Rectangle(r.left, r.top, r.width, r.height);
	}

	static fromLTRB(left: number, top: number, right: number, bottom: number): Rectangle{
	return new Rectangle(left, top, right - left, bottom - top);
	}

	constructor(readonly left: number, readonly top:number, readonly width: number, readonly height: number){}

	contains(p: Point): boolean{
	return p.x >= this.left && p.x <= this.right && p.y >= this.top && p.y <= this.bottom;
	}

	inflate(horizontal: number, vertical: number): Rectangle{
	return Rectangle.fromLTRB(this.left - horizontal, this.top - vertical, this.right + horizontal, this.bottom + vertical);
	}

	intersects(rectangle: Rectangle): boolean{
	let thisX = this.left;
	let thisY = this.top;
	let thisW = this.width;
	let thisH = this.height;
	let rectX = rectangle.left;
	let rectY = rectangle.top;
	let rectW = rectangle.width;
	let rectH = rectangle.height;
	return (rectX < thisX + thisW) && (thisX < (rectX + rectW)) && (rectY < thisY + thisH) && (thisY < rectY + rectH);
	}

	union(r: Rectangle): Rectangle{
	const x = [this.left, this.right, r.left, r.right];
	const y = [this.top, this.bottom, r.top, r.bottom];
	return Rectangle.fromLTRB(
	Math.min(...x), Math.min(...y),
	Math.max(...x), Math.max(...y)
	);
	}

	get center(): Point{
	return {
	x: this.left + this.width / 2,
	y: this.top + this.height / 2
	};
	}

	get right(): number{
	return this.left + this.width;
	}

	get bottom(): number{
	return this.top + this.height;
	}

	get location(): Point{
	return makePt(this.left, this.top);
	}

	get northEast(): Point{
	return {x: this.right, y: this.top};
	}

	get southEast(): Point{
	return {x: this.right, y: this.bottom};
	}

	get southWest(): Point{
	return {x: this.left, y: this.bottom};
	}

	get northWest(): Point{
	return {x: this.left, y: this.top};
	}

	get east(): Point{
	return makePt(this.right, this.center.y);
	}

	get north(): Point{
	return makePt(this.center.x, this.top);
	}

	get south(): Point{
	return makePt(this.center.x, this.bottom);
	}

	get west(): Point{
	return makePt(this.left, this.center.y);
	}

	get size(): Size{
	return {width: this.width, height: this.height};
	}
	}

	/**
	* Represents a node in a graph, whose data is a Point
	*/
	class PointNode{
	public distance = Number.MAX_SAFE_INTEGER;
	public shortestPath: PointNode[] = [];
	public adjacentNodes: Map<PointNode, number> = new Map();
	constructor(public data: Point){}
	}

	/***
	* Represents a Graph of Point nodes
	*/
	class PointGraph{

	private index: {[x: string]: {[y: string]: PointNode}} = {};

	add(p: Point){
	const {x, y} = p;
	const xs = x.toString(), ys = y.toString();

	if(!(xs in this.index)) {
	this.index[xs] = {}
	}
	if(!(ys in this.index[xs])){
	this.index[xs][ys] = new PointNode(p);
	}
	}

	private getLowestDistanceNode(unsettledNodes: Set<PointNode>): PointNode{
	let lowestDistanceNode: PointNode \| null = null;
	let lowestDistance = Number.MAX_SAFE_INTEGER;
	for(const node of unsettledNodes){
	const nodeDistance = node.distance;
	if(nodeDistance < lowestDistance) {
	lowestDistance = nodeDistance;
	lowestDistanceNode = node;
	}
	}
	return lowestDistanceNode!;
	}

	private inferPathDirection(node: PointNode): Direction \| null{
	if(node.shortestPath.length == 0) {
	return null;
	}

	return this.directionOfNodes(node.shortestPath[node.shortestPath.length - 1], node);
	}

	calculateShortestPathFromSource(graph: PointGraph, source: PointNode): PointGraph {
	source.distance = 0;

	const settledNodes: Set<PointNode> = new Set();
	const unsettledNodes: Set<PointNode> = new Set();

	unsettledNodes.add(source);

	while (unsettledNodes.size != 0){
	const currentNode = this.getLowestDistanceNode(unsettledNodes);
	unsettledNodes.delete(currentNode);

	for(const [adjacentNode, edgeWeight] of currentNode.adjacentNodes){
	if(!settledNodes.has(adjacentNode)) {
	this.calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
	unsettledNodes.add(adjacentNode);
	}

	}
	settledNodes.add(currentNode);
	}

	return graph;

	}

	private calculateMinimumDistance(evaluationNode: PointNode, edgeWeigh: number, sourceNode: PointNode){
	const sourceDistance = sourceNode.distance;
	const comingDirection = this.inferPathDirection(sourceNode);
	const goingDirection = this.directionOfNodes(sourceNode, evaluationNode);
	const changingDirection = comingDirection && goingDirection && comingDirection != goingDirection;
	const extraWeigh = changingDirection ? Math.pow(edgeWeigh + 1, 2) : 0;

	if(sourceDistance + edgeWeigh + extraWeigh < evaluationNode.distance) {
	evaluationNode.distance = sourceDistance + edgeWeigh + extraWeigh;
	const shortestPath: PointNode[] = [...sourceNode.shortestPath];
	shortestPath.push(sourceNode);
	evaluationNode.shortestPath = shortestPath;
	}
	}

	private directionOf(a: Point, b: Point): Direction \| null{
	if(a.x === b.x) {
	return 'h';
	}else if(a.y === b.y){
	return 'v';
	}else{
	return null;
	}
	}

	private directionOfNodes(a: PointNode, b: PointNode): Direction \| null{
	return this.directionOf(a.data, b.data);
	}

	connect(a: Point, b: Point){
	const nodeA = this.get(a);
	const nodeB = this.get(b);

	if(!nodeA \|\| !nodeB) {
	throw new Error(`A point was not found`);
	}

	nodeA.adjacentNodes.set(nodeB, distance(a, b));
	}

	has(p: Point): boolean{
	const {x, y} = p;
	const xs = x.toString(), ys = y.toString();
	return xs in this.index && ys in this.index[xs];
	}

	get(p: Point): PointNode \| null{
	const {x, y} = p;
	const xs = x.toString(), ys = y.toString();

	if(xs in this.index && ys in this.index[xs]) {
	return this.index[xs][ys];
	}

	return null;
	}

	}

	/**
	* Gets the actual point of the connector based on the distance parameter
	* @param p
	*/
	function computePt(p: ConnectorPoint): Point{
	const b = Rectangle.fromRect(p.shape);
	switch(p.side){
	case "bottom": return makePt(b.left + b.width * p.distance, b.bottom);
	case "top": return makePt(b.left + b.width * p.distance, b.top);
	case "left": return makePt(b.left, b.top + b.height * p.distance);
	case "right": return makePt(b.right, b.top + b.height * p.distance);
	}
	}

	/**
	* Extrudes the connector point by margin depending on it's side
	* @param cp
	* @param margin
	*/
	function extrudeCp(cp: ConnectorPoint, margin: number): Point{
	const {x, y} = computePt(cp);
	switch (cp.side){
	case "top": return makePt(x, y - margin);
	case "right": return makePt(x + margin, y);
	case "bottom": return makePt(x, y + margin);
	case "left": return makePt(x - margin, y);
	}
	}

	/**
	* Returns flag indicating if the side belongs on a vertical axis
	* @param side
	*/
	function isVerticalSide(side: Side): boolean{
	return side == "top" \|\| side == "bottom";
	}

	/**
	* Creates a grid of rectangles from the specified set of rulers, contained on the specified bounds
	* @param verticals
	* @param horizontals
	* @param bounds
	*/
	function rulersToGrid(verticals: number[], horizontals: number[], bounds: Rectangle): Grid{

	const result: Grid = new Grid;

	verticals.sort((a, b) => a - b);
	horizontals.sort((a, b) => a - b);

	let lastX = bounds.left;
	let lastY = bounds.top;
	let column = 0;
	let row = 0;

	for(const y of horizontals){
	for(const x of verticals){
	result.set(row, column++, Rectangle.fromLTRB(lastX, lastY, x, y));
	lastX = x;
	}

	// Last cell of the row
	result.set(row, column, Rectangle.fromLTRB(lastX, lastY, bounds.right, y));
	lastX = bounds.left;
	lastY = y;
	column = 0;
	row++;
	}

	lastX = bounds.left;

	// Last fow of cells
	for(const x of verticals) {
	result.set(row, column++, Rectangle.fromLTRB(lastX, lastY, x, bounds.bottom));
	lastX = x;
	}

	// Last cell of last row
	result.set(row, column, Rectangle.fromLTRB(lastX, lastY, bounds.right, bounds.bottom));

	return result;

	}

	/**
	* Returns an array without repeated points
	* @param points
	*/
	function reducePoints(points: Point[]): Point[]{

	const result: Point[] = [];
	const map = new Map<number, number[]>();

	points.forEach(p => {
	const {x, y} = p;
	let arr: number[] = map.get(y) \|\| map.set(y, []).get(y)!;

	if(arr.indexOf(x) < 0) {
	arr.push(x);
	}
	});

	for(const [y, xs] of map){
	for(const x of xs){
	result.push(makePt(x, y));
	}
	}

	return result;

	}

	/**
	* Returns a set of spots generated from the grid, avoiding colliding spots with specified obstacles
	* @param grid
	* @param obstacles
	*/
	function gridToSpots(grid: Grid, obstacles: Rectangle[]): Point[]{

	const obstacleCollision = (p: Point) => obstacles.filter(o => o.contains(p)).length > 0;

	const gridPoints: Point[] = [];

	for(const [row, data] of grid.data){

	const firstRow = row == 0;
	const lastRow = row == grid.rows - 1;

	for(const [col, r] of data){

	const firstCol = col == 0;
	const lastCol = col == grid.columns - 1;
	const nw = firstCol && firstRow;
	const ne = firstRow && lastCol;
	const se = lastRow && lastCol;
	const sw = lastRow && firstCol;

	if(nw \|\| ne \|\| se \|\| sw) {
	gridPoints.push(r.northWest, r.northEast, r.southWest, r.southEast);
	}else if(firstRow){
	gridPoints.push(r.northWest, r.north, r.northEast);
	}else if(lastRow){
	gridPoints.push(r.southEast, r.south, r.southWest);
	}else if(firstCol){
	gridPoints.push(r.northWest, r.west, r.southWest);
	}else if(lastCol){
	gridPoints.push(r.northEast, r.east, r.southEast);
	}else{
	gridPoints.push(
	r.northWest, r.north, r.northEast, r.east,
	r.southEast, r.south, r.southWest, r.west, r.center);
	}

	}
	}

	// for(const r of grid) {
	// gridPoints.push(
	// r.northWest, r.north, r.northEast, r.east,
	// r.southEast, r.south, r.southWest, r.west, r.center);
	// }

	// Reduce repeated points and filter out those who touch shapes
	return reducePoints(gridPoints).filter(p => !obstacleCollision(p));
	}

	/**
	* Creates a graph connecting the specified points orthogonally
	* @param spots
	*/
	function createGraph(spots: Point[]): {graph: PointGraph, connections: Line[]} {
	const hotXs: number[] = [];
	const hotYs: number[] = [];
	const graph = new PointGraph();
	const connections: Line[] = [];

	spots.forEach(p => {
	const {x, y} = p;
	if(hotXs.indexOf(x) < 0) hotXs.push(x);
	if(hotYs.indexOf(y) < 0) hotYs.push(y);
	graph.add(p);
	});

	hotXs.sort((a, b) => a - b);
	hotYs.sort((a, b) => a - b);

	const inHotIndex = (p: Point): boolean => graph.has(p);

	for(let i = 0; i < hotYs.length; i++){
	for(let j = 0; j < hotXs.length; j++) {
	const b = makePt(hotXs[j], hotYs[i]);

	if(!inHotIndex(b)) continue;

	if(j > 0) {
	const a = makePt(hotXs[j - 1], hotYs[i]);

	if(inHotIndex(a)) {
	graph.connect(a, b);
	graph.connect(b, a);
	connections.push({a, b});
	}
	}

	if(i > 0) {
	const a = makePt(hotXs[j], hotYs[i - 1]);

	if(inHotIndex(a)) {
	graph.connect(a, b);
	graph.connect(b, a);
	connections.push({a, b});
	}
	}

	}
	}

	return {graph, connections};
	}

	/**
	* Solves the shotest path for the origin-destination path of the graph
	* @param graph
	* @param origin
	* @param destination
	*/
	function shortestPath(graph: PointGraph, origin: Point, destination: Point): Point[]{

	const originNode = graph.get(origin);
	const destinationNode = graph.get(destination);

	if(!originNode){
	throw new Error(`Origin node {${origin.x},${origin.y}} not found`);
	}

	if(!destinationNode){
	throw new Error(`Origin node {${origin.x},${origin.y}} not found`);
	}

	graph.calculateShortestPathFromSource(graph, originNode);

	return destinationNode.shortestPath.map(n => n.data);

	}

	/**
	* Given two segments represented by 3 points,
	* determines if the second segment bends on an orthogonal direction or not, and which.
	*
	* @param a
	* @param b
	* @param c
	* @return Bend direction, unknown if not orthogonal or 'none' if straight line
	*/
	function getBend(a: Point, b: Point, c: Point): BendDirection {

	const equalX = a.x === b.x && b.x === c.x;
	const equalY = a.y === b.y && b.y === c.y;
	const segment1Horizontal = a.y === b.y;
	const segment1Vertical = a.x === b.x;
	const segment2Horizontal = b.y === c.y;
	const segment2Vertical = b.x === c.x;

	if( equalX \|\| equalY ) {
	return 'none';
	}

	if(
	!(segment1Vertical \|\| segment1Horizontal) \|\|
	!(segment2Vertical \|\| segment2Horizontal)
	) {
	return 'unknown';
	}

	if(segment1Horizontal && segment2Vertical) {
	return c.y > b.y ? 's' : 'n';

	}else if(segment1Vertical && segment2Horizontal) {
	return c.x > b.x ? 'e' : 'w';
	}

	throw new Error('Nope');

	}

	/**
	* Simplifies the path by removing unnecessary points, based on orthogonal pathways
	* @param points
	*/
	function simplifyPath(points: Point[]): Point[]{

	if(points.length <= 2){
	return points;
	}

	const r: Point[] = [points[0]];
	for(let i = 1; i < points.length; i++){
	const cur = points[i];

	if(i === (points.length - 1)) {
	r.push(cur);
	break;
	}

	const prev = points[i - 1];
	const next = points[i + 1];
	const bend = getBend(prev, cur, next);

	if(bend !== 'none') {
	r.push(cur);
	}

	}
	return r;
	}

	/**
	* Helps create the grid portion of the algorithm
	*/
	class Grid{

	private _rows = 0;
	private _cols = 0;

	readonly data: Map<number, Map<number, Rectangle>> = new Map();

	constructor(){}

	set(row: number, column: number, rectangle: Rectangle){
	this._rows = Math.max(this.rows, row + 1);
	this._cols = Math.max(this.columns, column + 1);

	const rowMap: Map<number, Rectangle> = this.data.get(row) \|\| this.data.set(row, new Map()).get(row)!;

	rowMap.set(column, rectangle);
	}

	get(row: number, column: number): Rectangle \| null{
	const rowMap = this.data.get(row);

	if(rowMap) {
	return rowMap.get(column) \|\| null;
	}

	return null;

	}

	rectangles(): Rectangle[]{
	const r: Rectangle[] = [];

	for(const [_, data] of this.data){
	for(const[_, rect] of data){
	r.push(rect);
	}
	}

	return r;
	}

	get columns(): number{
	return this._cols;
	}

	get rows(): number{
	return this._rows;
	}
	}

	/**
	* Main logic wrapped in a class to hold a space for potential future functionallity
	*/
	export class OrthogonalConnector{

	static readonly byproduct: OrthogonalConnectorByproduct = {
	hRulers: [],
	vRulers: [],
	spots: [],
	grid: [],
	connections: [],
	};

	static route(opts: OrthogonalConnectorOpts): Point[]{

	const {pointA, pointB, globalBoundsMargin} = opts;
	const spots: Point[] = [];
	const verticals: number[] = [];
	const horizontals: number[] = [];
	const sideA = pointA.side, sideAVertical = isVerticalSide(sideA);
	const sideB = pointB.side, sideBVertical = isVerticalSide(sideB);
	const originA = computePt(pointA);
	const originB = computePt(pointB);
	const shapeA = Rectangle.fromRect(pointA.shape);
	const shapeB = Rectangle.fromRect(pointB.shape);
	const bigBounds = Rectangle.fromRect(opts.globalBounds);
	let shapeMargin = opts.shapeMargin;
	let inflatedA = shapeA.inflate(shapeMargin, shapeMargin);
	let inflatedB = shapeB.inflate(shapeMargin, shapeMargin);

	// Check bounding boxes collision
	if(inflatedA.intersects(inflatedB)){
	shapeMargin = 0;
	inflatedA = shapeA;
	inflatedB = shapeB;
	}

	const inflatedBounds = inflatedA.union(inflatedB).inflate(globalBoundsMargin, globalBoundsMargin);

	// Curated bounds to stick to
	const bounds = Rectangle.fromLTRB(
	Math.max(inflatedBounds.left, bigBounds.left),
	Math.max(inflatedBounds.top, bigBounds.top),
	Math.min(inflatedBounds.right, bigBounds.right),
	Math.min(inflatedBounds.bottom, bigBounds.bottom)
	);

	// Add edges to rulers
	for(const b of [inflatedA, inflatedB]){
	verticals.push(b.left);
	verticals.push(b.right);
	horizontals.push(b.top);
	horizontals.push(b.bottom);
	}

	// Rulers at origins of shapes
	(sideAVertical ? verticals : horizontals).push(sideAVertical ? originA.x : originA.y);
	(sideBVertical ? verticals : horizontals).push(sideBVertical ? originB.x : originB.y);

	// Points of shape antennas
	for(const connectorPt of [pointA, pointB]){
	const p = computePt(connectorPt);
	const add = (dx: number, dy: number) => spots.push(makePt(p.x + dx, p.y + dy));

	switch (connectorPt.side) {
	case "top": add(0, -shapeMargin); break;
	case "right": add(shapeMargin, 0); break;
	case "bottom": add(0, shapeMargin); break;
	case "left": add(-shapeMargin, 0); break;
	}
	}

	// Sort rulers
	verticals.sort((a, b) => a - b);
	horizontals.sort((a, b) => a - b);

	// Create grid
	const grid = rulersToGrid(verticals, horizontals, bounds);
	const gridPoints = gridToSpots(grid, [inflatedA, inflatedB]);

	// Add to spots
	spots.push(...gridPoints);

	// Create graph
	const {graph, connections} = createGraph(spots);

	// Origin and destination by extruding antennas
	const origin = extrudeCp(pointA, shapeMargin);
	const destination = extrudeCp(pointB, shapeMargin);

	const start = computePt(pointA);
	const end = computePt(pointB);

	this.byproduct.spots = spots;
	this.byproduct.vRulers = verticals;
	this.byproduct.hRulers = horizontals;
	this.byproduct.grid = grid.rectangles();
	this.byproduct.connections = connections;

	const path = shortestPath(graph, origin, destination);

	if(path.length > 0) {
	return simplifyPath([start, ...shortestPath(graph, origin, destination), end]);
	}else{
	return [];
	}
	}
	}