/* =============================================================================
 * D03_PlanAnalysis_Plan.ts
 * D 예정노선 2단계 손 긋기 꼴(PLAN 562-3 · 580) — 그은 선 · 갈래 · 조각(구역 × 연도) 다루기 ·
 *   선 뒤집기 · 잇기 · 꺾임점 옮김 · 지움 · 선 지움 · 선 통째 연도 · 마크 옮김 · 여러 조각 연도 · 끌어 고르기 판정(585-2) ·
 *   갈래 시점 지정 · 갈래 처음 해 = 붙은 자리 구간 해(585-3).
 *   DOM · fetch · sessionStorage 없음 · 길이 셈 = 562-1 짝(`D03_PlanAnalysis_Draw`).
 *   [저장] 은 서버가 선 · 조각으로 연도 행을 다시 셈(562-2) — 여기 값을 받아 적지 않음.
 * ========================================================================== */

import { lineLength, segmentLength, sliceLine } from "./D03_PlanAnalysis_Draw";

export type Vertex = [number, number];

/** 그은 선 하나 — `branch` 없음 = 본선(시점 · 종점에서) · 있음 = 갈래(붙은 선 · 꺾임점 차례) ·
 *  꼭짓점 차례 = 측점 차례(첫 점 = No.0). */
export interface PlanLine {
  id: string;
  vertices: Vertex[];
  branch: { line: string; vertex: number } | null;
}

/** 조각 = 선(id) 위 [from_m, to_m] 구역 · 연도(구역 마크 = 조각 경계 · id = 업체 지정이 붙는 열쇠라 나눠도 앞 조각이 지님). */
export interface PlanPiece {
  id: string;
  line: string;
  from_m: number;
  to_m: number;
  year: number;
}

export interface PlanNetwork {
  lines: PlanLine[];
  pieces: PlanPiece[];
}

/** 마크가 끝 · 다른 마크와 이보다 가까우면 안 놓음(m). */
export const MARK_GAP_M = 1;
/** 같은 점(m) — 서버 1 mm 와 같음. */
const SAME_M = 1e-3;

const round3 = (value: number): number => Math.round(value * 1000) / 1000;
export const samePoint = (a: Vertex, b: Vertex): boolean => segmentLength(a, b) <= SAME_M;

/** 새 조각 id — `p<n>`(있는 것 중 가장 큰 수 + 1). */
function nextPieceId(pieces: ReadonlyArray<PlanPiece>): string {
  const used = pieces.map((piece) => Number(/^p(\d+)$/.exec(piece.id)?.[1] ?? 0));
  return `p${Math.max(0, ...used) + 1}`;
}

/** 빈 꼴 — 선 없음(긋기 = 시점 · 종점 · 선에서 시작). */
export function emptyNetwork(): PlanNetwork {
  return { lines: [], pieces: [] };
}

/** 새 선 id — 처음 본선 = `main` · 그 밖 `<prefix>-<n>`. */
function nextLineId(lines: ReadonlyArray<PlanLine>, prefix: "line" | "branch"): string {
  const used = new Set(lines.map((entry) => entry.id));
  if (prefix === "line" && !used.has("main")) return "main";
  let n = lines.length;
  while (used.has(`${prefix}-${n}`)) n += 1;
  return `${prefix}-${n}`;
}

/** 새 본선 — `point` 한 점(끝에 꺾임점을 더해 감). */
export function newLine(network: PlanNetwork, point: Vertex): PlanNetwork {
  const line: PlanLine = {
    id: nextLineId(network.lines, "line"),
    vertices: [[point[0], point[1]]],
    branch: null,
  };
  return { ...network, lines: [...network.lines, line] };
}

/** 새 갈래 처음 해(585-3) = 붙은 자리 구간 해 · 붙은 자리 못 찾음 = null. */
function branchYear(network: PlanNetwork, line: PlanLine): number | null {
  const parent = network.lines.find((other) => other.id === line.branch?.line);
  if (!parent || !line.branch) return null;
  const atM = lineLength(parent.vertices.slice(0, line.branch.vertex + 1));
  return (
    network.pieces.find(
      (piece) =>
        piece.line === parent.id && atM >= piece.from_m - SAME_M && atM <= piece.to_m + SAME_M,
    )?.year ?? null
  );
}

/** 선마다 조각이 0 ~ 길이를 빈틈없이 덮게 맞춤 — 경계 = 조각 시작(0 · 끝 근처 빼고) · 연도 = 그 자리 조각 ·
 *  조각 없는 선 = 한 조각(`year`). 길이 0 선은 조각 없음. */
export function normalizePieces(network: PlanNetwork, year: number): PlanNetwork {
  const pieces: PlanPiece[] = [];
  for (const line of network.lines) {
    const length = round3(lineLength(line.vertices));
    if (!(length > 0)) continue;
    const own = network.pieces
      .filter((piece) => piece.line === line.id)
      .sort((a, b) => a.from_m - b.from_m);
    const starts = own
      .filter((piece) => piece.from_m > MARK_GAP_M / 2 && piece.from_m < length - MARK_GAP_M / 2)
      .map((piece) => ({ id: piece.id, from: round3(piece.from_m), year: piece.year }));
    const head = own.find((piece) => piece.from_m <= MARK_GAP_M / 2) ?? {
      id: "",
      year: own.length ? year : (branchYear(network, line) ?? year),
    };
    const cuts = [{ id: head.id, from: 0, year: head.year }, ...starts];
    cuts.forEach((cut, i) =>
      pieces.push({
        // id 빈 칸 · 연도 없음(서버 마크만 있던 구역) = 새 id · 처음 연도
        id: cut.id || nextPieceId([...network.pieces, ...pieces]),
        line: line.id,
        from_m: cut.from,
        to_m: i + 1 < cuts.length ? cuts[i + 1].from : length,
        year: Number.isFinite(cut.year) ? cut.year : year,
      }),
    );
  }
  return { ...network, pieces };
}

/** 선 위 `atM` 에 마크 — 그 자리 조각을 둘로(같은 연도) · 끝 · 경계와 가까우면 그대로. */
export function splitPiece(network: PlanNetwork, line: string, atM: number): PlanNetwork {
  const index = network.pieces.findIndex(
    (piece) => piece.line === line && atM > piece.from_m && atM < piece.to_m,
  );
  const piece = network.pieces[index];
  if (!piece || atM - piece.from_m < MARK_GAP_M || piece.to_m - atM < MARK_GAP_M) return network;
  const at = round3(atM);
  const pieces = [...network.pieces];
  pieces.splice(
    index,
    1,
    { ...piece, to_m: at },
    { ...piece, id: nextPieceId(pieces), from_m: at },
  );
  return { ...network, pieces };
}

/** `atM` 둘레 `toleranceM` 안 마크를 지움 — 두 조각을 합침(앞 조각 연도). 없으면 그대로. */
export function removeMark(
  network: PlanNetwork,
  line: string,
  atM: number,
  toleranceM: number,
): PlanNetwork {
  const index = network.pieces.findIndex(
    (piece) =>
      piece.line === line && piece.from_m > 0 && Math.abs(piece.from_m - atM) <= toleranceM,
  );
  if (index < 1 || network.pieces[index - 1].line !== line) return network;
  const pieces = [...network.pieces];
  const before = pieces[index - 1];
  pieces.splice(index - 1, 2, { ...before, to_m: pieces[index].to_m });
  return { ...network, pieces };
}

/** 조각 연도 바꿈. */
export function setPieceYear(network: PlanNetwork, index: number, year: number): PlanNetwork {
  return {
    ...network,
    pieces: network.pieces.map((piece, i) => (i === index ? { ...piece, year } : piece)),
  };
}

/** `line` 째 선의 `segment` 번째 구간 안에 꺾임점을 끼움 — 그 선에 붙은 갈래 차례를 한 칸 밈.
 *  선 위 점이라 누가 · 조각은 그대로. */
export function insertVertex(
  network: PlanNetwork,
  line: number,
  segment: number,
  point: Vertex,
): PlanNetwork {
  const id = network.lines[line].id;
  return {
    ...network,
    lines: network.lines.map((entry, i) => {
      if (i === line) {
        const vertices = [...entry.vertices];
        vertices.splice(segment + 1, 0, point);
        return { ...entry, vertices };
      }
      const branch = entry.branch;
      return branch && branch.line === id && branch.vertex > segment
        ? { ...entry, branch: { ...branch, vertex: branch.vertex + 1 } }
        : entry;
    }),
  };
}

/** 선 끝에 점을 더함. */
export function appendVertex(network: PlanNetwork, line: number, point: Vertex): PlanNetwork {
  return {
    ...network,
    lines: network.lines.map((entry, i) =>
      i === line ? { ...entry, vertices: [...entry.vertices, point] } : entry,
    ),
  };
}

/** 선 끝 점을 뺌 — 첫 점(본선 시점 · 갈래 붙은 점)은 못 뺌 · 갈래가 붙은 점도 못 뺌(까닭 글). */
export function dropLastVertex(network: PlanNetwork, line: number): PlanNetwork | string {
  const entry = network.lines[line];
  if (!entry || entry.vertices.length < 2) return "더 뺄 점이 없습니다.";
  const last = entry.vertices.length - 1;
  if (
    network.lines.some((other) => other.branch?.line === entry.id && other.branch.vertex === last)
  )
    return "갈래가 붙은 점은 뺄 수 없습니다 — 갈래를 먼저 지우세요.";
  return {
    ...network,
    lines: network.lines.map((other, i) =>
      i === line ? { ...other, vertices: other.vertices.slice(0, last) } : other,
    ),
  };
}

/** 마지막 선(그리던 갈래)을 지움 — 그 선 조각도. 갈래가 붙어 있으면 그대로. */
export function dropLastLine(network: PlanNetwork): PlanNetwork {
  const index = network.lines.length - 1;
  const id = network.lines[index]?.id;
  if (index < 1 || network.lines.some((line) => line.branch?.line === id)) return network;
  return {
    lines: network.lines.slice(0, index),
    pieces: network.pieces.filter((piece) => piece.line !== id),
  };
}

/** 새 갈래 — `line` 째 선의 `vertex` 꺾임점에서 시작. */
export function addBranch(network: PlanNetwork, line: number, vertex: number): PlanNetwork {
  const parent = network.lines[line];
  const from = parent.vertices[vertex];
  const id = nextLineId(network.lines, "branch");
  return {
    ...network,
    lines: [
      ...network.lines,
      { id, vertices: [[from[0], from[1]]], branch: { line: parent.id, vertex } },
    ],
  };
}

/** 서버 꼴(선 · 마크 · 조각 · 조각 없는 구역 있음) → 화면 꼴(조각이 선을 빈틈없이 덮음). */
export function fromServer(
  lines: PlanLine[],
  marks: ReadonlyArray<{ line: string; at_m: number }>,
  pieces: ReadonlyArray<PlanPiece>,
  year: number,
): PlanNetwork {
  const cuts: PlanPiece[] = marks
    .filter(
      (mark) =>
        !pieces.some(
          (piece) => piece.line === mark.line && Math.abs(piece.from_m - mark.at_m) < 0.01,
        ),
    )
    .map((mark) => ({ id: "", line: mark.line, from_m: mark.at_m, to_m: mark.at_m, year: NaN }));
  return normalizePieces({ lines, pieces: [...pieces, ...cuts] }, year);
}

/** 서버 꼴 마크 — 조각 경계(선마다 0 빼고 시작 자리). */
export function marksOf(network: PlanNetwork): Array<{ line: string; at_m: number }> {
  return network.pieces
    .filter((piece) => piece.from_m > 0)
    .map((piece) => ({ line: piece.line, at_m: piece.from_m }));
}

/** 선 이름 — 갈래 없는 선 = 본선(둘 이상이면 본선 1 · 2 …) · 갈래 = 갈래 1 · 2 …(선 차례).
 *  ⚠ 짝 = `D04_PlanConfirm_Repository.line_names`(조각 · 내보내기 이름) — 고치면 같이(거울 시험 530-3). */
export function lineNames(lines: ReadonlyArray<Pick<PlanLine, "branch">>): string[] {
  const roots = lines.filter((line) => !line.branch).length;
  let root = 0;
  let branch = 0;
  return lines.map((line) =>
    line.branch ? `갈래 ${++branch}` : roots > 1 ? `본선 ${++root}` : "본선",
  );
}

/** 선 차례 — 갈래는 부모 뒤(서버 셈이 앞에서부터 부모를 찾음) · 이미 맞으면 그대로. */
export function orderLines(lines: ReadonlyArray<PlanLine>): PlanLine[] {
  const done = new Set<string>();
  const out: PlanLine[] = [];
  let rest = [...lines];
  while (rest.length) {
    const left: PlanLine[] = [];
    for (const line of rest) {
      if (!line.branch || done.has(line.branch.line)) {
        out.push(line);
        done.add(line.id);
      } else left.push(line);
    }
    if (left.length === rest.length) return [...out, ...left];
    rest = left;
  }
  return out;
}

/** `id` 선과 그 아래 갈래 모두. */
function family(network: PlanNetwork, id: string): Set<string> {
  const out = new Set([id]);
  for (let grew = true; grew;) {
    grew = false;
    for (const line of network.lines)
      if (line.branch && out.has(line.branch.line) && !out.has(line.id)) {
        out.add(line.id);
        grew = true;
      }
  }
  return out;
}

/** 꺾임점마다 선 위 거리. */
function chainages(vertices: ReadonlyArray<Vertex>): number[] {
  const out = [0];
  for (let i = 1; i < vertices.length; i += 1)
    out.push(out[i - 1] + segmentLength(vertices[i - 1], vertices[i]));
  return out;
}

/** 선 모양이 바뀜 — 그 선 마크(조각 시작)를 `carry(옛 거리)` 로 옮겨 실음 · 끝은 `normalizePieces` 가 맞춤. */
function carryMarks(
  pieces: ReadonlyArray<PlanPiece>,
  line: string,
  carry: (m: number) => number,
): PlanPiece[] {
  return pieces.map((piece) =>
    piece.line === line && piece.from_m > 0
      ? { ...piece, from_m: round3(carry(piece.from_m)) }
      : piece,
  );
}

/** 옛 모양 위 거리 → 같은 구간 · 같은 비율의 새 모양 위 거리(꺾임점 수 같음). */
function sameShare(
  before: ReadonlyArray<Vertex>,
  after: ReadonlyArray<Vertex>,
): (m: number) => number {
  const [a, b] = [chainages(before), chainages(after)];
  return (m) => {
    const found = a.findIndex((s, k) => k > 0 && m <= s);
    const i = found < 0 ? a.length - 2 : found - 1;
    const span = a[i + 1] - a[i];
    return b[i] + (span > 0 ? (m - a[i]) / span : 0) * (b[i + 1] - b[i]);
  };
}

/** 꺾임점 옮김 — 이 점에 붙은 갈래 첫 점도 같이 · 마크는 구간 안 비율 그대로. */
export function moveVertex(
  network: PlanNetwork,
  line: number,
  vertex: number,
  point: Vertex,
): PlanNetwork {
  const moved = new Map<string, number>(); // 선 id → 옮길 꺾임점
  const visit = (id: string, v: number): void => {
    moved.set(id, v);
    for (const other of network.lines)
      if (other.branch?.line === id && other.branch.vertex === v) visit(other.id, 0);
  };
  visit(network.lines[line].id, vertex);
  let pieces = network.pieces;
  const lines = network.lines.map((entry) => {
    const v = moved.get(entry.id);
    if (v === undefined) return entry;
    const vertices = entry.vertices.map((p, i): Vertex => (i === v ? [point[0], point[1]] : p));
    pieces = carryMarks(pieces, entry.id, sameShare(entry.vertices, vertices));
    return { ...entry, vertices };
  });
  return { lines, pieces };
}

/** 꺾임점 지움 — 갈래 첫 점 · 갈래가 붙은 점 · 점 둘뿐인 선은 못 지움(까닭 글) · 뒤 갈래 차례 −1 ·
 *  마크는 합친 구간 안 비율. */
export function removeVertex(
  network: PlanNetwork,
  line: number,
  vertex: number,
): PlanNetwork | string {
  const entry = network.lines[line];
  if (entry.vertices.length <= 2) return "점이 둘뿐인 선입니다 — 선을 지우세요.";
  if (vertex === 0 && entry.branch) return "갈래 첫 점은 붙은 선 위라 지울 수 없습니다.";
  if (network.lines.some((o) => o.branch?.line === entry.id && o.branch.vertex === vertex))
    return "갈래가 붙은 점은 지울 수 없습니다 — 갈래를 먼저 지우세요.";
  const vertices = entry.vertices.filter((_, i) => i !== vertex);
  const [a, b] = [chainages(entry.vertices), chainages(vertices)];
  const last = entry.vertices.length - 1;
  const carry = (m: number): number => {
    if (vertex === 0) return Math.max(0, m - a[1]);
    if (vertex === last) return Math.min(m, b[b.length - 1]);
    if (m <= a[vertex - 1]) return m;
    if (m >= a[vertex + 1]) return m - a[vertex + 1] + b[vertex];
    const share = (m - a[vertex - 1]) / (a[vertex + 1] - a[vertex - 1]);
    return b[vertex - 1] + share * (b[vertex] - b[vertex - 1]);
  };
  return {
    lines: network.lines.map((other, i) => {
      if (i === line) return { ...other, vertices };
      const branch = other.branch;
      return branch?.line === entry.id && branch.vertex > vertex
        ? { ...other, branch: { ...branch, vertex: branch.vertex - 1 } }
        : other;
    }),
    pieces: carryMarks(network.pieces, entry.id, carry),
  };
}

/** 선 방향 바꿈(측점 No.0 쪽 바꿈) — 조각 · 붙은 갈래 차례 따라감 · 갈래는 못 바꿈(까닭 글). */
export function reverseLine(network: PlanNetwork, line: number): PlanNetwork | string {
  const entry = network.lines[line];
  if (entry.branch) return "갈래는 방향을 바꿀 수 없습니다 — 첫 점이 붙은 선 위입니다.";
  const n = entry.vertices.length;
  const length = round3(lineLength(entry.vertices));
  return {
    lines: network.lines.map((other, i) => {
      if (i === line) return { ...other, vertices: [...other.vertices].reverse() };
      const branch = other.branch;
      return branch?.line === entry.id
        ? { ...other, branch: { ...branch, vertex: n - 1 - branch.vertex } }
        : other;
    }),
    pieces: network.pieces.map((piece) =>
      piece.line === entry.id
        ? { ...piece, from_m: round3(length - piece.to_m), to_m: round3(length - piece.from_m) }
        : piece,
    ),
  };
}

/** 선 지움 — 그 선 조각도 · 갈래가 붙어 있으면 못 지움(까닭 글). */
export function removeLine(network: PlanNetwork, line: number): PlanNetwork | string {
  const id = network.lines[line]?.id;
  if (network.lines.some((other) => other.branch?.line === id))
    return "갈래가 붙은 선은 지울 수 없습니다 — 갈래를 먼저 지우세요.";
  return {
    lines: network.lines.filter((_, i) => i !== line),
    pieces: network.pieces.filter((piece) => piece.line !== id),
  };
}

/** `a` 선 꼬리에 `b` 선(머리 = a 꼬리)을 이어 한 선 — 조각 id 그대로 · 이음 자리 두 조각이 같은 해면 하나로. */
function joinLines(network: PlanNetwork, a: number, b: number): PlanNetwork {
  const [head, tail] = [network.lines[a], network.lines[b]];
  const offset = round3(lineLength(head.vertices));
  const shift = head.vertices.length - 1;
  const last = network.pieces
    .filter((piece) => piece.line === head.id)
    .sort((x, y) => y.from_m - x.from_m)[0];
  const pieces = network.pieces
    .map((piece) =>
      piece.line === tail.id
        ? {
            ...piece,
            line: head.id,
            from_m: round3(piece.from_m + offset),
            to_m: round3(piece.to_m + offset),
          }
        : piece,
    )
    .filter(
      (piece) =>
        !(
          piece.line === head.id &&
          Math.abs(piece.from_m - offset) < SAME_M &&
          last?.year === piece.year
        ),
    );
  const lines = network.lines
    .map((line, i) => {
      if (i === a) return { ...line, vertices: [...line.vertices, ...tail.vertices.slice(1)] };
      const branch = line.branch;
      return branch?.line === tail.id
        ? { ...line, branch: { line: head.id, vertex: branch.vertex + shift } }
        : line;
    })
    .filter((_, i) => i !== b);
  return { lines: orderLines(lines), pieces };
}

/** 갈래 없는 선 머리가 다른 선 꼬리에 닿으면 이어 붙이고 · 꺾임점에 닿으면 그 점의 갈래로(제 갈래 빼고). */
export function attachHead(network: PlanNetwork, line: number): PlanNetwork {
  const entry = network.lines[line];
  if (!entry || entry.branch || entry.vertices.length < 2) return network;
  const head = entry.vertices[0];
  const own = family(network, entry.id);
  const others = network.lines
    .map((other, index) => ({ other, index }))
    .filter(({ other }) => !own.has(other.id) && other.vertices.length > 0);
  const tail = others.find(({ other }) =>
    samePoint(other.vertices[other.vertices.length - 1], head),
  );
  if (tail) return joinLines(network, tail.index, line);
  for (const { other } of others) {
    const vertex = other.vertices.findIndex((v) => samePoint(v, head));
    if (vertex < 0) continue;
    const lines = network.lines.map((entry, i) =>
      i === line ? { ...entry, branch: { line: other.id, vertex } } : entry,
    );
    return { ...network, lines: orderLines(lines) };
  }
  return network;
}

/** 선 통째 연도 — 그 선 조각 모두. */
export function setLineYear(network: PlanNetwork, line: string, year: number): PlanNetwork {
  return {
    ...network,
    pieces: network.pieces.map((piece) => (piece.line === line ? { ...piece, year } : piece)),
  };
}

/** 마크 옮김 — `index` 조각의 시작(= 앞 조각 끝)을 `atM` 으로 · 양쪽 조각 안에서 `MARK_GAP_M` 남김. */
export function moveMark(network: PlanNetwork, index: number, atM: number): PlanNetwork {
  const piece = network.pieces[index];
  if (!piece || !(piece.from_m > 0)) return network;
  const before = network.pieces.find(
    (p) => p !== piece && p.line === piece.line && Math.abs(p.to_m - piece.from_m) < SAME_M,
  );
  if (!before) return network;
  const at = round3(Math.min(piece.to_m - MARK_GAP_M, Math.max(before.from_m + MARK_GAP_M, atM)));
  return {
    ...network,
    pieces: network.pieces.map((p) =>
      p === piece ? { ...p, from_m: at } : p === before ? { ...p, to_m: at } : p,
    ),
  };
}

/** 여러 조각 연도 바꿈(585-2 속성 판) — `ids` 조각 모두 `year`. */
export function setPiecesYear(
  network: PlanNetwork,
  ids: ReadonlyArray<string>,
  year: number,
): PlanNetwork {
  const pick = new Set(ids);
  return {
    ...network,
    pieces: network.pieces.map((piece) => (pick.has(piece.id) ? { ...piece, year } : piece)),
  };
}

/** 끌어 고르기 상자(보이는 화면 px · 축에 바른 네모). */
export interface ViewBox {
  x0: number;
  y0: number;
  x1: number;
  y1: number;
}

/** 토막 a–b 가 네모와 만나는가(한 끝이 안 · 또는 네 변 중 하나와 교차). */
function segmentHitsBox(a: Vertex, b: Vertex, box: ViewBox): boolean {
  const inside = ([x, y]: Vertex): boolean =>
    x >= box.x0 && x <= box.x1 && y >= box.y0 && y <= box.y1;
  if (inside(a) || inside(b)) return true;
  const cross = (p: Vertex, q: Vertex, r: Vertex, s: Vertex): boolean => {
    const d = (q[0] - p[0]) * (s[1] - r[1]) - (q[1] - p[1]) * (s[0] - r[0]);
    if (d === 0) return false;
    const t = ((r[0] - p[0]) * (s[1] - r[1]) - (r[1] - p[1]) * (s[0] - r[0])) / d;
    const u = ((r[0] - p[0]) * (q[1] - p[1]) - (r[1] - p[1]) * (q[0] - p[0])) / d;
    return t >= 0 && t <= 1 && u >= 0 && u <= 1;
  };
  const corners: Vertex[] = [
    [box.x0, box.y0],
    [box.x1, box.y0],
    [box.x1, box.y1],
    [box.x0, box.y1],
  ];
  return corners.some((c, i) => cross(a, b, c, corners[(i + 1) % 4]));
}

/** 끌어 고르기(585-2 · 오토캐드 꼴) — 창(`crossing` 아님) = 조각 꺾은선 점이 모두 상자 안 ·
 *  걸침 = 점 하나라도 안 또는 토막 하나라도 상자 변과 만남. `toView` = 작업 좌표계 점 → 보이는 px. */
export function piecesInBox(
  network: PlanNetwork,
  toView: (point: Vertex) => Vertex,
  box: ViewBox,
  crossing: boolean,
): string[] {
  const norm: ViewBox = {
    x0: Math.min(box.x0, box.x1),
    y0: Math.min(box.y0, box.y1),
    x1: Math.max(box.x0, box.x1),
    y1: Math.max(box.y0, box.y1),
  };
  const inside = ([x, y]: Vertex): boolean =>
    x >= norm.x0 && x <= norm.x1 && y >= norm.y0 && y <= norm.y1;
  return network.pieces
    .filter((piece) => {
      const vertices = network.lines.find((line) => line.id === piece.line)?.vertices;
      if (!vertices || vertices.length < 2) return false;
      const path = sliceLine(vertices, piece.from_m, piece.to_m).map(toView);
      if (!crossing) return path.every(inside);
      return path.some((p, i) => (i ? segmentHitsBox(path[i - 1], p, norm) : inside(p)));
    })
    .map((piece) => piece.id);
}

/** 갈래 시점 지정(585-3) — 본선 한 끝이 다른 선 꺾임점에 닿았으면 그 점을 시점(No.0)으로 그 선의 갈래로 ·
 *  머리가 다른 선 꼬리면 한 선으로 이음(연속 구간 = 측점 차례). 닿은 끝 없음 · 이미 갈래 = 까닭 글. */
export function branchFromEnd(network: PlanNetwork, line: number): PlanNetwork | string {
  const entry = network.lines[line];
  if (!entry || entry.vertices.length < 2) return "선을 고르세요.";
  if (entry.branch) return "이미 갈래입니다 — 갈라지는 점이 시점입니다.";
  const own = family(network, entry.id);
  const touches = (point: Vertex): boolean =>
    network.lines.some(
      (other) => !own.has(other.id) && other.vertices.some((v) => samePoint(v, point)),
    );
  if (touches(entry.vertices[0])) {
    const next = attachHead(network, line);
    if (next !== network) return next;
  }
  if (!touches(entry.vertices[entry.vertices.length - 1]))
    return "다른 선에 닿은 끝이 없습니다 — 끝을 다른 선 위에 놓고 지정하세요.";
  const turned = reverseLine(network, line);
  if (typeof turned === "string") return turned;
  const index = turned.lines.findIndex((other) => other.id === entry.id);
  const next = attachHead(turned, index);
  return next === turned ? "다른 선에 닿은 끝이 없습니다." : next;
}