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: Sun, 14 Dec 2008 16:13:02 +0000 (UTC)
Organization: Xoran Technologies
Lines: 24
Message-ID: <gi3bae$5c9$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> <gi2362$p41$1@fred.mathworks.com> <gi38m1$h17$1@fred.mathworks.com> <gi3a15$qar$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1229271182 5513 172.30.248.35 (14 Dec 2008 16:13:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 14 Dec 2008 16:13:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:506899



>  Thank you very much.This time it's really right.Could you explain your compute method.The computation idea to me. I can change it into mex function.Thank you very much.

Sure. Any convex polygon/polyhedron, and in particular a triangle, can be expressed as a set of linear inequalities. In matrix-vector form, point z is in the polygon if it satisfies

A*z<=b

In my code, the subfunction vert2con_special takes the given triangle vertices and finds the corresponding [A,b].

Additionally, the parametric equation for a line segment between x and y is

z(t)=x+t*(y-x),    0<=t<=1.

Substituting z(t) into the polygon inequalities gives
  
(A*(y-x))*t<=(b-A*x)

You must find the minimum and maximum scalar t satisfying all of these inequalities. Once you have tmin and tmax, the intersection points are given by z(tmin) and z(tmax)

NOTE:  The requirement 0<=t<=1 ensures that z(t) will lie  on the line segment between x and y.  You must therefore threshold tmin and tmax to this interval appropriately.