816 lines
36 KiB
JavaScript
816 lines
36 KiB
JavaScript
"use strict";
|
|
|
|
function lineageSegmentKind(x1, y1, x2, y2) {
|
|
if (Math.abs(y2 - y1) < 0.01) return 'h';
|
|
if (Math.abs(x2 - x1) < 0.01) return 'v';
|
|
return 'd';
|
|
}
|
|
|
|
function lineageSegmentsFromPoints(points) {
|
|
const segments = [];
|
|
for (let i = 1; i < points.length; i++) {
|
|
const [x1, y1] = points[i - 1];
|
|
const [x2, y2] = points[i];
|
|
segments.push({ kind: lineageSegmentKind(x1, y1, x2, y2), x1, y1, x2, y2 });
|
|
}
|
|
return segments;
|
|
}
|
|
|
|
function lineageRoutePointKey(x, y) {
|
|
return `${Math.round(Number(x || 0) * 10) / 10},${Math.round(Number(y || 0) * 10) / 10}`;
|
|
}
|
|
|
|
function lineageRouteSamePoint(a, b) {
|
|
return Math.abs(Number(a?.[0]) - Number(b?.[0])) < 0.05 && Math.abs(Number(a?.[1]) - Number(b?.[1])) < 0.05;
|
|
}
|
|
|
|
function lineageCleanRoutePoints(points) {
|
|
const raw = (points || [])
|
|
.map(p => [Number(p?.[0]), Number(p?.[1])])
|
|
.filter(p => Number.isFinite(p[0]) && Number.isFinite(p[1]));
|
|
const deduped = [];
|
|
for (const p of raw) {
|
|
if (!deduped.length || !lineageRouteSamePoint(deduped[deduped.length - 1], p)) deduped.push(p);
|
|
}
|
|
let changed = true;
|
|
while (changed) {
|
|
changed = false;
|
|
for (let i = 1; i < deduped.length - 1; i++) {
|
|
const a = deduped[i - 1];
|
|
const b = deduped[i];
|
|
const c = deduped[i + 1];
|
|
const sameX = Math.abs(a[0] - b[0]) < 0.05 && Math.abs(b[0] - c[0]) < 0.05;
|
|
const sameY = Math.abs(a[1] - b[1]) < 0.05 && Math.abs(b[1] - c[1]) < 0.05;
|
|
const reverse = lineageRouteSamePoint(a, c);
|
|
if (sameX || sameY || reverse) {
|
|
deduped.splice(i, 1);
|
|
changed = true;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
return deduped;
|
|
}
|
|
|
|
function lineagePathFromPoints(points) {
|
|
const clean = lineageForceOrthogonalPoints(points);
|
|
if (!clean.length) return "";
|
|
return `M ${clean[0][0].toFixed(1)} ${clean[0][1].toFixed(1)}` + clean.slice(1).map(p => ` L ${p[0].toFixed(1)} ${p[1].toFixed(1)}`).join('');
|
|
}
|
|
|
|
function lineagePointInsideRouteRect(x, y, rects = []) {
|
|
return (rects || []).some(r => x > r.left && x < r.right && y > r.top && y < r.bottom);
|
|
}
|
|
|
|
function lineageRouteSegmentClear(x1, y1, x2, y2, rects = []) {
|
|
if (!Number.isFinite(x1) || !Number.isFinite(y1) || !Number.isFinite(x2) || !Number.isFinite(y2)) return false;
|
|
if (Math.abs(x1 - x2) < 0.05 && Math.abs(y1 - y2) < 0.05) return true;
|
|
const vertical = Math.abs(x1 - x2) < 0.05;
|
|
const horizontal = Math.abs(y1 - y2) < 0.05;
|
|
if (!vertical && !horizontal) return false;
|
|
for (const r of rects || []) {
|
|
if (vertical) {
|
|
const top = Math.min(y1, y2);
|
|
const bottom = Math.max(y1, y2);
|
|
if (x1 > r.left && x1 < r.right && Math.max(top, r.top) < Math.min(bottom, r.bottom)) return false;
|
|
} else {
|
|
const left = Math.min(x1, x2);
|
|
const right = Math.max(x1, x2);
|
|
if (y1 > r.top && y1 < r.bottom && Math.max(left, r.left) < Math.min(right, r.right)) return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
function lineageOrthogonalFallbackPoints(x1, y1, x2, y2, rects = []) {
|
|
const candidates = [
|
|
[[x1, y1], [x2, y1], [x2, y2]],
|
|
[[x1, y1], [x1, y2], [x2, y2]],
|
|
];
|
|
const score = points => {
|
|
let bad = 0;
|
|
let length = 0;
|
|
for (let i = 1; i < points.length; i++) {
|
|
const a = points[i - 1];
|
|
const b = points[i];
|
|
length += Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
|
|
if (!lineageRouteSegmentClear(a[0], a[1], b[0], b[1], rects)) bad += 100000;
|
|
}
|
|
return bad + length;
|
|
};
|
|
candidates.sort((a, b) => score(a) - score(b));
|
|
return lineageCleanRoutePoints(candidates[0]);
|
|
}
|
|
|
|
function lineageForceOrthogonalPoints(points) {
|
|
const clean = lineageCleanRoutePoints(points);
|
|
if (clean.length <= 1) return clean;
|
|
const out = [clean[0]];
|
|
for (let i = 1; i < clean.length; i++) {
|
|
const prev = out[out.length - 1];
|
|
const cur = clean[i];
|
|
const diagonal = Math.abs(prev[0] - cur[0]) >= 0.05 && Math.abs(prev[1] - cur[1]) >= 0.05;
|
|
if (diagonal) {
|
|
const via = [cur[0], prev[1]];
|
|
if (!lineageRouteSamePoint(prev, via)) out.push(via);
|
|
}
|
|
if (!lineageRouteSamePoint(out[out.length - 1], cur)) out.push(cur);
|
|
}
|
|
return lineageCleanRoutePoints(out);
|
|
}
|
|
|
|
|
|
function lineageRelevantRouteRects(x1, y1, x2, y2, rects = [], margin = 92) {
|
|
const left = Math.min(x1, x2) - margin;
|
|
const right = Math.max(x1, x2) + margin;
|
|
const top = Math.min(y1, y2) - margin;
|
|
const bottom = Math.max(y1, y2) + margin;
|
|
return (rects || []).filter(r => r.right >= left && r.left <= right && r.bottom >= top && r.top <= bottom);
|
|
}
|
|
|
|
function lineageOrthogonalRoutePoints(x1, y1, x2, y2, rects = [], context = {}) {
|
|
if (!Number.isFinite(x1) || !Number.isFinite(y1) || !Number.isFinite(x2) || !Number.isFinite(y2)) return [];
|
|
if (Math.abs(x1 - x2) < 0.05 && Math.abs(y1 - y2) < 0.05) return [[x1, y1]];
|
|
const relevant = lineageRelevantRouteRects(x1, y1, x2, y2, rects, Number(context.routeMargin || 110) || 110);
|
|
if (lineageRouteSegmentClear(x1, y1, x2, y2, relevant)) return [[x1, y1], [x2, y2]];
|
|
|
|
const width = Number(context.width || 0) || 0;
|
|
const height = Number(context.height || 0) || 0;
|
|
const minX = 8;
|
|
const minY = Math.max(8, Number(context.minRouteY ?? 8) || 8);
|
|
const maxX = width > 24 ? width - 8 : Math.max(x1, x2, ...relevant.map(r => r.right + 30), 240);
|
|
const maxY = height > 24 ? height - 8 : Math.max(y1, y2, ...relevant.map(r => r.bottom + 30), 240);
|
|
const xs = [x1, x2, minX, maxX];
|
|
const ys = [y1, y2, minY, maxY];
|
|
if (Number.isFinite(Number(context.preferredX))) xs.push(Number(context.preferredX));
|
|
if (Number.isFinite(Number(context.preferredY))) ys.push(Number(context.preferredY));
|
|
for (const r of relevant) {
|
|
xs.push(r.left - 8, r.left, r.right, r.right + 8);
|
|
ys.push(r.top - 8, r.top, r.bottom, r.bottom + 8);
|
|
}
|
|
const norm = values => Array.from(new Set(values
|
|
.map(v => Math.round(Number(v) * 10) / 10)
|
|
.filter(Number.isFinite)))
|
|
.sort((a, b) => a - b);
|
|
let ux = norm(xs).filter(v => v >= minX && v <= maxX);
|
|
let uy = norm(ys).filter(v => v >= minY && v <= maxY);
|
|
if (!ux.some(v => Math.abs(v - x1) < 0.05)) ux.push(x1);
|
|
if (!ux.some(v => Math.abs(v - x2) < 0.05)) ux.push(x2);
|
|
if (!uy.some(v => Math.abs(v - y1) < 0.05)) uy.push(y1);
|
|
if (!uy.some(v => Math.abs(v - y2) < 0.05)) uy.push(y2);
|
|
ux = Array.from(new Set(ux.map(v => Math.round(v * 10) / 10))).sort((a, b) => a - b);
|
|
uy = Array.from(new Set(uy.map(v => Math.round(v * 10) / 10))).sort((a, b) => a - b);
|
|
|
|
const passable = new Set();
|
|
const keyFor = (i, j) => `${i}:${j}`;
|
|
for (let i = 0; i < ux.length; i++) {
|
|
for (let j = 0; j < uy.length; j++) {
|
|
if (!lineagePointInsideRouteRect(ux[i], uy[j], relevant)) passable.add(keyFor(i, j));
|
|
}
|
|
}
|
|
const ix1 = ux.findIndex(v => Math.abs(v - x1) < 0.05);
|
|
const iy1 = uy.findIndex(v => Math.abs(v - y1) < 0.05);
|
|
const ix2 = ux.findIndex(v => Math.abs(v - x2) < 0.05);
|
|
const iy2 = uy.findIndex(v => Math.abs(v - y2) < 0.05);
|
|
const start = keyFor(ix1, iy1);
|
|
const goal = keyFor(ix2, iy2);
|
|
passable.add(start);
|
|
passable.add(goal);
|
|
|
|
const dist = new Map([[start, 0]]);
|
|
const prev = new Map();
|
|
const open = new Set([start]);
|
|
const score = key => {
|
|
const [i, j] = key.split(':').map(Number);
|
|
return (dist.get(key) || 0) + Math.abs(ux[i] - x2) + Math.abs(uy[j] - y2) * 1.08;
|
|
};
|
|
let guard = 0;
|
|
while (open.size && guard++ < 20000) {
|
|
let cur = null;
|
|
for (const k of open) if (cur === null || score(k) < score(cur)) cur = k;
|
|
if (cur === goal) break;
|
|
open.delete(cur);
|
|
const [i, j] = cur.split(':').map(Number);
|
|
const neighbors = [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]];
|
|
for (const [ni, nj] of neighbors) {
|
|
if (ni < 0 || nj < 0 || ni >= ux.length || nj >= uy.length) continue;
|
|
const nk = keyFor(ni, nj);
|
|
if (!passable.has(nk)) continue;
|
|
if (!lineageRouteSegmentClear(ux[i], uy[j], ux[ni], uy[nj], relevant)) continue;
|
|
const turnPenalty = (() => {
|
|
const pk = prev.get(cur);
|
|
if (!pk) return 0;
|
|
const [pi, pj] = pk.split(':').map(Number);
|
|
const wasH = pi !== i;
|
|
const nowH = ni !== i;
|
|
return wasH === nowH ? 0 : 5;
|
|
})();
|
|
const step = Math.abs(ux[i] - ux[ni]) + Math.abs(uy[j] - uy[nj]) + turnPenalty;
|
|
const nd = (dist.get(cur) || 0) + step;
|
|
if (nd + 0.001 < (dist.get(nk) ?? Infinity)) {
|
|
dist.set(nk, nd);
|
|
prev.set(nk, cur);
|
|
open.add(nk);
|
|
}
|
|
}
|
|
}
|
|
if (dist.has(goal)) {
|
|
const keys = [];
|
|
let cur = goal;
|
|
while (cur) {
|
|
keys.push(cur);
|
|
if (cur === start) break;
|
|
cur = prev.get(cur);
|
|
}
|
|
keys.reverse();
|
|
return lineageCleanRoutePoints(keys.map(k => {
|
|
const [i, j] = k.split(':').map(Number);
|
|
return [ux[i], uy[j]];
|
|
}));
|
|
}
|
|
|
|
// Last-resort route: prefer an L shape that is at least connected and then
|
|
// simplify it. This should rarely be used, but avoids emitting orphaned SVG
|
|
// fragments when the obstacle grid is over-constrained.
|
|
const viaA = [[x1, y1], [x1, y2], [x2, y2]];
|
|
if (lineageRouteSegmentClear(x1, y1, x1, y2, relevant) && lineageRouteSegmentClear(x1, y2, x2, y2, relevant)) return lineageCleanRoutePoints(viaA);
|
|
const viaB = [[x1, y1], [x2, y1], [x2, y2]];
|
|
if (lineageRouteSegmentClear(x1, y1, x2, y1, relevant) && lineageRouteSegmentClear(x2, y1, x2, y2, relevant)) return lineageCleanRoutePoints(viaB);
|
|
return lineageOrthogonalFallbackPoints(x1, y1, x2, y2, relevant);
|
|
}
|
|
|
|
function lineageNodeRectsBetween(positions, nodeW, nodeH, y1, y2, excludeIds = new Set(), pad = 10) {
|
|
const top = Math.min(y1, y2) - pad;
|
|
const bottom = Math.max(y1, y2) + pad;
|
|
const rects = [];
|
|
for (const pos of positions?.values?.() || []) {
|
|
const id = pos?.node?.id;
|
|
if (!pos || (id && excludeIds.has(id))) continue;
|
|
const rectTop = pos.y - pad;
|
|
const rectBottom = pos.y + nodeH + pad;
|
|
if (rectBottom < top || rectTop > bottom) continue;
|
|
rects.push({ left: pos.x - pad, right: pos.x + nodeW + pad, top: rectTop, bottom: rectBottom });
|
|
}
|
|
return rects;
|
|
}
|
|
|
|
function lineageVerticalLaneClear(x, y1, y2, rects) {
|
|
const top = Math.min(y1, y2);
|
|
const bottom = Math.max(y1, y2);
|
|
return !(rects || []).some(r => x > r.left && x < r.right && Math.max(top, r.top) < Math.min(bottom, r.bottom));
|
|
}
|
|
|
|
function lineageRouteNodeRects(positions, nodeW, nodeH, excludeIds = new Set(), pad = 8) {
|
|
const rects = [];
|
|
for (const pos of positions?.values?.() || []) {
|
|
const id = pos?.node?.id;
|
|
if (!pos || (id && excludeIds.has(id))) continue;
|
|
rects.push({
|
|
left: pos.x - pad,
|
|
right: pos.x + nodeW + pad,
|
|
top: pos.y - pad,
|
|
bottom: pos.y + nodeH + pad,
|
|
});
|
|
}
|
|
return rects;
|
|
}
|
|
|
|
function lineageHorizontalLaneClear(y, x1, x2, rects) {
|
|
const left = Math.min(x1, x2);
|
|
const right = Math.max(x1, x2);
|
|
return !(rects || []).some(r => y > r.top && y < r.bottom && Math.max(left, r.left) < Math.min(right, r.right));
|
|
}
|
|
|
|
|
|
function lineageRouteVerticalClear(x, y1, y2, rects) {
|
|
const top = Math.min(y1, y2);
|
|
const bottom = Math.max(y1, y2);
|
|
return !(rects || []).some(r => x > r.left && x < r.right && Math.max(top, r.top) < Math.min(bottom, r.bottom));
|
|
}
|
|
|
|
function lineageRouteHorizontalClear(y, x1, x2, rects) {
|
|
const left = Math.min(x1, x2);
|
|
const right = Math.max(x1, x2);
|
|
return !(rects || []).some(r => y > r.top && y < r.bottom && Math.max(left, r.left) < Math.min(right, r.right));
|
|
}
|
|
|
|
function lineageChooseVerticalDetourX(x, y1, y2, rects, context = {}) {
|
|
const top = Math.min(y1, y2);
|
|
const bottom = Math.max(y1, y2);
|
|
const blockers = (rects || []).filter(r => Math.max(top, r.top) < Math.min(bottom, r.bottom));
|
|
const width = Number(context.width || 0) || 0;
|
|
const minX = 8;
|
|
const maxX = width > 16 ? width - 8 : Math.max(x + 120, ...blockers.map(r => r.right + 18), 240);
|
|
const candidates = [x - 34, x + 34, x - 58, x + 58];
|
|
for (const r of blockers) {
|
|
candidates.push(r.left - 12, r.right + 12, r.left - 22, r.right + 22);
|
|
}
|
|
const unique = Array.from(new Set(candidates
|
|
.map(v => clamp(Math.round(v * 10) / 10, minX, maxX))))
|
|
.filter(v => Number.isFinite(v) && lineageRouteVerticalClear(v, y1, y2, rects));
|
|
const pool = unique.length ? unique : Array.from(new Set(candidates.map(v => clamp(Math.round(v * 10) / 10, minX, maxX)))).filter(Number.isFinite);
|
|
if (!pool.length) return clamp(x, minX, maxX);
|
|
return pool.sort((a, b) => Math.abs(a - x) - Math.abs(b - x))[0];
|
|
}
|
|
|
|
function lineageChooseChildDetourY(y, x1, x2, rects, context = {}) {
|
|
const height = Number(context.height || 0) || 0;
|
|
const minY = 8;
|
|
const maxY = height > 16 ? height - 8 : Math.max(y + 120, ...((rects || []).map(r => r.bottom + 18)), 240);
|
|
const blockers = (rects || []).filter(r => Math.max(Math.min(x1, x2), r.left) < Math.min(Math.max(x1, x2), r.right));
|
|
const candidates = [y - 18, y + 18, y - 32, y + 32, y - 52, y + 52];
|
|
for (const r of blockers) {
|
|
candidates.push(r.top - 12, r.bottom + 12, r.top - 22, r.bottom + 22);
|
|
}
|
|
const unique = Array.from(new Set(candidates
|
|
.map(v => clamp(Math.round(v * 10) / 10, minY, maxY))))
|
|
.filter(v => Number.isFinite(v) && lineageRouteHorizontalClear(v, x1, x2, rects));
|
|
const pool = unique.length ? unique : Array.from(new Set(candidates.map(v => clamp(Math.round(v * 10) / 10, minY, maxY)))).filter(Number.isFinite);
|
|
if (!pool.length) return clamp(y, minY, maxY);
|
|
return pool.sort((a, b) => Math.abs(a - y) - Math.abs(b - y))[0];
|
|
}
|
|
|
|
function lineageVerticalPathAvoidingNodes(x, y1, y2, bridges = [], rects = [], context = {}) {
|
|
if (lineageRouteVerticalClear(x, y1, y2, rects)) return lineageVerticalBridgePath(x, y1, y2, bridges);
|
|
return lineagePathFromPoints(lineageOrthogonalRoutePoints(x, y1, x, y2, rects, context));
|
|
}
|
|
|
|
function lineageHorizontalConnectorAvoidingNodes(x1, y, x2, rects = [], context = {}) {
|
|
if (Math.abs(x2 - x1) <= 0.5) return '';
|
|
if (lineageRouteHorizontalClear(y, x1, x2, rects)) return ` L ${x2.toFixed(1)} ${y.toFixed(1)}`;
|
|
const points = lineageOrthogonalRoutePoints(x1, y, x2, y, rects, context).slice(1);
|
|
return points.map(p => ` L ${p[0].toFixed(1)} ${p[1].toFixed(1)}`).join('');
|
|
}
|
|
|
|
function lineageHorizontalPathAvoidingNodes(x1, y, x2, rects = [], context = {}) {
|
|
return lineagePathFromPoints(lineageOrthogonalRoutePoints(x1, y, x2, y, rects, context));
|
|
}
|
|
|
|
function lineageLanePenalty(y, x1, x2, rects) {
|
|
let penalty = 0;
|
|
for (const r of rects || []) {
|
|
const overlap = Math.max(0, Math.min(Math.max(x1, x2), r.right) - Math.max(Math.min(x1, x2), r.left));
|
|
if (overlap <= 0) continue;
|
|
if (y > r.top && y < r.bottom) penalty += 100000 + overlap;
|
|
else penalty += Math.max(0, 26 - Math.min(Math.abs(y - r.top), Math.abs(y - r.bottom))) * 3;
|
|
}
|
|
return penalty;
|
|
}
|
|
|
|
function lineageChooseHorizontalDetourY(y, x1, x2, a, b, nodeW, nodeH, rects, preferredY = NaN, context = {}) {
|
|
const rowTop = Math.min(a.y, b.y);
|
|
const rowBottom = Math.max(a.y, b.y) + nodeH;
|
|
const minY = Math.max(8, Number(context.minRouteY ?? 10) || 10);
|
|
const maxY = Number.isFinite(Number(context.height)) ? Math.max(minY, Number(context.height) - 8) : Number.POSITIVE_INFINITY;
|
|
const candidates = [];
|
|
if (Number.isFinite(preferredY)) candidates.push(preferredY);
|
|
// Escaping above the first generation is allowed, but keep the route inside
|
|
// the visible SVG instead of letting it disappear above the canvas.
|
|
candidates.push(rowTop - 48, rowTop - 32, rowTop - 18, rowBottom + 18, rowBottom + 32, rowBottom + 48);
|
|
const unique = Array.from(new Set(candidates
|
|
.map(v => clamp(Math.round(v * 10) / 10, minY, maxY))))
|
|
.filter(Number.isFinite);
|
|
unique.sort((ya, yb) => {
|
|
const ca = lineageLanePenalty(ya, x1, x2, rects) + Math.abs(ya - y) * 0.08;
|
|
const cb = lineageLanePenalty(yb, x1, x2, rects) + Math.abs(yb - y) * 0.08;
|
|
return ca - cb;
|
|
});
|
|
return unique[0] ?? clamp(y, minY, maxY);
|
|
}
|
|
|
|
function lineageAutoSideOffsetForLane(laneY, rowTop, rowBottom, nodeH) {
|
|
if (!Number.isFinite(laneY)) return 0;
|
|
if (laneY < rowTop - 2) return -nodeH * 0.30;
|
|
if (laneY > rowBottom + 2) return nodeH * 0.30;
|
|
return 0;
|
|
}
|
|
|
|
function lineageCrossGenerationPartnerLane(a, b, nodeW, nodeH, context = {}) {
|
|
const ay = a.y + nodeH / 2;
|
|
const by = b.y + nodeH / 2;
|
|
const exclude = new Set([a.node?.id, b.node?.id].filter(Boolean));
|
|
const rects = lineageNodeRectsBetween(context.positions, nodeW, nodeH, ay, by, exclude, 12);
|
|
const ax = a.x + nodeW / 2;
|
|
const bx = b.x + nodeW / 2;
|
|
const directX = Math.abs(ax - bx) < 18 ? Math.max(ax, bx) + 30 : (ax + bx) / 2;
|
|
if (lineageVerticalLaneClear(directX, ay, by, rects)) return directX;
|
|
const minLeft = Math.min(a.x, b.x, ...rects.map(r => r.left));
|
|
const maxRight = Math.max(a.x + nodeW, b.x + nodeW, ...rects.map(r => r.right));
|
|
const width = Number(context.width || 0) || Infinity;
|
|
const candidates = [
|
|
maxRight + 18,
|
|
minLeft - 18,
|
|
Math.max(a.x + nodeW, b.x + nodeW) + 18,
|
|
Math.min(a.x, b.x) - 18,
|
|
].filter(x => Number.isFinite(x) && x >= 12 && x <= width - 12);
|
|
const clear = candidates.filter(x => lineageVerticalLaneClear(x, ay, by, rects));
|
|
const pool = clear.length ? clear : candidates;
|
|
if (pool.length) return pool.sort((x, y) => Math.abs(x - directX) - Math.abs(y - directX))[0];
|
|
return directX;
|
|
}
|
|
|
|
function lineageCrossGenerationPartnerPath(a, b, nodeW, nodeH, unionY, context = {}) {
|
|
const railX = lineageCrossGenerationPartnerLane(a, b, nodeW, nodeH, context);
|
|
const aMidY = a.y + nodeH / 2;
|
|
const bMidY = b.y + nodeH / 2;
|
|
const aSideX = railX >= a.x + nodeW / 2 ? a.x + nodeW : a.x;
|
|
const bSideX = railX >= b.x + nodeW / 2 ? b.x + nodeW : b.x;
|
|
const exclude = new Set([a.node?.id, b.node?.id].filter(Boolean));
|
|
const rects = lineageRouteNodeRects(context.positions, nodeW, nodeH, exclude, 10);
|
|
const points = lineageOrthogonalRoutePoints(aSideX, aMidY, bSideX, bMidY, rects, { ...context, preferredX: railX, routeMargin: 180 });
|
|
const clean = lineageCleanRoutePoints(points);
|
|
const segments = lineageSegmentsFromPoints(clean);
|
|
const verticals = segments.filter(seg => seg.kind === "v").sort((sa, sb) => Math.abs(sb.y2 - sb.y1) - Math.abs(sa.y2 - sa.y1));
|
|
const rail = verticals[0];
|
|
return { d: lineagePathFromPoints(clean), segments, unionX: rail ? rail.x1 : railX, unionY: Math.max(aMidY, bMidY) };
|
|
}
|
|
|
|
function lineageSameGenerationPartnerPath(a, b, nodeW, nodeH, unionY, attachOffsetA = 0, attachOffsetB = 0, context = {}) {
|
|
const left = a.x <= b.x ? a : b;
|
|
const right = left === a ? b : a;
|
|
let leftOffset = left === a ? attachOffsetA : attachOffsetB;
|
|
let rightOffset = right === a ? attachOffsetA : attachOffsetB;
|
|
const x1 = left.x + nodeW;
|
|
const x2 = right.x;
|
|
if (x2 <= x1) return { d: "", segments: [] };
|
|
const exclude = new Set([left.node?.id, right.node?.id].filter(Boolean));
|
|
const rects = lineageRouteNodeRects(context.positions, nodeW, nodeH, exclude, 10);
|
|
let midYLeft = left.y + nodeH / 2 + leftOffset;
|
|
let midYRight = right.y + nodeH / 2 + rightOffset;
|
|
const directY = (midYLeft + midYRight) / 2;
|
|
const directClear = lineageHorizontalLaneClear(directY, x1, x2, rects);
|
|
const direct = directClear && left.rowIndex === right.rowIndex && x2 - x1 <= 156 && Math.abs(midYLeft - midYRight) < 10
|
|
&& (!Number.isFinite(unionY) || unionY <= Math.max(midYLeft, midYRight) + 16);
|
|
if (direct) {
|
|
const points = Math.abs(midYLeft - midYRight) < 0.5
|
|
? [[x1, midYLeft], [x2, midYRight]]
|
|
: [[x1, midYLeft], [(x1 + x2) / 2, midYLeft], [(x1 + x2) / 2, midYRight], [x2, midYRight]];
|
|
return { d: lineagePathFromPoints(points), segments: lineageSegmentsFromPoints(lineageCleanRoutePoints(points)), unionX: (x1 + x2) / 2, unionY: (midYLeft + midYRight) / 2 };
|
|
}
|
|
const gap = x2 - x1;
|
|
const bend = Math.max(10, Math.min(24, gap * 0.20));
|
|
const y = directClear && Number.isFinite(unionY) && lineageHorizontalLaneClear(unionY, x1, x2, rects)
|
|
? clamp(unionY, 10, Number.isFinite(Number(context.height)) ? Number(context.height) - 8 : Number.POSITIVE_INFINITY)
|
|
: lineageChooseHorizontalDetourY(directY, x1, x2, left, right, nodeW, nodeH, rects, unionY, context);
|
|
// If the route escapes above/below the row, attach from the corresponding
|
|
// side portion of the node instead of forcing every edge out of side-center.
|
|
const autoOffset = lineageAutoSideOffsetForLane(y, Math.min(left.y, right.y), Math.max(left.y, right.y) + nodeH, nodeH);
|
|
if (Math.abs(autoOffset) > 0.1) {
|
|
const minOffset = -nodeH * 0.38;
|
|
const maxOffset = nodeH * 0.38;
|
|
leftOffset = clamp(leftOffset + autoOffset, minOffset, maxOffset);
|
|
rightOffset = clamp(rightOffset + autoOffset, minOffset, maxOffset);
|
|
midYLeft = left.y + nodeH / 2 + leftOffset;
|
|
midYRight = right.y + nodeH / 2 + rightOffset;
|
|
}
|
|
const routeContext = { ...context, preferredY: y, routeMargin: Math.max(140, Math.abs(x2 - x1) + nodeW) };
|
|
const points = lineageOrthogonalRoutePoints(x1, midYLeft, x2, midYRight, rects, routeContext);
|
|
const clean = lineageCleanRoutePoints(points);
|
|
const horizontals = lineageSegmentsFromPoints(clean).filter(seg => seg.kind === "h");
|
|
const mainH = horizontals.sort((sa, sb) => Math.abs(sb.x2 - sb.x1) - Math.abs(sa.x2 - sa.x1))[0];
|
|
return {
|
|
d: lineagePathFromPoints(clean),
|
|
segments: lineageSegmentsFromPoints(clean),
|
|
unionX: mainH ? (mainH.x1 + mainH.x2) / 2 : (x1 + x2) / 2,
|
|
unionY: mainH ? mainH.y1 : y
|
|
};
|
|
}
|
|
|
|
function lineagePartnerPathFromPositions(a, b, nodeW, nodeH, unionY, attachOffsetA = 0, attachOffsetB = 0, context = {}) {
|
|
if (a.rowIndex !== b.rowIndex) return lineageCrossGenerationPartnerPath(a, b, nodeW, nodeH, unionY, context);
|
|
return lineageSameGenerationPartnerPath(a, b, nodeW, nodeH, unionY, attachOffsetA, attachOffsetB, context);
|
|
}
|
|
function lineageChildAnchorOnMarriageLine(partner, fallbackX, fallbackY) {
|
|
const horizontals = (partner?.segments || [])
|
|
.filter(seg => seg.kind === "h" && Math.abs(seg.x2 - seg.x1) > 10)
|
|
.sort((a, b) => {
|
|
const ty = Number.isFinite(partner?.unionY) ? partner.unionY : fallbackY;
|
|
const dy = Math.abs(a.y1 - ty) - Math.abs(b.y1 - ty);
|
|
if (Math.abs(dy) > 0.01) return dy;
|
|
return Math.abs(b.x2 - b.x1) - Math.abs(a.x2 - a.x1);
|
|
});
|
|
const seg = horizontals[0] || null;
|
|
if (!seg) return { x: fallbackX, y: fallbackY };
|
|
const minX = Math.min(seg.x1, seg.x2) + 8;
|
|
const maxX = Math.max(seg.x1, seg.x2) - 8;
|
|
const midX = (seg.x1 + seg.x2) / 2;
|
|
const x = minX <= maxX ? clamp(Number.isFinite(fallbackX) ? fallbackX : midX, minX, maxX) : midX;
|
|
return { x, y: seg.y1 };
|
|
}
|
|
|
|
|
|
function lineageVerticalBridgePath(x, y1, y2, bridges = [], radius = 8.5) {
|
|
if (!Number.isFinite(x) || !Number.isFinite(y1) || !Number.isFinite(y2)) return '';
|
|
const down = y2 >= y1;
|
|
const sign = down ? 1 : -1;
|
|
const sorted = bridges.slice().sort((a, b) => down ? a - b : b - a).filter(y => Math.abs(y - y1) > radius + 1 && Math.abs(y - y2) > radius + 1);
|
|
let d = `M ${x.toFixed(1)} ${y1.toFixed(1)}`;
|
|
let cursor = y1;
|
|
for (const by of sorted) {
|
|
const before = by - sign * radius;
|
|
const after = by + sign * radius;
|
|
d += ` L ${x.toFixed(1)} ${before.toFixed(1)}`;
|
|
d += ` Q ${(x + radius * 1.55).toFixed(1)} ${by.toFixed(1)} ${x.toFixed(1)} ${after.toFixed(1)}`;
|
|
cursor = after;
|
|
}
|
|
if (Math.abs(cursor - y2) > 0.01) d += ` L ${x.toFixed(1)} ${y2.toFixed(1)}`;
|
|
return d;
|
|
}
|
|
|
|
function lineageIntersectionYsForVertical(x, y1, y2, horizontalSegments) {
|
|
const top = Math.min(y1, y2);
|
|
const bottom = Math.max(y1, y2);
|
|
const ys = [];
|
|
for (const seg of horizontalSegments || []) {
|
|
if (seg.kind !== 'h') continue;
|
|
const minX = Math.min(seg.x1, seg.x2);
|
|
const maxX = Math.max(seg.x1, seg.x2);
|
|
const y = seg.y1;
|
|
if (x > minX + 3 && x < maxX - 3 && y > top + 3 && y < bottom - 3) ys.push(y);
|
|
}
|
|
return ys;
|
|
}
|
|
|
|
function lineageBuildChildPathGroup(group, nodeW, nodeH, bridgeHorizontals, context = {}) {
|
|
const children = group.children;
|
|
if (!children.length) return { d: '' };
|
|
const joinX = group.joinX;
|
|
const fromY = group.fromY;
|
|
const laneY = group.busY;
|
|
const routeRects = group.routeRects || [];
|
|
const childPoints = children
|
|
.map(c => ({ x: c.x + nodeW / 2, y: c.y }))
|
|
.sort((a, b) => a.x - b.x || a.y - b.y);
|
|
if (childPoints.length === 1 && Math.abs(childPoints[0].x - joinX) <= 0.5) {
|
|
const p = childPoints[0];
|
|
const bridges = lineageIntersectionYsForVertical(p.x, fromY, p.y, bridgeHorizontals);
|
|
return { d: lineageVerticalPathAvoidingNodes(p.x, fromY, p.y, bridges, routeRects, context) };
|
|
}
|
|
if (childPoints.length === 1) {
|
|
const p = childPoints[0];
|
|
const parentBridges = lineageIntersectionYsForVertical(joinX, fromY, laneY, bridgeHorizontals);
|
|
const childBridges = lineageIntersectionYsForVertical(p.x, laneY, p.y, bridgeHorizontals);
|
|
const parentLane = lineageVerticalPathAvoidingNodes(joinX, fromY, laneY, parentBridges, routeRects, context);
|
|
const horizontal = lineageHorizontalConnectorAvoidingNodes(joinX, laneY, p.x, routeRects, context);
|
|
const childLane = lineageVerticalPathAvoidingNodes(p.x, laneY, p.y, childBridges, routeRects, context).replace(/^M\s+[-\d.]+\s+[-\d.]+/, "");
|
|
return { d: `${parentLane}${horizontal}${childLane}` };
|
|
}
|
|
const minX = Math.min(joinX, ...childPoints.map(p => p.x));
|
|
const maxX = Math.max(joinX, ...childPoints.map(p => p.x));
|
|
let d = lineageVerticalPathAvoidingNodes(joinX, fromY, laneY, lineageIntersectionYsForVertical(joinX, fromY, laneY, bridgeHorizontals), routeRects, context);
|
|
d += ` ${lineageHorizontalPathAvoidingNodes(minX, laneY, maxX, routeRects, context)}`;
|
|
for (const p of childPoints) {
|
|
const bridges = lineageIntersectionYsForVertical(p.x, laneY, p.y, bridgeHorizontals);
|
|
const branch = lineageVerticalPathAvoidingNodes(p.x, laneY, p.y, bridges, routeRects, context);
|
|
d += ` ${branch}`;
|
|
}
|
|
return { d };
|
|
}
|
|
|
|
function lineageChildBusSpan(group, nodeW) {
|
|
const childCenters = (group.children || []).map(c => c.x + nodeW / 2);
|
|
if (!childCenters.length) return null;
|
|
return {
|
|
left: Math.min(group.joinX, ...childCenters),
|
|
right: Math.max(group.joinX, ...childCenters),
|
|
};
|
|
}
|
|
|
|
function lineageSpansOverlap(a, b, pad = 12) {
|
|
if (!a || !b) return false;
|
|
return Math.max(a.left, b.left) <= Math.min(a.right, b.right) + pad;
|
|
}
|
|
|
|
function lineageSeparateChildBusLanes(groupsInGap, nodeW) {
|
|
const lanes = [];
|
|
const ordered = (groupsInGap || [])
|
|
.filter(group => group && Number.isFinite(group.busY))
|
|
.map(group => ({ group, span: lineageChildBusSpan(group, nodeW), baseY: group.busY }))
|
|
.filter(entry => entry.span)
|
|
.sort((a, b) => a.baseY - b.baseY || a.span.left - b.span.left || a.span.right - b.span.right);
|
|
|
|
for (const entry of ordered) {
|
|
let laneIndex = 0;
|
|
while (lanes[laneIndex]?.some(prev => Math.abs(prev.group.busY - entry.baseY) < 12 && lineageSpansOverlap(prev.span, entry.span))) {
|
|
laneIndex += 1;
|
|
}
|
|
if (!lanes[laneIndex]) lanes[laneIndex] = [];
|
|
const fromY = Number(entry.group.fromY);
|
|
const childTop = Number(entry.group.childTop);
|
|
const minY = Number.isFinite(fromY) ? fromY + 26 : -Infinity;
|
|
const maxY = Number.isFinite(childTop) ? childTop - 18 : Infinity;
|
|
const offset = laneIndex * 9;
|
|
entry.group.busY = clamp(entry.baseY - offset, minY, maxY);
|
|
lanes[laneIndex].push(entry);
|
|
}
|
|
}
|
|
|
|
function lineageComponentSignature(component, family) {
|
|
family = lineageEdgeFamily(family);
|
|
const idSet = new Set(component.map(x => x?.id).filter(Boolean));
|
|
return component
|
|
.filter(Boolean)
|
|
.map(n => {
|
|
const parents = lineageMutualParentIds(n, family, idSet).join(",");
|
|
const children = lineageMutualChildIds(n, family, idSet).join(",");
|
|
return [
|
|
n.id,
|
|
n.name || "",
|
|
n.type || "",
|
|
n.generation || 1,
|
|
n.birthTime || 0,
|
|
Number(n.scale || 0).toFixed(3),
|
|
Number(n.adultScale || 0).toFixed(3),
|
|
Number(n.growth || 0).toFixed(2),
|
|
n.hasPaired ? 1 : 0,
|
|
n.alive === false ? 0 : 1,
|
|
n.deathReason || "",
|
|
parents,
|
|
children,
|
|
].join(":");
|
|
})
|
|
.sort()
|
|
.join("|");
|
|
}
|
|
|
|
function lineageComponentIdentity(component) {
|
|
return Array.from(new Set((component || []).map(n => n?.id).filter(Boolean))).sort().join(",");
|
|
}
|
|
|
|
function lineageFamilyCacheKey(component, family, signature = "") {
|
|
const uniqueComponent = Array.from(new Map((component || []).filter(Boolean).map(n => [n.id, n])).values()).sort(lineageNodeSort);
|
|
return `${lineageComponentIdentity(uniqueComponent)}:${signature || lineageComponentSignature(uniqueComponent, family)}`;
|
|
}
|
|
|
|
function lineageHydrateFamilyHtml(html, index) {
|
|
return html
|
|
.split("{{LINEAGE_INDEX}}").join(String(index + 1))
|
|
.split("{{LINEAGE_MASK_ID}}").join(`lineage-node-mask-${index}`);
|
|
}
|
|
|
|
function lineageCaptureArchiveScroll() {
|
|
const root = ui.archiveContent;
|
|
if (!root) return null;
|
|
const familyScroll = {};
|
|
for (const el of root.querySelectorAll(".lineage-family-tree[data-lineage-key]")) {
|
|
const key = el.getAttribute("data-lineage-key");
|
|
if (key) familyScroll[key] = el.scrollLeft || 0;
|
|
}
|
|
return { top: root.scrollTop || 0, left: root.scrollLeft || 0, familyScroll };
|
|
}
|
|
|
|
function lineageRestoreArchiveScroll(state) {
|
|
const root = ui.archiveContent;
|
|
if (!root || !state) return;
|
|
const maxTop = Math.max(0, root.scrollHeight - root.clientHeight);
|
|
const maxLeft = Math.max(0, root.scrollWidth - root.clientWidth);
|
|
root.scrollTop = Math.min(state.top || 0, maxTop);
|
|
root.scrollLeft = Math.min(state.left || 0, maxLeft);
|
|
for (const el of root.querySelectorAll(".lineage-family-tree[data-lineage-key]")) {
|
|
const key = el.getAttribute("data-lineage-key");
|
|
if (!key || !Object.prototype.hasOwnProperty.call(state.familyScroll || {}, key)) continue;
|
|
el.scrollLeft = Math.min(state.familyScroll[key] || 0, Math.max(0, el.scrollWidth - el.clientWidth));
|
|
}
|
|
}
|
|
|
|
function lineageExpectedChildEdgeCount(component, family) {
|
|
family = lineageEdgeFamily(family);
|
|
const idSet = new Set(component.map(x => x?.id).filter(Boolean));
|
|
let count = 0;
|
|
for (const n of component || []) count += lineageParentIds(n, idSet, family).length;
|
|
return count;
|
|
}
|
|
function lineageArchiveNearViewport() {
|
|
if (!ui.archiveContent?.getBoundingClientRect) return true;
|
|
const rect = ui.archiveContent.getBoundingClientRect();
|
|
const h = window.innerHeight || document.documentElement?.clientHeight || 0;
|
|
return rect.top < h + 260 && rect.bottom > -260;
|
|
}
|
|
|
|
function lineageSetArchiveStaleStatus(show) {
|
|
if (!ui.archiveContent) return;
|
|
const existing = ui.archiveContent.querySelector(".lineage-stale-status");
|
|
if (!show) {
|
|
existing?.remove();
|
|
return;
|
|
}
|
|
if (existing) return;
|
|
ui.archiveContent.insertAdjacentHTML("afterbegin", `<div class="lineage-stale-status">\u5bb6\u7cfb\u56f3\u306e\u66f4\u65b0\u306fOFF\u3067\u3059\u3002\u300c\u66f4\u65b0\u300d\u3092ON\u306b\u3059\u308b\u3068\u53cd\u6620\u3055\u308c\u307e\u3059\u3002</div>`);
|
|
}
|
|
|
|
function lineageAssignPartnerAttachOffsets(linkGroups) {
|
|
const buckets = new Map();
|
|
const pushBucket = (nodeId, side, group) => {
|
|
const key = `${nodeId}:${side}`;
|
|
if (!buckets.has(key)) buckets.set(key, []);
|
|
buckets.get(key).push(group);
|
|
};
|
|
for (const group of linkGroups) {
|
|
if ((group.parents || []).length < 2) continue;
|
|
const left = group.parents[0];
|
|
const right = group.parents[group.parents.length - 1];
|
|
if (!group.attachOffsets) group.attachOffsets = new Map();
|
|
pushBucket(left.node.id, 'right', group);
|
|
pushBucket(right.node.id, 'left', group);
|
|
}
|
|
for (const [key, groups] of buckets.entries()) {
|
|
groups.sort((a, b) => a.joinX - b.joinX || a.childTop - b.childTop);
|
|
const n = groups.length;
|
|
const step = 18;
|
|
groups.forEach((group, i) => {
|
|
const offset = n <= 1 ? 0 : (i - (n - 1) / 2) * step;
|
|
const [nodeId] = key.split(':');
|
|
group.attachOffsets.set(nodeId, offset);
|
|
});
|
|
}
|
|
}
|
|
|
|
function lineageBuildLinks(nodes, idSet, layout) {
|
|
const { positions, nodeW, nodeH } = layout;
|
|
const groups = new Map();
|
|
for (const child of nodes) {
|
|
const parents = lineageParentIds(child, idSet).filter(id => positions.has(id));
|
|
if (parents.length < 1 || !positions.has(child.id)) continue;
|
|
const key = parents.slice().sort().join('+');
|
|
if (!groups.has(key)) groups.set(key, { parentIds: parents.slice().sort(), childIds: [] });
|
|
groups.get(key).childIds.push(child.id);
|
|
}
|
|
|
|
const linkGroups = [];
|
|
for (const group of groups.values()) {
|
|
const parents = group.parentIds.map(id => positions.get(id)).filter(Boolean).sort((a, b) => a.x - b.x);
|
|
const children = group.childIds.map(id => positions.get(id)).filter(Boolean).sort((a, b) => a.x - b.x);
|
|
if (!parents.length || !children.length) continue;
|
|
const parentBottom = Math.max(...parents.map(p => p.y + nodeH));
|
|
const childTop = Math.min(...children.map(c => c.y));
|
|
const joinX = parents.reduce((sum, p) => sum + p.x + nodeW / 2, 0) / parents.length;
|
|
const directCouple = parents.length >= 2 && parents[0].rowIndex === parents[1].rowIndex && (parents[1].x - (parents[0].x + nodeW) <= 168);
|
|
linkGroups.push({ parents, children, parentBottom, childTop, joinX, directCouple, attachOffsets: new Map() });
|
|
}
|
|
lineageAssignPartnerAttachOffsets(linkGroups);
|
|
const childLinkEdges = linkGroups.reduce((sum, group) => sum + group.children.length * group.parents.length, 0);
|
|
|
|
const byGap = new Map();
|
|
for (const group of linkGroups) {
|
|
const key = `${group.parentBottom.toFixed(1)}:${group.childTop.toFixed(1)}`;
|
|
if (!byGap.has(key)) byGap.set(key, []);
|
|
byGap.get(key).push(group);
|
|
}
|
|
|
|
const partnerLinks = [];
|
|
const childLinks = [];
|
|
const horizontalSegments = [];
|
|
|
|
for (const groupsInGap of byGap.values()) {
|
|
groupsInGap.sort((a, b) => a.joinX - b.joinX || a.children.length - b.children.length);
|
|
const top = Math.min(...groupsInGap.map(g => g.parentBottom)) + 58;
|
|
const bottom = Math.max(...groupsInGap.map(g => g.childTop)) - 54;
|
|
const span = Math.max(16, bottom - top);
|
|
groupsInGap.forEach((group, i) => {
|
|
const laneY = top + span * ((i + 1) / (groupsInGap.length + 1));
|
|
if (group.parents.length >= 2) {
|
|
const left = group.parents[0];
|
|
const right = group.parents[group.parents.length - 1];
|
|
// Marriage line stays at the parent-node center. The child trunk drops
|
|
// to a visible point below the parents before branching, so the fork is
|
|
// never hidden behind a node.
|
|
const attachA = group.attachOffsets?.get?.(left.node?.id) || 0;
|
|
const attachB = group.attachOffsets?.get?.(right.node?.id) || 0;
|
|
const partnerY = ((left.y + nodeH / 2) + (right.y + nodeH / 2)) / 2;
|
|
const partner = lineagePartnerPathFromPositions(left, right, nodeW, nodeH, partnerY, attachA, attachB, layout);
|
|
const unionY = Number.isFinite(partner.unionY) ? partner.unionY : partnerY;
|
|
const anchor = lineageChildAnchorOnMarriageLine(partner, Number.isFinite(partner.unionX) ? partner.unionX : group.joinX, unionY);
|
|
group.joinX = anchor.x;
|
|
group.fromY = anchor.y;
|
|
group.busY = group.children.length === 1 ? Math.min(group.childTop - 22, anchor.y + 38) : Math.min(group.childTop - 28, Math.max(anchor.y + 34, laneY + 24 + i * 5));
|
|
if (partner.d) {
|
|
partnerLinks.push(partner.d);
|
|
horizontalSegments.push(...partner.segments.filter(seg => seg.kind === 'h'));
|
|
}
|
|
} else {
|
|
group.fromY = group.parentBottom;
|
|
group.busY = group.children.length === 1 ? Math.min(group.childTop - 22, group.fromY + 38) : Math.min(group.childTop - 28, Math.max(group.fromY + 34, laneY + 24 + i * 5));
|
|
}
|
|
});
|
|
lineageSeparateChildBusLanes(groupsInGap, nodeW);
|
|
}
|
|
|
|
for (const groupsInGap of byGap.values()) {
|
|
groupsInGap.sort((a, b) => a.joinX - b.joinX || a.children.length - b.children.length);
|
|
for (const group of groupsInGap) {
|
|
const childCenters = group.children.map(c => c.x + nodeW / 2).sort((a, b) => a - b);
|
|
if (group.children.length > 1 || (childCenters.length === 1 && Math.abs(childCenters[0] - group.joinX) > 0.5)) {
|
|
horizontalSegments.push({ kind: 'h', x1: Math.min(group.joinX, ...childCenters), y1: group.busY, x2: Math.max(group.joinX, ...childCenters), y2: group.busY });
|
|
}
|
|
const excludeIds = new Set([
|
|
...group.parents.map(p => p?.node?.id).filter(Boolean),
|
|
...group.children.map(c => c?.node?.id).filter(Boolean),
|
|
]);
|
|
group.routeRects = lineageRouteNodeRects(positions, nodeW, nodeH, excludeIds, 12);
|
|
const child = lineageBuildChildPathGroup(group, nodeW, nodeH, horizontalSegments, layout);
|
|
if (child.d) childLinks.push(child.d);
|
|
}
|
|
}
|
|
|
|
return { partnerLinks, childLinks, childLinkGroups: linkGroups.length, childLinkEdges };
|
|
}
|