mapboxのearcutライブラリとd3のd3-delaunayライブラリでポリゴンの三角形分割を見比べてみた
こんにちわ。nap5です。
mapboxのearcutライブラリとd3のd3-delaunayライブラリでポリゴンの三角形分割を見比べてみたので紹介したいと思います。
earcutについてはポリゴンの三角形分割の文脈で登場してきます。
threejsからも提供されています。
mapboxのearcutライブラリはこちらです。
d3のd3-delaunayライブラリはこちらです。
この手のポリゴン操作系のライブラリはシンプルな手順で差異をとらえやすくしたいので、使いまわせるイメージを念頭に書いてみました。シンプルに見比べたかったので、プログラムの実行結果は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パス
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パス
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
Earcut三角形分割をした後のSVGパス
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でも上記のプログラムをもとにちょこっと変えれば、同様に動かすことができると思いますので、トライしてみても面白いかもしれません。
最近では、Twitterでモックアップ動画を公開しているので、こちらもよかったら、覗いてみてください。
最後に、Udemyでコースを公開しました。
良かったら覗いてみてください。
また、コースの内容紹介記事は以下になります。
簡単ですが、以上です。