计算矢量的相交坐标

本文关键字：坐标 计算 | 更新日期: 2024-11-07 09:56:50

给定一个向量（或两个点），我怎样才能得到这个向量在某个给定间隔内相交的离散坐标？

我正在使用它，给定一个射线（矢量），我可以计算该光线相交的图像中的像素，并将其用作图像的索引。在3D的情况下，光线始终在图像的平面上。

此外，矢量来自另一个坐标系，而不是用于图像索引的坐标系，但这只是坐标系之间的缩放。

我正在寻找 3D 解决方案，但可以接受 2D。

编辑：区间是一个 2d 空间，因此解决方案是这个 2d 区间中的一组点。这将在具有 CUDAfy.NET 的GPU上运行

计算矢量的相交坐标

你的向量 P1，P2 是所有这些点：

vector := P1 + a * (P2-P1)  with a in [0;1]

你的间隔P3，P4是所有这些点：

interval := P3 + b * (P4 - P3)  with b in [0,1]

他们在同一点上穿插：

vector == interval
P1 + a * (P2-P1) == P3 + b * (P4-P3)

在 2d 中，这是两个具有两个未知数的方程 ->可解

以下是我的假设：

  • 图像的左下角是原点（坐标为(0, 0)的点）
  • 您有一个宽度w和高度的图像h
  • 你可以把向量放在线性方程的形式（即y=mx+b，其中m是斜率，b是y截距）

根据这些假设，请执行以下操作以查找线与图像边缘相交的离散坐标：

    /// <summary>
    /// Find discreet coordinates where the line y=mx+b intersects the edges of a w-by-h image.
    /// </summary>
    /// <param name="m">slope of the line</param>
    /// <param name="b">y-intercept of the line</param>
    /// <param name="w">width of the image</param>
    /// <param name="h">height of the image</param>
    /// <returns>the points of intersection</returns>
    List<Point> GetIntersectionsForImage(double m, double b, double w, double h)
    {
        var intersections = new List<Point>();
        // Check for intersection with left side (y-axis).
        if (b >= 0 && b <= h)
        {
            intersections.Add(new Point(0.0, b));
        }
        // Check for intersection with right side (x=w).
        var yValRightSide = m * w + b;
        if (yValRightSide >= 0 && yValRightSide <= h)
        {
            intersections.Add(new Point(w, yValRightSide));
        }
        // If the slope is zero, intersections with top or bottom will be taken care of above.
        if (m != 0.0)
        {
            // Check for intersection with top (y=h).
            var xValTop = (h - b) / m;
            if (xValTop >= 0 && xValTop <= w)
            {
                intersections.Add(new Point(xValTop, h));
            }
            // Check for intersection with bottom (y=0).
            var xValBottom = (0.0 - b) / m;
            if (xValBottom >= 0 && xValBottom <= w)
            {
                intersections.Add(new Point(xValBottom, 0));
            }
        }
        return intersections;
    }

以下是确保其正常工作的测试：

    [TestMethod]
    public void IntersectingPoints_AreCorrect()
    {
        // The line y=x intersects a 1x1 image at points (0, 0) and (1, 1).
        var results = GetIntersectionsForImage(1.0, 0.0, 1.0, 1.0);
        foreach (var p in new List<Point> { new Point(0.0, 0.0), new Point(1.0, 1.0) })
        {
            Assert.IsTrue(results.Contains(p));
        }
        // The line y=1 intersects a 2x2 image at points (0, 1), and (2, 1).
        results = GetIntersectionsForImage(0.0, 1.0, 2.0, 2.0);
        foreach (var p in new List<Point> { new Point(0.0, 1.0), new Point(2.0, 1.0) })
        {
            Assert.IsTrue(results.Contains(p));
        }
    }

经过一番搜索，我找到了布雷森汉姆的直线算法，它或多或少正是我所需要的。

如果您对我使用的算法感兴趣，请参考此答案。

相关文章：