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 #include <simgear/structure/exception.hxx>
  33
  34 #include <Navaids/PositionedOctree.hxx>
  35
  36 using namespace flightgear;
  37
  38 PolyLine::PolyLine(Type aTy, const SGGeodVec& aPoints) :
  39     m_type(aTy),
  40     m_data(aPoints)
  41 {
  42     assert(!aPoints.empty());
  43 }
  44
  45 PolyLine::~PolyLine()
  46 {
  47
  48 }
  49
  50 unsigned int PolyLine::numPoints() const
  51 {
  52     return m_data.size();
  53 }
  54
  55 SGGeod PolyLine::point(unsigned int aIndex) const
  56 {
  57     assert(aIndex <= m_data.size());
  58     return m_data[aIndex];
  59 }
  60
  61 PolyLineList PolyLine::createChunked(Type aTy, const SGGeodVec& aRawPoints)
  62 {
  63     PolyLineList result;
  64     if (aRawPoints.size() < 2) {
  65         return result;
  66     }
  67
  68     const double maxDistanceSquaredM = 40000 * 40000; // 40km to start with
  69
  70     SGVec3d chunkStartCart = SGVec3d::fromGeod(aRawPoints.front());
  71     SGGeodVec chunk;
  72     SGGeodVec::const_iterator it = aRawPoints.begin();
  73
  74     while (it != aRawPoints.end()) {
  75         SGVec3d ptCart = SGVec3d::fromGeod(*it);
  76         double d2 = distSqr(chunkStartCart, ptCart);
  77
  78     // distance check, but also ensure we generate actual valid line segments.
  79         if ((chunk.size() >= 2) && (d2 > maxDistanceSquaredM)) {
  80             chunk.push_back(*it); // close the segment
  81             result.push_back(new PolyLine(aTy, chunk));
  82             chunkStartCart = ptCart;
  83             chunk.clear();
  84         }
  85
  86         chunk.push_back(*it++); // add to open chunk
  87     }
  88
  89     // if we have a single trailing point, we already added it as the last
  90     // point of the previous chunk, so we're ok. Otherwise, create the
  91     // final chunk's polyline
  92     if (chunk.size() > 1) {
  93         result.push_back(new PolyLine(aTy, chunk));
  94     }
  95
  96     return result;
  97 }
  98
  99 PolyLineRef PolyLine::create(PolyLine::Type aTy, const SGGeodVec &aRawPoints)
 100 {
 101     return new PolyLine(aTy, aRawPoints);
 102 }
 103
 104 void PolyLine::bulkAddToSpatialIndex(const PolyLineList &lines)
 105 {
 106     NavDataCache::Transaction txn( NavDataCache::instance());
 107     flightgear::PolyLineList::const_iterator it;
 108     for (it=lines.begin(); it != lines.end(); ++it) {
 109         (*it)->addToSpatialIndex();
 110     }
 111     txn.commit();
 112 }
 113
 114 void PolyLine::addToSpatialIndex() const
 115 {
 116     Octree::Node* node = Octree::global_spatialOctree->findNodeForBox(cartesianBox());
 117     node->addPolyLine(const_cast<PolyLine*>(this));
 118 }
 119
 120 SGBoxd PolyLine::cartesianBox() const
 121 {
 122     SGBoxd result;
 123     SGGeodVec::const_iterator it;
 124     for (it = m_data.begin(); it != m_data.end(); ++it) {
 125         SGVec3d cart = SGVec3d::fromGeod(*it);
 126         result.expandBy(cart);
 127     }
 128
 129     return result;
 130 }
 131
 132 class SingleTypeFilter : public PolyLine::TypeFilter
 133 {
 134 public:
 135     SingleTypeFilter(PolyLine::Type aTy) :
 136         m_type(aTy)
 137     { }
 138
 139     virtual bool pass(PolyLine::Type aTy) const
 140     { return (aTy == m_type); }
 141 private:
 142     PolyLine::Type m_type;
 143 };
 144
 145 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, Type aTy)
 146 {
 147     return linesNearPos(aPos, aRangeNm, SingleTypeFilter(aTy));
 148 }
 149
 150
 151 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, const TypeFilter& aFilter)
 152 {
 153     std::set<PolyLineRef> resultSet;
 154
 155     SGVec3d cart = SGVec3d::fromGeod(aPos);
 156     double cutoffM = aRangeNm * SG_NM_TO_METER;
 157     Octree::FindLinesDeque deque;
 158     deque.push_back(Octree::global_spatialOctree);
 159
 160     while (!deque.empty()) {
 161         Octree::Node* nd = deque.front();
 162         deque.pop_front();
 163
 164         PolyLineList lines;
 165         nd->visitForLines(cart, cutoffM, lines, deque);
 166
 167     // merge into result set, filtering as we go.
 168         BOOST_FOREACH(PolyLineRef ref, lines) {
 169             if (aFilter.pass(ref->type())) {
 170                 resultSet.insert(ref);
 171             }
 172         }
 173     } // of deque iteration
 174
 175     PolyLineList result;
 176     result.insert(result.end(), resultSet.begin(), resultSet.end());
 177     return result;
 178 }
 179
 180