Skip to content

Virtual whiteboard for sketching hand-drawn like diagrams

21.2 KB
Raw Blame
import { invariant, toBrandedType, type Bounds } from "@excalidraw/common";

import { clamp, pointFrom, PRECISION } from "@excalidraw/math";

import type {
  AppState,
  PendingExcalidrawElements,
} from "@excalidraw/excalidraw/types";

import { bindBindingElement } from "./binding";
import { updateElbowArrowPoints } from "./elbowArrow";
import { LinearElementEditor } from "./linearElementEditor";
import { mutateElement } from "./mutateElement";
import {
  newArrowElement,
  newElement,
  newStickyNoteElement,
} from "./newElement";
import { aabbForElement } from "./bounds";
import { elementsAreInFrameBounds, elementOverlapsWithFrame } from "./frame";
import {
  isBindableElement,
  isArrowElement,
  isFrameElement,
  isFlowchartNodeElement,
} from "./typeChecks";
import {
  type NonDeleted,
  type ElementsMap,
  type ExcalidrawBindableElement,
  type ExcalidrawElement,
  type ExcalidrawFlowchartNodeElement,
  type NonDeletedExcalidrawElement,
  type NonDeletedSceneElementsMap,
  type Ordered,
  type OrderedExcalidrawElement,
} from "./types";

import type { Scene } from "./Scene";

export type LinkDirection = "up" | "right" | "down" | "left";

const VERTICAL_OFFSET = 100;
const HORIZONTAL_OFFSET = 100;

type Interval = { start: number; end: number };

const mergeIntervals = (intervals: Interval[]): Interval[] => {
  const sorted = [...intervals].sort((a, b) => a.start - b.start);
  const merged: Interval[] = [];

  for (const interval of sorted) {
    const last = merged[merged.length - 1];
    if (last && interval.start <= last.end) {
      last.end = Math.max(last.end, interval.end);
    } else {
      merged.push({ ...interval });
    }
  }

  return merged;
};

const intervalIsFree = (start: number, size: number, occupied: Interval[]) =>
  occupied.every((o) => start + size <= o.start || start >= o.end);

// Nearest `start` for a segment of `size` avoiding every occupied interval,
// searching both sides of `ideal`; a tie resolves toward the positive side.
const findNearestFreeSlot = (
  ideal: number,
  size: number,
  occupied: Interval[],
): number => {
  if (intervalIsFree(ideal, size, occupied)) {
    return ideal;
  }

  const gapStarts = [-Infinity, ...occupied.map((o) => o.end)];
  const gapEnds = [...occupied.map((o) => o.start), Infinity];

  let best = ideal;
  let bestDistance = Infinity;
  for (let i = 0; i < gapStarts.length; i++) {
    if (gapEnds[i] - gapStarts[i] < size) {
      continue;
    }
    const start = clamp(ideal, gapStarts[i], gapEnds[i] - size);
    const distance = Math.abs(start - ideal);
    if (distance <= bestDistance) {
      best = start;
      bestDistance = distance;
    }
  }

  return best;
};

// Walk the arrow bindings to collect every node that belongs to the same
// flowchart as `node` — the whole connected component acts as the obstacle
// set during placement (#8518).
const getConnectedFlowchartNodes = (
  node: ExcalidrawBindableElement,
  elementsMap: ElementsMap,
): ExcalidrawBindableElement[] => {
  // one pass over the scene, so the walk below costs the size of the chart,
  // not chart nodes × all arrows in the scene
  const neighbors = new Map<string, string[]>();
  const addNeighbor = (from: string, to: string) => {
    const list = neighbors.get(from);
    if (list) {
      list.push(to);
    } else {
      neighbors.set(from, [to]);
    }
  };
  for (const element of elementsMap.values()) {
    if (isArrowElement(element) && element.startBinding && element.endBinding) {
      addNeighbor(element.startBinding.elementId, element.endBinding.elementId);
      addNeighbor(element.endBinding.elementId, element.startBinding.elementId);
    }
  }

  const visited = new Set<string>([node.id]);
  const queue: string[] = [node.id];
  const connected: ExcalidrawBindableElement[] = [];

  for (let i = 0; i < queue.length; i++) {
    for (const neighborId of neighbors.get(queue[i]) ?? []) {
      if (visited.has(neighborId)) {
        continue;
      }

      visited.add(neighborId);
      const neighbor = elementsMap.get(neighborId);
      if (neighbor && isBindableElement(neighbor)) {
        connected.push(neighbor);
        queue.push(neighborId);
      }
    }
  }

  return connected;
};

// Place a cluster of `count` equally-sized nodes next to `parent`:
// - the primary axis (the creation direction) is fixed at exactly one gap
//   away from the parent, forming a search band the cluster will occupy
// - along the cross axis the cluster slides into the free slot nearest the
//   parent-centered ideal, treating band obstacles as immovable
// - `stickyCrossStart` anchors an already-visible pending cluster that an
//   obstacle pushed off-center: growing it extends it at either end so the
//   existing pending nodes keep their positions, unless the grown cluster
//   centers on the parent again or no longer fits there
const placeCluster = (
  parent: ExcalidrawFlowchartNodeElement,
  direction: LinkDirection,
  count: number,
  obstacles: readonly Bounds[],
  stickyCrossStart: number | null,
): { positions: { x: number; y: number }[]; crossStart: number } => {
  const horizontal = direction === "left" || direction === "right";
  // INSIGHT: new nodes copy the parent's dimensions
  const nodePrimarySize = horizontal ? parent.width : parent.height;
  const nodeCrossSize = horizontal ? parent.height : parent.width;
  const primaryGap = horizontal ? HORIZONTAL_OFFSET : VERTICAL_OFFSET;
  const crossGap = horizontal ? VERTICAL_OFFSET : HORIZONTAL_OFFSET;

  const parentPrimaryStart = horizontal ? parent.x : parent.y;
  const parentCrossCenter = horizontal
    ? parent.y + parent.height / 2
    : parent.x + parent.width / 2;

  const primaryStart =
    direction === "right" || direction === "down"
      ? parentPrimaryStart + nodePrimarySize + primaryGap
      : parentPrimaryStart - primaryGap - nodePrimarySize;

  // the band widened by one gap on both sides, so nodes the cluster would end
  // up closer than a gap to count as obstacles too; the near side stops
  // exactly at the parent's facing edge, keeping the parent's row out
  const [zoneStart, zoneEnd] =
    direction === "right" || direction === "down"
      ? [
          parentPrimaryStart + nodePrimarySize,
          primaryStart + nodePrimarySize + primaryGap,
        ]
      : [primaryStart - primaryGap, parentPrimaryStart];

  // cross-axis intervals of the obstacles in that zone, inflated so the
  // cluster keeps at least one gap of clearance
  const occupied = mergeIntervals(
    obstacles
      .filter((bounds) => {
        const start = horizontal ? bounds[0] : bounds[1];
        const end = horizontal ? bounds[2] : bounds[3];
        // Ignore rounding noise so nodes a full gap away stay out of the zone.
        return start < zoneEnd - PRECISION && end > zoneStart + PRECISION;
      })
      .map((bounds) => ({
        start: (horizontal ? bounds[1] : bounds[0]) - crossGap,
        end: (horizontal ? bounds[3] : bounds[2]) + crossGap,
      })),
  );

  const step = nodeCrossSize + crossGap;
  const clusterCrossSize = count * nodeCrossSize + (count - 1) * crossGap;
  const centeredStart = parentCrossCenter - clusterCrossSize / 2;

  // the centered slot sorts first (zero distance), so the cluster re-centers
  // whenever it fits there
  const anchoredStart =
    stickyCrossStart === null
      ? null
      : [centeredStart, stickyCrossStart, stickyCrossStart - step]
          .filter((start) => intervalIsFree(start, clusterCrossSize, occupied))
          .sort(
            (a, b) =>
              Math.abs(a + clusterCrossSize / 2 - parentCrossCenter) -
              Math.abs(b + clusterCrossSize / 2 - parentCrossCenter),
          )[0] ?? null;

  const crossStart =
    anchoredStart ??
    findNearestFreeSlot(centeredStart, clusterCrossSize, occupied);

  const positions = Array.from({ length: count }, (_, index) => {
    const cross = crossStart + index * step;
    return horizontal
      ? { x: primaryStart, y: cross }
      : { x: cross, y: primaryStart };
  });

  return { positions, crossStart };
};

const cloneFlowchartNode = (
  template: ExcalidrawFlowchartNodeElement,
  x: number,
  y: number,
) => {
  const commonNodeProps = {
    x,
    y,
    width: template.width,
    height: template.height,
    roundness: template.roundness,
    roughness: template.roughness,
    backgroundColor: template.backgroundColor,
    strokeColor: template.strokeColor,
    strokeWidth: template.strokeWidth,
    opacity: template.opacity,
    fillStyle: template.fillStyle,
    strokeStyle: template.strokeStyle,
  };

  const node =
    template.type === "stickynote"
      ? newStickyNoteElement({
          type: "stickynote",
          ...commonNodeProps,
          baseHeight: template.baseHeight,
        })
      : newElement({
          type: template.type,
          ...commonNodeProps,
        });

  invariant(
    isFlowchartNodeElement(node),
    "not an ExcalidrawFlowchartNodeElement",
  );

  return node;
};

export const addNewNodes = (
  startNode: NonDeleted<ExcalidrawFlowchartNodeElement>,
  appState: AppState,
  direction: LinkDirection,
  scene: Scene,
  numberOfNodes: number,
  stickyCrossStart: number | null = null,
) => {
  const elementsMap = scene.getNonDeletedElementsMap();
  const obstacles = getConnectedFlowchartNodes(startNode, elementsMap).map(
    (node) => aabbForElement(node, elementsMap),
  );

  const { positions, crossStart } = placeCluster(
    startNode,
    direction,
    numberOfNodes,
    obstacles,
    stickyCrossStart,
  );

  const nodes: NonDeletedExcalidrawElement[] = [];
  for (const position of positions) {
    const nextNode = cloneFlowchartNode(startNode, position.x, position.y);
    const bindingArrow = createBindingArrow(
      startNode,
      nextNode,
      direction,
      appState,
      scene,
    );

    nodes.push(nextNode, bindingArrow);
  }

  return { nodes, crossStart };
};

const createBindingArrow = (
  startBindingElement: NonDeleted<ExcalidrawFlowchartNodeElement>,
  endBindingElement: NonDeleted<ExcalidrawFlowchartNodeElement>,
  direction: LinkDirection,
  appState: AppState,
  scene: Scene,
) => {
  let startX: number;
  let startY: number;

  const PADDING = 6;

  switch (direction) {
    case "up": {
      startX = startBindingElement.x + startBindingElement.width / 2;
      startY = startBindingElement.y - PADDING;
      break;
    }
    case "down": {
      startX = startBindingElement.x + startBindingElement.width / 2;
      startY = startBindingElement.y + startBindingElement.height + PADDING;
      break;
    }
    case "right": {
      startX = startBindingElement.x + startBindingElement.width + PADDING;
      startY = startBindingElement.y + startBindingElement.height / 2;
      break;
    }
    case "left": {
      startX = startBindingElement.x - PADDING;
      startY = startBindingElement.y + startBindingElement.height / 2;
      break;
    }
  }

  let endX: number;
  let endY: number;

  switch (direction) {
    case "up": {
      endX = endBindingElement.x + endBindingElement.width / 2 - startX;
      endY = endBindingElement.y + endBindingElement.height - startY + PADDING;
      break;
    }
    case "down": {
      endX = endBindingElement.x + endBindingElement.width / 2 - startX;
      endY = endBindingElement.y - startY - PADDING;
      break;
    }
    case "right": {
      endX = endBindingElement.x - startX - PADDING;
      endY = endBindingElement.y - startY + endBindingElement.height / 2;
      break;
    }
    case "left": {
      endX = endBindingElement.x + endBindingElement.width - startX + PADDING;
      endY = endBindingElement.y - startY + endBindingElement.height / 2;
      break;
    }
  }

  const bindingArrow = newArrowElement({
    type: "arrow",
    x: startX,
    y: startY,
    startArrowhead: null,
    endArrowhead: appState.currentItemEndArrowhead,
    strokeColor: startBindingElement.strokeColor,
    strokeStyle: startBindingElement.strokeStyle,
    strokeWidth: startBindingElement.strokeWidth,
    opacity: startBindingElement.opacity,
    roughness: startBindingElement.roughness,
    points: [pointFrom(0, 0), pointFrom(endX, endY)],
    elbowed: true,
  });

  const elementsMap = scene.getNonDeletedElementsMap();

  bindBindingElement(
    bindingArrow,
    startBindingElement,
    "orbit",
    "start",
    scene,
    appState.zoom,
  );
  bindBindingElement(
    bindingArrow,
    endBindingElement,
    "orbit",
    "end",
    scene,
    appState.zoom,
  );

  const changedElements = new Map<string, OrderedExcalidrawElement>();
  changedElements.set(
    startBindingElement.id,
    startBindingElement as OrderedExcalidrawElement,
  );
  changedElements.set(
    endBindingElement.id,
    endBindingElement as OrderedExcalidrawElement,
  );
  changedElements.set(
    bindingArrow.id,
    bindingArrow as OrderedExcalidrawElement,
  );

  LinearElementEditor.movePoints(
    bindingArrow,
    scene,
    new Map([
      [
        1,
        {
          point: bindingArrow.points[1],
        },
      ],
    ]),
  );

  const update = updateElbowArrowPoints(
    bindingArrow,
    toBrandedType<NonDeletedSceneElementsMap>(
      new Map([
        ...elementsMap.entries(),
        [startBindingElement.id, startBindingElement],
        [endBindingElement.id, endBindingElement],
        [bindingArrow.id, bindingArrow],
      ] as [string, Ordered<NonDeletedExcalidrawElement>][]),
    ),
    { points: bindingArrow.points },
  );

  return {
    ...bindingArrow,
    ...update,
    isDeleted: bindingArrow.isDeleted,
  };
};

// Alt+arrow navigation moves to whichever node of the flowchart *looks* next
// in the pressed direction, picking the nearest node of the first non-empty
// tier:
// 1. nodes in line with the current one (sharing its row for left/right, its
//    column for up/down)
// 2. nodes linked to the current one whose center lies past its edge in the
//    pressed direction, at any angle
// 3. nodes whose center lies within the 45° cone of the pressed direction
//    (an X through the current node's center)
// 4. any other node whose center lies past the current one's edge, so a
//    direction only does nothing when there's nothing that way at all
// Near-ties (within 10%) go to a node the current one links to, then to one
// linking to it, then to the one more level with the current one's center,
// then reading order (the upper one for left/right, the left one for
// up/down).
const NAVIGATION_TIE_TOLERANCE = 0.1;

export class FlowChartNavigator {
  isExploring: boolean = false;

  clear() {
    this.isExploring = false;
  }

  exploreByDirection(
    element: ExcalidrawElement,
    elementsMap: ElementsMap,
    direction: LinkDirection,
  ): ExcalidrawElement["id"] | null {
    if (!isBindableElement(element)) {
      return null;
    }

    const next = FlowChartNavigator.findNodeInDirection(
      element,
      elementsMap,
      direction,
    );

    if (!next) {
      return null;
    }

    this.isExploring = true;

    return next.id;
  }

  private static findNodeInDirection(
    node: ExcalidrawBindableElement,
    elementsMap: ElementsMap,
    direction: LinkDirection,
  ) {
    const horizontal = direction === "left" || direction === "right";
    const sign = direction === "right" || direction === "down" ? 1 : -1;
    const [minX, minY, maxX, maxY] = aabbForElement(node, elementsMap);
    const [nodeMainStart, nodeMainEnd, nodeCrossStart, nodeCrossEnd] =
      horizontal ? [minX, maxX, minY, maxY] : [minY, maxY, minX, maxX];
    const nodeMainCenter = (nodeMainStart + nodeMainEnd) / 2;
    const nodeCrossCenter = (nodeCrossStart + nodeCrossEnd) / 2;
    const nodeEdge = sign > 0 ? nodeMainEnd : nodeMainStart;

    const successors = new Set<string>();
    const predecessors = new Set<string>();
    for (const element of elementsMap.values()) {
      if (
        isArrowElement(element) &&
        element.startBinding &&
        element.endBinding
      ) {
        if (element.startBinding.elementId === node.id) {
          successors.add(element.endBinding.elementId);
        }
        if (element.endBinding.elementId === node.id) {
          predecessors.add(element.startBinding.elementId);
        }
      }
    }
    const linkRank = (id: string) =>
      successors.has(id) ? 0 : predecessors.has(id) ? 1 : 2;

    const candidates = getConnectedFlowchartNodes(node, elementsMap).flatMap(
      (candidate) => {
        const bounds = aabbForElement(candidate, elementsMap);
        const [mainStart, mainEnd, crossStart, crossEnd] = horizontal
          ? [bounds[0], bounds[2], bounds[1], bounds[3]]
          : [bounds[1], bounds[3], bounds[0], bounds[2]];
        const mainCenter = (mainStart + mainEnd) / 2;
        const crossCenter = (crossStart + crossEnd) / 2;

        if ((mainCenter - nodeMainCenter) * sign <= 0) {
          return [];
        }

        // positive when the boxes are apart along that axis, negative when
        // they overlap
        const mainGap = Math.max(
          mainStart - nodeMainEnd,
          nodeMainStart - mainEnd,
        );
        const crossGap = Math.max(
          crossStart - nodeCrossEnd,
          nodeCrossStart - crossEnd,
        );
        const inCone =
          Math.abs(mainCenter - nodeMainCenter) >=
          Math.abs(crossCenter - nodeCrossCenter);
        // either center falls within the other node's span, so the two mostly
        // share a row (column) — a sliver of overlap between neighboring rows
        // doesn't count
        const inLine =
          (nodeCrossStart < crossCenter && crossCenter < nodeCrossEnd) ||
          (crossStart < nodeCrossCenter && nodeCrossCenter < crossEnd);
        const pastEdge = (mainCenter - nodeEdge) * sign > 0;

        const tier = inLine
          ? 0
          : pastEdge && linkRank(candidate.id) < 2
          ? 1
          : inCone
          ? 2
          : pastEdge
          ? 3
          : null;

        if (tier === null) {
          return [];
        }

        return [
          {
            node: candidate,
            tier,
            distance:
              tier === 0
                ? Math.max(mainGap, 0)
                : Math.hypot(Math.max(mainGap, 0), Math.max(crossGap, 0)),
            crossCenter,
          },
        ];
      },
    );

    if (!candidates.length) {
      return null;
    }

    const topTier = Math.min(...candidates.map((candidate) => candidate.tier));
    const pool = candidates.filter((candidate) => candidate.tier === topTier);
    const nearest = Math.min(...pool.map((candidate) => candidate.distance));
    const tolerance = Math.max(nearest * NAVIGATION_TIE_TOLERANCE, 1);
    // how far a candidate's center is off the current node's center line;
    // within a pixel it's a tie (symmetric layouts), left to reading order
    const offset = (candidate: typeof pool[number]) =>
      Math.abs(candidate.crossCenter - nodeCrossCenter);
    const compareOffsets = (a: typeof pool[number], b: typeof pool[number]) =>
      Math.abs(offset(a) - offset(b)) > 1 ? offset(a) - offset(b) : 0;

    return pool
      .filter((candidate) => candidate.distance <= nearest + tolerance)
      .sort(
        (a, b) =>
          linkRank(a.node.id) - linkRank(b.node.id) ||
          compareOffsets(a, b) ||
          a.crossCenter - b.crossCenter ||
          a.distance - b.distance,
      )[0].node;
  }
}

export class FlowChartCreator {
  isCreatingChart: boolean = false;
  private numberOfNodes: number = 0;
  private direction: LinkDirection | null = null;
  // cross-axis anchor of the pending cluster, so growing it keeps the
  // already-visible pending nodes in place
  private clusterCrossStart: number | null = null;
  pendingNodes: PendingExcalidrawElements | null = null;

  createNodes(
    startNode: NonDeleted<ExcalidrawFlowchartNodeElement>,
    appState: AppState,
    direction: LinkDirection,
    scene: Scene,
  ) {
    const elementsMap = scene.getNonDeletedElementsMap();

    if (direction !== this.direction) {
      this.numberOfNodes = 1;
      this.clusterCrossStart = null;
    } else {
      this.numberOfNodes += 1;
    }

    const { nodes, crossStart } = addNewNodes(
      startNode,
      appState,
      direction,
      scene,
      this.numberOfNodes,
      this.clusterCrossStart,
    );

    this.isCreatingChart = true;
    this.direction = direction;
    this.clusterCrossStart = crossStart;
    this.pendingNodes = nodes;

    // add pending nodes to the same frame as the start node
    // if every pending node is at least intersecting with the frame
    if (startNode.frameId) {
      const frame = elementsMap.get(startNode.frameId);

      invariant(
        frame && isFrameElement(frame),
        "not an ExcalidrawFrameElement",
      );

      if (
        frame &&
        this.pendingNodes.every(
          (node) =>
            elementsAreInFrameBounds([node], frame, elementsMap) ||
            elementOverlapsWithFrame(node, frame, elementsMap),
        )
      ) {
        this.pendingNodes = this.pendingNodes.map((node) =>
          mutateElement(node, elementsMap, {
            frameId: startNode.frameId,
          }),
        );
      }
    }
  }

  clear() {
    this.isCreatingChart = false;
    this.pendingNodes = null;
    this.direction = null;
    this.numberOfNodes = 0;
    this.clusterCrossStart = null;
  }
}

export const isNodeInFlowchart = (
  element: ExcalidrawFlowchartNodeElement,
  elementsMap: ElementsMap,
) => {
  for (const [, el] of elementsMap) {
    if (
      el.type === "arrow" &&
      (el.startBinding?.elementId === element.id ||
        el.endBinding?.elementId === element.id)
    ) {
      return true;
    }
  }

  return false;
};