Mac用プロットライブラリ-22「隠面消去と半順序集合」

一人で面白がっている3次元プロットの隠面消去の問題。半順序集合と見なして見通しをよくしようと考えた。多分こういう問題はさんざっぱら研究されて当たり前になっているんだろうけど、ネットで調べるぐらいだとあまり有益な情報は見当たらない。自力でなんとかしよう、面白いし。

半順序集合を視覚的に表すのに、ハッセ図（ベキ集合の右上図）というのがある。上から下に向かって点が線で繋がっている。線で繋がれた点同士は、上の点をAとして下をBとすると

を表している。
また、つながっていない点は順序付けされていない、とする。
さらに

から導かれる

に対応する線は明示的には引かれない。ハッセ図の例を図-11に示す。

Mathematicaには、有名な Combinatorica パッケージの中にHasseDiagramという非循環有向グラフを並び替えてハッセ図としてグラフ表示するための関数がある。

今問題にしている前後関係の表現は、オブジェクトについてのハッセ図が描ければ（プログラミング上は非循環有向グラフとして表現できれば）できたことになる。 つまり

1. ハッセ図を表現するクラスを作る
2. オブジェクトの奥行きの値に従ってハッセ図（を表す構造）を作る
3. ハッセ図の最大元（最も遠いオブジェクト）から始めて線をたどりながら描画する
4. 全部のオブジェクトを描画し終わったら終わり

ということになる。

図-12の四つのオブジェクトの前後関係は、図-11のハッセ図で表すことができる。

ハッセ図を表すクラスをえいやっ、で考えてみると、

@interface HasseElement : NSObject {
id	transformedObject;
NSArray	*toFurtherElements;
}
@end
interface HasseDiagram : NSObject {
NSArray	*hasseElements;
}
@end

と、ま、こんなもんだろ。HasseElementの一つ目のidが射影変換後の２次元オブジェクトへのポインタで、二つ目はハッセ図の線のアレイを持っている。HasseDiagramはそのHasseElementのアレイを持っている。

オブジェクトの奥行きを比較しながらハッセ図を作るところが半順序集合のソートをすると言うことに対応する。具体的には

1. HasseDiagramを生成して、オブジェクトの数だけHasseElementを作る
2. その中から順に二つを取り出して奥行きを比較する
3. もし一方がもう一方を踏んづけていたら線を引く（近い方が遠い方のポインタを持つ）
4. すべての組み合わせに関して以上をやる

とする。ちょっと線を引くときに微妙な問題を含んでいる。これはあとから考える。

ハッセ図ができてしまえば一番近いオブジェクトから線を逆に再帰的にたどって描画する順序を決めればいい。

再帰的に描画順序を決めるとは

1. まず一番近いオブジェクトに着目する
2. もしそれよりも線一本分遠いオブジェクトがあれば、一番近いオブジェクトを描くのを保留して遠い方に着目する
3. さらにそのオブジェクトより線一本分遠いオブジェクトがあればまた保留してそちらに着目する
4. もし線一本分遠いオブジェクトを持たないオブジェクトに行き着いたらそれを実際に描く
5. そのオブジェクトで保留されたオブジェクトがあればこんどはそれを描く
6. 一番近いオブジェクトの保留が解けるとそれを実際に描いて終わり

と言う感じで、スタックをいっぱい食うけどいわゆるリカーシブコールで実装がすごく簡単になる。特に「線一本分遠いオブジェクト」を複数個もっていた場合にもスタックを消費するだけでコードを変更する必要がない。よくやるパターン。でもあまり慌てないで実装は後回しにしよう。

さてここで、また一つ問題が。さっき「線を引くときの微妙な問題」として軽く流したところが実は大きな問題として浮上。おお、これどうしよう。なんだかわかる？　往々にしてこういうことってあるんだよねえ、「たいしたことないと思っていたことが別の場面で致命的に」ということが。ちょっと落ち着いて考えよ。

でも、何度も書くけどこれ、考えるのが面白い。ついつい毎晩連続して悩んでしまう。あるところを解決できたと思うとその中に新たな問題が発生する。またその解決を考える。当然プログラミングにまつわるアルゴリズミックな問題なので解決法がないなんてことはなく、それなりの解決法は考えつく。数論の問題みたいに悩んでもなんにも思いつかん、というのではないので楽しいんだろな、やっぱり。