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

Question

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

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

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

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

EDIT: Интервал является пространством 2d, поэтому решение представляет собой набор точек в этом интервале 2d. И это будет работать на GPU с CUDAfy.NET

Answer 1

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

Если вас интересует алгоритм, который я использовал, обратитесь к this answer.

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] 

Они interscet в той же точке:

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