【Processing】多角形のオフセット

成果物

f:id:Nekodigi:20200401174504p:plain
多角形の外側に赤い多角形が生成されています。オフセットした線が自己交差する場合の処理は出来ませんが、大半の場合は対応できると思います。

仕組み

頂点に接する二つ辺のの法線の和を正規化し移動方向を求め、オフセットの量÷（1+二つの法線の内積）の分だけ移動させれば頂点をオフセットすることができます。
$\begin{array}{l} bis=na+nb\ \ \\ bis=\frac{bis}{|bis|}\\ \ l=\frac{d\sqrt{2}}{\sqrt{1\ +\ na\cdot nb}}\\ P'=P+l\cdot bis \end{array}$
こちらのサイトを参考にしています。ただ元のサイトでは、d/sqrt(1+na・nb)となっていて、直角の場合長さがdの√2倍にならないので、独断で√2倍しています。間違いであれば連絡していただけるとありがたいです。
stackoverflow.com
※追記 Convex hullの場合で自己交差を解決する方法を考えました。
先に全ての自己交差を計算し、頂点に追加しておきます。法線方向にどのぐらいの位置にいるのかを調べることで、頂点が有効な場所にあるか判定できるため、無効な頂点を全て削除すれば、自己交差も考慮した結果が得られます。ただ、完全にひっくり返る以上の大きいオフセットを行うと、頂点が正しい結果が得られません。内側にオフセット後が元の図形からはみ出していないかで対策しています。
nekodigi.hatenablog.com