3D-алгоритм линейного обзора

Question

В настоящее время я реализую алгоритм прямой видимости, который расскажет мне о точках, которые я могу видеть и не могу видеть вдоль линии. Итак, если я стою на холмистой местности, я могу знать, где я могу и не могу видеть.

Линия, которая генерируется из точки A в точку B, включает в себя несколько точек, равномерно расположенных между A и B. Начиная с A, я вижу, какой угол возвышения находится между A и B. Я отмечаю, что как мой alphaAngle ,

Далее, для каждой точки между A и B, я получаю угол возвышения между A и этой точкой. Если эта точка является самым высоким углом возвышения до сих пор (исключая alphaAngle), тогда я отмечаю ее как таковую. В противном случае он имеет более низкий угол подъема, и поэтому я не должен его видеть, и отметьте эту точку как hasLOS = false.

Вот некоторые определения объектов, которые я использую:

struct TerrainProfilPnt 
{ 
double m_x_lon; //lon 
double m_y_lat; //lat 
double m_z_elev; //elev 
bool m_hasLOS; //Does this point have line of sight from another point? 
}; 

class TerrainProfilePartitioner; // Holds a collection of points that make up the line 

Вот мой алгоритм выписанный, однако он не возвращает правильные результаты. Либо он утверждает, что у него есть ЛОС, когда он не должен (например, переходить из-за одного холма на противоположную сторону другого холма, я не должен этого видеть). Или он утверждает, что я не вижу конечной точки, когда я должен (верх холма к долине под ним). Итак, я подозреваю, что либо моя реализация поиска прямой видимости неверна, либо я неправильно ее использую в коде.

using Point = TerrainProfilePnt; 

    auto pointsInLine = terrainProfilePartitioner->GetPoints(); 
    auto& pointsVec = pointsInLine->GetVector(); 
    std::vector<Point> terrainProfileVec; 
    terrainProfileVec.reserve(pointsVec.size()); 

    double start_xlon = 0.0f; 
    double start_ylat = 0.0f; 
    double start_zelev = 0.0f; 

    double end_xlon = 0.0f; 
    double end_ylat = 0.0f; 
    double end_zelev = 0.0f; 

    //The angle between the starting point and the ending point 
    double initialElevAngle = 0.0f; 


    //Assemble the first and last points 
    start_xlon = pointsVec.front().x(); 
    start_ylat = pointsVec.front().y(); 
    GetPointElevation(start_xlon, start_ylat, start_zelev);  
    end_xlon = pointsVec.back().x(); 
    end_ylat = pointsVec.back().y(); 
    GetPointElevation(end_xlon, end_ylat, end_zelev); 

    //Calculate the angle between the beginning and ending points 
    initialElevAngle = atan2(start_zelev, end_zelev) * 180/M_PI; 

    Point initialPoint; 
    initialPoint.m_x_lon = start_xlon; 
    initialPoint.m_y_lat = start_ylat; 
    initialPoint.m_z_elev = start_zelev; 
    initialPoint.m_hasLOS = true; 

    //pointsVec.push_back(initialPoint); 
    terrainProfileVec.push_back(initialPoint); 

    double oldAngle = 0.0f;; 
    bool hasOldAngle = false; 
    for (std::size_t i = 1; i < pointsVec.size(); ++i) 
    { 
     Point p; 
     p.m_x_lon = pointsVec.at(i).x(); 
     p.m_y_lat = pointsVec.at(i).y(); 
     GetPointElevation(p.m_x_lon, p.m_y_lat, p.m_z_elev); 

     double newAngle = atan2(start_zelev, p.m_z_elev) * 180/M_PI; 
     if (!hasOldAngle) 
     { 
      hasOldAngle = true; 
      oldAngle = newAngle; 
      p.m_hasLOS = true; 
     } 
     else 
     { 
      if (newAngle < oldAngle) 
      { 
       p.m_hasLOS = false; 
      } 
      else 
      { 
       oldAngle = newAngle; 
       p.m_hasLOS = true; 
      } 
     } 

    } 

    auto terrainPrfileSeq = new Common::ObjectRandomAccessSequence<TerrainProfilePnt>(terrainProfileVec); 

    return terrainPrfile 

Answer 1

atan2(start_zelev, p.m_z_elev) не имеет смысла.Вам нужно

atan2(distance, p.m_z_elev - start_zelev); 

где distance является горизонтальное расстояние между p и initialPoint.

Answer 2

Я вижу несколько проблем: Вы не сортировать точки по расстоянию от A восходящих и использовать только высоту. Также использовать гониометрию для каждого местоположения карты, которое, вероятно, медленное. Я хотел бы использовать другой подход вместо:

1. набора LOS=false для всей карты

2. написать строки интерполяции ДВР

   P(t)=A+(B-A).t 
   

   где (B-A) ваше направление просмотра и t является параметром приращения по шаг меньше, чем размер вашей сетки (так что вы ничего не пропустите). Это даст вам long,lat без каких-либо медленных гониометрий.

   Затем найдите объект на карте. Если топология отсортирован, то это либо испытание O(1) или O(log(n).log(m))

3. каждое фактическое местонахождение P(t)

   для видимости. Если true комплект LOS=true и петля # 2 иначе остановите все это.

кстати это иногда называют ray-casting.