前日の記事は、Adventarの投稿をSlackやDiscordに通知する / UEC Advent Calendar 2024 #JavaScript - Qiita です。
はじめに
こういうゲームを作りたいのですが、複雑な面積を求める方法が分からないので、自分でアルゴリズムを組んでみました。
この記事は、UEC Advent Calendar 2024 - Adventar 9日の記事です。
単純な面積を掛け合わせた複雑な面積を求める
単に複雑な面積を求める(解析的に式で表されている図形の面積を数値解析的に求める)的な話は色々な記事に載っていたのですが、単純な図形の和集合の面積を求める方法はどう探してもなかったので、備忘録としてここに記しておきます。
作りたいゲーム
マルバツゲームの拡張というか、説明が難しいんですけど、相当数重なった〇の和集合と、相当数重なった×の和集合の共通部分の面積を求める必要が出て来て、それをやります。
失敗した解決案①強引に区切って足し合わせる
古典的な積分ですが、まともな面積を出力してくれるレベルになるまで細かく区切ると計算時間が長くかかりすぎてまともにゲームとして動くレベルではなくなってきたので、没になりました。
失敗した解決案②幾何的に解く
直線と円のみで図形が構成されているため、小学校の頃やった、扇形が重なった図形の面積を求める要領で求めることができないか試行錯誤してみましたが、5,6個重なったベン図の要素を数え挙げるような羽目になったので、当然撤退しました。
採用した解決案｜直線と曲線の交点で区切って足し合わせる
順を追って説明していきます。思想としては積分ですが、構成する曲線の面積が簡単に出せる状況で使いやすいと思います。
大まかな手順
今回面積を求めたい図形は、構成する曲線が単純で面積が求められ(今回は円と直線)、曲線同士の交点が求められる時に使えます。
1.曲線同士の交点を全て求める
2.すべての曲線同士の交点ですべての曲線を座標の方向に短冊形に区切る
3.短冊内の曲線の位置の上下を並べ替える
4.短冊内のある曲線について、それが図形内の下側である場合-1を、上である場合1を足して、0になった場合で面積を足して、短冊の面積を決定する
5.すべての短冊の面積を足し合わせる
例として、以下のようなマス内の2円で構成された図形の面積を求めます。
１．曲線同士の交点を求める
今回は×も〇も直線と円のみで構成されているので、交点が簡単に求められます。あと、端点も求めておきます。
2.端点で区切る
3.曲線の位置の上下を並べ替える
短冊内では曲線の上下が変わらないので、クイックソートとかで、
曲線の上下を決定して並べ替えます。
4.短冊内のある曲線について、それが図形内の下側である場合-1を、上である場合1を足して、0になった場合で面積を足して、短冊の面積を決定する
単純閉曲線のみで構成された図形を相手にしてるので、xy座標で、下から数えていくと必ず下側の曲線と上側の曲線が1対1で同数になります。このことを利用すると、下から数えて初めて下側の曲線にぶつかった時のその曲線から図形が始まり、下側と上側の曲線が同数になった時図形が閉じます。
アルゴリズム的には、下側の図形にぶつかった時は-1を、上側の図形にぶつかった時は+1を足して、-1になった瞬間下側の曲線の面積を引き、0になった瞬間にその上側曲線の面積を足します。
例では、パラメーターが-1の時は枠外なので無視して、0になったら、その時の曲線の面積を足します。
これは短冊内で図形が分かれてない時は一番下の曲線を引いて一番上の曲線を足せばいいのですが、分かれている時はどのタイミングで図形の内外が切り替わるか不明なので、この方法を取らないといけなくなります。
5.すべての短冊の面積を足し合わせる
一つの短冊の面積が決定したので、全部の面積の短冊を足して、図形の面積を決定します。
実践
以上の求め方で、ちゃんと面積を求めれるか試してみます。
１．ただの円
半径1の円です。ちゃんと求められれば、だいたいπになります。
結果は・・・・・・・
成功！ 図形が少ないので、相当良い精度です。
2.半円2つ
今度も大体同じになるはずです。
結果は・・・・・・・
はい完璧。ヤラセじゃないです。
3.円でマスを埋め尽くす
枠の1辺は3なので、9くらいになると嬉しいです。
結果は・・・・・・・
大体9！ここまで複雑な図形でちゃんと求まれば実用的に使えるはずです。
終わりに
×はまだ出来ていません！ただ、メゾット自体はちゃんと使えるはずなので、今後拡張していきます。
