Рассчитать пересекающиеся координаты из вектора

Question

Учитывая вектор (или две точки), как я могу получить дискретные координаты, которые этот вектор пересекает в некотором данном интервале?

Я использую это так, что с учетом луча (вектора) я могу вычислить пиксели в изображении, которое этот луч пересекает, и использовать их в качестве индексов для моего изображения. Луч всегда находится в плоскости изображения в случае 3D.

Также вектор исходит из другой системы координат, чем та, которая используется для индексов изображений, но это всего лишь масштабирование между системами координат.

Я ищу решение в 3D, но 2D можно принять.

РЕДАКТИРОВАТЬ: Интервал является 2-мерным пространством, поэтому решение представляет собой набор точек в этом 2-мерном интервале. И это будет работать на GPU с CUDAfy.NET

Answer 1

После небольшого поиска я нашел линейный алгоритм Брезенхэма, который был более или менее именно тем, что мне было нужно.

Пожалуйста, обратитесь к этому ответу, если вы заинтересованы в алгоритме, который я использовал.

Answer 2

Ваш вектор P1,P2 - это все эти точки:

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

Yout intervall P3, P4 это все эти точки:

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

Они пересекаются в одной точке:

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

В 2d это два уравнения с двумя неизвестными -> разрешимыми

Answer 3

Вот мои предположения:

• нижний левый угол вашего изображения - это начало координат (точка с координатами (0, 0))
• у вас есть изображение с шириной w и высота h
• Вы можете поместить вектор в виде линейного уравнения (т.е. y=mx+b, где m это склон и b это у-перехват)

Учитывая эти предположения, сделайте следующее, чтобы найти дискретные координаты, где линия пересекает края вашего изображения:

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