src/Navaids/PolyLine.cxx

   1 /**
   2  * Polyline - store geographic line-segments */
   3
   4 // Written by James Turner, started 2013.
   5 //
   6 // Copyright (C) 2013 James Turner <zakalawe@mac.com>
   7 //
   8 // This program is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU General Public License as
  10 // published by the Free Software Foundation; either version 2 of the
  11 // License, or (at your option) any later version.
  12 //
  13 // This program is distributed in the hope that it will be useful, but
  14 // WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 // General Public License for more details.
  17 //
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  21
  22 #ifdef HAVE_CONFIG_H
  23     #include "config.h"
  24 #endif
  25
  26 #include "PolyLine.hxx"
  27
  28 #include <cassert>
  29 #include <boost/foreach.hpp>
  30
  31 #include <simgear/math/sg_geodesy.hxx>
  32
  33 #include <Navaids/PositionedOctree.hxx>
  34
  35 using namespace flightgear;
  36
  37 PolyLine::PolyLine(Type aTy, const SGGeodVec& aPoints) :
  38     m_type(aTy),
  39     m_data(aPoints)
  40 {
  41     assert(!aPoints.empty());
  42 }
  43
  44 PolyLine::~PolyLine()
  45 {
  46
  47 }
  48
  49 unsigned int PolyLine::numPoints() const
  50 {
  51     return m_data.size();
  52 }
  53
  54 SGGeod PolyLine::point(unsigned int aIndex) const
  55 {
  56     assert(aIndex <= m_data.size());
  57     return m_data[aIndex];
  58 }
  59
  60 PolyLineList PolyLine::createChunked(Type aTy, const SGGeodVec& aRawPoints)
  61 {
  62     PolyLineList result;
  63     if (aRawPoints.size() < 2) {
  64         return result;
  65     }
  66
  67     const double maxDistanceSquaredM = 40000 * 40000; // 40km to start with
  68
  69     SGVec3d chunkStartCart = SGVec3d::fromGeod(aRawPoints.front());
  70     SGGeodVec chunk;
  71     SGGeodVec::const_iterator it = aRawPoints.begin();
  72
  73     while (it != aRawPoints.end()) {
  74         SGVec3d ptCart = SGVec3d::fromGeod(*it);
  75         double d2 = distSqr(chunkStartCart, ptCart);
  76
  77     // distance check, but also ensure we generate actual valid line segments.
  78         if ((chunk.size() >= 2) && (d2 > maxDistanceSquaredM)) {
  79             chunk.push_back(*it); // close the segment
  80             result.push_back(new PolyLine(aTy, chunk));
  81             chunkStartCart = ptCart;
  82             chunk.clear();
  83         }
  84
  85         chunk.push_back(*it++); // add to open chunk
  86     }
  87
  88     // if we have a single trailing point, we already added it as the last
  89     // point of the previous chunk, so we're ok. Otherwise, create the
  90     // final chunk's polyline
  91     if (chunk.size() > 1) {
  92         result.push_back(new PolyLine(aTy, chunk));
  93     }
  94
  95     return result;
  96 }
  97
  98 PolyLineRef PolyLine::create(PolyLine::Type aTy, const SGGeodVec &aRawPoints)
  99 {
 100     return new PolyLine(aTy, aRawPoints);
 101 }
 102
 103 void PolyLine::addToSpatialIndex() const
 104 {
 105     Octree::Node* node = Octree::global_spatialOctree->findNodeForBox(cartesianBox());
 106     node->addPolyLine(const_cast<PolyLine*>(this));
 107 }
 108
 109 SGBoxd PolyLine::cartesianBox() const
 110 {
 111     SGBoxd result;
 112     SGGeodVec::const_iterator it;
 113     for (it = m_data.begin(); it != m_data.end(); ++it) {
 114         SGVec3d cart = SGVec3d::fromGeod(*it);
 115         result.expandBy(cart);
 116     }
 117
 118     return result;
 119 }
 120
 121 class SingleTypeFilter : public PolyLine::TypeFilter
 122 {
 123 public:
 124     SingleTypeFilter(PolyLine::Type aTy) :
 125         m_type(aTy)
 126     { }
 127
 128     virtual bool pass(PolyLine::Type aTy) const
 129     { return (aTy == m_type); }
 130 private:
 131     PolyLine::Type m_type;
 132 };
 133
 134 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, Type aTy)
 135 {
 136     return linesNearPos(aPos, aRangeNm, SingleTypeFilter(aTy));
 137 }
 138
 139
 140 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, const TypeFilter& aFilter)
 141 {
 142     std::set<PolyLineRef> resultSet;
 143
 144     SGVec3d cart = SGVec3d::fromGeod(aPos);
 145     double cutoffM = aRangeNm * SG_NM_TO_METER;
 146     Octree::FindLinesDeque deque;
 147     deque.push_back(Octree::global_spatialOctree);
 148
 149     while (!deque.empty()) {
 150         Octree::Node* nd = deque.front();
 151         deque.pop_front();
 152
 153         PolyLineList lines;
 154         nd->visitForLines(cart, cutoffM, lines, deque);
 155
 156     // merge into result set, filtering as we go.
 157         BOOST_FOREACH(PolyLineRef ref, lines) {
 158             if (aFilter.pass(ref->type())) {
 159                 resultSet.insert(ref);
 160             }
 161         }
 162     } // of deque iteration
 163
 164     PolyLineList result;
 165     result.insert(result.end(), resultSet.begin(), resultSet.end());
 166     return result;
 167 }
 168
 169