たとえば、n個のコンポーネントがあり、それらのパーセンテージ値が配列にある円グラフが描かれています。そして今、パーセンテージの配列を更新して、円グラフを再描画したいと思います。最小限の色の変更で描画するアルゴリズムはありますか? 私は A* が最適な解決策であると考えていましたが、この問題のヒューリスティックを見つけるのは困難です。
3 に答える
個人的には、円グラフを再描画するだけで構いません。チャートの変更されていない部分を再描画しないことで節約される時間は、何を変更するかを考え出すために費やされる時間に圧倒されると思います。
それにもかかわらず、ここにアイデアがあります:
円に配置された 100 個の三角形のセットとして円グラフを描きます。100 ではグラフがきれいに見えない場合は、100 の整数倍を選択します。セグメント A が元のグラフの 20% であり、グラフの最初の (12 時から時計回りに数えた) セグメントであるとします。ペイントでは、三角形 1 ~ 20 を好きなように色付けするだけです。セグメント A が 25% に拡大する場合は、三角形 21 ~ 25 を再描画します。等々。
パーセンテージの分数が視覚的に意味のある円グラフを見たことがないと思うので、23.8% などの値を処理するのに苦労することはありません。四捨五入するだけです。
これは解決策ではありません。私は単に問題を形式化して、何か思いつくことができるかどうかを確認しようとしました。残念ながら、この問題には計算コストの低い解がありません。
問題を形式化することから始めましょう。
入力:
円周上の n 個の点の 2 つの順序集合:
A(1)..A(n) および B(1)..B(n) は、それぞれ次のような弧のセットを定義します。
- 変更前: 弧 m は角度 A(m) と角度 A(mod(m+1,n)) の間にあります
- 変更後: 円弧 m は角度 B(m) と角度 B(mod(m+1,n)) の間にあります
基本的な数学:
角度 x と y の間の弧の長さはmod(yx,360)です (弧は時計回りに表記されます)。
ここで、mod(a,b) = ab *floor(a/b)*
O(a1,a2,b1,b2)をアーク [a1,a2) とアーク [b1,b2) の交点としてマークします。
2 つの円弧の交点は 0 ~ 2 であることに注意してください。例: O(270,100,90,280)= {[270,280),[90,100)}、O(10,20,30,40)= {}
L(a1,a2,b1,b2)は、アーク [a1,a2) とアーク [b1,b2) の間の大きな交点のアーク長としてマークします。
ここでは、L(a1,a2,b1,b2) の計算については説明しません。
特殊なケース: アークの順序を同じに保つ:
最大化する描画オフセットwを見つけます
L(A(1),A(2),mod(B(1)+w,360),mod(B(2)+w,360)) +
L(A(2),A(3),mod(B(2)+w,360),mod(B(3)+w,360)) + ... +
L(A(n),A(1),mod(B(n)+w,360),B(1),mod(B(1)+w,360)
一般的なケース: 円弧の順序を維持しない場合:
両方を見つける
- 点セット B によって定義される円弧のセットの順序の順列
- 図面オフセット w
これにより、特殊な場合と同じ式が最大化されます。
私の考え
残念ながら、モジュロ関数の不連続性のために、最適解を見つける簡単な方法はありません。
特殊なケースでは、与えられた解像度 (例えば 0.1 度) から始まる最適なwを単純に検索し、最適なw の近くで解像度を上げることができます (とにかくサブピクセル解像度は必要ありません)。
一般的なケースに関しては、順列セットを制限するための優れたヒューリスティックを見つける必要があると思います-おそらく、ほぼ同じ場所に大きなアークを残すことによって。
後の作業を再描画するだけでなく、dubbelbufferを作成し、比較し、違いをペイントすると思います。