未分類Pythonでパスのブーリアン演算TiBra2019年2月1日プログラミングCommentsさて、前回こしらえた点と点をベジェ曲線で結ぶ自前のパスをブーリアン演算で差分を取りたいと言っていたのはどうなったのか。ソースは一番最後まぁ、最後の合成は余分なパスを生成してるけど、ご愛嬌ってことで。以下、よもやまプログラミング話。点と点をベジェ曲線で結んでいるから交差判定は違うけど、きっと、ポリゴン(多角形)のブーリアン演算は共有するところが多いはずだよね。ことで、まずは既存のアルゴリズムを探し漁りました。Wikiによると、代表的なアルゴリズムは以下の3つ。下2つは特殊ケースのアルゴリズムと書かれているので、おそらくベーシックなのは、一番上のVattiクリッピング法という方法なのでしょう。日本語の情報が見つからない。Clippinghttp://extras.springer.com/2005/978-1-84628-108-2/VattiClip.pdfオープンソースのライブラリhttp://www.angusj.com/delphi/clipper.phpVattiと違うのかもわかりませんが、他の日本語の解説してくれてるページを発見。んー、なんとなく曲線パスへの転用が難しそう。凸多角形の交差計算(前編)http://gihyo.jp/dev/serial/01/geometry/0009んー、自分で考えたものでも、案外上手くいくんじゃね?っといういつもの取り敢えずやってみよう精神で考えてみました。パスとパスをつなぐセグメントに対する交点を順番に探していって、相手の内側にあるならそのセグメントをリストに追加っといった処理を繰り返して、閉領域を探し出します。パス内にいる時リストに加えるのか、パス外にいる時に加えるのかで、合成するのか差分するのかを選択できます。問題があって、困った事に閉じたパスを前提で考えしまったので、開いたパスは対応していません。(内側にいるとき、交点を通れば必ず外側になるっということを前提としているので)その他、最後パスAとパスBそれぞれの処理の中で、全く同じ交点探索を繰り返してたり、明らかに無駄な部分もあったり、自己交差は考えてなかったり、色々と問題があるのですが、意欲も失せてにきたのでこの辺で・・・。この中で、ベジェ曲線同士の交点とか、ベジェ曲線の分割とか要所のコードは備忘録サイトの方にまとめています。http://code.tiblab.net/python/calculate/ほぼ先人のコピペです。数学がてんで駄目の僕でも、人の知識を借りて、こうした処理ができるのだから、ウェブ社会素晴らしい。本当に素晴らしいのは、こうやって自前でコードを書かなくても、matplotlibやshapelyと言ったライブラリでできちゃうってことさ!そう、もはや頑張ってアルゴリズムを考えて、実装する必要なんてなかった。コメントをキャンセルメールアドレスが公開されることはありません。ブログ内容TibLab管理人TiBraのつぶやき程度の内容です。決まった趣旨はありません。興味を持ったこと・日常で行ったことを何でも書きます。共有価値がありそうな記事は昔からやっているTB-note(http://timiditybraver.blog71.fc2.com)に投稿します。