2 * Polyline - store geographic line-segments */
4 // Written by James Turner, started 2013.
6 // Copyright (C) 2013 James Turner <zakalawe@mac.com>
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.
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.
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.
26 #include "PolyLine.hxx"
29 #include <boost/foreach.hpp>
31 #include <simgear/math/sg_geodesy.hxx>
32 #include <simgear/structure/exception.hxx>
34 #include <Navaids/PositionedOctree.hxx>
36 using namespace flightgear;
38 PolyLine::PolyLine(Type aTy, const SGGeodVec& aPoints) :
42 assert(!aPoints.empty());
50 unsigned int PolyLine::numPoints() const
55 SGGeod PolyLine::point(unsigned int aIndex) const
57 assert(aIndex <= m_data.size());
58 return m_data[aIndex];
61 PolyLineList PolyLine::createChunked(Type aTy, const SGGeodVec& aRawPoints)
64 if (aRawPoints.size() < 2) {
68 const double maxDistanceSquaredM = 40000 * 40000; // 40km to start with
70 SGVec3d chunkStartCart = SGVec3d::fromGeod(aRawPoints.front());
72 SGGeodVec::const_iterator it = aRawPoints.begin();
74 while (it != aRawPoints.end()) {
75 SGVec3d ptCart = SGVec3d::fromGeod(*it);
76 double d2 = distSqr(chunkStartCart, ptCart);
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;
86 chunk.push_back(*it++); // add to open chunk
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));
99 PolyLineRef PolyLine::create(PolyLine::Type aTy, const SGGeodVec &aRawPoints)
101 return new PolyLine(aTy, aRawPoints);
104 void PolyLine::bulkAddToSpatialIndex(const PolyLineList &lines)
106 NavDataCache::Transaction txn( NavDataCache::instance());
107 flightgear::PolyLineList::const_iterator it;
108 for (it=lines.begin(); it != lines.end(); ++it) {
109 (*it)->addToSpatialIndex();
114 void PolyLine::addToSpatialIndex() const
116 Octree::Node* node = Octree::global_spatialOctree->findNodeForBox(cartesianBox());
117 node->addPolyLine(const_cast<PolyLine*>(this));
120 SGBoxd PolyLine::cartesianBox() const
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);
132 class SingleTypeFilter : public PolyLine::TypeFilter
135 SingleTypeFilter(PolyLine::Type aTy) :
139 virtual bool pass(PolyLine::Type aTy) const
140 { return (aTy == m_type); }
142 PolyLine::Type m_type;
145 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, Type aTy)
147 return linesNearPos(aPos, aRangeNm, SingleTypeFilter(aTy));
151 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, const TypeFilter& aFilter)
153 std::set<PolyLineRef> resultSet;
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);
160 while (!deque.empty()) {
161 Octree::Node* nd = deque.front();
165 nd->visitForLines(cart, cutoffM, lines, deque);
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);
173 } // of deque iteration
176 result.insert(result.end(), resultSet.begin(), resultSet.end());