algorithm - 扫描飞机上的已知位置

Question

想象一个在已知位置有许多点的平面。大多数都聚集在一起，但有些是异常值，并且有大片区域根本没有点。我有多个客户可以通过矩形视口(viewport)查看飞机。每个客户的视口(viewport)可能具有不同的尺寸，并且可以立即移动到飞机上的任何位置。客户不知道点的位置；只有服务器。当客户端连接时，它会将其视口(viewport)的大小传达给服务器，并且服务器应响应一个或多个点对该客户端视口(viewport)可见的位置。客户端访问该位置，从访问这些点收集数据，将该数据发送回服务器，然后请求下一个要访问的位置。这一直持续到至少一个客户访问了所有点。

我需要一个高效的算法来选择要访问的位置。一个理想的解决方案将通过在视口(viewport)位置中包含尽可能多的未访问点、最小化对点的重复访问以及不访问没有未访问点的位置来最大限度地减少客户需要访问的位置数量。你能推荐一个算法吗？

Answer 1

为此:

   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)