1 /******************************************************************************
2 * Copyright (c) 2014, Connor Manning (connor@hobu.co)
3 *
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following
8 * conditions are met:
9 *
10 *     * Redistributions of source code must retain the above copyright
11 *       notice, this list of conditions and the following disclaimer.
12 *     * Redistributions in binary form must reproduce the above copyright
13 *       notice, this list of conditions and the following disclaimer in
14 *       the documentation and/or other materials provided
15 *       with the distribution.
16 *     * Neither the name of Hobu, Inc. or Flaxen Geo Consulting nor the
17 *       names of its contributors may be used to endorse or promote
18 *       products derived from this software without specific prior
19 *       written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
28 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
32 * OF SUCH DAMAGE.
33 ****************************************************************************/
34 
35 #include <limits>
36 #include <cmath>
37 #include <memory>
38 
39 #include <pdal/PointView.hpp>
40 #include <pdal/QuadIndex.hpp>
41 #include <pdal/util/Utils.hpp>
42 
43 namespace
44 {
45     using namespace pdal;
46 
47     struct BBox
48     {
BBox__anonaeb719a50111::BBox49         BBox(Point minimum, Point maximum)
50             : minimum(minimum)
51             , maximum(maximum)
52             , center(minimum.x + (maximum.x - minimum.x) / 2,
53                 minimum.y + (maximum.y - minimum.y) / 2)
54             , halfWidth(center.x - minimum.x)
55             , halfHeight(center.y - minimum.y)
56         { }
57 
BBox__anonaeb719a50111::BBox58         BBox(const BBox& other)
59             : minimum(other.minimum)
60             , maximum(other.maximum)
61             , center(other.center)
62             , halfWidth(other.halfWidth)
63             , halfHeight(other.halfHeight)
64         { }
65 
66         // Returns true if this BBox shares any area in common with another.
overlaps__anonaeb719a50111::BBox67         bool overlaps(const BBox& other) const
68         {
69             return
70                 std::abs(center.x - other.center.x) <
71                     halfWidth + other.halfWidth &&
72                 std::abs(center.y - other.center.y) <
73                     halfHeight + other.halfHeight;
74         }
75 
overlaps__anonaeb719a50111::BBox76         bool overlaps(
77             const double xBegin,
78             const double xEnd,
79             const double yBegin,
80             const double yEnd) const
81         {
82             const BBox other(
83                     Point(xBegin, yBegin),
84                     Point(xEnd, yEnd));
85 
86             return overlaps(other);
87         }
88 
89         // Returns true if the requested point is contained within this BBox.
contains__anonaeb719a50111::BBox90         bool contains(const Point& p) const
91         {
92             return p.x >= minimum.x && p.y >= minimum.y &&
93                 p.x < maximum.x && p.y < maximum.y;
94         }
95 
96         const Point minimum;
97         const Point maximum;
98 
99         // Pre-calculate these properties, rather than exposing functions to
100         // calculate them on-demand, due to the large number of times that
101         // these will be needed when querying the quad tree.
102         const Point center;
103         const double halfWidth;
104         const double halfHeight;
105 
106         BBox& operator=(const BBox&); // not implemented
107     };
108 
109 } // anonymous namespace
110 
111 namespace pdal
112 {
113 
114 // Recursive quadtree implementation.
115 struct Tree
116 {
Treepdal::Tree117     Tree(BBox bbox, const QuadPointRef* data = 0)
118         : bbox(bbox)
119         , data(data)
120         , nw()
121         , ne()
122         , se()
123         , sw()
124     { }
125 
126     void getFills(std::vector<std::size_t>& fills, std::size_t level = 0) const;
127 
128     // Returns depth resulting from the insertion of this point.
129     std::size_t addPoint(const QuadPointRef* toAdd, std::size_t curDepth = 0);
130 
131     void getPoints(
132             PointIdList& results,
133             std::size_t depthBegin,
134             std::size_t depthEnd,
135             std::size_t curDepth) const;
136 
137     void getPoints(
138             PointIdList& results,
139             std::size_t rasterize,
140             double xBegin,
141             double xEnd,
142             double xStep,
143             double yBegin,
144             double yEnd,
145             double yStep,
146             std::size_t curDepth) const;
147 
148     void getPoints(
149             PointIdList& results,
150             double xBegin,
151             double xEnd,
152             double xStep,
153             double yBegin,
154             double yEnd,
155             double yStep) const;
156 
157     void getPoints(
158             PointIdList& results,
159             const BBox& query,
160             std::size_t depthBegin,
161             std::size_t depthEnd,
162             std::size_t curDepth) const;
163 
164     const BBox bbox;
165     const QuadPointRef* data;
166 
167     std::unique_ptr<Tree> nw;
168     std::unique_ptr<Tree> ne;
169     std::unique_ptr<Tree> se;
170     std::unique_ptr<Tree> sw;
171 };
172 
addPoint(const QuadPointRef * toAdd,const std::size_t curDepth)173 std::size_t Tree::addPoint(const QuadPointRef* toAdd, const std::size_t curDepth)
174 {
175     if (data)
176     {
177         const Point& center(bbox.center);
178 
179         if (toAdd->point.sqDist(center) < data->point.sqDist(center))
180         {
181             std::swap(data, toAdd);
182         }
183 
184         const std::size_t nextDepth(curDepth + 1);
185 
186         if (toAdd->point.x < center.x)
187         {
188             if (toAdd->point.y < center.y)
189             {
190                 if (sw)
191                 {
192                     return sw->addPoint(toAdd, nextDepth);
193                 }
194                 else
195                 {
196                     sw.reset(new Tree(
197                             BBox(
198                                 Point(bbox.minimum.x, bbox.minimum.y),
199                                 Point(center.x, center.y)),
200                             toAdd));
201 
202                     return nextDepth;
203                 }
204             }
205             else
206             {
207                 if (nw)
208                 {
209                     return nw->addPoint(toAdd, nextDepth);
210                 }
211                 else
212                 {
213                     nw.reset(new Tree(
214                             BBox(
215                                 Point(bbox.minimum.x, center.y),
216                                 Point(center.x, bbox.maximum.y)),
217                             toAdd));
218 
219                     return nextDepth;
220                 }
221             }
222         }
223         else
224         {
225             if (toAdd->point.y < center.y)
226             {
227                 if (se)
228                 {
229                     return se->addPoint(toAdd, nextDepth);
230                 }
231                 else
232                 {
233                     se.reset(new Tree(
234                             BBox(
235                                 Point(center.x, bbox.minimum.y),
236                                 Point(bbox.maximum.x, center.y)),
237                             toAdd));
238 
239                     return nextDepth;
240                 }
241             }
242             else
243             {
244                 if (ne)
245                 {
246                     return ne->addPoint(toAdd, nextDepth);
247                 }
248                 else
249                 {
250                     ne.reset(new Tree(
251                             BBox(
252                                 Point(center.x, center.y),
253                                 Point(bbox.maximum.x, bbox.maximum.y)),
254                             toAdd));
255 
256                     return nextDepth;
257                 }
258             }
259         }
260     }
261     else
262     {
263         data = toAdd;
264         return curDepth;
265     }
266 }
267 
268 // Fills are a count of the number of points at each level of the quad tree.
getFills(std::vector<std::size_t> & fills,std::size_t level) const269 void Tree::getFills(std::vector<std::size_t>& fills, std::size_t level) const
270 {
271     if (data)
272     {
273         if (level >= fills.size())
274             fills.resize(level + 1);
275         (fills[level])++;
276     }
277 
278     ++level;
279     if (nw) nw->getFills(fills, level);
280     if (ne) ne->getFills(fills, level);
281     if (sw) sw->getFills(fills, level);
282     if (se) se->getFills(fills, level);
283 }
284 
285 
getPoints(PointIdList & results,const std::size_t depthBegin,const std::size_t depthEnd,std::size_t curDepth) const286 void Tree::getPoints(
287         PointIdList& results,
288         const std::size_t depthBegin,
289         const std::size_t depthEnd,
290         std::size_t curDepth) const
291 {
292     if (data && curDepth >= depthBegin)
293     {
294         results.push_back(data->pbIndex);
295     }
296 
297     if (++curDepth < depthEnd || depthEnd == 0)
298     {
299         if (nw) nw->getPoints(results, depthBegin, depthEnd, curDepth);
300         if (ne) ne->getPoints(results, depthBegin, depthEnd, curDepth);
301         if (se) se->getPoints(results, depthBegin, depthEnd, curDepth);
302         if (sw) sw->getPoints(results, depthBegin, depthEnd, curDepth);
303     }
304 }
305 
getPoints(PointIdList & results,const std::size_t rasterize,const double xBegin,const double xEnd,const double xStep,const double yBegin,const double yEnd,const double yStep,std::size_t curDepth) const306 void Tree::getPoints(
307         PointIdList& results,
308         const std::size_t rasterize,
309         const double xBegin,
310         const double xEnd,
311         const double xStep,
312         const double yBegin,
313         const double yEnd,
314         const double yStep,
315         std::size_t curDepth) const
316 {
317     if (curDepth == rasterize)
318     {
319         if (data)
320         {
321             double xOffset(Utils::sround((bbox.center.x - xBegin) / xStep));
322             double yOffset(Utils::sround((bbox.center.y - yBegin) / yStep));
323 
324             const std::size_t index(
325                 static_cast<size_t>(
326                     Utils::sround(yOffset * (xEnd - xBegin) / xStep +
327                         xOffset)));
328 
329             results.at(index) = data->pbIndex;
330         }
331     }
332     else if (++curDepth <= rasterize)
333     {
334         if (nw) nw->getPoints(
335                 results,
336                 rasterize,
337                 xBegin,
338                 xEnd,
339                 xStep,
340                 yBegin,
341                 yEnd,
342                 yStep,
343                 curDepth);
344 
345         if (ne) ne->getPoints(
346                 results,
347                 rasterize,
348                 xBegin,
349                 xEnd,
350                 xStep,
351                 yBegin,
352                 yEnd,
353                 yStep,
354                 curDepth);
355 
356         if (se) se->getPoints(
357                 results,
358                 rasterize,
359                 xBegin,
360                 xEnd,
361                 xStep,
362                 yBegin,
363                 yEnd,
364                 yStep,
365                 curDepth);
366 
367         if (sw) sw->getPoints(
368                 results,
369                 rasterize,
370                 xBegin,
371                 xEnd,
372                 xStep,
373                 yBegin,
374                 yEnd,
375                 yStep,
376                 curDepth);
377     }
378 }
379 
getPoints(PointIdList & results,const double xBegin,const double xEnd,const double xStep,const double yBegin,const double yEnd,const double yStep) const380 void Tree::getPoints(
381         PointIdList& results,
382         const double xBegin,
383         const double xEnd,
384         const double xStep,
385         const double yBegin,
386         const double yEnd,
387         const double yStep) const
388 {
389     if (!bbox.overlaps(xBegin, xEnd, yBegin, yEnd))
390     {
391         return;
392     }
393 
394     if (nw) nw->getPoints(
395             results,
396             xBegin,
397             xEnd,
398             xStep,
399             yBegin,
400             yEnd,
401             yStep);
402 
403     if (ne) ne->getPoints(
404             results,
405             xBegin,
406             xEnd,
407             xStep,
408             yBegin,
409             yEnd,
410             yStep);
411 
412     if (se) se->getPoints(
413             results,
414             xBegin,
415             xEnd,
416             xStep,
417             yBegin,
418             yEnd,
419             yStep);
420 
421     if (sw) sw->getPoints(
422             results,
423             xBegin,
424             xEnd,
425             xStep,
426             yBegin,
427             yEnd,
428             yStep);
429 
430     // Add data after calling child nodes so we prefer upper levels of the tree.
431     if (
432             data &&
433             data->point.x >= xBegin &&
434             data->point.y >= yBegin &&
435             data->point.x < xEnd - xStep &&
436             data->point.y < yEnd - yStep)
437     {
438         double xOffset(Utils::sround((data->point.x - xBegin) / xStep));
439         double yOffset(Utils::sround((data->point.y - yBegin) / yStep));
440 
441         std::size_t index(
442             static_cast<size_t>(
443                 Utils::sround(yOffset * (xEnd - xBegin) / xStep + xOffset)));
444 
445         if (index < results.size())
446         {
447             results.at(index) = data->pbIndex;
448         }
449     }
450 }
451 
getPoints(PointIdList & results,const BBox & query,const std::size_t depthBegin,const std::size_t depthEnd,std::size_t curDepth) const452 void Tree::getPoints(
453         PointIdList& results,
454         const BBox& query,
455         const std::size_t depthBegin,
456         const std::size_t depthEnd,
457         std::size_t curDepth) const
458 {
459     if (!query.overlaps(bbox))
460     {
461         return;
462     }
463 
464     if (data &&
465         query.contains(data->point) &&
466         curDepth >= depthBegin &&
467         (curDepth < depthEnd || depthEnd == 0))
468     {
469         results.push_back(data->pbIndex);
470     }
471 
472     if (++curDepth < depthEnd || depthEnd == 0)
473     {
474         if (nw) nw->getPoints(results, query, depthBegin, depthEnd, curDepth);
475         if (ne) ne->getPoints(results, query, depthBegin, depthEnd, curDepth);
476         if (se) se->getPoints(results, query, depthBegin, depthEnd, curDepth);
477         if (sw) sw->getPoints(results, query, depthBegin, depthEnd, curDepth);
478     }
479 }
480 
481 struct QuadIndex::QImpl
482 {
483     QImpl(const PointView& view, std::size_t topLevel);
484     QImpl(
485             const PointView& view,
486             double xMin,
487             double yMin,
488             double xMax,
489             double yMax,
490             std::size_t topLevel);
491     QImpl(
492             const std::vector<std::shared_ptr<QuadPointRef> >& points,
493             double xMin,
494             double yMin,
495             double xMax,
496             double yMax,
497             std::size_t topLevel);
498 
499     void getBounds(
500             double& xMin,
501             double& yMin,
502             double& xMax,
503             double& yMax) const;
504 
505     std::size_t getDepth() const;
506 
507     std::vector<std::size_t> getFills();
508 
509     PointIdList getPoints(
510             std::size_t depthBegin,
511             std::size_t depthEnd) const;
512 
513     PointIdList getPoints(
514             std::size_t rasterize,
515             double& xBegin,
516             double& xEnd,
517             double& xStep,
518             double& yBegin,
519             double& yEnd,
520             double& yStep) const;
521 
522     PointIdList getPoints(
523             double xBegin,
524             double xEnd,
525             double xStep,
526             double yBegin,
527             double yEnd,
528             double yStep) const;
529 
530     PointIdList getPoints(
531             double xMin,
532             double yMin,
533             double xMax,
534             double yMax,
535             std::size_t depthBegin,
536             std::size_t depthEnd) const;
537 
538     std::size_t m_topLevel;
539     std::vector<std::shared_ptr<QuadPointRef> > m_pointRefVec;
540     std::unique_ptr<Tree> m_tree;
541     std::size_t m_depth;
542     std::vector<std::size_t> m_fills;
543 };
544 
QImpl(const PointView & view,std::size_t topLevel)545 QuadIndex::QImpl::QImpl(const PointView& view, std::size_t topLevel)
546     : m_topLevel(topLevel)
547     , m_pointRefVec()
548     , m_tree()
549     , m_depth(0)
550     , m_fills()
551 {
552     m_pointRefVec.resize(view.size());
553 
554     double xMin((std::numeric_limits<double>::max)());
555     double yMin((std::numeric_limits<double>::max)());
556     double xMax((std::numeric_limits<double>::min)());
557     double yMax((std::numeric_limits<double>::min)());
558 
559     for (PointId i(0); i < view.size(); ++i)
560     {
561         m_pointRefVec[i].reset(
562                 new QuadPointRef(
563                     Point(
564                         view.getFieldAs<double>(Dimension::Id::X, i),
565                         view.getFieldAs<double>(Dimension::Id::Y, i)),
566                 i));
567 
568         const QuadPointRef* pointRef(m_pointRefVec[i].get());
569         if (pointRef->point.x < xMin) xMin = pointRef->point.x;
570         if (pointRef->point.x > xMax) xMax = pointRef->point.x;
571         if (pointRef->point.y < yMin) yMin = pointRef->point.y;
572         if (pointRef->point.y > yMax) yMax = pointRef->point.y;
573     }
574 
575     m_tree.reset(new Tree(BBox(Point(xMin, yMin), Point(xMax, yMax))));
576 
577     for (std::size_t i = 0; i < m_pointRefVec.size(); ++i)
578     {
579         m_depth = (std::max)(m_tree->addPoint(m_pointRefVec[i].get()), m_depth);
580     }
581 }
582 
QImpl(const PointView & view,double xMin,double yMin,double xMax,double yMax,std::size_t topLevel)583 QuadIndex::QImpl::QImpl(
584         const PointView& view,
585         double xMin,
586         double yMin,
587         double xMax,
588         double yMax,
589         std::size_t topLevel)
590     : m_topLevel(topLevel)
591     , m_pointRefVec()
592     , m_tree()
593     , m_depth(0)
594     , m_fills()
595 {
596     m_pointRefVec.resize(view.size());
597 
598     for (PointId i(0); i < view.size(); ++i)
599     {
600         m_pointRefVec[i].reset(
601                 new QuadPointRef(
602                     Point(
603                         view.getFieldAs<double>(Dimension::Id::X, i),
604                         view.getFieldAs<double>(Dimension::Id::Y, i)),
605                 i));
606     }
607 
608     m_tree.reset(new Tree(BBox(Point(xMin, yMin), Point(xMax, yMax))));
609 
610     for (std::size_t i = 0; i < m_pointRefVec.size(); ++i)
611     {
612         m_depth = (std::max)(m_tree->addPoint(m_pointRefVec[i].get()), m_depth);
613     }
614 }
615 
QImpl(const std::vector<std::shared_ptr<QuadPointRef>> & points,double xMin,double yMin,double xMax,double yMax,std::size_t topLevel)616 QuadIndex::QImpl::QImpl(
617         const std::vector<std::shared_ptr<QuadPointRef> >& points,
618         double xMin,
619         double yMin,
620         double xMax,
621         double yMax,
622         std::size_t topLevel)
623     : m_topLevel(topLevel)
624     , m_pointRefVec(points.size())
625     , m_tree()
626     , m_depth(0)
627     , m_fills()
628 {
629     m_tree.reset(new Tree(BBox(Point(xMin, yMin), Point(xMax, yMax))));
630 
631     for (std::size_t i = 0; i < points.size(); ++i)
632     {
633         m_pointRefVec[i] = points[i];
634         m_depth = (std::max)(m_tree->addPoint(m_pointRefVec[i].get()), m_depth);
635     }
636 }
637 
getBounds(double & xMin,double & yMin,double & xMax,double & yMax) const638 void QuadIndex::QImpl::getBounds(
639         double& xMin,
640         double& yMin,
641         double& xMax,
642         double& yMax) const
643 {
644     if (m_tree)
645     {
646         xMin = m_tree->bbox.minimum.x;
647         yMin = m_tree->bbox.minimum.y;
648         xMax = m_tree->bbox.maximum.x;
649         yMax = m_tree->bbox.maximum.y;
650     }
651 }
652 
getDepth() const653 std::size_t QuadIndex::QImpl::getDepth() const
654 {
655     return m_depth;
656 }
657 
getFills()658 std::vector<std::size_t> QuadIndex::QImpl::getFills()
659 {
660     if (m_tree && !m_fills.size())
661     {
662         m_tree->getFills(m_fills);
663     }
664 
665     return m_fills;
666 }
667 
getPoints(const std::size_t minDepth,const std::size_t maxDepth) const668 PointIdList QuadIndex::QImpl::getPoints(
669         const std::size_t minDepth,
670         const std::size_t maxDepth) const
671 {
672     PointIdList results;
673 
674     if (m_tree)
675     {
676         m_tree->getPoints(results, minDepth, maxDepth, m_topLevel);
677     }
678 
679     return results;
680 }
681 
getPoints(const std::size_t rasterize,double & xBegin,double & xEnd,double & xStep,double & yBegin,double & yEnd,double & yStep) const682 PointIdList QuadIndex::QImpl::getPoints(
683         const std::size_t rasterize,
684         double& xBegin,
685         double& xEnd,
686         double& xStep,
687         double& yBegin,
688         double& yEnd,
689         double& yStep) const
690 {
691     PointIdList results;
692 
693     if (m_tree)
694     {
695         const size_t exp(static_cast<size_t>(std::pow(2, rasterize)));
696         const double xWidth(m_tree->bbox.maximum.x - m_tree->bbox.minimum.x);
697         const double yWidth(m_tree->bbox.maximum.y - m_tree->bbox.minimum.y);
698 
699         xStep = xWidth / exp;
700         yStep = yWidth / exp;
701         xBegin =    m_tree->bbox.minimum.x + (xStep / 2);
702         yBegin =    m_tree->bbox.minimum.y + (yStep / 2);
703         // One tick past the end.
704         xEnd =      m_tree->bbox.maximum.x + (xStep / 2);
705         yEnd =      m_tree->bbox.maximum.y + (yStep / 2);
706 
707         results.resize(exp * exp, (std::numeric_limits<PointId>::max)());
708 
709         m_tree->getPoints(
710                 results,
711                 rasterize,
712                 xBegin,
713                 xEnd,
714                 xStep,
715                 yBegin,
716                 yEnd,
717                 yStep,
718                 m_topLevel);
719     }
720 
721     return results;
722 }
723 
getPoints(const double xBegin,const double xEnd,const double xStep,const double yBegin,const double yEnd,const double yStep) const724 PointIdList QuadIndex::QImpl::getPoints(
725         const double xBegin,
726         const double xEnd,
727         const double xStep,
728         const double yBegin,
729         const double yEnd,
730         const double yStep) const
731 {
732     PointIdList results;
733 
734     if (m_tree)
735     {
736         size_t width(
737             static_cast<size_t>(Utils::sround((xEnd - xBegin) / xStep)));
738         std::size_t height(
739             static_cast<size_t>(Utils::sround((yEnd - yBegin) / yStep)));
740         results.resize(width * height, (std::numeric_limits<PointId>::max)());
741 
742         m_tree->getPoints(
743                 results,
744                 xBegin,
745                 xEnd,
746                 xStep,
747                 yBegin,
748                 yEnd,
749                 yStep);
750     }
751 
752     return results;
753 }
754 
getPoints(double xMin,double yMin,double xMax,double yMax,std::size_t minDepth,std::size_t maxDepth) const755 PointIdList QuadIndex::QImpl::getPoints(
756         double xMin,
757         double yMin,
758         double xMax,
759         double yMax,
760         std::size_t minDepth,
761         std::size_t maxDepth) const
762 {
763     PointIdList results;
764 
765     // Making BBox from external parameters here, so do some light validation.
766     if (m_tree)
767     {
768         m_tree->getPoints(
769                 results,
770                 BBox(
771                     Point((std::min)(xMin, xMax), (std::min)(yMin, yMax)),
772                     Point((std::max)(xMin, xMax), (std::max)(yMin, yMax))),
773                 minDepth,
774                 maxDepth,
775                 m_topLevel);
776     }
777 
778     return results;
779 }
780 
QuadIndex(const PointView & view,std::size_t topLevel)781 QuadIndex::QuadIndex(const PointView& view, std::size_t topLevel)
782     : m_qImpl(new QImpl(view, topLevel))
783 { }
784 
QuadIndex(const PointView & view,double xMin,double yMin,double xMax,double yMax,std::size_t topLevel)785 QuadIndex::QuadIndex(
786         const PointView& view,
787         double xMin,
788         double yMin,
789         double xMax,
790         double yMax,
791         std::size_t topLevel)
792     : m_qImpl(new QImpl(view, xMin, yMin, xMax, yMax, topLevel))
793 { }
794 
QuadIndex(const std::vector<std::shared_ptr<QuadPointRef>> & points,double xMin,double yMin,double xMax,double yMax,std::size_t topLevel)795 QuadIndex::QuadIndex(
796         const std::vector<std::shared_ptr<QuadPointRef> >& points,
797         double xMin,
798         double yMin,
799         double xMax,
800         double yMax,
801         std::size_t topLevel)
802     : m_qImpl(new QImpl(points, xMin, yMin, xMax, yMax, topLevel))
803 { }
804 
~QuadIndex()805 QuadIndex::~QuadIndex()
806 { }
807 
getBounds(double & xMin,double & yMin,double & xMax,double & yMax) const808 void QuadIndex::getBounds(
809         double& xMin,
810         double& yMin,
811         double& xMax,
812         double& yMax) const
813 {
814     m_qImpl->getBounds(xMin, yMin, xMax, yMax);
815 }
816 
getDepth() const817 std::size_t QuadIndex::getDepth() const
818 {
819     return m_qImpl->getDepth();
820 }
821 
getFills() const822 std::vector<std::size_t> QuadIndex::getFills() const
823 {
824     return m_qImpl->getFills();
825 }
826 
getPoints(std::size_t depthEnd) const827 PointIdList QuadIndex::getPoints(
828         std::size_t depthEnd) const
829 {
830     return m_qImpl->getPoints(0, depthEnd);
831 }
832 
getPoints(std::size_t depthBegin,std::size_t depthEnd) const833 PointIdList QuadIndex::getPoints(
834         std::size_t depthBegin,
835         std::size_t depthEnd) const
836 {
837     return m_qImpl->getPoints(depthBegin, depthEnd);
838 }
839 
getPoints(const std::size_t rasterize,double & xBegin,double & xEnd,double & xStep,double & yBegin,double & yEnd,double & yStep) const840 PointIdList QuadIndex::getPoints(
841         const std::size_t rasterize,
842         double& xBegin,
843         double& xEnd,
844         double& xStep,
845         double& yBegin,
846         double& yEnd,
847         double& yStep) const
848 {
849     return m_qImpl->getPoints(
850             rasterize,
851             xBegin,
852             xEnd,
853             xStep,
854             yBegin,
855             yEnd,
856             yStep);
857 }
858 
getPoints(const double xBegin,const double xEnd,const double xStep,const double yBegin,const double yEnd,const double yStep) const859 PointIdList QuadIndex::getPoints(
860         const double xBegin,
861         const double xEnd,
862         const double xStep,
863         const double yBegin,
864         const double yEnd,
865         const double yStep) const
866 {
867     return m_qImpl->getPoints(
868             xBegin,
869             xEnd,
870             xStep,
871             yBegin,
872             yEnd,
873             yStep);
874 }
875 
getPoints(double xMin,double yMin,double xMax,double yMax,std::size_t depthEnd) const876 PointIdList QuadIndex::getPoints(
877         double xMin,
878         double yMin,
879         double xMax,
880         double yMax,
881         std::size_t depthEnd) const
882 {
883     return m_qImpl->getPoints(
884             xMin,
885             yMin,
886             xMax,
887             yMax,
888             0,
889             depthEnd);
890 }
891 
getPoints(double xMin,double yMin,double xMax,double yMax,std::size_t depthBegin,std::size_t depthEnd) const892 PointIdList QuadIndex::getPoints(
893         double xMin,
894         double yMin,
895         double xMax,
896         double yMax,
897         std::size_t depthBegin,
898         std::size_t depthEnd) const
899 {
900     return m_qImpl->getPoints(
901             xMin,
902             yMin,
903             xMax,
904             yMax,
905             depthBegin,
906             depthEnd);
907 }
908 
909 } // namespace pdal
910 
911