draw.io is a JavaScript, client-side editor for general diagramming.
/*
* libavoid-routing.js — the draw.io routing core over the libavoid solver.
* Hand-authored; engine-agnostic (takes the `Avoid` namespace as a parameter,
* so it works whether the host loads libavoid as WASM or pure JS) and never
* changes with the libavoid build.
*
* CANONICAL SOURCE: this file (drawio-dev js/libavoid-js/). drawio-mcp vendors
* verbatim copies (mcp-app-server/vendor/libavoid/ and
* mcp-tool-server/vendor/libavoid/) — copy this file over when it changes.
*
* A plain script defining globalThis.AvoidRouting, so the SAME artifact is:
* - concatenated into extensions.min.js here (glue → wasm → loader → this →
* the Closure-compiled LibavoidRouting editor binding),
* - inlined into (or CDN-loaded by) the drawio-mcp app-server viewer,
* - side-effect imported from Node by the drawio-mcp tool server
* (import the file, then read globalThis.AvoidRouting).
* It does not depend on the glue/loader — every entry point takes the Avoid
* namespace as a parameter — and must stay dependency-free (no mxGraph, no
* DOM): anything editor-specific belongs in js/diagramly/LibavoidRouting.js.
*
* libavoid API gotchas baked in here (empirically verified against the
* vendored build, libavoid-js 0.5.0-beta.5):
* - Router flag is an integer: RouterFlag.OrthogonalRouting.value
* - setRoutingParameter takes the enum OBJECT (RoutingParameter.x), not
* .value (the integer silently no-ops and routes run flush against boxes)
* - cleanup is router.delete() (embind), not Avoid.destroy()
* - Point/Rectangle/ConnEnd/Checkpoint(+vector) are embind wrappers COPIED
* into the objects they parameterize and NOT freed by router.delete();
* free each temporary with .delete()
* - displayRoute() and PolyLine.at() return a fresh OWNED copy per call in
* this build, but an unowned reference in draw.io's own binding
* (drawio-libavoid) — read routes through readRoute, which frees exactly
* the copies. A leaked copy changes later routes: libavoid breaks ties
* by object address, and leaks move where the next solve allocates
* - a directed ShapeConnectionPin gives the route NO minimum straight
* lead-out (it may turn at the anchor and run flush along the shape); a
* minimum stub needs a routing checkpoint at the stub tip. Checkpoint
* DIRECTION flags have an inverted vertical convention in this build —
* use plain 1-arg checkpoints only.
* - setRoutingCheckpoints does not queue the connector for rerouting in
* draw.io's own build (drawio-libavoid; the libavoid-js WASM build
* does), so a processTransaction after it keeps the old route: set an
* end of the connector again (setSourceEndpoint) to queue it
*/
(function()
{
var AvoidRouting = {};
// libavoid ConnDirFlags (the enum isn't exposed by the JS bindings): a
// bitmask of the directions a connector may approach an endpoint.
AvoidRouting.DIR = {up: 1, down: 2, left: 4, right: 8, all: 15};
/**
* Clamp to [0,1] — the ShapeConnectionPin proportional-offset domain.
*/
AvoidRouting.clamp01 = function(v)
{
return (v < 0) ? 0 : ((v > 1) ? 1 : v);
};
/**
* ConnDirFlags for a proportional connection point: perpendicular to the
* nearest shape edge (x<=0 left, x>=1 right, y<=0 up, y>=1 down), else any
* direction.
*/
AvoidRouting.dirForPoint = function(x, y)
{
var DIR = AvoidRouting.DIR;
var d = 0;
if (x <= 0) { d |= DIR.left; }
else if (x >= 1) { d |= DIR.right; }
if (y <= 0) { d |= DIR.up; }
else if (y >= 1) { d |= DIR.down; }
return (d != 0) ? d : DIR.all;
};
/**
* A fixed connection point as a routing constraint {x, y, dir}: the
* proportional position clamped to [0,1] (some shapes' connection points
* sit slightly outside, e.g. a hexagon tip at y=-0.017, which
* ShapeConnectionPin rejects) plus the ConnDirFlags direction derived from
* the ORIGINAL values so it still points off the correct edge. perimeter
* is the edge's exitPerimeter/entryPerimeter (false only when set to 0;
* see shapePin). Returns null when either coordinate is missing/not a
* number (floating endpoint).
*/
AvoidRouting.constraintForPoint = function(x, y, perimeter)
{
if (x == null || y == null || isNaN(x) || isNaN(y))
{
return null;
}
var c = {x: AvoidRouting.clamp01(x), y: AvoidRouting.clamp01(y),
dir: AvoidRouting.dirForPoint(x, y)};
// Only false matters (exitPerimeter=0): flips then move the point
// on a transformed shape (shapePin).
if (perimeter === false)
{
c.perimeter = false;
}
return c;
};
/**
* Proportional pin points for one masked side of bounds b ({x,y,w,h}):
* one pin per ~20px of side length (1..9, spread evenly so a single pin
* sits at the side midpoint), each directed off its side. Side letters
* follow the mxGraph port-constraint vocabulary (N/S/E/W). Used by
* computeRoutes' sourceSides/targetSides handling — the pins of all
* allowed sides share one pin class, so libavoid picks the side AND the
* position that route best.
*/
AvoidRouting.maskPinPoints = function(side, b)
{
var DIR = AvoidRouting.DIR;
var horizontal = (side == 'N' || side == 'S');
var len = horizontal ? b.w : b.h;
var n = Math.max(1, Math.min(9, Math.round(len / 20)));
var pts = [];
for (var i = 0; i < n; i++)
{
var f = (i + 0.5) / n;
pts.push((side == 'N') ? {x: f, y: 0, dir: DIR.up} :
(side == 'S') ? {x: f, y: 1, dir: DIR.down} :
(side == 'W') ? {x: 0, y: f, dir: DIR.left} :
{x: 1, y: f, dir: DIR.right});
}
return pts;
};
/**
* True when the point lies strictly inside any of the obstacles. A pinned
* anchor sits ON its own shape's boundary, so the strict test never
* matches the point's own shape.
*/
AvoidRouting.insideAny = function(x, y, obstacles)
{
if (obstacles != null)
{
for (var i = 0; i < obstacles.length; i++)
{
var v = obstacles[i];
if (v != null && x > v.x && x < v.x + v.w && y > v.y && y < v.y + v.h)
{
return true;
}
}
}
return false;
};
/**
* The stub tip a jetty checkpoint pins the route through: the constrained
* anchor on bounds b ({x,y,w,h}), moved jetty px outward along the pin's
* single ConnDirFlags direction. Returns {x, y} or null when there is
* nothing to enforce: no constraint, non-positive jetty, an ambiguous
* direction (corner/interior anchors carry 2+ direction bits), or a tip
* inside an obstacle ({x,y,w,h} array) INFLATED by the solve's buffer —
* libavoid's orthogonal visibility network stays clear of the buffered
* zones, so a checkpoint there is unreachable and libavoid warns
* ("Warning: skipping checkpoint for connector ...") on the console and
* ignores it; not requesting it keeps the route identical without the
* noise. The stub's OWN shape (matched by bounds) is exempt from the
* inflation — the pin's lead-out segment crosses its own buffer zone
* legitimately (verified against the WASM: no warning there).
*/
AvoidRouting.jettyStub = function(constraint, jetty, b, obstacles, buffer)
{
if (constraint == null || !(jetty > 0))
{
return null;
}
var d = constraint.dir;
var DIR = AvoidRouting.DIR;
if (d != DIR.up && d != DIR.down && d != DIR.left && d != DIR.right)
{
return null;
}
var x = b.x + constraint.x * b.w +
((d == DIR.right) ? jetty : ((d == DIR.left) ? -jetty : 0));
var y = b.y + constraint.y * b.h +
((d == DIR.down) ? jetty : ((d == DIR.up) ? -jetty : 0));
if (obstacles != null)
{
var inflate = (buffer > 0) ? buffer : 0;
for (var i = 0; i < obstacles.length; i++)
{
var v = obstacles[i];
if (v == null ||
(v.x == b.x && v.y == b.y && v.w == b.w && v.h == b.h))
{
continue;
}
if (x > v.x - inflate && x < v.x + v.w + inflate &&
y > v.y - inflate && y < v.y + v.h + inflate)
{
return null;
}
}
}
return {x: x, y: y};
};
/**
* One end's jetty capped to the clearance toward the OTHER terminal along
* the stub's own axis: half the directed gap (stub's base side to the
* facing side of the other shape) minus the 4px routing channel — so two
* facing stubs can never cross and a capped tip lands on the corridor
* channel's boundary; an uncapped stub in a tight gap puts its checkpoint
* past the channel and libavoid answers with a self-overlapping hairpin
* that nudging splays into flat side-loops. No cap when the end floats,
* the anchor is a corner/interior one (2+ direction bits — jettyStub
* skips those ends anyway), the stub points away from the other shape, or
* the shapes overlap along the stub's axis: such a stub never enters the
* pair's corridor, so a narrow gap along the OTHER axis must not shorten
* it (only the center segment squeezes through that gap, e.g. an L around
* a 15px horizontal gap keeps its full vertical lead-out).
*/
AvoidRouting.cappedJetty = function(jetty, constraint, from, to)
{
// A dangling (free-point) end has no bounds to measure the gap against.
if (from == null || to == null)
{
return jetty;
}
var DIR = AvoidRouting.DIR;
var d = (constraint != null) ? constraint.dir : 0;
var dgap = (d == DIR.down) ? to.y - (from.y + from.h) :
((d == DIR.up) ? from.y - (to.y + to.h) :
((d == DIR.right) ? to.x - (from.x + from.w) :
((d == DIR.left) ? from.x - (to.x + to.w) : 0)));
if (dgap > 0)
{
var half = Math.max(2, Math.floor((dgap - 4) / 2));
if (jetty > half)
{
return half;
}
}
return jetty;
};
/**
* Obstacles minus ENCLOSING shapes: a shape whose bounds fully contain a
* routed edge's terminal (and that is not itself a terminal of one of the
* edges) is the container/pool/group the terminal lives IN, not something
* to route around. Registering it starves the solve of corridors (both
* endpoints sit inside a hard obstacle, so routes escape it or degenerate)
* and suppresses the terminals' jetty stubs (jettyStub refuses tips inside
* any obstacle). Model ancestry is unknown here (this file is model-free),
* so containment is geometric: rect-contains-rect, inclusive. Terminals of
* the routed edges are never dropped (their ShapeRefs carry the connection
* pins). Returns a filtered copy; the input arrays are not modified.
*/
AvoidRouting.filterEnclosing = function(vertices, edges)
{
if (vertices == null || edges == null || edges.length === 0)
{
return vertices;
}
var terminalIds = Object.create(null);
var i;
for (i = 0; i < edges.length; i++)
{
if (edges[i] != null)
{
terminalIds[edges[i].source] = true;
terminalIds[edges[i].target] = true;
}
}
var terminals = [];
for (i = 0; i < vertices.length; i++)
{
var v = vertices[i];
if (v != null && terminalIds[v.id] === true)
{
terminals.push(v);
}
}
var out = [];
for (i = 0; i < vertices.length; i++)
{
var v = vertices[i];
if (v == null)
{
continue;
}
var enclosing = false;
if (terminalIds[v.id] !== true)
{
for (var j = 0; j < terminals.length; j++)
{
var t = terminals[j];
if (v.x <= t.x && v.y <= t.y &&
v.x + v.w >= t.x + t.w && v.y + v.h >= t.y + t.h)
{
enclosing = true;
break;
}
}
}
if (!enclosing)
{
out.push(v);
}
}
return out;
};
/**
* The transform a shape's style applies to its connection points, from a
* plain map of draw.io style values (a parsed style or getCellStyle
* result): rotation (degrees, clockwise), direction (north/south/west turn
* the shape inside its bounds), flipH/flipV — plus the legacy
* stencilFlipH/stencilFlipV when the shape is a stencil (stencil = true),
* and anchorPointDirection=0, which keeps the connection points still
* under a direction. Returns null for an untransformed shape. Set it as a
* vertex's `frame` (computeRoutes, obstacleBounds, shapePin).
*/
AvoidRouting.shapeFrame = function(style, stencil)
{
if (style == null)
{
return null;
}
var rotation = parseFloat(style.rotation);
rotation = isNaN(rotation) ? 0 : ((rotation % 360) + 360) % 360;
var direction = (style.direction == 'north' || style.direction == 'south' ||
style.direction == 'west') ? style.direction : null;
var flipH = style.flipH == 1 || (stencil == true && style.stencilFlipH == 1);
var flipV = style.flipV == 1 || (stencil == true && style.stencilFlipV == 1);
if (rotation == 0 && direction == null && !flipH && !flipV)
{
return null;
}
return {rotation: rotation, direction: direction, flipH: flipH, flipV: flipV,
anchorPointDirection: style.anchorPointDirection == null ||
style.anchorPointDirection == 1,
legacy: style.legacyAnchorPoints == null || style.legacyAnchorPoints == 1};
};
// {cos, sin} of a clockwise turn in degrees, EXACT for multiples of 90
// (the common case) so mapped pins land exactly on the box's sides.
function turn(degrees)
{
var r = ((degrees % 360) + 360) % 360;
return (r == 0) ? {cos: 1, sin: 0} : ((r == 90) ? {cos: 0, sin: 1} :
((r == 180) ? {cos: -1, sin: 0} : ((r == 270) ? {cos: 0, sin: -1} :
{cos: Math.cos(r * Math.PI / 180), sin: Math.sin(r * Math.PI / 180)})));
}
/**
* The obstacle box of vertex v ({x,y,w,h,frame?}): the bounding box of its
* bounds rotated about their centre by frame.rotation (direction and flips
* turn the drawing INSIDE the bounds, so they do not move it). v itself
* when it is not rotated.
*/
AvoidRouting.obstacleBounds = function(v)
{
if (v == null || v.frame == null || !v.frame.rotation)
{
return v;
}
var t = turn(v.frame.rotation);
var w = Math.abs(v.w * t.cos) + Math.abs(v.h * t.sin);
var h = Math.abs(v.w * t.sin) + Math.abs(v.h * t.cos);
return {id: v.id, x: v.x + (v.w - w) / 2, y: v.y + (v.h - h) / 2, w: w, h: h};
};
/**
* A pin {x, y, dir, perimeter?} given in vertex v's OWN frame (exitX/exitY,
* a declared connection point — proportional, dir and perimeter from
* constraintForPoint) mapped to where the shape draws it, as a pin on
* obstacleBounds(v). Follows the renderer: draw.io's default
* Graph.getLegacyConnectionPoint (frame.legacy) turns a point by the
* shape's direction and rotation and applies the flips only to a point
* NOT projected on the perimeter (perimeter false, i.e.
* exitPerimeter=0) — the projection undoes them; with
* legacyAnchorPoints=0, mxGraph.getConnectionPoint flips every point
* first. Direction north/south place the point in the bounds with width
* and height swapped (in legacy mode only while anchorPointDirection is
* on), flips swap with them. The approach direction turns with the
* point. The projection itself is not applied, as for unrotated shapes.
* Returns pin unchanged when v has no frame. At angles other than
* multiples of 90 the point lies inside the box and its direction snaps
* to the nearest axis (both at 45).
*/
AvoidRouting.shapePin = function(v, pin)
{
var f = (v != null) ? v.frame : null;
if (f == null || pin == null)
{
return pin;
}
var turned = f.direction == 'north' || f.direction == 'south';
var swap = turned && (f.anchorPointDirection || !f.legacy);
var flip = !f.legacy || pin.perimeter === false;
var flipH = flip && (turned ? f.flipV : f.flipH);
var flipV = flip && (turned ? f.flipH : f.flipV);
var dx = (pin.x - 0.5) * (swap ? v.h : v.w);
var dy = (pin.y - 0.5) * (swap ? v.w : v.h);
var steps = (f.direction != null && f.anchorPointDirection) ?
((f.direction == 'north') ? 270 : ((f.direction == 'west') ? 180 : 90)) : 0;
var t = turn(f.rotation + steps);
var b = AvoidRouting.obstacleBounds(v);
function clean(value)
{
// Float noise off the exact sides, then the pin domain.
return AvoidRouting.clamp01(Math.round(value * 1e9) / 1e9);
}
dx = flipH ? -dx : dx;
dy = flipV ? -dy : dy;
var DIR = AvoidRouting.DIR;
var bits = [[DIR.up, 0, -1], [DIR.down, 0, 1], [DIR.left, -1, 0], [DIR.right, 1, 0]];
var dir = 0;
for (var i = 0; i < bits.length; i++)
{
if ((pin.dir & bits[i][0]) != 0)
{
var vx = flipH ? -bits[i][1] : bits[i][1];
var vy = flipV ? -bits[i][2] : bits[i][2];
var rx = vx * t.cos - vy * t.sin;
var ry = vx * t.sin + vy * t.cos;
if (Math.abs(rx) >= Math.abs(ry) - 1e-9)
{
dir |= (rx > 0) ? DIR.right : DIR.left;
}
if (Math.abs(ry) >= Math.abs(rx) - 1e-9)
{
dir |= (ry > 0) ? DIR.down : DIR.up;
}
}
}
return {x: clean((v.w / 2 + dx * t.cos - dy * t.sin + (v.x - b.x)) / b.w),
y: clean((v.h / 2 + dx * t.sin + dy * t.cos + (v.y - b.y)) / b.h),
dir: (dir != 0) ? dir : pin.dir};
};
/**
* vertices and edges in the frame the solver works in: every vertex with
* a frame becomes its obstacle box, and each end on such a vertex has its
* constraint and snap points mapped (shapePin). Side masks are taken as
* already in that frame (the editor resolves them with
* portConstraintRotation). Returns new arrays; the inputs are not
* modified, and they come back as they are when nothing is transformed.
*/
AvoidRouting.toWorldFrame = function(vertices, edges)
{
var framed = Object.create(null);
var boxes = [];
var any = false;
var i, k;
for (i = 0; i < vertices.length; i++)
{
var v = vertices[i];
if (v != null && v.frame != null)
{
framed[v.id] = v;
any = true;
}
boxes.push(AvoidRouting.obstacleBounds(v));
}
if (!any)
{
return {vertices: vertices, edges: edges};
}
function points(v, pts)
{
if (pts == null)
{
return pts;
}
var out = [];
for (var q = 0; q < pts.length; q++)
{
out.push(AvoidRouting.shapePin(v, {x: pts[q].x, y: pts[q].y,
dir: (pts[q].dir != null) ? pts[q].dir : AvoidRouting.DIR.all,
perimeter: pts[q].perimeter}));
}
return out;
}
var mapped = [];
for (i = 0; i < edges.length; i++)
{
var e = edges[i];
var s = (e != null) ? framed[e.source] : null;
var t = (e != null) ? framed[e.target] : null;
if (s == null && t == null)
{
mapped.push(e);
continue;
}
var c = {};
for (k in e)
{
c[k] = e[k];
}
if (s != null)
{
c.sourceConstraint = AvoidRouting.shapePin(s, e.sourceConstraint);
c.sourcePoints = points(s, e.sourcePoints);
}
if (t != null)
{
c.targetConstraint = AvoidRouting.shapePin(t, e.targetConstraint);
c.targetPoints = points(t, e.targetPoints);
}
mapped.push(c);
}
return {vertices: boxes, edges: mapped};
};
/**
* Suffix of the id of the obstacle that libavoidLabels adds for the
* outside label of a vertex.
*/
AvoidRouting.LABEL_SUFFIX = '\u0000label';
/**
* Outside labels (labelPerimeter=1, mxGraphView.getLabelPerimeterSide):
* a vertex may carry label = {side, x, y, w, h}, the box of its label
* placed outside the shape on side 'N', 'S', 'E' or 'W', in the vertex's
* coordinates. Such a vertex routes as the shape grown over the label on
* that side, as wide (or tall) as the shape, plus the label's own box as
* a second obstacle, so no route crosses the label. An end on the label
* side ends at the label's far edge, where mxGraphView.getPerimeterPoint
* ends the edge: a floating end gets one pin at the middle of each side,
* the label side's at the label's far edge, and the shape's own
* connection points move with the grown box. Vertices with a frame
* (rotated, turned or flipped) and labels that don't reach beyond the
* shape are left as they are. Returns {vertices, edges, any} with new
* arrays, or the inputs and any false when no vertex has a label.
*/
AvoidRouting.withOutsideLabels = function(vertices, edges)
{
var grown = Object.create(null);
var out = [];
var any = false;
var i, k;
for (i = 0; i < vertices.length; i++)
{
var v = vertices[i];
var l = (v != null && v.frame == null) ? v.label : null;
var d = (l == null) ? 0 : ((l.side == 'S') ? l.y + l.h - (v.y + v.h) :
((l.side == 'N') ? v.y - l.y : ((l.side == 'E') ?
l.x + l.w - (v.x + v.w) : ((l.side == 'W') ? v.x - l.x : 0))));
if (!(d > 0) || !(l.w > 0) || !(l.h > 0))
{
out.push(v);
continue;
}
var g = {id: v.id, x: v.x, y: v.y, w: v.w, h: v.h};
if (l.side == 'S' || l.side == 'N')
{
g.h += d;
g.y -= (l.side == 'N') ? d : 0;
}
else
{
g.w += d;
g.x -= (l.side == 'W') ? d : 0;
}
grown[v.id] = {v: v, g: g, side: l.side};
out.push(g);
out.push({id: v.id + AvoidRouting.LABEL_SUFFIX, x: l.x, y: l.y, w: l.w, h: l.h});
any = true;
}
if (!any)
{
return {vertices: vertices, edges: edges, any: false};
}
// A pin of the shape (proportional to v) as a pin of the grown box: a
// pin on the label side's edge that is projected on the perimeter moves
// to the label's far edge, like the renderer's perimeter point.
function move(o, pin)
{
if (pin == null)
{
return pin;
}
var v = o.v, g = o.g;
var c = {};
for (var key in pin)
{
c[key] = pin[key];
}
c.x = (v.x + pin.x * v.w - g.x) / g.w;
c.y = (v.y + pin.y * v.h - g.y) / g.h;
if (pin.perimeter !== false)
{
if (o.side == 'S' && pin.y >= 1)
{
c.y = 1;
}
else if (o.side == 'N' && pin.y <= 0)
{
c.y = 0;
}
else if (o.side == 'E' && pin.x >= 1)
{
c.x = 1;
}
else if (o.side == 'W' && pin.x <= 0)
{
c.x = 0;
}
}
return c;
}
function pins(o, pts)
{
if (pts == null)
{
return pts;
}
var res = [];
for (var q = 0; q < pts.length; q++)
{
res.push(move(o, pts[q]));
}
return res;
}
// One pin at the middle of each side of the shape, the label side's at
// the label's far edge: where a floating end meets the shape.
function floating(o)
{
var DIR = AvoidRouting.DIR;
var v = o.v, g = o.g;
var cx = (v.x + v.w / 2 - g.x) / g.w;
var cy = (v.y + v.h / 2 - g.y) / g.h;
return [{x: cx, y: 0, dir: DIR.up}, {x: 1, y: cy, dir: DIR.right},
{x: cx, y: 1, dir: DIR.down}, {x: 0, y: cy, dir: DIR.left}];
}
function end(o, e, prefix, c)
{
var constraint = e[prefix + 'Constraint'];
var points = e[prefix + 'Points'];
var sides = e[prefix + 'Sides'];
if (constraint != null && constraint.dir != null)
{
c[prefix + 'Constraint'] = move(o, constraint);
}
else if (points != null && points.length > 0)
{
c[prefix + 'Points'] = pins(o, points);
}
else if (sides == null || sides.length == 0)
{
c[prefix + 'Points'] = floating(o);
}
}
var mapped = [];
for (i = 0; i < edges.length; i++)
{
var e = edges[i];
var so = (e != null) ? grown[e.source] : null;
var to = (e != null) ? grown[e.target] : null;
if (so == null && to == null)
{
mapped.push(e);
continue;
}
var c = {};
for (k in e)
{
c[k] = e[k];
}
if (so != null)
{
end(so, e, 'source', c);
}
if (to != null)
{
end(to, e, 'target', c);
}
mapped.push(c);
}
return {vertices: out, edges: mapped, any: true};
};
/**
* The candidate pins of one end on bounds b ({x,y,w,h}), as proportional
* {x, y, dir}, by the renderer's precedence: a fixed constraint (just its
* anchor) wins over a snap-point set (the shape's declared connection
* points, dir defaulting to DIR.all), which wins over a side mask (pins
* along every allowed side, maskPinPoints). Returns null for a floating
* end (none of the three).
*/
AvoidRouting.endPins = function(b, constraint, sides, points)
{
if (constraint != null && constraint.dir != null)
{
return [constraint];
}
var pins = [];
var i;
if (points != null && points.length > 0)
{
for (i = 0; i < points.length; i++)
{
pins.push({x: points[i].x, y: points[i].y,
dir: (points[i].dir != null) ? points[i].dir : AvoidRouting.DIR.all});
}
return pins;
}
if (sides != null && sides.length > 0)
{
for (i = 0; i < sides.length; i++)
{
pins = pins.concat(AvoidRouting.maskPinPoints(sides[i], b));
}
return pins;
}
return null;
};
/**
* Length of a route's first (atStart) or last straight run, px: the
* lead-out a jetty minimum is checked against. route: the route's points
* ({x, y}, endpoints included). Collinear raw points are merged (libavoid
* may split a straight lead-out) — the run ends at the first point that
* leaves the terminal's row/column. Infinity for a degenerate route, which
* checkpoints cannot improve. Shared by computeRoutes' lazy jetty check and
* the editor's drag preview, so both enforce the same minimum.
*/
AvoidRouting.endSegment = function(route, atStart)
{
var n = route.length;
if (n < 2)
{
return Infinity;
}
var a = route[atStart ? 0 : n - 1];
var b = route[atStart ? 1 : n - 2];
var horizontal = Math.abs(b.x - a.x) >= Math.abs(b.y - a.y);
var len = 0;
for (var k = atStart ? 1 : n - 2; k >= 0 && k < n; k += atStart ? 1 : -1)
{
var p = route[k];
if (Math.abs(horizontal ? p.y - a.y : p.x - a.x) > 0.5)
{
break;
}
len = Math.abs(horizontal ? p.x - a.x : p.y - a.y);
}
return len;
};
/**
* True when a route is libavoid's NO-ROUTE fallback instead of a route.
* When the search finds no path, libavoid returns the straight segment
* between the connector's two end vertices; for a pinned end that vertex
* is the pin class's dummy at the shape CENTRE, not a pin. A real
* orthogonal route is axis-aligned and starts/ends ON one of a pinned
* end's pins. pts: the route's absolute points. sourcePins/targetPins:
* the pinned ends' absolute pin positions ({x, y}), null for a floating
* or dangling end — whose fallback is only recognisable when diagonal.
*/
AvoidRouting.isFallbackRoute = function(pts, sourcePins, targetPins)
{
if (pts == null || pts.length != 2)
{
return false;
}
function onPin(p, pins)
{
if (pins == null)
{
return true;
}
for (var i = 0; i < pins.length; i++)
{
if (Math.abs(p.x - pins[i].x) < 0.5 && Math.abs(p.y - pins[i].y) < 0.5)
{
return true;
}
}
return false;
}
return (Math.abs(pts[0].x - pts[1].x) >= 0.5 && Math.abs(pts[0].y - pts[1].y) >= 0.5) ||
!onPin(pts[0], sourcePins) || !onPin(pts[1], targetPins);
};
/**
* Initial distance in px between the ends of the routed edges and the
* border of the region whose obstacles computeRoutes registers. Doubled
* each time a route comes too close to the border.
*/
AvoidRouting.regionMargin = 100;
/**
* Largest clearance in px that computeRoutes uses (as the Spacing of an
* edge in the editor). A connector without a route is retried at half the
* clearance down to 2px, so a crafted clearance (eg. 1e300) would retry
* about 1000 times.
*/
AvoidRouting.maxShapeBufferDistance = 999;
/**
* The given region ({x, y, x2, y2}, null for none) extended by the box
* b ({x, y, w, h}) or the point b ({x, y}). Returns region when b is null.
*/
AvoidRouting.addToRegion = function(region, b)
{
if (b == null)
{
return region;
}
var x2 = b.x + ((b.w > 0) ? b.w : 0);
var y2 = b.y + ((b.h > 0) ? b.h : 0);
return (region == null) ? {x: b.x, y: b.y, x2: x2, y2: y2} :
{x: Math.min(region.x, b.x), y: Math.min(region.y, b.y),
x2: Math.max(region.x2, x2), y2: Math.max(region.y2, y2)};
};
/**
* The given region grown by margin on all sides, or null if the grown
* region contains the given extent of all obstacles (no region needed).
*/
AvoidRouting.growRegion = function(region, margin, extent)
{
if (region == null || extent == null)
{
return null;
}
region = {x: region.x - margin, y: region.y - margin,
x2: region.x2 + margin, y2: region.y2 + margin};
return (region.x <= extent.x && region.y <= extent.y &&
region.x2 >= extent.x2 && region.y2 >= extent.y2) ? null : region;
};
/**
* The obstacles ({x, y, w, h}) that intersect the given region.
*/
AvoidRouting.obstaclesIn = function(obstacles, region)
{
var result = [];
for (var i = 0; i < obstacles.length; i++)
{
var v = obstacles[i];
if (v != null && v.x <= region.x2 && v.x + v.w >= region.x &&
v.y <= region.y2 && v.y + v.h >= region.y)
{
result.push(v);
}
}
return result;
};
/**
* True if all points of the given routes keep the given clearance from the
* border of the region, ie. the routes keep the clearance from all
* obstacles outside of the region.
*/
AvoidRouting.routesInside = function(routes, region, clearance)
{
for (var i = 0; i < routes.length; i++)
{
for (var k = 0; k < routes[i].length; k++)
{
var p = routes[i][k];
if (p.x < region.x + clearance || p.x > region.x2 - clearance ||
p.y < region.y + clearance || p.y > region.y2 - clearance)
{
return false;
}
}
}
return true;
};
/**
* Compute obstacle-avoiding orthogonal routes for a set of edges.
*
* @param {object} Avoid - the libavoid instance (AvoidLib.getInstance()).
* @param {Array<{id:string,x:number,y:number,w:number,h:number,frame?}>} vertices
* Obstacles, in ABSOLUTE coordinates: the UNROTATED bounds, with
* the shape's transform as frame (shapeFrame of its style) — the
* obstacle is then its rotated box and its ends' constraints and
* snap points, given in the shape's own frame, are mapped to where
* it draws them (toWorldFrame). Shapes enclosing a terminal of a
* routed edge are dropped (filterEnclosing). label = the box of a
* label outside the shape, {side, x, y, w, h}: see
* withOutsideLabels.
* @param {Array<{id,source,target,sourcePoint?,targetPoint?,
* sourceConstraint?,targetConstraint?,
* sourcePoints?,targetPoints?,sourceSides?,targetSides?,
* sourceJetty?,targetJetty?}>} edges
* Edges referencing vertex ids. An end may instead be a DANGLING free
* point — sourcePoint/targetPoint {x,y} in absolute coords, used when
* that terminal has no vertex (an unconnected endpoint): it routes to
* a plain Point ConnEnd (no shape, no direction), matching the
* drag-preview, and takes no constraint/pin/mask/jetty. An edge is
* skipped when an end is neither a vertex nor a free point, and
* when it is a SELF-LOOP (source === target) — loops keep the
* caller's own loop styling and waypoints.
* *Constraint = {x,y,dir} (constraintForPoint): a
* fixed connection point routed via a directed ShapeConnectionPin;
* absent => the endpoint floats at the shape centre. *Points = an
* array of {x,y,dir} candidate anchors (draw.io's snapToPoint —
* the shape's declared connection points): non-exclusive directed
* pins at each candidate under one pin class, libavoid picks the
* anchor that routes best; beaten by a *Constraint on the same end
* (an explicit anchor wins) and beats a *Sides mask (the renderer's
* snapToPoint branch runs before mask enforcement). *Sides = an
* array of allowed attach sides ('N'/'S'/'E'/'W', the legacy
* mxGraph portConstraint masks): non-exclusive pins spread along
* the allowed sides under one pin class, libavoid picks side and
* position. *Jetty = the minimum length of the first/last
* segment in px (draw.io's jettySize), enforced for ends with a
* *Constraint by a routing checkpoint at the stub tip — requested
* lazily, only for edges whose natural route falls short of the
* minimum; snapped and masked ends behave like floating ones here
* (their first bend naturally sits ~shapeBufferDistance out).
* Ends with the same candidate pins on one shape share them.
* @param {{shapeBufferDistance?:number,idealNudgingDistance?:number,
* nudgeShapeSegments?:boolean}} [opts]
* Defaults: 16 / 14 / false. nudgeShapeSegments nudges apart the
* segments that attach to a shape, so that ends sharing a pin
* (a side midpoint) don't share their first segment; always on when
* a vertex has an outside label. A connector libavoid finds no route for is
* retried alone at half the buffer, down to 2px. The buffer is at
* most maxShapeBufferDistance, and a buffer that is not a finite
* number uses the default.
* @returns {Object<string, Array<{x:number,y:number}>>} edge id -> interior
* bend points (ABSOLUTE, collinear-filtered). The first/last route
* points (endpoints) are dropped — a floating endpoint connects at
* the shape side midpoint, which is where a floating
* orthogonalEdgeStyle endpoint lands anyway. An edge with a
* straight (bend-free) route maps to []; an edge libavoid found no
* route for even on retry has NO entry, like a skipped one.
*/
AvoidRouting.computeRoutes = function(Avoid, vertices, edges, opts)
{
var out = Object.create(null);
if (Avoid == null || vertices == null || edges == null)
{
return out;
}
var buffer = (opts && opts.shapeBufferDistance != null) ? opts.shapeBufferDistance : 16;
var nudge = (opts && opts.idealNudgingDistance != null) ? opts.idealNudgingDistance : 14;
// Half of an infinite clearance is infinite, so the retry of the
// connectors without a route below would never end
if (!isFinite(buffer))
{
buffer = 16;
}
else if (buffer > AvoidRouting.maxShapeBufferDistance)
{
buffer = AvoidRouting.maxShapeBufferDistance;
}
// Outside labels: route around the shape and its label, and end on the
// label side at the label's far edge.
var labels = AvoidRouting.withOutsideLabels(vertices, edges);
vertices = labels.vertices;
edges = labels.edges;
// Opt-in, so that routes without outside labels stay as they are:
// nudge apart the segments that attach to a shape, so that ends
// sharing a pin don't share their first segment.
var nudgeShapeSegments = labels.any || (opts != null && opts.nudgeShapeSegments === true);
// Rotated, turned and flipped shapes: route around the box they are
// drawn in, from the connection points where they are drawn.
var world = AvoidRouting.toWorldFrame(vertices, edges);
vertices = world.vertices;
edges = world.edges;
// Containers the terminals live in are not obstacles (also feeds the
// jettyStub checks below, so stubs inside a container are preserved).
vertices = AvoidRouting.filterEnclosing(vertices, edges);
function collinear(a, b, c)
{
// Zero cross product (1px tolerance) => b lies on segment a..c (redundant).
return Math.abs((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)) < 1;
}
// A connector's display route as plain {x, y} points, freeing exactly
// what the binding hands over: displayRoute() and PolyLine.at() are
// UNOWNED references in draw.io's own binding (drawio-libavoid: the
// editor, the mcp app server) — deleting one destroys the route in
// place — and a fresh OWNED copy per call in the upstream libavoid-js
// build (the mcp tool server). Two calls alias one object only for
// references (isAliasOf), probed once per call. A leaked copy is not
// just memory: libavoid breaks ties between equal coordinates by
// object address, so it moved the next solve's allocations and a
// long-lived module routed identical input differently.
var ownedRoutes = null;
var ownedPoints = null;
function owned(first, second)
{
if (first.isAliasOf(second))
{
return false;
}
second.delete();
return true;
}
function readRoute(conn)
{
var route = conn.displayRoute();
var n = route.size();
var pts = [];
if (ownedRoutes == null)
{
ownedRoutes = owned(route, conn.displayRoute());
}
for (var k = 0; k < n; k++)
{
var p = route.at(k);
if (ownedPoints == null)
{
ownedPoints = owned(p, route.at(k));
}
pts.push({x: p.x, y: p.y});
if (ownedPoints)
{
p.delete();
}
}
if (ownedRoutes)
{
route.delete();
}
return pts;
}
// Proportional pins on bounds b as absolute {x, y} (null stays null).
function absolutePins(b, pins)
{
if (pins == null)
{
return null;
}
var abs = [];
for (var k = 0; k < pins.length; k++)
{
abs.push({x: b.x + pins[k].x * b.w, y: b.y + pins[k].y * b.h});
}
return abs;
}
// Endpoint anchor: the free point for a dangling end, else the fixed
// connection point, else the shape centre — the point the ConnEnd routes
// from.
function anchor(b, constraint, freePoint)
{
if (b == null)
{
return freePoint;
}
return (constraint != null) ?
{x: b.x + constraint.x * b.w, y: b.y + constraint.y * b.h} :
{x: b.x + b.w / 2, y: b.y + b.h / 2};
}
// One libavoid solve of batch at the given clearance around the given
// obstacles. Returns {routes, points, failed}: the routed edges' bends
// by edge id, every route's points (endpoints included) and the edges
// libavoid found NO route for (isFallbackRoute), in batch order.
function solveWith(batch, clearance, obstacles)
{
var result = {routes: Object.create(null), points: [], failed: []};
var bounds = Object.create(null);
var shapes = [];
var routable = [];
var i;
for (i = 0; i < obstacles.length; i++)
{
var v = obstacles[i];
if (v != null && v.id != null && v.w > 0 && v.h > 0)
{
bounds[v.id] = v;
shapes.push(v);
}
}
for (i = 0; i < batch.length; i++)
{
var e = batch[i];
// An end is either a known vertex or a dangling free point
// (e.sourcePoint / e.targetPoint, absolute coords) for an
// unconnected endpoint. Self-loops are out of scope: obstacle
// avoidance between identical endpoints is meaningless and the
// orthogonal router degenerates to a buffer-sized hook beside the
// shape. Skipping leaves the caller's loop styling and waypoints
// untouched (an edge with no route entry is never written), e.g.
// draw.io's inner-loop-waypoint self-loops.
if (e != null && (bounds[e.source] != null || e.sourcePoint != null) &&
(bounds[e.target] != null || e.targetPoint != null) &&
(e.source == null || e.source !== e.target))
{
routable.push(e);
}
}
// No router without connectors: a ShapeRef only queues its ShapeAdd,
// it becomes one of the obstacles that ~Router deletes in
// processTransaction, so a router deleted before a transaction
// leaked every shape with its vertices and pins (eg. a batch whose
// terminals are all on edges). The leak moved the next solves'
// allocations, and libavoid breaks ties by address.
if (routable.length === 0)
{
return result;
}
var router = new Avoid.Router(Avoid.RouterFlag.OrthogonalRouting.value);
try { router.setRoutingParameter(Avoid.RoutingParameter.shapeBufferDistance, clearance); } catch (e) {}
try { router.setRoutingParameter(Avoid.RoutingParameter.idealNudgingDistance, nudge); } catch (e) {}
if (nudgeShapeSegments)
{
try { router.setRoutingOption(Avoid.RoutingOption.nudgeOrthogonalSegmentsConnectedToShapes, true); } catch (e) {}
try { router.setRoutingOption(Avoid.RoutingOption.penaliseOrthogonalSharedPathsAtConnEnds, true); } catch (e) {}
}
var shapeRefs = Object.create(null);
var pinClasses = Object.create(null);
var pinClass = 0;
for (i = 0; i < shapes.length; i++)
{
v = shapes[i];
// Point/Rectangle are embind value wrappers that COPY into the
// ShapeRef and are NOT freed by router.delete(); free the temporaries.
var rp1 = new Avoid.Point(v.x, v.y);
var rp2 = new Avoid.Point(v.x + v.w, v.y + v.h);
var rect = new Avoid.Rectangle(rp1, rp2);
shapeRefs[v.id] = new Avoid.ShapeRef(router, rect);
rect.delete();
rp1.delete();
rp2.delete();
}
// ONE pin class per distinct candidate set on a shape, with
// non-exclusive pins, shared by every end that attaches there.
// Two pins at the SAME point in different classes break libavoid's
// orthogonal visibility sweep, which assumes no two breakpoints
// coincide (an assert in orthogonal.cpp, compiled out in release
// builds): the connector registered second got no route at all —
// every fan-out/fan-in on one fixed connection point, snap-point
// set or side mask. The key is order-free; the pins are registered
// in the first end's order.
function pinClassFor(vid, pins)
{
var parts = [];
for (var k = 0; k < pins.length; k++)
{
parts.push(pins[k].x + ',' + pins[k].y + ',' + pins[k].dir);
}
var key = vid + '\n' + parts.sort().join(' ');
if (pinClasses[key] == null)
{
pinClasses[key] = ++pinClass;
for (k = 0; k < pins.length; k++)
{
// Registers itself with the ShapeRef (freed with the
// router); the wrapper is only kept to make it shareable.
var pin = new Avoid.ShapeConnectionPin(shapeRefs[vid], pinClass,
pins[k].x, pins[k].y, true, 0, pins[k].dir);
pin.setExclusive(false);
}
}
return pinClasses[key];
}
// An endpoint is FLOATING (ConnEnd at the shape centre) unless it
// has candidate pins (endPins): a fixed connection point — a
// directed pin makes the route leave/enter the anchor
// perpendicular to the shape edge instead of cutting through it —
// a snap-point set (draw.io's snapToPoint: the shape's declared
// connection points) or a side MASK (the legacy mxGraph
// portConstraint vocabulary). A set's pins share one class, so
// libavoid picks the anchor (side and position) that routes best;
// ends sharing a class share its pins and nudging separates their
// corridors, like the render-time router spreading floating
// attaches.
function makeEnd(vid, b, pins, freePoint)
{
// Dangling end: no vertex bounds, just a free point (the edge's
// unconnected endpoint). Route to a plain Point ConnEnd — no shape,
// no direction — exactly as the warm-session drag preview does, so a
// committed edge with an unconnected end matches its live preview.
if (b == null)
{
var dp = new Avoid.Point(freePoint.x, freePoint.y);
var dce = new Avoid.ConnEnd(dp);
dp.delete();
return dce;
}
if (pins != null && shapeRefs[vid] != null)
{
return new Avoid.ConnEnd(shapeRefs[vid], pinClassFor(vid, pins));
}
// Free the temporary centre Point (copied into the ConnEnd); the
// ConnEnd itself is freed by the ConnRef caller below.
var cp = new Avoid.Point(b.x + b.w / 2, b.y + b.h / 2);
var ce = new Avoid.ConnEnd(cp);
cp.delete();
return ce;
}
// Wrap a stub tip as a routing checkpoint. Checkpoint copies the Point
// and the vector copies the Checkpoint — free both embind wrappers.
function addCheckpoint(vec, p)
{
if (p != null)
{
var pt = new Avoid.Point(p.x, p.y);
var cp = new Avoid.Checkpoint(pt);
vec.push_back(cp);
cp.delete();
pt.delete();
}
}
var conns = [];
for (i = 0; i < routable.length; i++)
{
e = routable[i];
var sb = bounds[e.source];
var tb = bounds[e.target];
var sPins = (sb != null) ? AvoidRouting.endPins(sb,
e.sourceConstraint, e.sourceSides, e.sourcePoints) : null;
var tPins = (tb != null) ? AvoidRouting.endPins(tb,
e.targetConstraint, e.targetSides, e.targetPoints) : null;
// ConnRef copies the ConnEnds, so free them after construction
// (they are not owned by the router).
var se = makeEnd(e.source, sb, sPins, e.sourcePoint);
var de = makeEnd(e.target, tb, tPins, e.targetPoint);
var conn = new Avoid.ConnRef(router, se, de);
se.delete();
de.delete();
// Jetty stubs: force the route through a checkpoint jetty px
// outward of each constrained anchor, so the first/last segment is
// at least that long. Capped per end to the clearance the terminal
// pair's gap allows along the stub's axis (cappedJetty). Skipped
// for ends where there is nothing to enforce (jettyStub), and for
// the whole edge when the anchors are closer than the summed
// stubs — the same too-short guard as mxEdgeStyle.OrthConnector —
// so a short edge isn't forced to double back through its
// checkpoints. The stubs are computed here but requested LAZILY
// after the first solve (see below).
var sourceJetty = AvoidRouting.cappedJetty(e.sourceJetty, e.sourceConstraint, sb, tb);
var targetJetty = AvoidRouting.cappedJetty(e.targetJetty, e.targetConstraint, tb, sb);
var sa = anchor(sb, e.sourceConstraint, e.sourcePoint);
var ta = anchor(tb, e.targetConstraint, e.targetPoint);
// A pinned anchor buried inside ANOTHER obstacle (a shape dragged
// over the terminal) puts the whole route into libavoid's escape /
// degenerate mode: checkpoints on such a route are unreachable and
// libavoid warns ("skipping checkpoint") for EVERY end — including
// tips in perfectly clear space — before discarding them. Skip BOTH
// stubs for the edge instead (verified against the WASM: same
// route, no console noise).
var buried = (e.sourceConstraint != null &&
AvoidRouting.insideAny(sa.x, sa.y, vertices)) ||
(e.targetConstraint != null &&
AvoidRouting.insideAny(ta.x, ta.y, vertices));
var scp = buried ? null :
AvoidRouting.jettyStub(e.sourceConstraint, sourceJetty, sb, vertices, clearance);
var tcp = buried ? null :
AvoidRouting.jettyStub(e.targetConstraint, targetJetty, tb, vertices, clearance);
if (scp != null || tcp != null)
{
var dx = ta.x - sa.x;
var dy = ta.y - sa.y;
var total = ((scp != null) ? sourceJetty : 0) +
((tcp != null) ? targetJetty : 0);
if (dx * dx + dy * dy < total * total)
{
scp = null;
tcp = null;
}
}
conns.push({edge: e, conn: conn, scp: scp, tcp: tcp,
sourceJetty: sourceJetty, targetJetty: targetJetty,
sourcePins: absolutePins(sb, sPins),
targetPins: absolutePins(tb, tPins),
sourceEnd: [e.source, sb, sPins, e.sourcePoint]});
}
router.processTransaction();
// LAZY jetty enforcement: the first solve runs WITHOUT the stub
// checkpoints; they are requested only for edges whose natural route
// violates a jetty minimum, and the transaction re-processed once. A
// checkpoint is a hard point the route must touch: when libavoid
// TURNS at one instead of crossing it mid-segment, the adjacent bend
// is pinned at the stub tip and nudging cannot center the segment in
// its channel — lopsided lead-outs (e.g. 30/10 on one edge next to a
// centered 20/20 twin) on routes that met the minimum for free.
// Enforcing lazily keeps the nudged, evenly distributed route
// wherever it already satisfies the jetty, and falls back to the
// checkpointed solve only where it does not. A connector without a
// route gets no checkpoints: they cannot give it one, only
// "skipping checkpoint" warnings.
var dirty = false;
for (i = 0; i < conns.length; i++)
{
var c = conns[i];
if (c.scp == null && c.tcp == null)
{
continue;
}
// 0.5px tolerance: sub-pixel misses vanish in the output rounding
// and do not warrant pinning the route to the checkpoints.
var r0 = readRoute(c.conn);
if (!AvoidRouting.isFallbackRoute(r0, c.sourcePins, c.targetPins) &&
((c.scp != null && AvoidRouting.endSegment(r0, true) < c.sourceJetty - 0.5) ||
(c.tcp != null && AvoidRouting.endSegment(r0, false) < c.targetJetty - 0.5)))
{
// In route order (source first); setRoutingCheckpoints copies
// the vector, so free the wrapper.
var cps = new Avoid.CheckpointVector();
addCheckpoint(cps, c.scp);
addCheckpoint(cps, c.tcp);
c.conn.setRoutingCheckpoints(cps);
cps.delete();
// Queues the reroute: see the setRoutingCheckpoints gotcha
// in the header
var se2 = makeEnd.apply(null, c.sourceEnd);
c.conn.setSourceEndpoint(se2);
se2.delete();
dirty = true;
}
}
if (dirty)
{
router.processTransaction();
}
for (i = 0; i < conns.length; i++)
{
var pts = readRoute(conns[i].conn);
if (AvoidRouting.isFallbackRoute(pts, conns[i].sourcePins, conns[i].targetPins))
{
result.failed.push(conns[i].edge);
continue;
}
var wps = [];
for (var k = 1; k < pts.length - 1; k++)
{
if (collinear(pts[k - 1], pts[k], pts[k + 1]))
{
continue;
}
wps.push({x: Math.round(pts[k].x), y: Math.round(pts[k].y)});
}
result.routes[conns[i].edge.id] = wps;
result.points.push(pts);
}
router.delete();
return result;
}
// Terminal bounds by id for the regions, matching the bounds that
// solveWith registers, and the extent of all obstacles
var terminals = Object.create(null);
var extent = null;
for (var i = 0; i < vertices.length; i++)
{
var v = vertices[i];
if (v != null)
{
extent = AvoidRouting.addToRegion(extent, v);
if (v.id != null && v.w > 0 && v.h > 0)
{
terminals[v.id] = v;
}
}
}
// One solve of batch at the given clearance. Writes the routed edges
// into out; returns the edges libavoid found NO route for, in batch
// order, for the retry below. The obstacles are limited to a region
// around the batch's ends: the cost of a solve grows with the number
// of obstacles (~400ms for one edge among 2600 shapes), not with the
// distance the routes cover. A route that keeps the clearance from
// the region's border is also valid with all obstacles and, as fewer
// obstacles never make the best route worse, also a best route with
// all obstacles. Routes closer to the border are solved again in a
// larger region. A connector without a route in the region has none
// with all obstacles either, as more obstacles never open up a route.
function solve(batch, clearance)
{
var margin = AvoidRouting.regionMargin;
var region = null;
for (var i = 0; i < batch.length; i++)
{
var e = batch[i];
if (e != null)
{
var sb = (e.source != null) ? terminals[e.source] : null;
var tb = (e.target != null) ? terminals[e.target] : null;
region = AvoidRouting.addToRegion(region, (sb != null) ? sb : e.sourcePoint);
region = AvoidRouting.addToRegion(region, (tb != null) ? tb : e.targetPoint);
}
}
region = AvoidRouting.growRegion(region, margin, extent);
while (true)
{
var result = solveWith(batch, clearance, (region != null) ?
AvoidRouting.obstaclesIn(vertices, region) : vertices);
if (region == null || AvoidRouting.routesInside(
result.points, region, clearance))
{
for (var id in result.routes)
{
out[id] = result.routes[id];
}
return result.failed;
}
for (i = 0; i < result.points.length; i++)
{
for (var k = 0; k < result.points[i].length; k++)
{
region = AvoidRouting.addToRegion(region, result.points[i][k]);
}
}
margin *= 2;
region = AvoidRouting.growRegion(region, margin, extent);
}
}
// A connector libavoid found NO route for is retried on its own with
// the clearance halved, down to 2px: typically a pinned end faces a
// gap narrower than twice the buffer (a label or marker placed a few
// px from the shape), which the buffered obstacles close. Only the
// failed connectors are re-solved — the others keep the configured
// clearance — so a retried route is not nudged against the rest,
// like the editor's per-buffer buckets. Whatever still fails has no
// entry: callers leave such an edge as authored instead of writing
// the fallback's straight line over its waypoints.
var failed = solve(edges, buffer);
for (var retry = Math.floor(buffer / 2); failed.length > 0 && retry >= 2;
retry = Math.floor(retry / 2))
{
failed = solve(failed, retry);
}
return out;
};
globalThis.AvoidRouting = AvoidRouting;
})();