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 回答