塗られたマス目の境界を描く
以下のように格子状の面があり、マス目のいくつかが塗られているとします。
この塗られたマスについて、下図の境界を描く方法を考えます。
まず、塗られたマス目の周囲を時計回りに囲む4本の矢印を考えます。塗られたマス目が隣接していれば、その境界では2本の矢印が逆向きで重なります。このようなペアを消していくと境界だけが残ります。
これを実装すると次のようになります。座標は左方向と下方向を正とし、 (x,y) の位置のマス目は左上が (x,y) 、右下が (x+1,y+1) の正方形とします。
1type Point = [number, number];2const isSamePoint = (a: Point, b: Point) => a.every((v, i) => v === b[i]);34type Edge = [Point, Point];5const isSameEdge = (a: Edge, b: Edge) => a.every((v, i) => isSamePoint(v, b[i]));67const getBoundaryEdgeList = (cellList: Array<Point>): Array<Edge> => {8 const edgeList: Array<Edge> = [];9 for (const [x, y] of cellList) {10 const vertices = [11 [x, y], // (x,y)------>(x+1,y)12 [x + 1, y], // | |13 [x + 1, y + 1], // | |14 [x, y + 1], // (x,y+1)<--(x+1,y+1)15 ];16 for (let i = 0; i < 4; i++) {17 const p1 = vertices[i];18 const p2 = vertices[(i + 1) % 4];19 const reversed = [p2, p1];20 const index = edgeList.findIndex(e => isSameEdge(e, reversed));21 if (index < 0) {22 edgeList.push(edge);23 } else {24 edgeList.splice(index, 1);25 }26 }27 }28 return edgeList;29}これで終わりでもいいのですが、つなげられる矢印はつなぎましょう。<path>のdは短い方が気持ちがいいですよね。
つなげる処理は境界の矢印リストから1つ取り出して、その終点が始点の矢印を探すようにしました。左折と右折の両方が見つかる場合にどちらを優先するかはあらかじめ決めておきます。この決め方によって、角が接触している場合のつながり方が変わります。
以上です。