TypeScriptと関数型プログラミングで実現するパス上の点の計算の抽象化

はじめに

関数型言語の理論に関する記事はWEBで検索すると割と豊富にあるが、それを具体的なプログラミングへ応用する実践的な内容は意外と少ない。特にフロントエンドの分野では、その例をほとんど目にすることがない。この記事では、関数型プログラミングの原則を活用し、フロントエンド開発における具体的な問題「線上の点を計算する方法」に焦点を当てる。

フロントエンドアプリケーションでは、まれにTweenライブラリを使って複数の線に沿うようにオブジェクトを動かしたいときがある。例えば、複数の点を結ぶ直線や曲線上でオブジェクトの位置を特定の時間 t（0から1までの値）に基づいて決定したい場合、単純な方法は全体のパスを線の数で均等に分割し、その分割点から t の値に応じた位置を求めることだ。しかしこのアプローチでは、各線の実際の長さが異なるため問題が生じる。具体的には、長い線と短い線が混在している場合、オブジェクトの移動が均一ではなくなり、結果として視覚的な滑らかさが損なわれ、スムーズなアニメーションが実現できなくなる。

このような問題を解決するため、@sumisonic/find-point-on-path ライブラリを開発した。このライブラリは TypeScript で実装され、関数型プログラミングライブラリ fp-ts を使用しており、パス上の正確な座標や角度を計算するためのAPIを提供する。次のセクションでは、このライブラリがどのように線の長さを考慮しながらパス上の点を計算するか、具体的なコード例を交えて解説する。

実際の使用例のデモはこちらから。

PathCalculator の定義

PathCalculator は、複数の点を結ぶパスを効率的に計算するために設計されたインターフェースだ。このインターフェースは PathParams を利用して、具体的なパス計算を抽象化し、任意のパスタイプ（直線、曲線など）に適応可能な柔軟性を提供する。

// 基本的な点の型定義
export type Point = {
  x: number
  y: number
}

/**
 * 点を拡張して追加データを含む型。
 * @template T - 追加されるデータの型。
 */
export type ExtendedPoint<T> = Point & T

/**
 * パス上の計算を行うための関数群を定義する型。
 * この型は、与えられた点の配列を基にパス（曲線や直線など）上の特定のポイントを見つけるために必要な計算を抽象化する。
 * @template PathParams パスの計算に必要なパラメータを格納する型。
 * @template ExtraPointData - 追加の点データの型
 */
export type PathCalculator<PathParams, ExtraPointData> = {
  /**
   * パスの特定のセグメントまたはパラメータに基づき距離を計算する。
   * @param params - 距離計算に使用するパスのパラメータ。
   * @returns 計算された距離の数値。
   */
  calculateLength: (params: PathParams) => number

  /**
   * 与えられた点の配列からパスの計算に必要なパラメータの配列を生成する。
   * @param points - パスを形成する点の配列。
   * @returns パスの各セグメントまたは部分に対応するパラメータの配列。
   */
  getPathParams: (points: Point[]) => PathParams[]

  /**
   * パスの特定のパラメータとパラメータ`t`に基づき、パス上の点を計算する。
   * @param params - ポイントを計算するためのパスのパラメータ。
   * @param t - パス上の特定の点を決定するためのパラメータ（通常は0から1の間）。
   * @returns パス上の計算された点。
   */
  calculatePoint: (params: PathParams, t: number) => ExtendedPoint<ExtraPointData>
}

2点間のパスの抽象化

複数の点を結ぶパスでも、基本的には2点間のパスを計算する必要がある。PathCalculator ではこの2点間のパスを PathParams というジェネリクスを使って抽象化し、ここでは直線や曲線などの具体的な形状に依存させない。

複数の点から PathParams を得る

PathCalculator は、 getPathParams を用いて、複数の点から最小単位である2点間の各 PathParams の配列を生成する。このプロセスはパス全体を適切に扱うための基盤を提供し、後の計算を容易にする。

パスの長さの計算

calculateLength を用いて、PathParams からパスセグメントの長さを計算する。これはパス全体の長さを求める際や、特定の位置を割り出す際に重要な役割を果たす。

時間に基づく位置の計算

calculatePoint を用いて PathParams と、パラメータ t（通常0から1の間）からパス上の特定の位置を計算できる。戻り値を Point ではなく ExtendedPoint<ExtraPointData> としているのは、単純な位置情報だけではなく、角度などの追加情報も含めたいためである。

createFindPointOnPath の定義

createFindPointOnPath 関数は、与えられた点の配列とパラメータからパス上の特定の点を計算するためのAPIを提供する関数を生成する。この関数は、抽象的な PathCalculator インターフェースを利用して、直線、曲線などの任意のパスタイプに適用可能である。関数型プログラミングの原則に基づき、パラメータ化されたデータ構造と純粋関数を活用してパス計算の複雑さを抽象化し、柔軟で再利用可能なコードを実現する。

/**
 * `createFindPointOnPath`は、特定のパス計算ロジックに基づいてパス上の点を見つける関数を生成する。
 * @param calculator パス上のポイントを計算するための関数群を提供するオブジェクト。
 * @returns ポイントの配列を引数に取り、`t`値に基づいて計算されたポイントを`Option`型で返す関数。
 */
export const createFindPointOnPath = <PathParams, ExtraPointData>(
  calculator: PathCalculator<PathParams, ExtraPointData>,
): FindPointOnPathFunction<ExtraPointData> => {
  return (points: Point[]) => {
    const params = calculator.getPathParams(points)
    const distances = params.map((p) => calculator.calculateLength(p))
    const totalDistance = distances.reduce((acc, length) => acc + length, 0)

    return (t: number): O.Option<ExtendedPoint<ExtraPointData>> => {
      if (t < 0 || t > 1) {
        return O.none
      }

      const targetDistance = totalDistance * t
      const findPoint = (index: number, accumulatedDistance: number): O.Option<ExtendedPoint<ExtraPointData>> => {
        if (index >= points.length - 1) {
          return O.some(calculator.calculatePoint(params[index], 1))
        }

        const dist = distances[index]
        if (accumulatedDistance + dist >= targetDistance) {
          const ratio = (targetDistance - accumulatedDistance) / dist
          return O.some(calculator.calculatePoint(params[index], ratio))
        }

        return findPoint(index + 1, accumulatedDistance + dist)
      }

      return findPoint(0, 0)
    }
  }
}

この関数は特に、複数の点を結ぶパスの全長を計算し、与えられたパラメータ t（0から1の間で、パス上の位置を表す比率）に基づいてパス上の特定の位置を求める。再帰的な探索を利用して、正確な位置を計算し、fp-ts の Option の形で結果を返す。このメカニズムはエラーハンドリングも効果的に行うことができ、パス上の点が存在しない場合には安全に O.none を返すことができる。

計算の流れの詳細

まず、与えられた点から各セグメントの PathParams を取得し、それぞれの距離を計算して、パス全体の長さを算出する。

const params = calculator.getPathParams(points)
const distances = params.map((p) => calculator.calculateLength(p))
const totalDistance = distances.reduce((acc, length) => acc + length, 0)

続いて、この関数はパス上の特定の位置を求めるための関数を返す。パラメータ t（0から1の間の値）に基づき、パス全体の長さから目的の位置を算出し、その位置を見つけるために findPoint 関数を再帰的に呼び出す。

return (t: number): O.Option<ExtendedPoint<ExtraPointData>> => {
  if (t < 0 || t > 1) {
    return O.none
  }

  const targetDistance = totalDistance * t
  const findPoint = (index: number, accumulatedDistance: number): O.Option<ExtendedPoint<ExtraPointData>> => {
    if (index >= points.length - 1) {
      return O.some(calculator.calculatePoint(params[index], 1))
    }

    const dist = distances[index]
    if (accumulatedDistance + dist >= targetDistance) {
      const ratio = (targetDistance - accumulatedDistance) / dist
      return O.some(calculator.calculatePoint(params[index], ratio))
    }

    return findPoint(index + 1, accumulatedDistance + dist)
  }

  return findPoint(0, 0)
}

findPoint 関数は、パスのセグメントを順番に調べていき、累積距離が目的の距離を超えた時点で、そのセグメント内での正確な位置（比率 ratio）を計算する。この比率は、セグメント内の特定の点の正確な位置を求めるために使用される。全てのセグメントを検証し終えるまで、この関数は自身を再帰的に呼び出し続け、必要な位置が見つかるか、またはポイントリストの末尾に到達するまで処理を続ける。この再帰的アプローチにより、パス上の任意の点を効率的かつ正確に見つけることが可能となる。

カリー化とクロージャの活用

createFindPointOnPath 関数はカリー化されており、関数が生成するクロージャを通じてパスの計算を行う。この設計により、複数の関数呼び出しを通じて段階的に引数を適用し、部分的に適用された関数を生成できる。また、クロージャは計算済みのパスのパラメータ params、各セグメントの距離 distances、そしてパス全体の距離 totalDistance を保持する。これにより、これらの計算が複数回行われることを防ぎ、同じ点の配列に対して複数の異なる t 値で点を計算する際に再計算する必要がなくなる。

このクロージャは、関数が外部スコープの変数を「記憶」し、これらの保存された計算結果を利用して必要な位置を迅速に特定できるようにする。この最適化により、createFindPointOnPath は、計算コストを削減しつつ、高速な関数呼び出しとパフォーマンスの向上を実現している。

複数の点を通る直線

ここからは具体的な実装に入っていく。直線の実装は比較的シンプルだ。

直線の PathParams

直線における PathParams の実装は LinearPoint という型で定義する。この型は、直線のセグメントを構成する始点 (start) と終点 (end) のペアを保持する。これにより、直線上の任意の点を計算するための基本情報が提供される。

export type LinearPoint = {
  start: Point;
  end: Point;
}

関数の説明

直線上の計算は基本的な数学を使用し、以下のような関数を通じて実行される。

二点間の直線距離の計算

calculateLinearLength 関数は、開始点 (start) と終了点 (end) を引数に取り、これら二点間の距離を計算する。

/**
 * 与えられた二点間の直線距離を計算する。
 * @param start 開始点
 * @param end 終了点
 * @returns 二点間の距離
 */
export const calculateLinearLength = ({ start, end }: LinearPoint): number =>
  Math.sqrt((end.x - start.x) ** 2 + (end.y - start.y) ** 2)

直線のセグメントのパラメータ生成

getLinearPathParams 関数は、点の配列を受け取り、fp-ts ライブラリの zipWith 関数を利用して隣接する点のペアを使用して直線のセグメントパラメータを生成する。

zipWith 関数は、二つの配列を取り、それらの対応する要素を組み合わせて新しい配列を生成する高階関数。この場合、zipWith は点の配列とその配列の1つ先の要素をスライスした配列を組み合わせ、各点から次の点へのペアを形成する。このペアは直線のセグメントパラメータを定義するために使用される。

import * as A from 'fp-ts/Array'

/**
 * 点の配列から直線のセグメントのパラメータを生成する。
 * @param points 点の配列
 * @returns 直線のセグメントのパラメータの配列
 */
export const getLinearPathParams = (points: Point[]): LinearPoint[] =>
  A.zipWith(points, points.slice(1), (a, b) => ({ start: a, end: b }))

パラメータtに基づく直線上の点の計算

calculateLinearPoint 関数は、線分の始点と終点を定義する LinearPoint と、線分上の位置を決定するパラメータ t を使用して、直線上の特定の点を計算する。

/**
 * 与えられた線分の特定の`t`値に基づき、直線上の点を計算する。
 * @param linearPoint 線分を定義する始点と終点を含むオブジェクト
 * @param t 0から1までの値で、線分上の点の位置を決定
 * @returns 計算された点
 */
export const calculateLinearPoint = ({ start, end }: LinearPoint, t: number): Point => ({
  x: start.x + (end.x - start.x) * t,
  y: start.y + (end.y - start.y) * t,
})

createFindPointOnLinearPath 関数と Reader モナドの使用

createFindPointOnLinearPath 関数は直線上の点を計算するための設定を受け取り、その設定に基づいて直線上の特定のt値に対応する点を見つける関数を生成するために Reader モナドを使用する。この関数は fp-ts ライブラリを活用し、設定（環境）に依存する計算をより柔軟に扱えるようにする。

LinearConfig 型の説明

LinearConfig 型は Record<string, never> で定義されており、これはキーと値のペアを持たないオブジェクト（{}）である。直線計算に特別な設定は必要ないため、この型が採用される。

Reader モナドの利用

export const createFindPointOnLinearPath: R.Reader<LinearConfig, FindPointOnPathFunction<{}>> = pipe(
  R.ask<LinearConfig>(),
  R.map((_config) => {
    const linearCalculator: PathCalculator<LinearPoint, {}> = {
      calculateLength: calculateLinearLength,
      getPathParams: getLinearPathParams,
      calculatePoint: calculateLinearPoint,
    };
    return createFindPointOnPath(linearCalculator);
  }),
);

Reader モナドは依存する環境を持つ計算をモデル化するために使用される。ここでは R.ask を使って LinearConfig 環境を要求し、R.map を通じて環境に基づいて直線上の点を計算する PathCalculator 関数を生成する。直線では依存する環境がなく LinearConfig は空のオブジェクトであるが、このような冗長的なコードにする理由は、後述するスプライン曲線のコードと記述を統一するためである。

PathCalculator を生成した後は、前述した createFindPointOnPath 関数を使用し、FindPointOnPathFunction を生成している。これにより、与えられたポイント配列から直線上の任意の位置を求める関数が作成される。

createFindPointOnLinearPath の使用例

以下は createFindPointOnLinearPath 関数を使用して特定のポイントを計算する例である。ここでは、始点 { x: 0, y: 0 } と終点 { x: 10, y: 10 } を持つ線分に対して、線分の中点を求める。

const points = [
  { x: 0, y: 0 },
  { x: 10, y: 10 }
];
const findPointOnPath = createFindPointOnLinearPath({})(points);
const t = 0.5; // パス上の位置を示すパラメータ (0から1まで)
const point = findPointOnPath(t);
console.log(point); // Option<{ x: 5, y: 5 }>

この例では、t の値が 0.5 なので、線分の中点 { x: 5, y: 5 } が計算される。createFindPointOnPath が返す関数は fp-ts の Option 型で結果をラップし、計算結果が存在しない場合には安全にハンドリングすることができる。

複数の点を通る曲線：スプライン曲線の実装

スプライン曲線の実装は直線よりも複雑で、複数の制御点を使用して滑らかな曲線を生成する。スプラインにおける PathParams の実装は SplineControlPoint という型で定義され、各セグメントの始点、終点、および二つの制御点を含む。

スプラインの PathParams

export type SplineControlPoint = {
  p1: Point;  // 始点
  p2: Point;  // 終点
  cp1: Point; // 制御点1
  cp2: Point; // 制御点2
}

関数の説明

スプライン曲線上の点の計算

calculateSplinePoint 関数は、スプライン制御点とパラメータ t に基づいて、曲線上の点を計算する。この関数は3次ベジェ曲線の式を使用しており、曲線は4つのポイント（始点 p1、終点 p2、そして二つの制御点 cp1 と cp2）を使って形成される。この曲線は以下の数式で表される。

B(t) = (1−t)^3 × p1 + 3 × (1−t)^2 × t × cp1 + 3 × (1−t) × t^2 × cp2 + t^3 × p2

/**
 * スプライン制御点とパラメータに基づきスプライン曲線上の点を計算する。
 * @param splineControlPoint スプライン曲線の制御点を含むオブジェクト
 * @param t 曲線上の点を決定するパラメータ（0から1の間）
 * @return 曲線上の点
 */
export const calculateSplinePoint = (splineControlPoint: SplineControlPoint, t: number): Point => {
  const { p1, cp1, cp2, p2 } = splineControlPoint
  const tSquared = t * t
  const tCubed = tSquared * t
  const inverseT = 1 - t
  const inverseTSquared = inverseT * inverseT
  const inverseTCubed = inverseTSquared * inverseT

  const x = inverseTCubed * p1.x + 3 * inverseTSquared * t * cp1.x + 3 * inverseT * tSquared * cp2.x + tCubed * p2.x
  const y = inverseTCubed * p1.y + 3 * inverseTSquared * t * cp1.y + 3 * inverseT * tSquared * cp2.y + tCubed * p2.y

  return { x, y }
}

この式によって、パラメータ t の値に基づいて曲線上の任意の点を計算できる。ここで t は0から1までの間で、曲線の始点から終点までの位置を示す。この計算は、曲線の形状を滑らかに描画するために不可欠であり、グラフィックスアプリケーションやアニメーションで広く使用されている。

スプライン曲線の長さの近似計算

calculateSplineLength 関数は、スプライン制御点を使用して曲線の長さを近似的に計算する。曲線を近似するために多数の線分を使用し、各セグメント間の距離を合計する。

/**
 * スプライン制御点を使用してスプライン曲線の長さを近似的に計算する。
 * @param segments 曲線を近似するために使用する線分の数
 * @return 曲線の近似長
 */
export const calculateSplineLength = (segments: number = 50) =>
  (splineControlPoint: SplineControlPoint): number =>
    pipe(
      A.makeBy(segments, (i) => i / segments),
      A.map((t) => calculateSplinePoint(splineControlPoint, t)),
      A.chainWithIndex((i, point) =>
        i === 0 ? [] : [calculateDistance(point, calculateSplinePoint(splineControlPoint, i / segments - 1 / segments))],
      ),
      A.reduce(0, (acc, length) => acc + length),
    )

createFindPointOnSplinePath 関数と Reader モナドの使用

createFindPointOnSplinePath 関数は、スプライン設定に基づいてスプラインパス上の点を見つける関数を生成するために Reader モナドを使用する。

この関数は fp-ts ライブラリを活用し、設定（環境）に依存する計算をより柔軟に扱えるようにする。

export const createFindPointOnSplinePath = pipe(
  R.ask<SplineConfig>(),
  R.map((config) => {
    const calculator: PathCalculator<SplineControlPoint, {}> = {
      calculateLength: calculateSplineLength(config.segments),
      getPathParams: getSplinePathParams(config.tension),
      calculatePoint: calculateSplinePoint,
    };
    return createFindPointOnPath(calculator);
  }),
);

この関数は PathCalculator を生成した後、createFindPointOnPath 関数を使用し、FindPointOnPathFunction を生成する。これにより、与えられたポイント配列からスプライン曲線上の任意の位置を求める関数が作成される。

角度付きの点への拡張

角度付きの点の計算は、直線やスプライン曲線上の位置とともにその点での角度を求める。これは、グラフィックスやアニメーションでのオブジェクトの向きを調整するのに役立つ。

直線

直線における角度付きの点の計算では、線分の始点から終点へのベクトルの角度を算出する。以下のコードは、直線上の特定のパラメータ t に基づき、点とその角度を計算する関数を示す。

/**
 * 与えられた線分の特定の`t`値に基づき、直線上の点とその点の角度を計算する。
 * 角度は始点から終点への線の傾きから計算される。
 * @param linearPoint 線分を定義する始点と終点を含むオブジェクト
 * @param t 0から1までの値で、線分上の点の位置を決定
 * @returns 計算された点とその点の角度を含むオブジェクト
 */
export const calculateLinearPointWithAngle = ({ start, end }: LinearPoint, t: number): PointWithAngle => {
  const { x, y } = calculateLinearPoint({ start, end }, t);
  const angle = Math.atan2(end.y - start.y, end.x - start.x); // Y差分をX差分で割り、アークタンジェントを取る
  return { x, y, angle };
}

/**
 * 直線上の点を計算する設定を受け取り、直線上の特定の`t`に対応する点を見つける関数を生成する Reader。
 * @returns 直線上の点を計算する関数を生成する Reader。
 */
export const createFindPointOnLinearPathWithAngle: R.Reader<
  LinearConfig,
  FindPointOnPathFunction<PointWithAngle>
> = pipe(
  R.ask<LinearConfig>(),
  R.map((_config) => {
    const linearCalculator: PathCalculator<LinearPoint, PointWithAngle> = {
      calculateLength: calculateLinearLength,
      getPathParams: getLinearPathParams,
      calculatePoint: calculateLinearPointWithAngle,
    };
    return createFindPointOnPath(linearCalculator);
  }),
);

曲線

曲線の角度付きの点の計算では、点の現在位置と微小な t の増分によって得られる次の位置との間で行われる。以下のコードは、角度計算のための精度（微小な増分）を制御する anglePrecision パラメータが追加されている。

/**
 * スプライン設定に追加で角度の計算精度を含む型。
 * `anglePrecision` は角度計算のための `t` の増分を指定する。
 */
type SplineWithAngleConfig = SplineConfig & {
  anglePrecision?: number // 角度計算のための `t` の増分
}

/**
 * スプライン制御点とパラメータに基づき、スプライン曲線上の点とその角度を計算する。
 * 角度は点の現在位置と次の位置から計算される。
 * @param anglePrecision 角度計算の精度（デフォルトは0.01）
 * @param splineControlPoint スプライン曲線の制御点を含むオブジェクト
 * @param t 曲線上の点を決定するパラメータ（0から1の間）
 * @return 角度を含む計算された点
 */
export const calculateSplinePointWithAngle =
  (anglePrecision: number = 0.01) =>
  (splineControlPoint: SplineControlPoint, t: number): PointWithAngle => {
    const point = calculateSplinePoint(splineControlPoint, t);
    // 次の t 値を決定: t が1の場合は少し手前を、それ以外は少し後ろを参照する
    const nextT = t >= 1 ? t - anglePrecision : t + anglePrecision;
    const nextPoint = calculateSplinePoint(splineControlPoint, Math.min(nextT, 1));

    // 進行方向を表すベクトルのための点を選択
    const basePoint = t >= 1 ? nextPoint : point; // t が1のときは前の点を基準にする
    const directionPoint = t >= 1 ? point : nextPoint; // t が1のときは現在の点を方向の終点にする

    // ベクトルの方向から角度を計算
    const angle = Math.atan2(directionPoint.y - basePoint.y, directionPoint.x - basePoint.x);

    return { ...point, angle };
  }

/**
 * スプライン設定に基づき、スプラインパス上の点とその角度を見つける関数を生成する。
 * @return スプラインパス上の点と角度を計算する関数を生成する Reader。
 */
export const createFindPointOnSplinePathWithAngle = pipe(
  R.ask<SplineWithAngleConfig>(),
  R.map((config) => {
    const calculator: PathCalculator<SplineControlPoint, PointWithAngle> = {
      calculateLength: calculateSplineLength(config.segments),
      getPathParams: getSplinePathParams(config.tension),
      calculatePoint: calculateSplinePointWithAngle(config.anglePrecision),
    };
    return createFindPointOnPath(calculator);
  }),
);

デモ

@sumisonic/find-point-on-path ライブラリの実際の動作を示すためにデモを用意した。このデモではランダムに生成された10点を使い、ライブラリがどのように動作するかを視覚的に確認できる。

デモはこちらから

まとめ

この記事を通じて、@sumisonic/find-point-on-path ライブラリの機能と使用法について詳しく説明した。このライブラリは、直線やスプライン曲線上の点を計算するためのツールを提供する。また、角度情報を含む点の計算もサポートしており、グラフィックスやアニメーションにおけるオブジェクトの向きを正確に制御できる。

本ライブラリの核となる createFindPointOnPath 関数は、複数の点を結ぶ線分から点を求めるというプロセスを抽象化しており、その柔軟性において使いやすく設計されている。この関数は、任意の PathCalculator を受け取ることができ、直線や曲線だけでなく、様々な形状のパス上の点を計算することが可能である。この特性により、開発者はライブラリをカスタマイズし、特定のアプリケーションに最適化したパス計算ロジックを組み込むことができる。