Algorithm to project light and detect if a given point falls within it?

Question

Basically, projecting light like a flashlight, and checking if a point - I only need to check for a point, but it wouldn't hurt to be able to check for more than one - is in the area illuminated by it or not.

Also, I assume most (all?) algorithms work in 2D/3D, but would it be possible to use one that works in an N-dimensional space? I'm only interested if it's usable for an arbitrary number of dimensions with a reasonable complexity.

Is there geometry that the light is hitting that we need to take into consideration, or is this in empty space and you just want to determine if a point lies in a n-dimensional cone? — John Kugelman, Jul 25 '10 at 02:46
@John Kugelman: Only nodes and light cones, so no geometry. But the light cones cannot overlap, so if neighboring cones were to "touch", I'd have to consider that a "line" between them. Each coordinate could be considered in the [-1,1] range if it makes it easier. — gendum, Jul 25 '10 at 02:55
possible duplicate of [How do you test if a point is inside a circle?](http://stackoverflow.com/questions/481144/how-do-you-test-if-a-point-is-inside-a-circle) — James Black, Jul 25 '10 at 03:04
@James Black: Projecting light isn't the same problem as creating a circle around a point, and I'm interested in a solution that works for n >= 2. — gendum, Jul 25 '10 at 03:13
@gendum - if you pick a point in n-space, unless light is being displayed differently in your n-space, in real space if I pick a spot at (x,y,z) I go from a light cone to some shape, such as a circle, as I am not interested in only whether my point is within the light cone, so looking for a 3D solution would be meaningless. — James Black, Jul 25 '10 at 03:17
@pst: What exactly are you asking? You know I can't draw it. But the idea is that space would be divided around a central point, "illuminating" different areas around it, depending on the equation/algorithm used to generate the "light". Like I said, I can't draw it, but you can get the idea in either 2D or 3D. — gendum, Jul 25 '10 at 03:22
@James Black: I don't understand what you mean. Suppose I have 20 points on a 10 dimensional space. First, I need to know if there exists an algorithm to divide space so that each one is "illuminated" by a different "light cone", all originating at a given/fixed point. Second, I need to know whether a given point belongs to the cone or not. I can't see how a circle has anything to do with it. — gendum, Jul 25 '10 at 03:29
@gendum: Your first problem is easy. To solve, just form for each point the narrowest possible light cone which will still illuminate the point. If one of these cones illuminates two points, no solution is possible for the chosen origin. — Borealid, Jul 25 '10 at 03:33
@gendum: That depends on how "wide" your points are. If you're in a truly mathematical space, the cone you want is infinitely thin - it approaches a ray originating from your origin and continuing through the illuminated point. If the points have a "width", you need to generate the cone which transcribes this width when it reaches the point. — Borealid, Jul 25 '10 at 03:56
@Borealid: Each coordinate would be in the [-1, 1] interval. Points have no width. — gendum, Jul 25 '10 at 04:17

Drew Hall · Answer 1 · 2010-07-26T08:42:25.790

Assuming you've got a normalized vector n pointing in the direction of the light cone, a light at Pl, and test point at Pp, and half-cone angle theta, you can do the test like this (independent of the dimensionality of your space):

vector Vl = Pl + n
vector Vp = Pp - Pl

phi = acos(dot(Vl, Vp) / (||Vl|| * ||Vp||))

if phi <= theta
  p in light cone
else
  p not in light cone

Here dot(a,b) is the dot product of the two vectors (a1*b1 + ... + an*bn) and ||a|| is the magnitude of vector a, sqrt(a1*a1 + ... + an*an).

The basic idea is to figure out the angle between the centerline of the light beam and the vector from the light source to the point of interest. If that angle is bigger than the spotlight (half-)angle, the point of interest is outside of the beam--otherwise it's inside.

Note that real lights don't really cutoff so sharply, but this will get you started.

Algorithm to project light and detect if a given point falls within it?

1 Answers1