mapboxのearcutライブラリとd3のd3-delaunayライブラリでポリゴンの三角形分割を見比べてみた

こんにちわ。nap5です。

mapboxのearcutライブラリとd3のd3-delaunayライブラリでポリゴンの三角形分割を見比べてみたので紹介したいと思います。

earcutについてはポリゴンの三角形分割の文脈で登場してきます。

Polygon triangulation - Wikipedia

threejsからも提供されています。

three.js docs

mapboxのearcutライブラリはこちらです。

GitHub - mapbox/earcut: The fastest and smallest JavaScript polygon triangulation library for your WebGL apps

d3のd3-delaunayライブラリはこちらです。

GitHub - d3/d3-delaunay: Compute the Voronoi diagram of a set of two-dimensional points.

この手のポリゴン操作系のライブラリはシンプルな手順で差異をとらえやすくしたいので、使いまわせるイメージを念頭に書いてみました。シンプルに見比べたかったので、プログラムの実行結果はSVGのパスにしてsvg path editorで眺めました。

こちらが見比べた時のプログラムです。エッジカウントは6個以上だと違いが現れ始めると思います

import { default as earcut } from "earcut";
import "array-each-slice";
import { Delaunay } from "d3-delaunay";

const buildPoints = ({ edgeCount }) => {
  const stepSize = (Math.PI * 2) / edgeCount;
  return [...Array(edgeCount)].map((_, edgeIndex) => {
    return [Math.cos(edgeIndex * stepSize), Math.sin(edgeIndex * stepSize)];
  });
};

const points = buildPoints({ edgeCount: 7 }); // edge count over 6

const doDelaunay = ({ verticles }) => {
  const d = [];
  const delaunay = Delaunay.from(verticles);
  const { points, triangles } = delaunay;
  for (let i = 0; i < triangles.length; i++) {
    const t0 = triangles[i * 3 + 0];
    const t1 = triangles[i * 3 + 1];
    const t2 = triangles[i * 3 + 2];
    let path = "";
    if (
      points[t0 * 2] !== undefined &&
      points[t0 * 2 + 1] !== undefined &&
      points[t1 * 2] !== undefined &&
      points[t1 * 2 + 1] !== undefined &&
      points[t2 * 2] !== undefined &&
      points[t2 * 2 + 1] !== undefined
    ) {
      path = path + `M${points[t0 * 2]},${points[t0 * 2 + 1]}`;
      path = path + `L${points[t1 * 2]},${points[t1 * 2 + 1]}`;
      path = path + `L${points[t2 * 2]},${points[t2 * 2 + 1]}`;
      path = path + `Z`;
      d.push(path);
    }
  }
  return d.join("");
};

const doEarcut = ({ verticles }) => {
  const triangles = earcut(verticles);
  const xyList = verticles.eachSlice(2);
  const d = [];
  for (let i = 0; i < triangles.length; i++) {
    const t0 = triangles[i * 3 + 0];
    const t1 = triangles[i * 3 + 1];
    const t2 = triangles[i * 3 + 2];
    let path = ``;
    if (
      points[t0] !== undefined &&
      points[t1] !== undefined &&
      points[t2] !== undefined
    ) {
      path = path + `M${xyList[t0][0]},${xyList[t0][1]}`;
      path = path + `L${xyList[t1][0]},${xyList[t1][1]}`;
      path = path + `L${xyList[t2][0]},${xyList[t2][1]}`;
      path = path + `Z`;
      d.push(path)
    }
  }
  return d.join("")
}

const doOriginal = ({ verticles }) => {
  const xyList = verticles.eachSlice(2);
  let path = `M ${xyList[0][0]},${xyList[0][1]}`;
  for (let index = 1; index < xyList.length; index++) {
    const [x, y] = xyList[index];
    path = path + `L${x},${y}`;
  }
  path = path + `Z`;
  return path;
}

const resultOriginal = doOriginal({ verticles: points.flat() }); // flat array of vertices like [ x0,y0, x1,y1, x2,y2, ... ]
console.log(resultOriginal);

const resultDelaunay = doDelaunay({ verticles: points }); // non flat array of vertices like [ [x0,y0], [x1,y1], [x2,y2], ... ]
console.log(resultDelaunay);

const resultEarcut = doEarcut({ verticles: points.flat() }); // flat array of vertices like [ x0,y0, x1,y1, x2,y2, ... ]
console.log(resultEarcut);

実行結果は以下のようになります。
1行目が三角形分割をする前のオリジナルなSVGパスです。
2行目がドロネー三角形分割をした後のSVGパスです。
3行目がEarcut三角形分割をした後のSVGパスです。

$ time node index.js
M 1,0L0.6234898018587336,0.7818314824680298L-0.22252093395631434,0.9749279121818236L-0.900968867902419,0.43388373911755823L-0.9009688679024191,-0.433883739117558L-0.2225209339563146,-0.9749279121818236L0.6234898018587334,-0.7818314824680299Z
M1,0L-0.9009688679024191,-0.433883739117558L0.6234898018587336,0.7818314824680298ZM1,0L0.6234898018587334,-0.7818314824680299L-0.9009688679024191,-0.433883739117558ZM-0.9009688679024191,-0.433883739117558L-0.22252093395631434,0.9749279121818236L0.6234898018587336,0.7818314824680298ZM-0.9009688679024191,-0.433883739117558L-0.900968867902419,0.43388373911755823L-0.22252093395631434,0.9749279121818236ZM0.6234898018587334,-0.7818314824680299L-0.2225209339563146,-0.9749279121818236L-0.9009688679024191,-0.433883739117558Z
M-0.2225209339563146,-0.9749279121818236L0.6234898018587334,-0.7818314824680299L1,0ZM1,0L0.6234898018587336,0.7818314824680298L-0.22252093395631434,0.9749279121818236ZM-0.22252093395631434,0.9749279121818236L-0.900968867902419,0.43388373911755823L-0.9009688679024191,-0.433883739117558ZM-0.9009688679024191,-0.433883739117558L-0.2225209339563146,-0.9749279121818236L1,0ZM1,0L-0.22252093395631434,0.9749279121818236L-0.9009688679024191,-0.433883739117558Z

real    0m0.105s
user    0m0.159s
sys     0m0.001s

それぞれをsvg path editorに張り付けて眺めてみました。

ファイルにも保存し、添付しましたので、ダウンロード後、ブラウザにドラッグアンドドロップすると見れると思います。

三角形分割をする前のオリジナルなSVGパス

original.svg

391 Bytes

ファイルダウンロードについて

ダウンロード

M 1,0L0.6234898018587336,0.7818314824680298L-0.22252093395631434,0.9749279121818236L-0.900968867902419,0.43388373911755823L-0.9009688679024191,-0.433883739117558L-0.2225209339563146,-0.9749279121818236L0.6234898018587334,-0.7818314824680299Z

三角形分割をする前のオリジナルなSVGパス

ドロネー三角形分割をした後のSVGパス

delaunay.svg

673 Bytes

ファイルダウンロードについて

ダウンロード

M1,0L-0.9009688679024191,-0.433883739117558L0.6234898018587336,0.7818314824680298ZM1,0L0.6234898018587334,-0.7818314824680299L-0.9009688679024191,-0.433883739117558ZM-0.9009688679024191,-0.433883739117558L-0.22252093395631434,0.9749279121818236L0.6234898018587336,0.7818314824680298ZM-0.9009688679024191,-0.433883739117558L-0.900968867902419,0.43388373911755823L-0.22252093395631434,0.9749279121818236ZM0.6234898018587334,-0.7818314824680299L-0.2225209339563146,-0.9749279121818236L-0.9009688679024191,-0.433883739117558Z

ドロネー三角形分割をした後のSVGパス

Earcut三角形分割をした後のSVGパス

earcut.svg

606 Bytes

ファイルダウンロードについて

ダウンロード

M-0.2225209339563146,-0.9749279121818236L0.6234898018587334,-0.7818314824680299L1,0ZM1,0L0.6234898018587336,0.7818314824680298L-0.22252093395631434,0.9749279121818236ZM-0.22252093395631434,0.9749279121818236L-0.900968867902419,0.43388373911755823L-0.9009688679024191,-0.433883739117558ZM-0.9009688679024191,-0.433883739117558L-0.2225209339563146,-0.9749279121818236L1,0ZM1,0L-0.22252093395631434,0.9749279121818236L-0.9009688679024191,-0.433883739117558Z

Earcut三角形分割をした後のSVGパス

同じ三角形分割でも分割方法が変わると違いが出て面白いですね。

threejsからも提供されているEarcutでも上記のプログラムをもとにちょこっと変えれば、同様に動かすことができると思いますので、トライしてみても面白いかもしれません。

three.js docs

最近では、Twitterでモックアップ動画を公開しているので、こちらもよかったら、覗いてみてください。

Tweets by napzak5

最後に、Udemyでコースを公開しました。
良かったら覗いてみてください。

FaunaDBを使用したRSSキュレーションミニシステムの構築

また、コースの内容紹介記事は以下になります。

簡単ですが、以上です。