探测光的预测和路口在二维空间中使用C＃ [英] Detecting light projections and intersections in 2D space using C#

问题描述

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

有多个光源围绕在不同的地点，每个散发出8光的光的方向N，S，E，W，西北，东北，西南，东南。所有灯光的坐标是已知的。

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

 长宽度= int.MaxValue; // 2D网格宽度。
长个儿= int.MaxValue * 3; // 2D网格的高度。
名单＆LT;点＆GT;灯=一堆随机放置光源。
名单＆LT;点＆GT;路口=计算所有可能的交叉点。

的for（int i = 0; I＆LT; lights.Count  -  1;我++）
{
    对于（INT J = I + 1; J＆LT; lights.Count; J ++）
    {
        //如何只使用整数比较？
        //如果这是不可能的，什么是最快的方法吗？
    }
}
 

解决方案

我的答案是基于关上链接的问题，您的评论的：有也一个简单的方法来确定其坐标光斜光线彼此相交，两给点意见？它看起来像你想确定由光源提供的光线的交叉点。

从你刚才所说，水平/垂直方向的情况下很容易。在两个源之间的点描述的交叉点。对角的情况下都比较棘手，我想接近它只是计算直线相交处的最简单的方法。

您可以描述每个角/反对角线用矢量方程光= S + U * D ，其中取值是光源的位置和 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 和光线方向 D 1 ， D 2 。您只需插入 U1 和 U2 的值到原始的线方程和你有交点的一对。在你的情况下，存在交集，当且仅当 U1 和 U2 是整数。还有一个情况下，除数为零时，当方向是 [1,0] 和 [0,1] ，但这种情况下，是微不足道的解决（来源非零坐标形成的交点的坐标）。

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

解决方案

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

这篇关于探测光的预测和路口在二维空间中使用C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！