请教 凸壳判断：递归函数+超出矩阵维

canglang

我想用下面的函数消去生成的随机多边形的凹点，使其成为凸多边形。其中用到了递归函数。
可是总是说我超出矩阵维！不知道是不是该函数的问题？！该子函数的代码如下：

function [S,R,n,x,y]=mydeleteconcave(S,R,n,x,y)
if S(n)>4                                                                           % 如果边数S(n)<=4,肯定为凸多边形
    for i=4:length(x)
        triangle1=det([x(i),y(i),1;x(i-2),y(i-2),1;x(i-1),y(i-1),1])
        triangle2=det([x(i-3),y(i-3),1;x(i-2),y(i-2),1;x(i-1),y(i-1),1])
        if triangle1.*triangle2>0
           continue
       else
           x(:,i-1)=[];y(:,i-1)=[];R(:,i-1)=[];S(n)=S(n)-1;   % 如果第i点为凹点，则消去第i-1点
           [S,R,n,x,y]=mydeleteconcave(S,R,n,x,y);
        end
     end
end
**: S为多边形的边数；
     R为以多边形内某点为心和各顶点形成的“半经”；
     n表示生成的多边形个数；
     x,y为第n个多边形的顶点坐标。

运行时总是显示：
??? Index exceeds matrix dimensions.

Error in ==> E:\matlab6.5\work\convexpolygon.m (myreuse)
On line 154  ==>         tri1=det([x(i),y(i),1;x(i-2),y(i-2),1;x(i-1),y(i-1),1])

Error in ==> E:\matlab6.5\work\convexpolygon.m
On line 45  ==> [S,R,n,x,y]=myreuse(S,R,n,x,y)

恳请各位高人指点迷津，小弟感激不尽！

[ 本帖最后由 canglang 于 2007-5-19 22:15 编辑 ]

canglang

算法描述：
1.(x,y)为原始多边形的顶点坐标集p1,p2,p3,...
2.按逆序排序各顶点
3.按序连线成一多边形
4.i=4，向前倒查，若p4,p2,p3构成的三角形与p3,p2,p1构成的三角形面积之乘积大于0，继续查下去，否则，删去第i-1点，并从头开始重新倒查（i=4,向前倒查，...）
5.最后得到凸壳的各个顶点

spano

4边形也可能是凹多边形。
系统提示的错误根本不在你贴出的程序段内.
推荐你debug 慢慢看矩阵的形状.

eight

原帖由 canglang 于 2007-5-19 22:12 发表

                               
登录/注册后可看大图

我想用下面的函数消去生成的随机多边形的凹点，使其成为凸多边形。其中用到了递归函数。
可是总是说我超出矩阵维！不知道是不是该函数的问题？！该子函数的代码如下：

function [S,R,n,x,y]=mydeleteconcav ...

使用变量前先预分配空间，具体请参阅 置顶贴：聚宝盆 中的精华贴

canglang

谢谢关注与提示！谢谢
对，4边形也可能是凹的！！

[ 本帖最后由 canglang 于 2007-5-20 21:06 编辑 ]

canglang

[quote]原帖由 eight 于 2007-5-19 23:28 发表

                               
登录/注册后可看大图

“使用变量前先预分配空间，具体请参阅 置顶贴：聚宝盆 中的精华贴 [/quote]“

S,R,n,x,y是调用此程序之前得到的已知值（S,n）或向量（R,x,y)!

triangle1和triangle2的值在每轮循环时自动替换。因此，对于该函数的错误提示我实在
是不知所措，因为我认为 这个子函数本身没有问题。可是在没有运用这个函数之前
我用的是如下代码：

%c=[];
%if S(n)>4
%    for i=4:length(x)
%        tri1=det([x(i),y(i),1;x(i-2),y(i-2),1;x(i-1),y(i-1),1]);
%        tri2=det([x(i-3),y(i-3),1;x(i-2),y(i-2),1;x(i-1),y(i-1),1]);
%        if tri1.*tri2>0
%             continue
%       else
%            c=[c,i-1];
%       end
%   end
%end
%x(:,c)=[];y(:,c)=[];      
%S(n)=length(x)-1;R(:,c)=[];

**：**: S为多边形的边数；
     R为以多边形内某点为心和各顶点形成的“半经”；
     n表示生成的多边形个数；即第n个多边形
     x,y为第n个多边形的顶点坐标。

这段代码能够成功运行，只是该段代码在记下某凹点下标后不能重新开始该段代码，而是继续下轮循环，
故用了[S,R,n,x,y]=mydeleteconcave(S,R,n,x,y)，于是才产生了错误！

[ 本帖最后由 canglang 于 2007-5-20 22:48 编辑 ]