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 #pragma once
36 
37 #include <vector>
38 #include <memory>
39 
40 #include <pdal/pdal_types.hpp>
41 #include <pdal/util/Bounds.hpp>
42 
43 namespace pdal
44 {
45 
46 class PointView;
47 
48 struct Point
49 {
Pointpdal::Point50     Point(double x, double y) : x(x), y(y) { }
Pointpdal::Point51     Point(const Point& other) : x(other.x), y(other.y) { }
52 
53     // Calculates the distance-squared to another point.
sqDistpdal::Point54     double sqDist(const Point& other) const
55     {
56         return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
57     }
58 
59     const double x;
60     const double y;
61 
62     Point& operator=(const Point&); // not implemented
63 };
64 
65 struct QuadPointRef
66 {
QuadPointRefpdal::QuadPointRef67     QuadPointRef(const Point& point, std::size_t pbIndex)
68         : point(point)
69         , pbIndex(pbIndex)
70     { }
71 
72     const Point point;
73     const std::size_t pbIndex;
74 
75     QuadPointRef& operator=(const QuadPointRef&); // not implemented
76     QuadPointRef(const QuadPointRef&); // not implemented
77 };
78 
79 class PDAL_DLL QuadIndex
80 {
81 public:
82     QuadIndex(const PointView& view, std::size_t topLevel = 0);
83     QuadIndex(
84             const PointView& view,
85             double xMin,
86             double yMin,
87             double xMax,
88             double yMax,
89             std::size_t topLevel = 0);
90     QuadIndex(
91             const std::vector<std::shared_ptr<QuadPointRef> >& points,
92             double xMin,
93             double yMin,
94             double xMax,
95             double yMax,
96             std::size_t topLevel = 0);
97     ~QuadIndex();
98 
99     void getBounds(
100             double& xMin,
101             double& yMin,
102             double& xMax,
103             double& yMax) const;
104 
105     std::size_t getDepth() const;
106 
107     std::vector<std::size_t> getFills() const;
108 
109     // Return all points at depth levels strictly less than depthEnd.
110     // A depthEnd value of zero returns all points in the tree.
111     PointIdList getPoints(
112             std::size_t depthEnd = 0) const;
113 
114     // Return all points at depth levels between [depthBegin, depthEnd).
115     // A depthEnd value of zero will return all points at levels >= depthBegin.
116     PointIdList getPoints(
117             std::size_t depthBegin,
118             std::size_t depthEnd) const;
119 
120     // Rasterize a single level of the tree.  Empty positions will contain
121     // std::numeric_limits<PointId>::max().
122     PointIdList getPoints(
123             std::size_t rasterize,
124             double& xBegin,
125             double& xEnd,
126             double& xStep,
127             double& yBegin,
128             double& yEnd,
129             double& yStep) const;
130 
131     // Get custom raster via bounds and resolution query.  Empty positions will
132     // contain std::numeric_limits<PointId>::max().
133     PointIdList getPoints(
134             double xBegin,
135             double xEnd,
136             double xStep,
137             double yBegin,
138             double yEnd,
139             double yStep) const;
140 
141     // Return all points within the query bounding box, searching only up to
142     // depth levels strictly less than depthEnd.
143     // A depthEnd value of zero will return all existing points that fall
144     // within the query range regardless of depth.
145     PointIdList getPoints(
146             double xMin,
147             double yMin,
148             double xMax,
149             double yMax,
150             std::size_t depthEnd = 0) const;
151 
getPoints(const BOX3D & box,std::size_t depthEnd=0) const152     PointIdList getPoints(
153             const BOX3D& box,
154             std::size_t depthEnd=0) const
155     {
156         return getPoints(box.minx, box.miny, box.maxx, box.maxy, depthEnd);
157     }
158 
159     // Return all points within the bounding box, searching at tree depth
160     // levels from [depthBegin, depthEnd).
161     // A depthEnd value of zero will return all points within the query range
162     // that have a tree level >= depthBegin.
163     PointIdList getPoints(
164             double xMin,
165             double yMin,
166             double xMax,
167             double yMax,
168             std::size_t depthBegin,
169             std::size_t depthEnd) const;
170 
171 private:
172     struct QImpl;
173     std::unique_ptr<QImpl> m_qImpl;
174 
175     // Disable copying and assignment.
176     QuadIndex(const QuadIndex&);
177     QuadIndex& operator=(QuadIndex&);
178 };
179 
180 } // namespace pdal
181 
182