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