Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: How to get the intersection point coordinate between polygon and segment
Date: Sat, 13 Dec 2008 16:24:02 +0000 (UTC)
Organization: Xoran Technologies
Lines: 64
Message-ID: <gi0nj2$f1r$1@fred.mathworks.com>
References: <gi0epq$lk3$1@fred.mathworks.com>
Reply-To: <HIDDEN>
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 1229185442 15419 172.30.248.37 (13 Dec 2008 16:24:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 13 Dec 2008 16:24:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:506747


"zedong 
" <zdongwu@gmail.com> wrote in message <gi0epq$lk3$1@fred.mathworks.com>...
> How to get the intersection point coordinate between polygon and segment;
> for example(a is a triangle a(i,:) is the ith coordinate of the triangle.b is an segment,b(i,:) is the side point coordinate):

I believe the function below does the job. It employs vert2con from the FEX

I also tested its speed on 10000 successive triangles using both a for loop and cellfun()

a=[0 0;1 0;0 1]; b=[0.4 0.4;1 1];
A=cell(1,10000);B=A;  A(:)={a}; B(:)={b};

>> tic, C=cellfun(@cutpoints,A,B,'UniformOutput',false); toc
Elapsed time is 11.256645 seconds.

>> tic, for ii=1:10000, c=cutpoints(a,b); end,toc
Elapsed time is 11.231848 seconds.

Not much difference, so I guess you'll have to be the judge of  whether it's fast enough.


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);
 
 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
 lb=zeros(size(CC));
 
 ii=CC<0; lb(ii)=qq(ii)./CC(ii);
 
 tmin=max(max(lb),0);
 
  %%%Min upper bound
  
   ub=ones(size(CC));
   
   ii=CC>0; ub(ii)=qq(ii)./CC(ii);
   
   tmax=min(min(ub),1);
   
   c(1,:)=(xx+tmin*dd).';
   c(2,:)=(xx+tmax*dd).';