2
$\begingroup$

Suppose that we have $n$ points in 3D.

I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum.

I read this article. However, I need an algorithmic solution.

So far, this answer from SO was the simplest one. However, this solution projects the points onto $z=0$ plane all the time.

Could you help me to write the algorithm? I'll code it in Java.

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't know what you mean by "However, I need an algorithmic solution." Least squares is an algorithmic solution. It does have the problem that it doesn't solve your problem -- it solves a related optimization problem, but not your problem -- but it's certainly an algorithmic solution, as there are standard algorithms to compute the least squares fit plane. $\endgroup$
    – D.W. ♦
    Commented Jan 13, 2015 at 0:30

1 Answer 1

Reset to default
1
$\begingroup$

This is exactly the problem that PCA (principal component analysis) solves. So, use PCA -- that provides an algorithmic solution to this problem. See this explanation over at Statistics.SE for an explanation of why PCA solves this problem.

[Least squares fitting is almost a solution to this problem, except that it doesn't minimize the orthogonal distance -- it minimizes the distance along the $y$ axis, or any single axis you might pick.]

If for some reason you didn't want to use PCA, you could frame this as a mathematical optimization problem (the objective function is the total orthogonal distance) and then use any standard optimization technique -- e.g., gradient descent -- to find an approximate optimum.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.