1

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

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

我需要计算网格内这些光线的所有交点。

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?
    }
}
4

3 回答 3

3

我的回答是基于您对一个链接问题的评论：是否还有一种简单的方法可以确定两个给定点的对角线光线在哪些坐标处相互交叉？看起来您想要确定光源给出的光线的交点。

从您已经描述的内容来看，水平/垂直案例很容易。两个源之间的点描述了交叉点。对角线的情况比较棘手，我认为最简单的方法就是计算线的交叉点。

您可以将每个对角线/反对角线描述为由矢量方程描述的线，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，就可以得到一对的交点。在您的情况下，当且仅当和是整数时才存在交集。在一种情况下，当方向为和时，会发生除以零，但这种情况很容易解决（源的非零坐标形成交点的坐标）。u2rayu1u2[1, 0][0, 1]

于 2012-07-27T03:50:34.107 回答
1

假设您有一个固定的坐标平面大小，并且您将对不同位置的光源进行多次这些计算，您可以做得比迭代每个点更好。

您可以创建四个布尔（或位）数组。

  1. 水平
  2. 垂直
  3. 诊断
  4. 诊断

对于我们的每个光源，我们将它们“投影”到那些一维阵列上。（在图片中我只显示了两个投影）。

在此处输入图像描述

投影到 Horiz 和 Verti 上很简单。

在图中所示的 DiagR 数组上投影一个点 (x,y) 就像 x 加 y 一样简单。

现在您可以简单地遍历所有网格点，看看是否至少有 2 个投影设置为真。

但我们可以做得更好，

例如，在示例中，我们可以从遍历 Verti 数组开始。

我们注意到 Verti[0] 设置为 true，现在我们想看看它是否与 Horiz、DiagR、DiagL 相交。

我们计算它来检查与 DiagR（我们图片中的另一个数组）的交集，我们只需要查看 DiagR[0]、DiagR[1]、DiagR[2] 和 DiagR[3] 是否为真，我们可以忽略该数组的其余部分。

Verti[0] 的光可以在其任何元素处与 horiz 相交。

Verti[0] 的光只能在 DiagL 位置 0、1、2 和 3 处与 DiagL 相交。

继续 Verti[i] 的其余部分。

我们现在可以做一些类似的事情来寻找真正的 Horiz[i] 与 DiagR 和 DiagL 的交集。

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

这将为您返回所有光线交点的列表，但其中还包括光源的点。

您可以忽略存在点源的所有交叉点，或者使用一些独创性来解释这些点。

于 2012-07-27T19:51:37.697 回答
1

我已经从这里提升了数学，

好的，所以每个点都有 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);
}

要找到两条射线的相交，我们可以做

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

显然这里有很多迭代，我没有编译或测试过这个，但是因为在它的核心，数学似乎相当有效，我对性能持乐观态度。

于 2012-07-30T09:33:17.250 回答