algorithm - 不等式アルゴリズムのプロット

Question

HTML5 キャンバスを使用して単純なグラフ作成アプリケーションを作成しています。入力は次のような不等式のシステムです (すべての関数は線形です)。

4x + y >= 4
x  + y <= 4
x,y >= 0

私が望む出力は、塗りつぶす形状を形成する一連の点です。たとえば、この例では、グラフは次のようになります。

ポイントのセット: [0,4]、[1,0]、[4,0]。これらの点を見つけるアルゴリズムは何ですか? 線の交点が線形システムの解であることは知っていますが、正しい塗りつぶしの方法がわかりません。この質問はグラフシステムの実装に関するものではなく、塗りつぶされた形状の点を見つける方法に関するものです。

Answer 1

あなたの問題は本当に2つの問題であるように私には思えます：方程式は閉じた多角形を定義していますか、そしてそれをどのように埋めるか？

たとえば、
*方程式にx + y> 10が含まれ、x + y <5の場合、その解を見つける方法はなく、埋めるものはありません。*方程式が単純にx> 0の場合、 y> 0の場合、ペイントするサーフェスは無制限/無限になるため、問題が発生します。

連立方程式に解があるかどうかは、線形計画法のシンプレックスアルゴリズムとほぼ同等であると私は信じています。アルゴリズムのフェーズIは、問題が実行可能かどうかを判断します。

その解が閉じた多角形を形成するかどうかは、線形計画法にとって一般的に重要なことではありません。ただし、不等式が与えられた場合、xを最小化、xを最大化、yを最小化、yを最大化の4つの問題に解決策があるかどうかを確認することで、これにアプローチできます。これらの問題のいずれかが解決しない場合は、問題に制限がないことがわかります。これは、ポリゴンが閉じていないことを意味していると思います。

ポリゴンが閉じていることがわかったら、すべての線の交点を計算し、凸包に縮小して、結果のポリゴンを塗りつぶします。

Answer 2

線形半空間の和集合として定義された領域は、半無限である可能性がありますが、単一の凸領域でなければならないという事実を利用できます。これにより、混乱が生じる可能性があります。

1. グラフ化するドメインのスーパーセットである不等式の長方形の「ウィンドウ」を追加することから始めます。このようにして、結果が半無限のスペースである場合を無視できます。

2. 境界のすべてのペア間の交点を見つけます。これは、2つのネストされたループと交差チェッカーです。（必要に応じて、最初にウィンドウ以外の不等式のすべての交差を見つけ、これらすべてを含むようにウィンドウを設定してから、ウィンドウ関連の交差を追加できます。）

3. 不等式を満たさないすべてのポイントを破棄します。

4. ポイントが残っている場合は、凸包アルゴリズムを使用して囲まれた領域を見つけて描画します。

グラフ作成ウィンドウが事前にわかっている場合は、ウィンドウ内にある境界のセグメントのみを考慮し、拡張Bentley-Ottmanのような配置アルゴリズムを使用することで、交差計算をはるかに効率的にすることができます。

Answer 3

次のアルゴリズムを提案できます。このアルゴリズムは、線の交点を見つけるという考えに基づいていないことに注意する必要があります。この方法は、アルゴリズムの実現が複雑に見えるためです。
計算の空間はどのような方法でも離散的であるため、何らかの直交グリッドを導入するのは自然なことのように思われます。
そう：

1. いくつかの特徴的なセル サイズを持つ直交グリッドを紹介しましょう。このサイズは、問題ステートメントの詳細によって異なります。グリッドに N*M ノード (x_i, y_j)、0 <= i < N、0 <=j < M があると仮定します。
2. すべての K 個の不等式 a_k*x1_i+b_k*y1_j-c_k <= 0 for 0 <= k< K を満たすすべての点 (x1_i, y1_j) を見つけます。これらの点は埋められる必要があります。
3. グリッド解像度が視覚化に十分であれば、それだけです。そうでない場合は、どの線が境界点の近くを通過するかを判断する必要があります。このために、各境界点とその近傍をチェックします。点の近傍で S 番目の不等式が破られていることがわかった場合、S 番目の線がこの点とこの近傍の間を通過していることを意味します。