Closest point of a simplex to a random point
in [Matlab]
|
Prev: help for image restore
Next: MATLAB Dynamic tooltips
From: John D'Errico on 5 Jun 2010 12:10 "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <huds88$h5$1(a)fred.mathworks.com>... > "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. You don't think that such a complete search is also needlessly complex? Just write it in any of several forms, as a QP, or an LDP* problem (if you have an LDP solver at hand), or in a form that lsqlin can handle, and be done with it. Any of those tools would suffice. John * LDP = Least Distance Programming, described in Lawson and Hanson.
From: Matt J on 5 Jun 2010 15:40 "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hudsst$cec$1(a)fred.mathworks.com>... > > You don't think that such a complete search is also > needlessly complex? Just write it in any of several forms, > as a QP, or an LDP* problem (if you have an LDP solver > at hand), or in a form that lsqlin can handle, and be > done with it. Any of those tools would suffice. ======== But these are iterative solvers, are they not? In terms of speed, it seems like you're gambling that it will take fewer than 14 iterations to complete (the equivalent number of function evaluations that the complete search would take).
From: Bruno Luong on 5 Jun 2010 16:08 "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hue96m$10n$1(a)fred.mathworks.com>... > But these are iterative solvers, are they not? QP is iterative but converge in finite number of steps (I believe it's NP hard problem theoretically, but who care at only 3 variables). A well implemented method (anti cycling, etc...) will find the constraints set without exploring them all (i.e., 14 for 4 constraints). Now a day people (I) use daily QP with thousands variables (some might go up to millions variables), and it works just fine. Bruno
From: John D'Errico on 5 Jun 2010 16:22 "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hue96m$10n$1(a)fred.mathworks.com>... > "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hudsst$cec$1(a)fred.mathworks.com>... > > > > > You don't think that such a complete search is also > > needlessly complex? Just write it in any of several forms, > > as a QP, or an LDP* problem (if you have an LDP solver > > at hand), or in a form that lsqlin can handle, and be > > done with it. Any of those tools would suffice. > ======== > > But these are iterative solvers, are they not? In terms of speed, it seems like you're gambling that it will take fewer than 14 iterations to complete (the equivalent number of function evaluations that the complete search would take). While they are iterative, the amount of computation, tests, branches, potential for bugs in hand written code to test every face and edge is "needlessly complex". While neither method will be computationally intensive, I would guess that any method you use will take a similar amount of cpu time. QP will be pretty fast, and it is probably written with more attention paid to efficiency and accuracy than will be hand written code written by a somewhat novice. John
From: Bruno Luong on 5 Jun 2010 18:13
"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <huear3$h5a$1(a)fred.mathworks.com>... > > QP is iterative but converge in finite number of steps (I believe it's NP hard problem theoretically, but who care at only 3 variables). A well implemented method (anti cycling, etc...) will find the constraints set without exploring them all (i.e., 14 for 4 constraints). I would add that there are actually 2^4 = 16 possible number of active sets for 4 constraints. But because the tetrahedron is not empty, and because the point is outside it, two of the 16 actives sets (no constraint and all 4 active constraints) never occur. Which makes the count 14. Bruno |