Circular Constraintsを伝播で解く一手法

概要

論文の詳細を見る
描画方式(picture description scheme)の1つに、完成された図形が満たすべき条件-幾何学的制約-のみをシステムに与える宣言的方式がある。この方式による描画システムでは、これらの制約をシステムが解くことによって、図形の生成に必要な点の座標値を求めていかなければならない。伝播(propagation)は最も簡単な制約解法の1つである。この方法は制約をグラフの形で表し、既知の値をグラフ内のノードからノードへと次々に伝えていくものである。我々は、この方法を2次元の幾何学的制約問題に適用して非線形の制約も簡単に解けるようにし、また、対話的な環境にも十分耐えられるようにインプリメントした。しかし、この方法は簡単で正確な反面、局所的に解を探索していくために、ループになってしまう制約(circular constraints)も多い。そこで、almost sufficient subgraphの概念を導入し、制約グラフを更に階層的に表わすことにより、ある種のcircular constraintsを解くことを可能とした。
一般社団法人情報処理学会の論文
1993-03-01