先日BULBではオフィス間取り図自動VR化サービス、AutoFloorのbeta版をリリースしました。AutoFloorでは、2DのEditor画面でレイアウトを編集したり、3Dでオフィスの雰囲気を確認する事が出来ます。
2Dにしろ3Dにしろ壁を描画する際に厚みを持たせる必要がありますが、実はこれが予想以上に複雑です。2DではSVGを使っていますが、単純にSVGのstrokeを使うと、この様に角に空きが出来てしまいます。
では壁一つ一つをlineとして扱わず、壁全部をpolylineをして扱えばいいじゃないかと思うかもしれません。実際polyineを使えば、角もキレイに描画してくれます。しかし全ての壁が１つの線になるとは限りませんし、仮にそうだとしても、壁を個別に選択する事が出来なくなります。Editor画面では壁を追加したり編集したりする事が出来るのですが、そのためには壁を個別に選択する必要があります。
というわけで、壁のアウトラインを生成するアルゴリズムを一から作る事にしました。アルゴリズムを作る際に一番重要な事は、ググり力です。というのは半分本気です。何と検索していいか分からず、"How to draw wall"とか闇雲に検索していたのを覚えています。同僚に教えてもらったStack Overflowに何とか救われました。"problem well defined is half solved"(正しく定義された問題は半分解決したようなものだ)という有名な引用文がありますが、それを身をもって体感しました。
そこから色々試行錯誤を繰り返し、何とかアルゴリズムを作る事が出来たので、その方法をご紹介します。
「説明は要らんからコードくれ！」という方はgithubをご覧ください。
問題提議
まずもう少し詳しく問題を定義しましょう。以下の図で言うと、黒い線を元に赤い線を作りたいわけです。（ちなみに、壁は直線であっても他に接続する壁があれば分割されているものと想定します。例えば以下の図では一番上の直線は２つの線として捉えます。将来的には自動で分割出来るようにしたいです。）
実際にSVGで描画する際には、壁と両辺の線をそれぞれ２つの点として表し、その６点をpathで繋ぎます。
pathで６点を繋ぐ事自体は単純ですしプログラミングの環境によるところなので、アルゴリズムのスコープとしては、両辺の線をアウトプットするところまでとなります。しかし６点の順番を間違えるとpathがグチャグチャになるので、順番には気を付けなければなりません。
アルゴリズムはjavascriptで書きました。インプットのデータストラクチャーはこんな感じです。[[x1,y1],[x2,y2]]が１つの壁となります。壁を構成する２点の順番については後ほど説明します。
[
[[x1,y1],[x2,y2]],
...
]
アウトプットは、このように右辺、元の線、左辺をobjectに入れます。
[
{
location: [[x1,y1],[x2,y2]],
right: [[x1,y1],[x2,y2]],
left: [[x1,y1],[x2,y2]]
},
...
]
アルゴリズムを作る際に注意しなければならない点は主に３つあります。
- 壁の厚さは自由に設定する事が出来る。
- 壁は縦横だけでなく、斜めもある。
- ３つ以上の壁が接触する事もある。
特に３番は中々厄介でした。
実装タイム！
アルゴリズムの流れは以下の通りです。
- 元の線から平行線（右辺、左辺）を求める。
- 線が繋がっている点を探し、それぞれの平行線の交点を求め、平行線を上書きする。
- ３つ目以上の壁の場合は、以前求めた平行線と比較し、長さが短い方を採用する。
こう文字でダラダラ書いてもよく分からないと思うので、数学とコードで詳しく説明していきます。
メインとなる関数、constructWallOutlineはwalls(インプット)とwidth(壁の厚さ)を引数として受け取ります。（ちなみにwidthは中央の線から各辺への長さなので、実際の壁の２分の１になります。）
function constructWallOutline(walls, width=1) {
const newWalls = walls.map(w => {
const sorted = sortPoints(w)
const newWall = makeParallelLines(sorted, width)
newWall.location = sorted
newWall.rightDefault = newWall.right.slice(0)
newWall.leftDefault = newWall.left.slice(0)
newWall.done = [false, false]
return newWall
})
}
まずはsortPointsで正しい順番に点を入れ替えます。その後、makeParallellinesで平行線を作ります。他は一旦無視し、sortPointsを実装しましょう。
function sortPoints(points) {
const [[x1,y1],[x2,y2]] = points
return (x1 > x2 || (x1 === x2 && y1 > y2)) ? [points[1],points[0]] : points
}
console.log(sortPoints([[1,1],[2,2]])) //[ [ 1, 1 ], [ 2, 2 ] ]
console.log(sortPoints([[2,1],[1,2]])) //[ [ 1, 2 ], [ 2, 1 ] ]
console.log(sortPoints([[2,2],[2,1]])) //[ [ 2, 1 ], [ 2, 2 ] ]
順番のルールは、x値が小さい方が先になります。もしx値が同じ場合（垂直）、y値が小さい方が先になります。図で表すとこんな感じです。一番右が垂直の例です。SVGはy値が上から下にいくにつれ高くなるので、垂直の場合は上から下という順番になります。
平行線を求める
次にソートされた壁から平行線を計算していきます。
function makeParallelLines(line, width) {
/***
Given 2 points and width, return 2 parallel lines
***/
const [[x1,y1],[x2,y2]] = line
// vector representation of the line
const [u_a, u_b] = [x2-x1, y2-y1]
// vertical
if (u_a === 0) {
return {
right: [[x1-width, y1],[x2-width, y2]],
left: [[x1+width, y1],[x2+width, y2]]
}
}
// horizontal
if (u_b === 0) {
return {
right: [[x1, y1+width],[x2, y2+width]],
left: [[x1, y1-width],[x2, y2-width]]
}
}
// perpendicular to u
const [v_a, v_b] = [1, -u_a / u_b]
const mag = magnitude(v_a, v_b)
// change the length to width
const [w_a, w_b] = [v_a*width/mag, v_b*width/mag]
// parallel lines
const l1 = [[x1+w_a, y1+w_b], [x2+w_a, y2+w_b]]
const l2 = [[x1-w_a, y1-w_b], [x2-w_a, y2-w_b]]
return (y1 > y2) ? {right: l1, left: l2} : {right: l2, left: l1}
}
まず壁(line)をベクトルに変換します。ベクトルが垂直の場合と平行の場合は、計算が楽なので個別に対応します。それ以外の場合は、uに対し垂直のベクトルvを計算し、その長さ(magnitude)を求めます。magnitudeの関数は以下の通りです。
function magnitude(vx, vy) {
return Math.sqrt(vx**2 + vy**2)
}
その後、uの長さをwidthに変えます。その結果がwです。
wを使って平行線を２本作ります。最後に、壁が上向きかどうかによって、どちらの平行線が右側でどちらが左側かを決めます。
これで平行線の完成です！
交点を求める
ここからが本番です。constructWallOutlineの残りを見てみましょう。
function constructWallOutline(walls, width=1) {
...
let inter1, inter2;
for (const wall1 of newWalls) {
for (const [i, _] of wall1.location.entries()) {
for (const wall2 of newWalls) {
for (const [j, _] of wall2.location.entries()) {
// Skip if wall1 and wall2 don't have a commont point or they are the same walls
if (JSON.stringify(wall1.location[i]) !== JSON.stringify(wall2.location[j]) ||
JSON.stringify(wall1.location) === JSON.stringify(wall2.location)) {
continue
}
if (isParallel(wall1.location, wall2.location)) {
inter1 = wall1.rightDefault[i]
inter2 = wall1.leftDefault[i]
wall1.right = pickIntersection(wall1.right, wall1.done[i], inter1, i)
wall2.right = pickIntersection(wall2.right, wall2.done[j], inter1, j)
wall1.left = pickIntersection(wall1.left, wall1.done[i], inter2, i)
wall2.left = pickIntersection(wall2.left, wall2.done[j], inter2, j)
}
else if (i !== j) {
inter1 = intersection(wall1.right, wall2.right)
inter2 = intersection(wall1.left, wall2.left)
wall1.right = pickIntersection(wall1.right, wall1.done[i], inter1, i)
wall2.right = pickIntersection(wall2.right, wall2.done[j], inter1, j)
wall1.left = pickIntersection(wall1.left, wall1.done[i], inter2, i)
wall2.left = pickIntersection(wall2.left, wall2.done[j], inter2, j)
}
else {
inter1 = intersection(wall1.right, wall2.left)
inter2 = intersection(wall1.left, wall2.right)
wall1.right = pickIntersection(wall1.right, wall1.done[i], inter1, i)
wall2.left = pickIntersection(wall2.left, wall2.done[j], inter1, j)
wall1.left = pickIntersection(wall1.left, wall1.done[i], inter2, i)
wall2.right = pickIntersection(wall2.right, wall2.done[j], inter2, j)
}
wall1.done[i] = true
wall2.done[j] = true
}
}
}
}
for (const wall of newWalls) {
delete wall.done
delete wall.rightDefault
delete wall.leftDefault
}
return newWalls
}
ループが４つありますが、ここでどの壁の点が接触しているかを探します。接触している点を見つけたら、交点を計算します。pickIntersectionというのは、３点以上が接してる時に必要になってくるものなので、今は一旦無視します。
1. ２つの壁が並行の場合
並行の場合は特に何もする必要がありません。壁が並行かどうか確かめる関数は以下の通りです。
function slope(x1, y1, x2, y2) {
return (y2 - y1) / (x2 - x1)
}
function isParallel(l1, l2) {
const [[x1,y1],[x2,y2]] = l1
const [[x3,y3],[x4,y4]] = l2
return (x1 === x2 && x3 === x4) || slope(x1,y1,x2,y2) === slope(x3,y3,x4,y4)
}
2. 壁の終わりと始まりが接触している場合（i !== j）
この場合はそれぞれの右側と左側の交点を求めます。
3. 壁の終わり同士又は始まり同士が接触している場合（i === j）
この場合はwall1の右側とwall2の左側、wall1の左側とwall2の右側の交点を求めます。
交点を求める関数は以下の通りです。どちらかの壁が垂直の場合は個別対応しています。詳しい計算式の説明は割愛します。「２線分の交点」でググると沢山情報が出てきます。
function intersection(l1, l2) {
/***
Return the intersection of the two lines
***/
const [[x1,y1],[x2,y2]] = l1
const [[x3,y3],[x4,y4]] = l2
if (x1 === x2) {
const x = x1
const m = slope(x3, y3, x4, y4)
const y = m * x - m * x3 + y3
return [x, y]
}
if (x3 === x4) {
const x = x3
const m = slope(x1, y1, x2, y2)
const y = m * x - m * x1 + y1
return [x, y]
}
const m1 = slope(x1, y1, x2, y2)
const m2 = slope(x3, y3, x4, y4)
const x = ((-m2 * x3 + y3) - (-m1 * x1 + y1)) / (m1 - m2)
const y = m1 * x - m1 * x1 + y1
return [x, y]
}
交点をアップデートする。
１点につき最大２つの壁しか接続しないのであれば、これで完成です。しかし３つ以上接続する場合はもう少しやる事があります。
現状ではどうなるかというと、一回計算した交点を完全に上書きしてしまいます。以下の図は３つの壁が接続している例です。濃い紫の部分が交点を計算している壁です。左から順番に見ていきます。
まず上の並行の壁２つの交点を計算します。並行なのでそのままです。
次に右と真ん中を計算します。上に交点が２つ出来てしまっているのが分かります。
最後に左と真ん中を計算します。結果、点の数は勿論場所も全体的に間違っています。
これを解決するには、どの交点が正しいか判断する必要があります。まず１回目は普通に計算します。そして計算した事が分かるようにdoneをtrueにします。２回目以降は、線が短い方を選ぶだけです。
function length(line) {
return Math.round(((line[1][0] - line[0][0])**2 + (line[1][1] - line[0][1])**2)*100)
}
function pickIntersection(current, done, intersection, index) {
const newLine = current.slice(0)
newLine[index] = intersection
return (!done || length(newLine) <= length(current)) ? newLine : current
}
以下の図の中央を見ると分かるように、１回目に計算した線の方が短いのでそちらを採用しています。
まとめ
ネットで調べてみると意外とありそうで無い情報だったので、同じようなプログラムを作ろうとしている人の参考になれば幸いです。
完成版のコードはgithubをご覧ください。