# Finding a cone from 3D data

I have data in form of many 3D coordinates (say $(x_1,y_1,z_1)...(x_n,y_n,z_n)$).

EDIT - The points are known to shape something similar to the top of a lemon. Assuming we know which point is the supposed apex, we want to derive a cone (one nappe) and measure it's angle.

Is there a way to derive a (EDIT) circular cone from this data, noting the points aren't necessarily part of the surface of the desired cone?

Sort of a "least squares" method for 3D.

Perhaps the easier/more plausible answer is "flattening" the data to 2D and then using least squares.

EDIT - elaborating on "flattening".

The meaning is to take a plane cutting through the "cone" to create a "triangle". If we do this 180 degrees and put all the results on a single plane, we get something close to an upside-down V. We mirror one side of the V over, and the result in a group of points - we find the closest line with least squares, then by rotating the line around it's top we get a cone which is closest to all points. That's the theory.

How would either be done?

-
By not necessarily on the cone, do you mean they might be "inside" the cone properly, or do you mean the points should fit to the surface of a cone as well as possible? –  hardmath Feb 6 '13 at 15:01
They might be on the surface, inside or out. I'm looking for the closest match. –  JNF Feb 6 '13 at 15:04
But you want to minimize the points distance to the surface? –  hardmath Feb 6 '13 at 15:09
Lets say you flatten to 2D by taking the intersection of a plane with the linear span of the points (through the origin). The intersection of the cone through the same plane will be an ellipse and points in it - is that how you see it? (In general the points themselves may not be contained in the plane) –  alancalvitti Feb 6 '13 at 15:09
You don't have to go to 2D to do least squares. You could do it in any vector space. For example, fitting a non-circular cone centered at the origin would be easy. It's the circularity which has me worried, as it introduces quadratic terms. Might be you'll have to find a best fitting cone first, and circularize that later on. –  MvG Feb 6 '13 at 15:47

Revised: From the clarifications it appears that the conical approximation of data points is only a rough one. However the apex is known, which leads to a revised suggestion of projecting points onto a sphere centered at the apex, which would lead to a rough circle of points on the sphere (these points would be exactly on a "small" circle of the sphere if the original data were actually on a cone).

Given the points on a sphere, one might proceed by fitting a small circle (great circles on a sphere being a special case) in a total least squares sense, i.e. minimizing the sum of squares of spherical distances from points to the fitted circle. This is a nonlinear problem, but it involves only three parameters (the radius and two coordinates for center of the circle). See Fujiki and Akaho, 2007 for exposition of both the 2D and higher dimensional analogs, and its references to the literature.

Your interest seems primarily to be identification of the axis of rotation, i.e. the pole that corresponds to the spherical circle. See here for some software tailored to this problem.

I think we should be careful about an approach that assumes points having a roughly uniform distribution over (around) the surface of a cone. If they were, it would make spotting a "V" shape in a slice of the data more likely, but perhaps there are more robust approaches (less dependent on an even sampling of points).

[Something else to keep in mind is that mathematically a cone proceeds in both directions of the axis through its apex. Therefore an ideal slice of the data through a plane containing the apex might reveal an "X" rather than a "V" shape.]

One possibility would be to assess for a candidate "apex" point $A$ of a cone, what axis gives the most tightly clustered slopes of lines passing through the sample points and the "apex". The axis is generated by a unit vector $U$ from $A$, and the slopes through sample point $P$ can be associated with a dot product of $U$ with $P - A$ divided by $||P - A||$.

In fact we might weight these slopes so that samples close to $A$ are less important than points far away (since the points close to $A$ are close to the cone regardless of what axis is chosen), and this suggests weighting by $||P - A||$, thereby cancelling the division used above.

This replaces the search for a "good slice" of the data with a search for a good approximation of the cone's apex.

The problem is of some importance in the field of computer vision and robotics. In this book chapter by Chernov and Ma, Least Squares Fitting of Quadratic Curves and Surfaces (2011), some improvements are sought using a "fast projection" method of Dave Eberly. The authors treat three non-degenerate quadratic surfaces in 3D, ellipsoids, hyperbolic paraboloids, and hyperboloids of one sheet, and mention without details that elliptic paraboloids and hyperboloids of two sheets can be treated similarly. A cone, however, is a degenerate quadric surface, intermediate between the hyperboloids of one and two sheets. I'd expect that the procedures described by Chernov and Ma would adapt readily to this specialization.

-
Thank you, many interesting thoughts put there. BTW, our case is that the only thing we know for sure is the point being the apex. (see comments on question) –  JNF Feb 10 '13 at 7:12
@JNF: I understand you to say that the apex of the cone is known (given), and that we want to approximate the points with a single nappe of a (circular double) cone. These are sufficiently important points that I recommend you edit the question to include them (or if you wish I'd be glad to edit it for you). Knowing the apex reduces the number of parameters to fit from six to three. –  hardmath Feb 10 '13 at 13:27
Thank you. I updated the question. –  JNF Feb 11 '13 at 7:33
Thank you! I update my answer. It's a pretty interesting problem. –  hardmath Feb 11 '13 at 16:21