この記事は グラフィックス全般 Advent Calendar 2024 17日目の記事です。
どうも。個人でElectron＆Webなお絵かきアプリ)を作っていたりいなかったりする者です。終わりの見えない不毛の道を歩み続けています。
まえがき
前回は単純な間引き処理を行うことで入力されたストロークのデータをそこそこ滑らかにしつつデータを削減しました。また、直角の部分で線を分割するようにもしました。そして、鋭角の部分がうまく描けないことにも触れました。
で、今回はその鋭角をそれなりにうまく描けるようにする我流のアルゴリズムについて説明します。
角っぽいところを検出するアルゴリズム
角（カド）の検出には下のようなモデル（概念）を考えます。
連続した点が５つあったとき、「①直線的なところ」と「②角になっているところ」があることを角であることの条件とするという考え方です。
ストロークに当てはめた例を見てみましょう。
下の図の左側は角になっている例で、右は角になっていない例です。ストロークに含まれる点を５つサンプルして、左のように①と②の条件が当てはまる個所は角として判定できます。また、右のように①と②のどちからでも条件に当てはまらない個所は角ではないと判定できます。
ところが実際にやってみると、下の図の左のように本当の角の周囲の点で連続して角として判定されます。上で説明したモデルだと、下の図の右のように、本当の角からいくらかずれていても判定にかかってしまうんですよね…
なので、このアルゴリズムはあくまで角っぽいところを検出するアルゴリズムということです。
角っぽい点の中から一番角っぽい点を見つけ出すアルゴリズム
連続して角として判定された点の中から一番角っぽい点を見つけ出すには、 Perpendicular Distance を使います。
アルファベットで書くとなんか学術的ですね！でもこれは要するに直線と点の距離のことです。わざわざアルファベットで書いたのは、ストローク中の不要な点を削減するアルゴリズムとして有名な Ramer–Douglas–Peucker法 というものがあり、そのアルゴリズムで Perpendicular Distance が使われていて、筆者はそこから着想を得たからです。
Ramer–Douglas–Peucker法は単純かつ強力で、正直これがあれば前回と今回考えたアルゴリズムなんていらんのじゃないかと思ったりもします…
それはともかく、本題の一番角っぽい点を見つけ出すアルゴリズムですが、やることは単純です。角っぽい点の最初の点と最後の点を通る直線を考えて、その直線との距離が最大の点を検索します。もともと角っぽい点として検出された点群なので、これだけで大体は「一番角っぽい点」が見つかるはずです。
作ってみた
前回やった直角の検出の前処理に今回の鋭角の判定を組み込んでみました。まだうまくいかないケースもありますが、前回よりは角の部分が入力しやすくなったと思います。
ちなみに前回は時間がなさすぎてクソコードすぎたので、他にも色々修正したバージョンです。まあクソコードなのは変わらないですが。
See the Pen Untitled by 柏崎ワロタロ (@warotarock) on CodePen.
おわりに
今回は鋭角の角を検出してみました。おそらく人類がすでに10000回はチャレンジした内容なのでしょうが、アドベントカレンダー向けに自分なりにまとめ直したことで、自作アプリで作ったときよりまたちょっと改善できた気がします。
前回も書いたようにリサンプリングとかスムージングとかをやってませんが、自作アプリ自体に関する記事もまだ書いていませんし、また次の課題にしたいと思います（今年は無理かも笑）
アドベントカレンダーも後半ですね。引き続きよろしくお願いいたします！