使用 C# 检测二维空间中的光投影和交叉点 [英] Detecting light projections and intersections in 2D space using C#

问题描述

光源是位于单个坐标中的 2D 空间中的实体.

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

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

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

推荐答案

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

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.

您可以将每个对角线/反对角线描述为由向量方程描述的线 ray = s + u * d 其中 s 是光源的位置d 是光线的方向([1, 1] ,[1, -1], [1,0] 或 [0, 1]).每个源有四个这样的方程，每个方向一个.现在，要找到对角线的交点，只需找到两个源的非平行线的交点(一对将平行，因此不能相交).

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.

更新

作为一个简单的优化，当且仅当 直线距离(|x1 - x2| + |y1 - y2|) 源之间是偶数.我认为还有其他条件可以帮助简化您的案例.

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

在笛卡尔坐标中:

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:

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

然后求解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，您只需计算上面的等式之一或使用:

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

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

所以你有它.给定源位置s1、s2和光线方向d1，求解u1和u2的两个方程, d2.您只需将 u1 和 u2 值插入到原始的 ray 方程中，就可以得到一对的交集.在您的情况下，当且仅当 u1 和 u2 是整数时才存在交集.当方向是 [1, 0] 和 [0, 1] 时，有一种情况会发生被零除，但这种情况很容易解决(非-源的零坐标形成交点的坐标).

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

这篇关于使用 C# 检测二维空间中的光投影和交叉点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！