お絵描きアプリのストローク入力のアルゴリズムその１

この記事は [グラフィックス全般 Advent Calendar 2024](https://qiita.com/advent-calendar/2024/graphics) 11日目の記事です。

どうも。個人で[Electron＆Webなお絵かきアプリ](https://warotarokz.sakura.ne.jp/illustmate/))を作っていたりいなかったりする者です。こりずに続けています。

[その２はこちら](https://qiita.com/warotarock/items/7ce425cc61f921283479)

# 背景

現在作成しているお絵描きアプリはいわゆるベクター系です。
つまり、絵をラスターデータ（画素データ）で保持するのではなく、点の座標とか線の太さとかいったベクトルデータで保持する形式です。

![ベクター系っぽいスクショ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/4b6fcd67-ca88-86ba-7342-9fb23eb8e58e.png)

ベクトルデータで持ち続ける関係で面倒なことの一つが、マウスやペンにより入力された座標をそのまま使うとデータが多くなりすぎたり、描画結果が美しくなくなったりしがちなことです。データが多くなるのはメモリ容量の問題だけでなく、後から編集しやすいというベクトルデータの良さも生かせなくなってしまいます。

自作のアプリでも、できるだけストロークを美しくかつデータ少なく入力できるようにしたいので、今まで適当だったアルゴリズムを改善することにしました。

この記事では、自分なりに考えたアルゴリズムのまとめとしてアウトプットしたいと思います。

# 線の入力アルゴリズム１－間引き処理

マウスで小さく「あ」と描くと、下の画像ような離散的な座標データが得られます。点が格子状に並んでいるのは、画面の１ピクセルより細かいマウスの位置が取れないからです。
拡大しているので極端に見えますが、ガクガクして見えますね。また、隣接した点がこれほどの数がなくとも、ストロークは十分表現できるはずです。これを改善するのがアルゴリズム１の間引き処理です。

![「あ」と描いたデータ例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/0b7c87ab-45d8-a355-2209-26c3dca7c8ed.png)

やることは単純で、一つ一つ入力されてくる座標が入力済みの最後の点から一定以上離れた座標になったときストロークの点として採用するだけです。

すると下のような感じで一定間隔で間引きされた状態になります。どんな間隔で間引くのが最適かはアプリによると思います。自作のアプリの場合は、基本は自分の好み（！）で決めて、それを画面のズームの状態に合わせて調節するようにしました。

![間引き処理後](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/83f0358a-45ce-4ff2-55c8-0493c1f680d5.png)

# 線の入力アルゴリズム２－角でストロークを分割

自作のアプリではストロークは描画時にベジエ曲線で補間して滑らかに表示するようにしています。ところが、ストロークに角になる部分があると、ベジエ曲線で補間されて下の画像のようにモニョッとした見た目になります。

![角がモニョッっとね](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/86863b9b-4a08-0385-4e8d-ff32cdd34867.png)

これは描画側では解決しづらいし、繋がっていないほうが後で編集しやすいので、入力の段階でストロークを角で分割するようにしました。これがアルゴリズム２です。

ところで、角には二種類あります。

![二種類の角のカタチ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/d8e2ed92-b32d-8643-4b32-9b0255486ff1.png)

一つ目は画像の左のように、角になる点が一つだけある場合です。これは点のところでストロークが曲がる角度を計算すれば簡単に検出できます。ただし、アルゴリズム１を適用した後でないと不要な角がたくさん検出されてしまうので注意が必要です。

二つ目は、画像の右のように、隣接する二つの点で角になっている場合です。この場合というのは、実はアルゴリズム１を適用することで頻繁に発生するようになります。しかも、アルゴリズム１を適用した後だと厳密にこれが角なのかどうか判定するのは、周囲の点も見ないといけないので結構面倒です。そこで今回は、直角に近い角だけを検出することにして（比較的）単純なアルゴリズムで検出することにします。具体的には、二つの点の曲がり角度を足すと９０度に近く、かつ二つの点の曲がり角度が同じくらいの場合を検出すれば、ちょうど画像の右のような形を検出できます。

そして今回はおまけで、二つの点で角になっている場合にかぎり、角に隣接する線分の延長線上にできる交点を求めることで、より正確な角の位置を計算する機能も追加で実装します。

![交点を新たな角の点とする](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/9e51e79f-d6f9-bd0f-1b19-c469dce18beb.png)

# 実装結果サンプル

見やすいようにかなり拡大して表示しています。

<p class="codepen" data-height="600" data-default-tab="result" data-slug-hash="wBwzGgJ" data-pen-title="Untitled" data-user="warotarock" style="height: 600px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/warotarock/pen/wBwzGgJ">
  Untitled</a> by 柏崎ワロタロ (<a href="https://codepen.io/warotarock">@warotarock</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

# おわりに

実行していただけるとお分かりになると思いますが、鋭角が入力しづらいとか、まだまだできることがたくさんあります。ストロークをなめらかにするスムージング処理とか、自作アプリではまだ色々細かいことをやっています。それらは今後の課題（記事を書くという課題＆もっと改善する課題）にしたいと思います。

![鋭角が入力しづらい](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/59191/87eeb49b-a192-876c-623d-dab93d1dcabd.png)
（鋭角が描けぬ…）

まだまだアドベントカレンダーは続きます。引き続きよろしくお願いいたします！

[その２はこちら](https://qiita.com/warotarock/items/7ce425cc61f921283479)