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>
33 #include <Navaids/PositionedOctree.hxx>
35 using namespace flightgear;
37 PolyLine::PolyLine(Type aTy, const SGGeodVec& aPoints) :
41 assert(!aPoints.empty());
49 unsigned int PolyLine::numPoints() const
54 SGGeod PolyLine::point(unsigned int aIndex) const
56 assert(aIndex <= m_data.size());
57 return m_data[aIndex];
60 PolyLineList PolyLine::createChunked(Type aTy, const SGGeodVec& aRawPoints)
63 if (aRawPoints.size() < 2) {
67 const double maxDistanceSquaredM = 40000 * 40000; // 40km to start with
69 SGVec3d chunkStartCart = SGVec3d::fromGeod(aRawPoints.front());
71 SGGeodVec::const_iterator it = aRawPoints.begin();
73 while (it != aRawPoints.end()) {
74 SGVec3d ptCart = SGVec3d::fromGeod(*it);
75 double d2 = distSqr(chunkStartCart, ptCart);
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;
85 chunk.push_back(*it++); // add to open chunk
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));
98 void PolyLine::addToSpatialIndex() const
100 std::set<Octree::Leaf*> seen;
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
109 lf->addPolyLine(const_cast<PolyLine*>(this));
110 } // of data points iteration
113 class SingleTypeFilter : public PolyLine::TypeFilter
116 SingleTypeFilter(PolyLine::Type aTy) :
120 virtual bool pass(PolyLine::Type aTy) const
121 { return (aTy == m_type); }
123 PolyLine::Type m_type;
126 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, Type aTy)
128 return linesNearPos(aPos, aRangeNm, SingleTypeFilter(aTy));
132 PolyLineList PolyLine::linesNearPos(const SGGeod& aPos, double aRangeNm, const TypeFilter& aFilter)
134 std::set<PolyLineRef> resultSet;
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);
141 while (!deque.empty()) {
142 Octree::Node* nd = deque.front();
146 nd->visitForLines(cart, cutoffM, lines, deque);
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);
154 } // of deque iteration
157 result.insert(result.end(), resultSet.begin(), resultSet.end());