难题求解,智商高的进来看看!
已知一个平面有若干个点,在每个点旁边放一个小矩形,矩形紧靠着点,怎样做才能使这些矩形尽可能的不重叠? 问题点数：202、回复次数：40Top
1 楼mousubin（msb）回复于 2001-11-08 22:55:19 得分 0
能提出一点想法的都给分奖励Top
2 楼wyzegg（蛋）回复于 2001-11-08 23:36:40 得分 0
如果只是这个约束的话很简单啦，矩形很小就可以啦
Top
3 楼mousubin（msb）回复于 2001-11-08 23:52:31 得分 0
倒~，什么回答Top
4 楼Hover_cn（翔)(:public IUnknown）回复于 2001-11-09 00:12:44 得分 0
什么题目嘛？Top
5 楼sizhi（人在江湖飘啊~,哪能不挨刀啊~~）回复于 2001-11-09 08:19:26 得分 7
请把题目说清楚：
是不是点不在矩形上，如果只是“紧靠”的话可以无限接近，而不相交，还有矩形是不是尽可能的大，以填充(有限）平面，点的分布毫无规律可言？一个点对应一个矩形？。。。。Top
6 楼juqiang（方枪枪（正在修炼伤心小箭））回复于 2001-11-09 08:35:38 得分 0
study!!1Top
7 楼fkpwolf（如果你没有安全感，请带上安全套）回复于 2001-11-09 08:36:17 得分 0
先从3或者4个点开始Top
8 楼ga3ga3（噶3噶3）回复于 2001-11-09 08:46:30 得分 0
这个题目有意思。矩形至少有大小吧Top
9 楼lxp981818（lxp981818）回复于 2001-11-09 08:46:42 得分 0
你得说得更清楚一点！Top
10 楼mousubin（msb）回复于 2001-11-09 12:44:04 得分 0
矩形是事先知道大小的
应用背景：地图显示，如显示城市、机场、地标等等，如果比较多，要使名字尽可能的不重叠显示，重叠的话就会看不清了Top
11 楼bluecrest（高歌）回复于 2001-11-09 12:47:38 得分 0
是不是弄个区域把点圈起来
然后在区域外化矩形好了Top
12 楼xtky_limi（窗外细雨）回复于 2001-11-09 12:48:16 得分 0
地图尽量大点！！Top
13 楼bluecrest（高歌）回复于 2001-11-09 12:49:18 得分 0
是把若干个点Top
14 楼mousubin（msb）回复于 2001-11-09 13:12:49 得分 0
我见过Encarta 世界地图这个东西就有这样的功能，它上面所有的名字都不会互相重叠显示，甚至河流的名字都会随着河流的走向自动调整，以保证能正确的显示出来（如果河流有部分在屏幕外），百思不得其解，觉得有点神奇Top
15 楼cp_wan（cp_wan）回复于 2001-11-09 13:14:08 得分 0
可否规定在点的右面及下面（或相反）的方向画矩形，当然，可能要测出点与点间的距离Top
16 楼flagfly（我也不知道要去哪里）回复于 2001-11-09 13:48:00 得分 20
给你个算法：
有N个点，点的坐标知道。从1开始，在每个点的0度的地方放置你的矩形，放置的大小，远近完全由自己定，但保证每个点对应的相同。放完后计算得到矩形的四个点坐标。
...
接着放置第k个，同样计算其矩形的坐标，然后分别计算其是否与前k-1个矩形重合（这个算法应该很好做了）。如果不重合，则处理k+1个。如果重合，然后在点的10度的地方放置此矩形，再计算一遍，以后每次增加10度，如果到360度还重合，则调整第k-1个点的矩形到10度，再计算k-1点是否与以前的重合...以此类推。
这里还可以有好多办法进行优化，比如N个点的顺序排列，或者在k点的360度摆放中统计与哪个点重合的次数最多，则调整该点的角度，而不是调整k-1点的角度等Top
17 楼whiskers（胡子）回复于 2001-11-09 14:16:54 得分 0
关键是看你的数据组织的如何
我的做法是根据比例尺来确定那些显示与否Top
18 楼Kevin_qing（）回复于 2001-11-09 14:23:29 得分 0
. .
.
.
->
------
|------|
------
Top
19 楼supperapplication（行星）回复于 2001-11-09 15:49:19 得分 0
up.Top
20 楼mousubin（msb）回复于 2001-11-09 20:04:32 得分 0
flagfly的计算方法在坏的情况下是否复杂度太高了Top
21 楼zengting（喜欢隐身的爱情魔法师）回复于 2001-11-10 11:13:02 得分 5
矩形是方形Top
22 楼passing_time（小龙祥子）回复于 2001-11-10 18:09:38 得分 20
第一点：以目标地址为中心，寻找出周围最近的可能与矩形重叠的点的位置。
第二点：我认为不必在任一角度测试能不能放下地址矩形，只在上下左右四处作测试即可。
第三点：测试放矩形的方法。首先，每个地名的长度是不一样的，因此应该根据地名的长度
选择合适的矩形，最好定义几种形态利用枚举法来检测是否可以放下。假如放不
下再考虑第四点。
第四点：假如放不下，需要分两步改变并测试。第一种：减小字体，当然也就减小了矩形的
大小，同时与方向的改变进行组合，然后测试。如果仍然有重叠，此时再考虑调
整周围每个方向最近的点的放置。如果能够直接调整重叠的点的矩形位置最好。
第五点：如何判别两个矩形是否重叠？最简单的方法：假设矩形的四个顶点的X，Y坐标中含
有以下四个值x1,x2,y1,y2，并且x1<x2,y1<y2.另一个矩形的某一个顶点的坐标
为x,y，如果x1<x<x2且y1<y<y2,则矩形必然重叠。
全部分析完成。
Top
23 楼mousubin（msb）回复于 2001-11-11 18:26:57 得分 0
自己UP一下Top
24 楼Arter（阿蒂尔）回复于 2001-11-11 20:51:20 得分 10
把过每个点与x轴, y轴平行的两条直线画出来,这样相交所得矩形列,放一个小矩形紧靠着点与矩形列中的一个至少有两边重叠,再对小矩形进行调整.
Top
25 楼laozi（老子）回复于 2001-11-12 11:03:09 得分 10
没有好的专业算法，你就回溯吧！Top
26 楼mousubin（msb）回复于 2001-11-12 22:42:56 得分 0
为何没有好的算法啊？Top
27 楼Fairton（飞云）回复于 2001-11-13 16:07:02 得分 10
模糊算法
想象一下很多水球挂在链子上，然后放入水中的排列方式就可以啦Top
28 楼GZCompiler（编译器）回复于 2001-11-13 17:26:04 得分 0
不要先画后摆方，这样不好。
我认为应先为每个点划分他们自己的“私有区域”，然后在每个点的“私有区域”里面作标注，这样谁也不影响谁了。
实现的关键在于怎么划分“私有区域”，还要算法简单，速度快。
我对划分“私有区域”的想法是：
1.选定一个点作为考虑对象，然后将与该点距离在一定范围内（标准是距离小于R或所处区域相隔较近，比如北京位于东八区、东京位于东七区。或者其他什么更合理的标准）的点也纳入考虑范围。
2.将主要考虑的点和他周围这些点的连线的中点找出来，这些中点可组成一个多边形，可以看出不同点的多边形是互不侵犯的。
3.想办法在“私有区域”里面作标注。
要注意的问题：如果一堆点离得很近，那什么算法也没办法，就是让你手工去标你也没法标，意思就是不能企图要在地图上标清四合院每家住的都是谁，因为他们离得太近了，当然这只是相对的，比例尺变了就不一样了，要灵活处理。^_^
“私有区域”怎么划分对实现来说关系很大，可以考虑其他别的什么好办法。Top
29 楼GZCompiler（编译器）回复于 2001-11-13 17:43:47 得分 0
又有一想法：
屏幕上的点一般不会互相冲突，为什么呢？因为在屏幕上，点用像素来表示，像素之间都是互斥的，所以不出现重叠情况。
再想一想为什么标注会重叠呢？因为标注是由多像素来表示的。
好了，解决问题的方法出现了：将屏幕重新划分成更大块（矩形）的“像素”，大小就看你标注的需要了。
这样划分之后，为某个点作标注时，就把标注作在离该点最近且未使用的大块“像素”里，然后把
该大块“像素”标记为已使用，依次标完每个点就可以了。
当然了，这种方法也会有不足的，可能出现某一点的标注离别的点比自己还近，但可以考虑一种方
法将结果优化一下。Top
30 楼jrju（）回复于 2001-11-13 22:01:14 得分 20
mousubin兄:
我觉得这个题目应该是这样的：
已知条件:有N个矩形（大小不一但已知）分别一一对应于平面上的N个点（坐标已知）
要求：将N个矩形放置在平面上。各矩形之间互不重叠，且与其对应点的距离尽量接近
并不得超过一给定距离r。
输入：N，r // 矩型数， 最大偏移距离
Rect(1),Point(1)，// 第一个矩形，第一个矩形对应的平面上的点
Rect(2),Point(2)，// 第二个矩形，第二个矩形对应的平面上的点
...
Rect(N),Point(N)) // 第N个矩形， 第N个矩形对应的平面上的点
输出：RectCenterPoint(1), // 第一个矩形的中点
RectCenterPoint(2), // 第二个矩形的中点
...
RectCenterPoint(N) // 第N个矩形的中点
若无解：Allert("No Solution")
很不错的一个题目，有点意思，我会考虑的。Top
31 楼mousubin（msb）回复于 2001-11-13 22:37:43 得分 0
非常感谢大家的热情参与，这个问题可能在许多情况都挺有用的，希望大家多提看法：）Top
32 楼mousubin（msb）回复于 2001-11-13 22:41:32 得分 0
对于GZCompiler(编译器)的第二种办法，我有一种想法不知可不可行，把屏幕按照点的坐标分割成矩形阵列，对于每一个点，找出它附近四个矩形中的最大的一个，以在此矩形中紧靠点放置矩形为优先考虑，这样是不是可以避免多数的重叠情况？Top
33 楼GZCompiler（编译器）回复于 2001-11-14 09:16:54 得分 20
这样划分也不错，还可以防止标注覆盖到点的情况发生。但这种划分方法还有一个问题：
如果某两点处于点比较稀疏的区域（如新疆省的城市），这两点之间距离也比较大，那么靠这两点
划分出的矩形也会较大，这么大的矩形足够容纳两个点的标注，那么第一个点在里面放置标注后，第二个点是否一定要避开呢？
我觉得，某一点不在某一区域放置标注的条件是：
1.该区域和点不相邻（废话）
2.该区域已被占用且大小不够再容纳另一标注。
3.该区域太小。
其实2、3是一致的，3是2的一个特例而已。
你再考虑考虑，这个问题很有意思。如果出成果了，别忘通知兄弟们一声。Top
34 楼hz1101（lake）回复于 2001-11-14 18:13:02 得分 20
我也是作地图的，我想通过算法无法解决这个问题，打一个比方，在一个非常小的范围内（10平米)有20个点，你的ZOOM值是20公里的话，你想矩形不重叠是不可能的，否则看上去很怪异，我觉得应利用绘图的优势去处理，首先根据对象的走向画矩形，如果在规定的范围内已有矩形存在（会重叠），则进行角度旋转扫描，以寻找合适的位置。在寻找位置过程中可能涉及较复杂的算法。Top
35 楼mousubin（msb）回复于 2001-11-14 18:16:23 得分 0
还有我上面也提到了另一个问题，就是对于象河流这样的折线的文字放置方法，应该采取些什么方法？Top
36 楼mousubin（msb）回复于 2001-11-14 18:18:40 得分 0
如果象HZ1101所说的无法避免的情况，是没有办法的，我以上是指在可能的情况之下，尽量作到不重叠处理Top
37 楼Zig（Zig）回复于 2001-11-14 18:29:24 得分 20
贪心了,最大独立集问题 Top
38 楼chunter（浪人）回复于 2001-11-15 00:08:19 得分 20
我觉得在每个点的周围去找方圆最近的点，(x1,y1) , (x2,y2) 其中x2 > x1.
1。y1< y2 or y1 > y2 时 如果以这两个点所在的线段为对角线的长方形，如果要存放的标注所需的大小比长方形面积大，可以考虑增加x的大小，这样就可以写下来，当然增加x后，没有点在这个区域范围内了。
2。y1 = y2 时，可以考虑那一个点的注释要大一点的面积，如果大的可以调整其的y值
使用后的矩形所在的区域，其他的矩形就不能跟它重叠了。
不过这还是要使用回溯，找出最优的方案，不能这样处理的再使用人工的算了。
人定胜天！Top
39 楼ritchiex（hxx）回复于 2001-11-15 01:19:55 得分 20
这和第九届IOI的第3题很象，那题是在地图上给点标上地名，记得当时max是1000*1000的地图，和max是1000的地点。规模相当大，用一般的回溯没法在规定的时间内完成，我做的时候用拉构造图论模型，和用贪心法求一个无向图的最大独立集，其算法比较简单，很容易实现。Top
40 楼mousubin（msb）回复于 2001-11-15 19:33:23 得分 0
ritchiex能给出具体一点的解释让大家讨论讨论吗?Top
