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 void PolyLine::addToSpatialIndex() const
  99 {
 100     std::set<Octree::Leaf*> seen;
 101
 102     BOOST_FOREACH(const SGGeod& g, m_data) {
 103         SGVec3d cart(SGVec3d::fromGeod(g));
 104         Octree::Leaf* lf = Octree::global_spatialOctree->findLeafForPos(cart);
 105         if (seen.find(lf) != seen.end()) {
 106             continue; // don't insert multiple times
 107         }
 108
 109         lf->addPolyLine(const_cast<PolyLine*>(this));
 110     } // of data points iteration
 111 }
 112
 113 class SingleTypeFilter : public PolyLine::TypeFilter
 114 {
 115 public:
 116     SingleTypeFilter(PolyLine::Type aTy) :
 117         m_type(aTy)
 118     { }
 119
 120     virtual bool pass(PolyLine::Type aTy) const
 121     { return (aTy == m_type); }
 122 private:
 123     PolyLine::Type m_type;
 124 };
 125
 126 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, Type aTy)
 127 {
 128     return linesNearPos(aPos, aRangeNm, SingleTypeFilter(aTy));
 129 }
 130
 131
 132 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, const TypeFilter& aFilter)
 133 {
 134     std::set<PolyLineRef> resultSet;
 135
 136     SGVec3d cart = SGVec3d::fromGeod(aPos);
 137     double cutoffM = aRangeNm * SG_NM_TO_METER;
 138     Octree::FindLinesDeque deque;
 139     deque.push_back(Octree::global_spatialOctree);
 140
 141     while (!deque.empty()) {
 142         Octree::Node* nd = deque.front();
 143         deque.pop_front();
 144
 145         PolyLineList lines;
 146         nd->visitForLines(cart, cutoffM, lines, deque);
 147
 148     // merge into result set, filtering as we go.
 149         BOOST_FOREACH(PolyLineRef ref, lines) {
 150             if (aFilter.pass(ref->type())) {
 151                 resultSet.insert(ref);
 152             }
 153         }
 154     } // of deque iteration
 155
 156     PolyLineList result;
 157     result.insert(result.end(), resultSet.begin(), resultSet.end());
 158     return result;
 159 }
 160
 161