Detecting light projections and intersections in 2

Question

A light source is an entity in 2D space that sits in a single coordinate.

There are multiple light sources around in various locations and each gives off 8 rays of light in directions N, S, E, W, NW, NE, SW, SE. The coordinates of all lights are known.

I need to calculate all intersections of these rays within the grid.

long width = int.MaxValue; // 2D grid width.
long height = int.MaxValue * 3; // 2D grid height.
List<Point> lights = a bunch of randomly placed light sources.
List<Point> intersections = calculate all possible intersections.

for (int i=0; i < lights.Count - 1; i++)
{
    for (int j=i + 1; j < lights.Count; j++)
    {
        // How to compare using integers only?
        // If that is not possible, what is the fastest alternative?
    }
}

Answer 1

My answer is based off of your comment on a linked question: is there also an easy way to determine at which coordinates diagonal rays of light intersect each other for two given points? It looks like you want to determine the points of the intersection for the rays given by the light sources.

From what you have already described, the horizontal/vertical cases are easy. The points between the two sources describe the intersection. The diagonal cases are more tricky, and I think the easiest way to approach it is just calculating line intersections.

You can describe each diagonal/anti-diagonal as a line described by a vector equation ray = s + u * d where s is the position of the light source and d is the direction of the ray (either [1, 1] ,[1, -1], [1, 0], or [0, 1]). You have four of such equations for each source, one for each direction. Now, to find the intersection of the diagonal, just find the intersection of the non-parallel lines for the two sources (one pair will be parallel, and so cannot intersection).

Sorry if this isn't clear, I'll try to update this.

Update

As a simple optimization, rays intersect diagonally if and only if the rectilinear distance (|x1 - x2| + |y1 - y2|) between the sources is even. I think there's other conditions that help to simplify your case.

Here's a derivation to find the equations you need. We start with two rays:

ray1 = s1 + u1 * d1
ray2 = s2 + u2 * d2

In cartesian coordinates:

ray1x = s1x + u1 * d1x
ray1y = s1y + u1 * d1y
ray2x = s2x + u2 * d2x
ray2y = s2y + u2 * d2y

At the intersection, ray1x = ray2x and ray1y = ray2y:

s1x + u1 * d1x = s2x + u2 * d2x
s1y + u1 * d1y = s2y + u2 * d2y

To make things easier, we can isolate and eliminate u2:

u2 = (s1x - s2x + u1 * d1x) / d2x
u2 = (s1y - s2y + u1 * d1y) / d2y

(s1x - s2x + u1 * d1x) / d2x = (s1y - s2y + u1 * d1y) / d2y
(s1x - s2x + u1 * d1x) * d2y = (s1y - s2y + u1 * d1y) * d2x

Then solve for u1:

(s1x - s2x) * d2y + u1 * d1x * d2y = (s1y - s2y) * d2x + u1 * d1y * d2x
u1 * (d1x * d2y - d1y * d2x) = (s1y - s2y) * d2x - (s1x - s2x) * d2y

u1 = ((s1y - s2y) * d2x - (s1x - s2x) * d2y) / (d1x * d2y - d1y * d2x)

To find u2 you can just evaluate one of equations above or use:

u2 = ((s2y - s1y) * d1x - (s2x - s1x) * d1y) / (d2x * d1y - d2y * d1x)

So there you have it. Two equations to solve for u1 and u2 given the source locations s1, s2 and ray directions d1, d2. You just plug in u1 and u2 values into the original ray equations and you have the intersections for one pair. In your case, an intersection exists if and only if u1 and u2 are integers. There's one case where a division by zero occurs, when the directions are [1, 0] and [0, 1], but that case is trivial to solve (the non-zero coordinates of the sources form the coordinates of the intersection).

Answer 2

Assuming you have a fixed coordinate plane size, and you will be doing these calculation many times for light sources in different positions, you can do better than iterating over every point.

You can create four bool (or bit) Arrays.

1. Horiz
2. Verti
3. DiagR
4. DiagL

and for each of our light sources, we 'project' them onto those 1-dimensional arrays. (in the picture I only show two of the projections).

Projecting onto the Horiz and Verti are simple.

Projecting a point (x,y) on the DiagR array shown in the picture is as easy as x plus y.

Now you could simply walk over all of the grid points, and see if at least 2 of its projections are set to true.

But we can do better,

For instance, in the example we can start by walking over the Verti array.

We notice that Verti[0] is set to true, now we want to see if it intersects with Horiz, DiagR, DiagL.

We compute that to check for an intersection with DiagR (the other array in our picture) we only need to see if DiagR[0], DiagR[1], DiagR[2], and DiagR[3] are true, and we can ignore the rest of that array.

The light of Verti[0] can intersect with horiz at any of its elements.

The light of Verti[0] can intersect with DiagL only at DiagL positions 0,1,2, and 3.

Continue for the rest of Verti[i].

We can now do something similar looking for intersections from the true Horiz[i]'s with DiagR and DiagL.

Lastly, we walk over DiagR and look for intersections with DiagL.

This will return you a list of all intersection points of rays, but which also includes the points of the light sources.

You could either just ignore all intersection points that occur where there are point sources, or use some ingenuity to account for those points.

Answer 3

I've lifted the maths from here,

Okay so each point has 4 "cardinal rays", a ray being a infinite line that passes between two points.

// A line in the form Ax+By=C from 2 points
public struct Ray
{
    public readonly float A;
    public readonly float B;
    public readonly float C;

    public Ray(PointF one, PointF two)
    {
       this.A = two.y - one.y;
       this.B = one.x - two.x;
       this.C = (this.A * one.x) + (this.B * two.x); 
    }
}

To get the cardinals we can extend PointF

private readonly SizeF NS = new SizeF(0.0F, 1.0F);
private readonly SizeF EW = new SizeF(1.0F, 0.0F);
private readonly SizeF NESW = new SizeF(1.0F, 1.0F);
private readonly SizeF NWSE = new SizeF(-1.0F, 1.0F);

public static IEnumerable<Ray> GetCardinals(this PointF point)
{
    yield return new Ray(point + NS, point - NS);
    yield return new Ray(point + EW, point - EW);
    yield return new Ray(point + NESW, point - NESW);
    yield return new Ray(point + NWSE, point - NWSE);
}

To find the inersection of two rays we can do

static PointF Intersection(Ray one, Ray two)
{
    var delta = (one.A * two.B) - (two.A * one.B);

    if (delta == 0.0F)
    {
        //Lines are parallel
        return PointF.Empty;
    }
    else
    {
        var x = ((two.B * one.C) - (one.B * two.C)) / delta;
        var y = ((one.A * two.C) - (two.A * one.C)) / delta;
        return new PointF(x, y);
    }
}

So, to get the intersections for the cardinals of two points,

public static IEnumerable<PointF> GetCardinalIntersections(
    this PointF point,
    PointF other);
{
    return point.GetCardianls().SelectMany(other.GetCardinals(), Intersection)
        .Where(i => !i.IsEmpty());
}

Which then enables,

public static IEnumerable<PointF> GetCardinalIntersections(
    this PointF point,
    IEnumerable<PointF> others);
{
    return others.SelectMany((o) => point.GetCardinalIntersections(o));
}

We can then use this functionality like this.

var point = new PointF(1.0F, 1.0F);

var others = new [] { new PointF(2.0F, 5.0F), new PointF(-13.0F, 32.0F) };

var intersections = point.GetCardinalIntersections(others);

Obviously there is lots of iteration here, I haven't compiled or tested this but since, at its nub, the maths seems fairly efficient I'm optimistic about performance.