« 塗潰し領域の判定 | メイン | メタセコイア用プラグイン »

2005年09月14日

System Sara 開発日誌:: 塗潰し処理

    

内外判定の時、コンピュータ・ジオメトリのページがヒットして、あれ?この本持ってると思って関連するところを読んだ。
が、結局は少し前にリンクを張った計測と検索を元に内外判定は組んだ。
で、塗潰し処理の段になって、コンピュータ・ジオメトリに載っていた処理と似た方法で実装できることに気付いた。
コンピュータ・ジオメトリでは、複数領域の中から、指定した点がどの領域に属するかを判定する処理について書かれていた。
だから、少し異なる目的だが、ほとんどそのまま使えると思い、実装してみた。
具体的には…
塗潰したい領域の全ての点のX座標値のところに縦線を引く。
塗潰し説明画像A
で、この線で囲まれている矩形を塗潰す。
ただそれだけ。
塗潰す領域は、上から塗る、塗らないと交互に表れるので判定は簡単。
本来であれば、横線も記憶し判定材料にするのだが、斜め線はないので、単にY座標値が同じなら線があるものとして処理することにした。

で、内側のみに移動出来るようにした後、塗潰し処理も組んで少し触ってみた。
が、何か囲んでも反転しない領域が出来た気がした。
でも、しぱらく再現できなかったのでなんだろう? と思っていると再現した。
了解。
次の図のような時に問題が発生する。
塗潰し説明画像B
この図で赤線の部分は本来存在しないはずの線だが、単にY座標値が同じかどうかだけで線の有無を判定していたので、このような場合線があると判定してしまい、その下の領域を塗潰されなくなっていた。
やっぱり線も記憶して判断材料にしないとダメか。
記憶しなくても、その両端を含む線が存在するかどうか判定しても良いが、覚えておく方が、速くて簡単かな?
縦線との交差判定をする時に、Y座標値をキーにしたmultisetに入れとくほうがいいかな?
データ構造とともに少し考えよう。



投稿者 Takenori : 2005年09月14日 01:48




comments powered by Disqus
Total : Today : Yesterday : なかのひと