Skip to content

Instantly share code, notes, and snippets.

@jean-merelis

jean-merelis/README.md

Forked from jose-mdz/README.md
Created March 5, 2023 04:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jean-merelis/9471f537d7d2ea63acc8a7bd69921518 to your computer and use it in GitHub Desktop.
Save jean-merelis/9471f537d7d2ea63acc8a7bd69921518 to your computer and use it in GitHub Desktop.
Download ZIP
Orthogonal Diagram Connector
Raw
README.md

Orthogonal Connectors

This algorithm returns the points that form an orthogonal path between two rectangles.

How to Use

// Define shapes
const shapeA = {left: 50,  top: 50, width: 100, height: 100};
const shapeB = {left: 200, top: 200, width: 50, height: 100};

// Get the connector path
const path = OrthogonalConnector.route({
    pointA: {shape: shapeA, side: 'bottom', distance: 0.5},
    pointB: {shape: shapeB, side: 'right',  distance: 0.5},
    shapeMargin: 10,
    globalBoundsMargin: 100,
    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();

Quick API

Only one method is exposed:

OrthogonalConnector.route(routeOptions)

Given two shapes represented by its bounding rectangles, provides an array of {x, y} coordinates that route an orthogonal path between them.

In order to properly create the routing, you must specify a side and a distance for both the origin and destination points.

RouteOptions

Options to pass to the route method. All fields are required.

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

ConnectorPoint

Represents either the source or the destination points of the route.

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

Rect

Represents a rectangle.

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
Raw
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>
Raw
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 [];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment