1

既知の場所にいくつかの点がある平面を想像してみてください。ほとんどが密集していますが、一部は外れ値であり、ポイントがまったくない広い領域があります。長方形のビューポートを介して平面を表示できるクライアントが複数あります。各クライアントのビューポートは異なる寸法である可能性があり、平面上の任意の場所に即座に移動できます。クライアントはポイントの場所を知りません。サーバーだけが行います。クライアントが接続すると、ビューポートのサイズがサーバーに伝達され、サーバーは、そのクライアントのビューポートに1つ以上のポイントが表示される場所で応答する必要があります。クライアントはその場所にアクセスし、それらのポイントへのアクセスからデータを収集し、そのデータをサーバーに送り返し、次にアクセスする場所を要求します。

訪問する場所を選択する効率的なアルゴリズムが必要です。理想的なソリューションは、ビューポートの場所にできるだけ多くの未訪問のポイントを含め、ポイントへの重複訪問を最小限に抑え、未訪問のポイントがない場所を訪問しないことで、クライアントが訪問する必要のある場所の数を最小限に抑えます。アルゴリズムをお勧めできますか？

4

1 に答える 1

0

これをする：

   1) generate a Dalauney triangulation for the points  
   2) sort the triangles by size    
   3) for each vertex in the largest triangle:  
       3a) locate a corner of the viewport at the vertex  
       3b) try each neighboring point on the longest diameter of the viewport
       3c) determine orientation which encloses the maximum number of points  
       3d) position viewport at that orientation
       3e) goto step (3b)  
   4) delete the visited points
   5) goto step (3)
于 2013-02-01T21:38:31.233 に答える