ドロネー三角分割


あけましておめでとうございます。冬休みは高校数学の復習をしながら過ごしていたのですが、数学で調べ物をしていたらドロネー三角形分割なるものを知り、アルゴリズムが面白そうだったので取り組んでみました。

20150111142629

ドロネー三角分割とはポリゴンにポイントを追加していくことで

20150111142717

プログラムが一定の規則に従って三角形を分割してくれます。頂点だけ配置していけば勝手にポリゴンを張ってくれるということころが便利です。

アルゴリズムはこちらを参考にしつつ、自分なりの方法で実装してみました。

三角形の外接円の中心座標

いくつかのサイトでアルゴリズムや実装について書かれているので、ここでは自分が探してもよい説明が見つからなかった三角形の外接円の中心座標の求め方について書いておこうと思います。

triangle_circumcenter

ピタゴラスの定理から

(x1 – Px)^2 + (y1 -Py)^2 = R^2・・・①
(x2 – Px)^2 + (y2 -Py)^2 = R^2・・・②
(x3 – Px)^2 + (y3 -Py)^2 = R^2・・・③

①-②
(x1 – Px)^2 – (x2 – Px)^2 + (y1 – Py)^2 – (y2 – Py)^2 = 0
まとめると
-2(x1 – x2)Px – 2(y1- y2)Py + x1^2 – x2^2 + y1^2 – y2^2 = 0

同様に①-③は
-2(x1 – x3)Px – 2(y1- y3)Py + x1^2 – x3^2 + y1^2 – y3^2 = 0

この二つの式は連立方程式なので、二元一次方程式のクラメル式を使う

a1x + b1y = c1
a2x + b2y = c2

のとき

x = (c1b2 – c2b1) / (a1b2 – a2b1)
y = (a1c2 – a2c1) / (a1b2 – a2b1)

で求まるので、

a1 : -2(x1 – x2)
b1 : -2(y1 – y2)
a2 : -2(x1 – x3)
b2 : -2(y1 – y3)
c1 : -(x1^2 – x2^2 + y1^2 – y2^2)
c2 : -(x1^2 – x3^2 + y1^2 – y3^2)

と当てはめていけば答えは

Px = ((x1^2 – x2^2 + y1^2 – y2^2)(y1 – y3) – (x1^2 – x3^2 + y1^2 – y3^2)(y1 – y2)) / (2(x1 – x2)(y1 – y3) – 2(x1 – x3)(y1 – y3))
Py = ((x1^2 – x3^2 + y1^2 – y3^2)(x1 – x2) – (x1^2 – x2^2 + y1^2 – y2^2)(x1 – x3)) / (2(x1 – x2)(y1 – y3) – 2(x1 – x3)(y1 – y3))

となりますね。長い・・・。

20150112112930

20150112112936

分割した三角形にテクスチャーを参照して色をつけたものです。ポイントの移動はもちろん、追加・削除したり、保存できるようにしました。

写真や画像を自動的にポリゴンぽいイラストにする機能があったら面白そうですね。ドロネー三角形分割はいろいろなことに応用できそうです。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中