So, here is my program description so far: it randomly generates vectors isotropically (all directions uniformly). I have a finite plane sitting somewhere in space. Now, my programs generates these vectors through a finite space randomly, isotropically, and then "traces" these vectors out to see if they hit the plane or not. It then gives the coordinates where it hit the plane. NOW, what I need to do is: "draw" evenly spaces squares on this plane. When these vectors miss a square it counts as a "miss" and when it hits a square, it counts a "hit." I'm trying to figure out how to go about drawing these squares and checking to see if the vector hits any of them as efficiently as possible. I have to do this process about a million times, so it has to be somewhat efficient. One way I thought about doing this is by giving the program the spacing dimension and the dimension of one square. It then generates a list of coordinates (four points for each square) and checking each vector against it. I'm worried though since there are about 10000 squares, so that would be incredibly inefficient to check 1 million vectors against 10000 coordinates. It would take forever. I was just wondering of anyone had a better idea (or hints?) on where to go from here.
Thank you.
Simple(?) Challenge: Vectors Hitting A Plane
Page 1 of 14 Replies  11082 Views  Last Post: 15 June 2012  06:12 AM
Replies To: Simple(?) Challenge: Vectors Hitting A Plane
#2
Re: Simple(?) Challenge: Vectors Hitting A Plane
Posted 13 June 2012  05:38 PM
you could use spatial hashing on the X and Y plain then again on either the XZ or YZ plain(maybe both) to limit the number of lineplain intersections that need to be checked. lines and plains can be in an arbitrary number of cells(buckets that correspond to the hash code) with plains you would test each of the points to see which buckets it's ends land in then include everything in between. with lines it would be trickier but still possible.
you *may* be able to adapt something like Sweep and Prune here but I'm not entirely sure how that would be done given.
Those are the typical ways around the O(n^2) algorithm.
you *may* be able to adapt something like Sweep and Prune here but I'm not entirely sure how that would be done given.
Those are the typical ways around the O(n^2) algorithm.
#3
Re: Simple(?) Challenge: Vectors Hitting A Plane
Posted 13 June 2012  07:50 PM
Suppose this finite plane is x units by y units. If a vector intersects with the plane you can calculate the point's coordinate with respect to x and y to determine which square it hit. All others would be a miss. If it doesn't hit the plane then all squares count a miss.
#4
Re: Simple(?) Challenge: Vectors Hitting A Plane
Posted 14 June 2012  06:20 AM
CTphpnwb, on 13 June 2012  08:50 PM, said:
Suppose this finite plane is x units by y units. If a vector intersects with the plane you can calculate the point's coordinate with respect to x and y to determine which square it hit. All others would be a miss. If it doesn't hit the plane then all squares count a miss.
I know this. This is a slow, brute force method though. You'd have to check millions of vectors against thousands of squares. This would take a long time. I was asking if anyone knew a better (and faster) method to go about doing this. Thanks for the response though.
#5
Re: Simple(?) Challenge: Vectors Hitting A Plane
Posted 15 June 2012  06:12 AM
AutumnStar, on 13 June 2012  06:56 PM, said:
It then generates a list of coordinates (four points for each square) and checking each vector against it. I'm worried though since there are about 10000 squares, so that would be incredibly inefficient to check 1 million vectors against 10000 coordinates.
If you need to check 1 million vectors then that's how many you need to check. It's still more efficient than trying to check 10000 squares against 1 million vectors.
Page 1 of 1
