ねこでじ(Nekodigi)

Nekodigi’s diary

学習中の気づきをまとめています。応援よろしくお願いします

【Processing】Convex Hull同士のMinkowski和を計算する。

成果物

f:id:Nekodigi:20201001174928p:plain
左上の物体Aを、真ん中の物体Bの周りで一周させ通った部分を物体Bに追加したのがMinkowski和です。これを使うと、危険物からXm以内の危険エリアを計算するといったことができます。また、Constrained Delaunayと組み合わせると、ある物体のXm以内に近づかない最短経路検索などといったことが可能になります。Convex Hull以外に対応させたり、Minkowski 差に対応させたりしようと思いましたが、あまりに大変だったので、今回は、これでとどめておきました。下の方にそちらの考察も書いておきますので、時間があるときに取り組ませていただきます。

仕組み

物体Bの各頂点で、物体Aの頂点を複製します。そして、複製された頂点のConvex Hullを求めると、Convex Hull同士のMinkowski和を求めることができます。

コード

4DのConvex Hullを使いまわしため、かなり長いコードになっていますが。3Dでも可能なので、よかったらトライしてみてください。
Quick hull minkowski sumという名前で追加しています。
github.com

Convex Hull以外、Minkowski差について

Convex Hull以外の場合、物体Bの辺ごとに、辺と物体AのMinkowski和をを計算する必要があります。(辺の始点に物体Aを複製し、辺の終点にも複製しConvex Hullを求める)ここまではいいのですが、辺は沢山あるので、Polygon ClippingのUnionを使って辺を接続する必要があります。既にコードはあるのですが、これが非常に難解なため、今回は、紹介しませんでした。
これで、物体Aと、物体Bの輪郭のMinkowski和を求めることができました。ここからは、この結果のPolygonを構成するリングに注目します。リングが元の物体Bの中にあれば削除します。多くの場合、これで完成です。ただ、例えば、物体Aが物体Bより遥かに大きい場合など、これでは正しく判定されない可能性もあります。残念ながら私は未だ解決策を発見できていません。
Minkowski差も大部分は同じで、違うのは元の物体B中にあるリングではなく、外にあるリングを削除するという点だけです。
github.com
JTSのライブラリが使われているので読むときにどうぞ。
github.com