一个数据图上面有很多数据点，怎么样找到一个位置来放一个给定大小的方框，使得这个框遮住的数据点个数最少
要是项目应用的话,我会用穷举法.写一个双重循环,将矩形所有的位置情况遍历一下,找出最合适的位置.实际应用中,简单粗暴的通常是最有效的.要是写论文的话,可以从四叉树的角度出发,感觉能实现一些优化算法.-------------------如果矩形方框不是轴向对齐的,允许有旋转,我就无能为力了.
■网友
不好意思，审题有问题，我的算法是要找出使给定矩形不覆盖任何点（在边界上不算）的位置
伪红学给出了必要条件。实际上可以构造如下算法：
1. 选取点集中一个非边框点P：(x,y)。
2. 找到P+： (x+, y+)满足 y+ = argmin(yi-y) 且 yi\u0026gt;=y 以及 P-：(x-,y-)满足y- = argmin(y-yi)且yi\u0026lt;=y。(xi,yi)表示异于(x,y)的点且P+与P-相异。
3. 在所有(xi,y+)和(xi,y-)的点里面找出x*满足x*=argmax(abs(xi-x)), 这时(x,y-,abs(x-x*), y+ - y-)就构成了一个不包含其它点的矩形。如果这个矩形包含题目要求的那个矩形，得到结论退出。否则到第4步
4. 如果x*\u0026gt;x, 从点集中拿掉所有xi\u0026gt;=x*的点(xi,yi)；如果x*\u0026lt;x, 从点集中拿掉所有xi\u0026lt;=x*的点(xi,yi)。如果此时点集不为空，转到步骤2；否则恢复点集中所有点并转到步骤1
5.如果所有点集中的点都考察过了但未找到符合要求的矩形，则无解
■网友
边界不算覆盖的话，一定有一个最优解，使方框的两条边上有点。
■网友
给george zhou的图：
黑色的方框是您的算法1~3步能选出的所有矩形。红色的方框是您的算法选不出来的。根据george zhou在评论中的补充，可以选出所有的矩形了：
其中，红色的矩形是我从所有矩形中选出的最佳矩形。选择的原则是：选出一个面积尽可以大，又尽可能接近方形的矩形。既不想找出很扁的大矩形，又不想找出很小的方形。为此我给所有的矩形设计一个参数：面积*(宽/长)^0.5，思路是：面积小，分数会低；面积虽然大，但是宽长比小于1的话，也会把分数拉低；只有面积又大，宽长比又接近1的，分数才会高。后面的加上开方原因是实际发现不开方的话分数最高的矩形还是太扁，加上开方之后效果正合适，没有什么严谨的理由。我问这个问题的目的是在一个已有的数据图中找到最佳位置放置插图（inset）或者图例（legend）。MATLAB 2014a以上版本的legend函数自带一个.Location=\u0026#39;best\u0026#39;属性，可以在图内找到覆盖数据点最少的位置放置图例，这个做法更复杂，因为它允许覆盖数据点。而且我无法打开MATLAB的源代码学习它的做法。现在我可以实现我要的目的了：
尽管有些选择结果还是很诡异，但也确实是符合我规定。
【一个数据图上面有很多数据点，怎么样找到一个位置来放一个给定大小的方框，使得这个框遮住的数据点个数最少】
推荐阅读
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- “一部手机读云南”上线力争建成国家方志大数据中心西南中心
- 联合国大数据全球平台中国区域中心在杭州成立
- 有必要重新开个C店吗
- 银行的数据中心可以跳槽去互联网公司吗
- 大学再有三个月就结束了，没学到知识，参加一个软件测试培训机构好吗
- 汽车|长安UNI-K又将开创一个新的"引力"纪元？
- 神话|武汉传奇父亲：一个平行班孩子创造的高考神话（感动上万家长）
- 王者荣耀李白能不能出肉