Finding a point inside of a cone/cube intersect

I am trying to solve a puzzle with a very large search space, and I think it would be most helpful if I could find points that lie within a certain region of the cube, defined by a cone.

That is, the points that define the cube are:

(0,0,0),

(0,0,1),

(0,1,0),

(0,1,1),

(1,0,0),

(1,0,1),

(1,1,0),

(1,1,1)

Now imagine a cone, with the point always being at (.5,.5,.5), and the base of the cone extends beyond the cube. I would like to be able to vary the base diameter, and then find some random point that exists where the cone and cube intersect.

Perhaps a graphic will help explain what I'm needing:

http://i214.photobucket.com/albums/c...r/gd_cone1.jpg

The orange dot represents the center of the unit cube.

The brownish rod represents a vector defining the center of the cone.

And of course the cone is obvious there.

The blue represents the intersect between the cone and the cube.

So, I want to write a function (pseudo code is fine), where I pass it the cone diameter, and the x,y,z location where the vector intersects the cube, and I'd like to have the function return any random point that is within the intersection.

Make sense? I'll not keep rambling. If you have any questions, please let me know.

Thanks in advance for any help,

Neil

P.S. - First post! :) Glad to be here!

Re: Finding a point inside of a cone/cube intersect

Hi SnackWhack,

I am assuming that you want the point to be uniformly distributed in the region of the cone intersected with the cube.

Here is one approach: Generate a point (x,y,z) inside the cube by using your favorite random number generator to generate three Uniform(0,1) numbers x, y, and z. Test to see if the point is inside the cone. If it is, keep it. If not, throw it away and try again.

As for testing to see if the point is inside the cone, let's say the angle of the cone with its axis is $\displaystyle \theta$. Compute the angle $\displaystyle \phi$ between the axis and the vector from the vertex to (x,y,z). You can use a dot product for this. If $\displaystyle \phi \leq \theta$ (or, equivalently, $\displaystyle \cos \phi \leq \cos \theta$), the point is in the cone.

[edit] That should be $\displaystyle \cos \phi \geq \cos \theta$ above. [/edit]

Re: Finding a point inside of a cone/cube intersect

Yep, I'm going to need some more hand holding here.

The problem is, even though I completed Calc 3, that was over 10 years ago, and I'm primarily a computer programmer. So, most of my math training has evaporated out of my head.

Can you walk me through this in layman's terms, assuming you have the time? lol

Also, One concern I have is speed. I'm doing this for a recreational mathematics contest. I currently have a program chugging away trying to find good solutions, but it's a bit slow. The cone idea I think will speed up my search considerably.... or not at all. We'll see. So, I'm concerned about just choosing a random point and testing to see if it's within the cone. If it's not, try again. That guessing will slow the algorithm way down I think. Can you think of any way to ensure the first random point chosen is definitely within the cone?

And yes, your assumptions are correct. The chosen points should be evenly distributed.

Thanks,

Neil

Re: Finding a point inside of a cone/cube intersect

Oh, BTW, I think I forgot to mention, the chosen point should exist on the surface of the cube, not the interior. I'm not sure if that makes things easier or more difficult, but thought I should mention it.

Re: Finding a point inside of a cone/cube intersect

Quote:

Originally Posted by

**SnackWhack** Oh, BTW, I think I forgot to mention, the chosen point should exist on the surface of the cube, not the interior. I'm not sure if that makes things easier or more difficult, but thought I should mention it.

So you want the point in the interior of the cone but on the surface of the cube, is that correct? (That's not what I understood initially, so my original approach won't work without modification.)

Re: Finding a point inside of a cone/cube intersect

That's correct, sorry for not specifying that before. One of the x,y or z coordinates will always be 0 or 1. Thus all points will reside on a face, edge, or corner of the cube.

Thanks,

Neil

Re: Finding a point inside of a cone/cube intersect

awkward, and anyone else interested, here is the description of the problem I'm working on:

Virtual Source Programming Contests

Anyone here is welcome to join in as well. This particular challenge is proving quite difficult for a lot of people.

Re: Finding a point inside of a cone/cube intersect

awkward,

Perhaps another graphic will help you visualize what I'm trying to do.

Imagine multiple rays emitting from the center of the cube like this:

http://i214.photobucket.com/albums/c...wer/gdrays.jpg

Now, imagine a cone around each of those rays. Each cone's tip is at the center of the cube. I plan on slowly decreasing the diameter of the base of the cone for each iteration of my algorithm. As you can imagine, the cone will slowly become a line. Or rather, a cone with a base diameter of zero. As soon as it reaches zero (or some cut off that I desire), I'll call that a solution, and start the process over. If the solution is my best yet, I'll store it away and submit it to the contest site later.

That being said, you can see why the random approach isn't a very good one since the area of the cone will become smaller and smaller, thus making it more and more difficult to find a qualifying point.

Am I making any sense, or just rambling now? Heh!

Thanks for your help awkward, and anyone else that wants to join in.

Neil