注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东南隅

wantnon的blog

 
 
 

日志

 
 
 
 

正方形覆盖  

2009-08-18 01:46:57|  分类: 数模 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

给平面上若干个点及一特定边长的正方形,要求用正方形覆盖尽量多的点。
解:
设正方形半径为r(给定值),则正方形的方位可以用三个数m,n,a表示,
其中(m,n)为左顶点,a为靠左的斜率为正的那个边与X轴夹角(0<=a<=pi/2)。
image
首先要解决的问题是如何判断一给定点q:(x,y)是否在正方形内(包括边界):
可以先将q点与正方形同时平移(-m,-n)使p4与原点重合,然后逆时针旋转q点及正方形使p4p1与Y轴重合。
设此时q点变换到q’:(x’,y’)的位置,则只要有0<=x’<=r及0<=y’<=r即可判定q在正方形内,否则不在。
而由平移和旋转公式易得:
x’=(x-m)*sin(a)-(y-n)*cos(a)
y’=(x-m)*cos(a)+(y-n)*sin(a)。
接下来就是搜索算法,
下面是一个初步尝试,用的是最简单的随机覆盖多次实验取最优值的方法:
(对此法的改进见另一张帖子“正方形覆盖(改进)”)
matlab程序:

%随机生成(0,0)-(1,1)的np个点
np=100;%点数
x=rand(1,np);
y=rand(1,np);
r=0.1;%正方形边长
%mcount,mm,mn,ma记录最好的一次实验的count,m,n,a值
mcount=-1;
mm=[];
mn=[];
ma=[];
ntry=10000;%实验次数
for turn=1:ntry
    m=rand();
    n=rand();
    a=rand()*pi/2;
    count=0;%本次实验覆盖的点数
    for i=1:length(x)
        %判断x(i),y(i)是否被覆盖
        x_(i)=(x(i)-m)*sin(a)-(y(i)-n)*cos(a);
        y_(i)=(x(i)-m)*cos(a)+(y(i)-n)*sin(a);
        if x_(i)>=0&&x_(i)<=r&&y_(i)>=0&&y_(i)<=r
            count=count+1;
        end
    end
    %记录最优值
    if count>mcount
        mcount=count;
        mm=m;
        mn=n;
        ma=a;
    end
end
%画点
plot(x,y,'o','Markersize',3);
hold on;
%设置标题
title({'',...%第一行空出为了美观
    ['随机生成(0,0)-(1,1)上',num2str(np),'个点,用边长',num2str(r),'的正方形随机覆盖'],...
    ['共进行了',num2str(ntry),'次实验'],...
    ['最好的一次覆盖了',num2str(mcount),'个点']});
%最优一次实验中矩形的四个顶点坐标p1,p2,p3,p4
p1=[mm+r*cos(ma),mn+r*sin(ma)];
p2=[mm+r*cos(ma)+r*sin(ma),mn+r*sin(ma)-r*cos(ma)];
p3=[mm+r*sin(ma),mn-r*cos(ma)];
p4=[mm,mn];
%画正方形
plot([p1(1),p2(1),p3(1),p4(1),p1(1)],[p1(2),p2(2),p3(2),p4(2),p1(2)],'-r');
axis equal;

运行结果:
image

  评论这张
 
阅读(154)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018