Path: news.mathworks.com!not-for-mail
From: "zedong 
" <zdongwu@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: How to get the intersection point coordinate between polygon and segment
Date: Sun, 14 Dec 2008 04:48:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 75
Message-ID: <gi2362$p41$1@fred.mathworks.com>
References: <gi0epq$lk3$1@fred.mathworks.com> <gi0nj2$f1r$1@fred.mathworks.com> <gi0omm$ov6$1@fred.mathworks.com> <gi0rih$ljc$1@fred.mathworks.com>
Reply-To: "zedong 
" <zdongwu@gmail.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1229230082 25729 172.30.248.37 (14 Dec 2008 04:48:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 14 Dec 2008 04:48:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1639198
Xref: news.mathworks.com comp.soft-sys.matlab:506817


"Matt" <mjacobson.removethis@xorantech.com> wrote in message <gi0rih$ljc$1@fred.mathworks.com>...
> I had some bugs in my previously posted code. Here it is again corrected (hopefully).
> 
> 
> function c=cutpoints(a,b)
> %find intersection points of line segment with polytope
> %
> % c=cutpoints(a,b)
> %
> %Rows of a define polytope vertices
> %Rows of b are line segment end points
> %Rows of c are intersection points
> 
> 
> c=nan(2);
> 
>  xx=b(1,:).';
>  yy=b(2,:).';
>  dd=yy-xx;
>   
>  %[AA,bb]=vert2con(a);
>  [AA,bb]=vert2con_special(a);
>  
>  
>  CC=AA*dd;  qq=bb-AA*xx;
> 
>  db=(CC==0); 
>  if any(qq(db)<0) %ray does not intersect polytope 
>     return    
>  end
>  
>  
>  %%%Max lower bound
>  
>  ii=CC<0; lb=qq(ii)./CC(ii);
>  
>  tmin=max(lb);
>  
>  %%%Min upper bound
>  
>    
>  ii=~ii; ub=qq(ii)./CC(ii);
>    
>  tmax=min(ub);
>    
> if tmin>1 | tmax<0, return, end %no intersection
>     
> tmin=max(tmin,0);
> tmax=min(tmax,1);
> 
>    c(1,:)=(xx+tmin*dd).';
>    c(2,:)=(xx+tmax*dd).';
> 
> 
> %%%%%%%%%
> function [A,b]=vert2con_special(a)
> 
> centroid=mean(a).';
> R=[0 1; -1 0];
> 
> A=diff([a;a(1,:)])*R;
> 
> b=sum(A.*a,2);
> 
> ii=(A*centroid>=b);
> 
> b(ii)=-b(ii);
> A(ii,:)=-A(ii,:);


Thank you very much.Thank you for your kind help.You have done it very well.At many cases.It's right.There are still two problem:
(1) I have tested that if   a=[0 0;1 0;0 1]  b=[-1 0;1 0];
the right answer must be c=[0 0;1 0] of course.But your code return c=[-1 0;1 0].It maybe a small bug.
(2)I will tell you that why I say that we should implement it by mex file.If I write it in mex file.I have tested that 1million by 1 thousand it only need less than 1 second.