Re: How to get the intersection point coordinate between polygon and segment

"zedong
" <zdongwu@xxxxxxxxx> wrote in message <gi0epq$lk3$1@xxxxxxxxxxxxxxxxxx>...
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).';
.

Relevant Pages

  • robust 3D triangle-triangle intersection test
    ... I wonder if there's any robust 3D triangle-triangle intersection predicate? ... It seems that the most widely used 3D triangle-triangle intersection routine is Tomas Moller's routine. ... For example, Moller's routine can correctly report the intersection for the above example based on certain epsilons, but will likely to fail on some other triangle pairs. ...
    (comp.graphics.algorithms)
  • Re: Families of Straight Lines
    ... Since every point of intersection ... Add the two diagonals; the ... the triangle case. ... If all intersection points are collinear then the configuration is ...
    (sci.math)
  • Ray-Triangle intersection, more details
    ... The tree dots are delimiting an invisible triangle "hovering" over the ... Intersection basically works, infact if you move the cursors in the ... var e1 = vec3.create; ...
    (comp.graphics.api.opengl)
  • Re: Detecting mouse click on a particular triangle
    ... Given that this is terrain geometry, you should be able to optimize ... intersection testing to only search a limited portion of the geometry. ... intersection as the selected triangle without having to search further. ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: Special Pascal Line
    ... ABC is a scalene triangle. ... > Let U the intersection point of tangents in B and C ...
    (sci.math)