This page is a personal scratchpad.

• G-Code弄りにおいて、ルートを最適化したい

• Lin-Kerningham法

/**
 * Stroke: ペンプロッターの「始点→終点」の2次元座標
 */
type Stroke = [
  [x1: number, y1: number],
  [x2: number, y2: number]
];

/**
 * Node: どのストロークを、正方向(始点→終点) or 逆方向(終点→始点)で描くか
 */
type Node = {
  strokeIndex: number; // 何番目のストロークか
  direction: 'forward' | 'backward';
};

/**
 * Nodeから「描き終わりの座標」を取り出す
 */
function getEndPoint(strokes: Stroke[], node: Node): [number, number] {
  const stroke = strokes[node.strokeIndex];
  return node.direction === 'forward' ? stroke[1] : stroke[0];
}

/**
 * Nodeから「描き始めの座標」を取り出す
 */
function getStartPoint(strokes: Stroke[], node: Node): [number, number] {
  const stroke = strokes[node.strokeIndex];
  return node.direction === 'forward' ? stroke[0] : stroke[1];
}

/**
 * 2点間の距離
 */
function distance(a: [number, number], b: [number, number]): number {
  const dx = a[0] - b[0];
  const dy = a[1] - b[1];
  return Math.sqrt(dx * dx + dy * dy);
}

/**
 * 連続するNodeの順序から経路の「移動コスト合計」を計算する
 * ペンを上げて移動する距離だけを加算する想定。
 * （ストロークを描く間のコストを考えたいなら、始点→終点の距離を足すなど工夫する）
 */
function totalRouteDistance(strokes: Stroke[], route: Node[]): number {
  let sum = 0;
  for (let i = 0; i < route.length - 1; i++) {
    const endPos = getEndPoint(strokes, route[i]);
    const startPos = getStartPoint(strokes, route[i + 1]);
    sum += distance(endPos, startPos);
  }
  return sum;
}

/**
 * ノード列のうち、区間 [i, j] を反転（2-optの一種）
 * 本当はストロークの向きも入れ替えたい場合があるが、ここでは「ノードの順序のみ」をひっくり返す簡易例
 */
function twoOptSwap(route: Node[], i: number, j: number): Node[] {
  const newRoute = route.slice();
  // 区間 i～j を反転
  while (i < j) {
    [newRoute[i], newRoute[j]] = [newRoute[j], newRoute[i]];
    i++;
    j--;
  }
  return newRoute;
}

/**
 * Lin-Kernighanの「ほんの入り口」を模した簡易例
 *  - 本格的には複数段階のk-optを再帰的に探すなど実装が大きくなる
 *  - ここでは「2-optを段階的に拡張し、改善があれば続行」という流れのイメージ
 */
function linKernighan(
  strokes: Stroke[],
  initialRoute: Node[],
  maxIterations: number
): Node[] {
  let bestRoute = initialRoute.slice();
  let bestDist = totalRouteDistance(strokes, bestRoute);

  // ここでは「2-optを改良する過程で少し拡張する」程度の擬似的な例
  // 実際のLKでは「k本の辺を切り替えながら改良があれば継続」など
  for (let iter = 0; iter < maxIterations; iter++) {
    let improved = false;

    // シンプルに全ペア (i, j) を走査（Nが大きいと厳しいので本来は絞り込み必須）
    for (let i = 0; i < bestRoute.length - 2; i++) {
      for (let j = i + 2; j < bestRoute.length - 1; j++) {
        const newRoute = twoOptSwap(bestRoute, i + 1, j);
        const newDist = totalRouteDistance(strokes, newRoute);
        if (newDist < bestDist) {
          bestRoute = newRoute;
          bestDist = newDist;
          improved = true;
          break; // 外ループに戻って再探索
        }
      }
      if (improved) break;
    }

    // 2-optでも改善が見つからなかった → 打ち切り
    if (!improved) break;

    // 本格的にはさらに「次のk本目を交換してみる」などを繰り返し探す
    // ただしここでは省略
  }

  return bestRoute;
}

// === 以下、使い方サンプル ===
function solveStrokes(strokes: Stroke[]): Node[] {
  // 例: 全てのストロークを正方向に描く初期解を作り、単純に並べる
  const initialRoute: Node[] = strokes.map((_, idx) => ({
    strokeIndex: idx,
    direction: 'forward',
  }));

  // Lin-Kernighan的アルゴリズムで順序を改善
  const improvedRoute = linKernighan(strokes, initialRoute, 200);

  return improvedRoute;
}

// 動作例
function main() {
  const strokes: Stroke[] = [
    <a href="0%2C%200%5D%2C%20%5B10%2C%2010">0, 0], [10, 10</a>,
    <a href="10%2C%2010%5D%2C%20%5B20%2C%205">10, 10], [20, 5</a>,
    <a href="20%2C%205%5D%2C%20%5B15%2C%200">20, 5], [15, 0</a>,
    // ... 以下多数
  ];

  const route = solveStrokes(strokes);
  console.log('Best route:', route);
}