Closest point of a simplex to a random point
in [Matlab]
|
Prev: help for image restore
Next: MATLAB Dynamic tooltips
From: George Antonopoulos on 5 Jun 2010 08:06 I have 4 points forming a tetrahedron in 3D space. I also have another point in 3D space which definitely does not lie within the tetrahedron. What I want is to find the point on the tetrahedron that is closest to the point out of it. I'm thinking about using barycentric coordinates and solving a constrained Least squares system to find these coordinates. However my implementation keeps returning the same result(which is of course wrong). The code I use is the following: function Bar = Barycentric(Points3D) %Construct the tranfromation matrix for barycentric coordinates T = Points3D(:,1:4); %Constrcut the Right hand side matrix of the equation R = Points3D(:,5); %Construct the constraint matrices that will force point m within the %tetrahedron and yield true barycentric coordinates lb = zeros(4,1);%biger than 0 ub = ones(4,1);%smaller than 1 Aeq = ones(1,4);%All coordinates sum up to... beq = 1; %...1 x0 = ones(4,1)/2.0;%Start from the middle %solve the system to acquire the barycentric coordinates Bar = lsqlin(T,R,[],[],Aeq,beq,lb,ub,x0,optimset('LargeScale','off','Display','off')); %We have 3 coordinates.The 4th is regained by subtraction from 1 %Bar = [Bar;1 - Bar(1) - Bar(2) - Bar(3)]; end The input is a matrix with 5 columns, 4 for each of the tetrahedron's edges, and 1 for the point out of it. The result is always [1 0 0 0]. An exmple input is 1.3672 0.0398 0.1414 0 15.2761 0.0952 -0.6948 -0.7246 0 -9.8303 -0.0112 -0.1615 0.1534 0 -42.8882 What could I be doing wrong? Thank you in advance
From: George Antonopoulos on 5 Jun 2010 08:14 I corrected the x0 to be 0.25s instead of the 0.5s I had, but this was not the problem.
From: Bruno Luong on 5 Jun 2010 08:19 "George Antonopoulos" <georanto(a)gmail.com> wrote in message <hudejb$7a7$1(a)fred.mathworks.com>... > I have 4 points forming a tetrahedron in 3D space. I also have another point in 3D space which definitely does not lie within the tetrahedron. > What I want is to find the point on the tetrahedron that is closest to the point out of it. > I'm thinking about using barycentric coordinates and solving a constrained Least squares system to find these coordinates. However my implementation keeps returning the same result(which is of course wrong). Not sure, but this is quadratic programming Min |x|^2 A*x <= b x in R^3 A*x <= b is four constraints that give equivalently the half-plane intersection form of the simplex. Rather use QUADPROG to solve your problem. Bruno
From: Matt J on 5 Jun 2010 10:28 "George Antonopoulos" <georanto(a)gmail.com> wrote in message <hudejb$7a7$1(a)fred.mathworks.com>... > I have 4 points forming a tetrahedron in 3D space. I also have another point in 3D space which definitely does not lie within the tetrahedron. > What I want is to find the point on the tetrahedron that is closest to the point out of it. > I'm thinking about using barycentric coordinates and solving a constrained Least squares system to find these coordinates. ================== If it's just a tetrahedron, this seems needlessly complicated. There are at most 14 possible solutions all of which you can check individually. Either the minimum projected distance is attained on one of the 4 faces or 6 edges or 4 vertices. Just find the unconstrained orthogonal projection of the point (analytically) onto the 4 faces of the tetrahedron and check that the minimum among those 4 projected distances is attained at a point that is on the tetrahedron. If it is, you're done. If not, project onto all 6 edges of the tetrahedron and do likewise. If the solution isn't attained there, project onto all 4 vertices, etc...
From: Matt J on 5 Jun 2010 11:59
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hudmtk$asa$1(a)fred.mathworks.com>... > Just find the unconstrained orthogonal projection of the point (analytically) onto the 4 faces of the tetrahedron and check that the minimum among those 4 projected distances is attained at a point that is on the tetrahedron. If it is, you're done. > > If not, project onto all 6 edges of the tetrahedron and do likewise. If the solution isn't attained there, project onto all 4 vertices, etc... ==================== Sorry, I was incorrect to say that you could search over the faces first, then edges, then vertices... You need to check the unconstrained orthogonal projections onto all those 14 subspaces intersected by the polyhedron. Then, among those, you search for the one with the minimum distance that also lies in the tetrahedron. |