# search algorithm in the volume of a cone.

3 views (last 30 days)
Nikhil Tej on 22 May 2012
I am trying to for search algorithm to determine all the points that are available in the volume of a cone. I have flight simulated data of latitude, Longitude and altitude information for 3 minutes time interval generated every second . I would like to search for any of these locations that fall into the cone of specify volume considering that we have the location of the cone.
Walter Roberson on 22 May 2012
"all points" would be an infinite number unless you are using a discretized grid.
Geoff on 22 May 2012
It seemed that way in the first sentence, but the last sentence suggests that a point in/out test for a cone is required. I chose to interpret it that way, because the other interpretation is pretty illogical. =) I think it was just poor choice of wording.

Geoff on 22 May 2012
Well, you need a point that defines the apex of the cone, a vector definining the cone's major axis, and the half-angle (angle between one edge of the cone and the major axis). If you're talking about cone volume, you also need to know how tall it is.
Consider also that latitude, longitude and altitude are actually spherical co-ordinates.
Anyway, if you know the half-angle, then you immediately have an in/out test. If you define your cone's major axis such that it begins at the apex and points in the direction that the cone expands, then you just need to find the angle between these two lines:
vec1 = testpoint - apex;
vec2 = coneaxis;
If the angle is less than or equal to the half-angle of the cone, the point is inside. Since some angle calculations also work on points inside the negative cone (out the other side), you should test that the dot product of those two vectors is positive.
If you have a base, you just need to project vec1 onto the normalised vec2 (with dot), which gives you the perpendicular distance of your point from the apex. If that is less than or equal to your cone's "height" then it is inside.

the cyclist on 22 May 2012
It sound like this submission in the File Exchange might be helpful to you: