检测使用C＃光突起和交叉点在二维空间(Detecting light projections and

的光源是在二维空间中的实体，在一个单一的坐标位于。

有多个光源周围的不同位置，并且每个放出8条射线光在方向N，S，E，W，NW，NE，SW，SE。所有灯光的坐标是已知的。

我需要计算网格内的这些射线的所有路口。

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:

我的答案是基于关闭一个链接的问题您的评论的：是也有一个简单的方法来确定其坐标光会是怎么样相互交叉的两个给分？它看起来像你想确定路口由光源提供的光线的点。

从你已经描述的那样，水平/垂直的情况下很容易。两个源之间的点描述的交叉点。对角线案件更棘手，而且我认为接近它只是计算的直线相交的最简单方法。

可以描述每个对角/反对角如由矢量方程描述一个线ray = s + u * d其中， s是光源的位置和d是光线的方向（或者[1, 1] [1, -1] [1, 0]或[0, 1] 你有这样的公式四为每个源，每个方向一个。现在，要找到对角线的交叉点，只要找到非平行线的两个源（一对将是平行的，所以不能交点）的交叉点。

很抱歉，如果这是不明确的，我会尝试更新此。

更新

作为一个简单的优化，光线相交对角线当且仅当该直线距离（ |x1 - x2| + |y1 - y2| ）的源极之间是均匀的。我认为有，有助于简化您的情况下，其他条件。

这里有一个推导找到你所需要的公式。我们先从两条射线：

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

在直角坐标系：

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

在交叉点处， ray1x = ray2x和ray1y = ray2y ：

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

为了方便起见，我们可以隔离和消除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

然后解决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)

为了找到u2你可以估算上述或使用一个方程：

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

所以你有它。两个方程以求解u1和u2给定源位置s1 ， s2和光线方向d1 ， d2 。您只需接上u1和u2的值到原ray方程和你有一对交叉点。在你的情况，当且仅当一个存在交集u1和u2是整数。有其中一个被零除发生时，当方向是一个的情况下[1, 0]和[0, 1]但该情况下是微不足道的解决（来源非零坐标形成的交叉点的坐标）。

Answer 2:

假设你有一个固定的坐标平面大小，你会做这些计算多次在不同位置的光源，你可以做得比每个点迭代更好。

您可以创建四个布尔（或位）阵列。

卧式
VERTI
DIAGR
DiagL

并为我们的每一个光源，我们“项目”他们在那些一维数组。（图中我只示出了两个突起）。

投射到卧式和VERTI很简单。

突出在图中所示的DIAGR阵列上的点（x，y）是为x加y一样容易。

现在，你可以简单地走在所有网格点，看看它的预测至少2设置为true。

但是，我们可以做的更好，

例如，在本例中，我们可以通过走在VERTI阵列开始。

我们注意到，VERTI [0]设置为true，现在我们要看看它是否有卧式，DIAGR，DiagL相交。

我们计算，要检查与DIAGR（在我们的图片中的另一阵列）的交点，我们只需要查看是否DIAGR [0]，DIAGR [1]，DIAGR [2]，和DIAGR [3]为真，我们可以忽略该阵列的其余部分。

VERTI [0]的光可以在任何其元件与HORIZ相交。

VERTI [0]的光只能在DiagL与DiagL相交位置0,1,2，和3。

继续VERTI [I]的其余部分。

现在，我们可以做同样的事情寻找从真正卧式交叉[I]的与DIAGR和DiagL。

最后，我们走过去DIAGR并寻找与DiagL交叉点。

这将返回射线的所有交叉点的列表，而且其中还包括光源的点。

你既可以忽略那里有点源发生的所有交叉点，或使用一些技巧来解释这些要点。

Answer 3:

我从解除了数学在这里，

好了，所以每个点具有4“基数射线”，射线在于两点之间经过的无限线。

// 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); 
    }
}

为了让红雀我们可以扩展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);
}

为了找到两条射线，我们可以做的inersection

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);
    }
}

因此，要获得交点的两个点的枢机主教，

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

从而启用，

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

然后，我们可以使用这样此功能。

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);

显然，有很多重复的在这里，我还没有编译或测试这一点，但因为在它的小块，在数学似乎是相当有效的，我对业绩持乐观态度。

文章来源: Detecting light projections and intersections in 2D space using C#