4 Replies - 8578 Views - Last Post: 15 June 2012 - 06:12 AM

#1 AutumnStar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 13-June 12

Simple(?) Challenge: Vectors Hitting A Plane

Posted 13 June 2012 - 03:56 PM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Simple(?) Challenge: Vectors Hitting A Plane

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

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 line-plain 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.
Was This Post Helpful? 0
  • +
  • -

#3 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2990
  • Posts: 10,329
  • Joined: 08-August 08

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.
Was This Post Helpful? 0
  • +
  • -

#4 AutumnStar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 13-June 12

Re: Simple(?) Challenge: Vectors Hitting A Plane

Posted 14 June 2012 - 06:20 AM

View PostCTphpnwb, 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.
Was This Post Helpful? 0
  • +
  • -

#5 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2990
  • Posts: 10,329
  • Joined: 08-August 08

Re: Simple(?) Challenge: Vectors Hitting A Plane

Posted 15 June 2012 - 06:12 AM

View PostAutumnStar, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1