WLariBoundaryDetector.h 12.2 KB
 Andreas Schwarzkopf committed Aug 23, 2014 1 2 3 4 ``````//--------------------------------------------------------------------------- // // Project: OpenWalnut ( http://www.openwalnut.org ) // `````` Alexander Wiebel committed Jul 20, 2017 5 ``````// Copyright 2013-2014 Andreas Schwarzkopf, OpenWalnut Community `````` Andreas Schwarzkopf committed Aug 23, 2014 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ``````// For more information see http://www.openwalnut.org/copying // // This file is part of OpenWalnut. // // OpenWalnut is free software: you can redistribute it and/or modify // it under the terms of the GNU Lesser General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // OpenWalnut is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU Lesser General Public License for more details. // // You should have received a copy of the GNU Lesser General Public License // along with OpenWalnut. If not, see . // //--------------------------------------------------------------------------- #ifndef WLARIBOUNDARYDETECTOR_H #define WLARIBOUNDARYDETECTOR_H #include #include #include "core/dataHandler/WDataSetPoints.h" #include "structure/WParameterDomainKdPoint.h" #include "structure/WSpatialDomainKdPoint.h" #include "structure/WBoundaryDetectPoint.h" #include "../common/datastructures/kdtree/WKdTreeND.h" #include "../common/datastructures/kdtree/WKdPointND.h" #include "../common/datastructures/kdtree/WPointSearcher.h" #include "../common/math/vectors/WVectorMaths.h" `````` 39 ``````#include "WLariPointClassifier.h" `````` Andreas Schwarzkopf committed Aug 23, 2014 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 `````` using std::cout; using std::endl; using std::numeric_limits; using std::vector; /** * Class postprocesses the surface detection that grouped points that belonged to the * same planar formula. But these can be spatially disconnected. This class resolves * that ambiguity. * * How it works: * A) Isolating points in sets to treat point sets only of a similar planar formula of * points in relation to their neighbors. * B) Treating each cluster * 1) Rotating that way so that this planar normal vector is approximately parallel * to the Z axis to enable the set to be analyzed using a two dimensional * coordinate system. That point set is added to the wait list. * 2) While still points remain in the wait list. * a) marking the most left point. * b) Detecting the bound from that point counterclockwise. * c) Remaining points are detected whether they are inside that bounds. * - Conting how many times the bound is hit going from an outer point to * the target point that is examined. * - It follows the theory that a point enters or leaves the area after * every bound hit. It supposes that this condition can't remain after a * bound hit. * d) Adding the bound and points inside to a new cluster. * e) Removing it from the waiting list. */ class WLariBoundaryDetector { public: /** * Creates the instance to separate spatially disconnected points that are * assigned to the same planar formula group. */ explicit WLariBoundaryDetector(); `````` Andreas Schwarzkopf committed Sep 19, 2014 79 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 80 81 82 83 `````` /** * Destroys the instance. */ virtual ~WLariBoundaryDetector(); `````` Andreas Schwarzkopf committed Sep 19, 2014 84 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 85 86 87 88 89 90 91 `````` /** * Rotates a point so that the normal vector if itsleast squares adjustment point * group is approximately perpendicular to the z axis. It makes the boundary * analysis on the two dimensional space possible. * \param transformable Point to be transformed. */ void transformPoint( vector* transformable ); `````` Andreas Schwarzkopf committed Sep 19, 2014 92 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 93 94 95 96 `````` /** * Applies the algorithm on the input point data set where points have been * clustered to groups that have a similar planar furmula. The algorithm splits * grops that are spatially disconnected. `````` 97 98 `````` * \param classifier Point classifier instance to fetch points of the spatial and * parameter domain. `````` Andreas Schwarzkopf committed Aug 23, 2014 99 `````` */ `````` 100 `````` void detectBoundaries( WLariPointClassifier* classifier ); `````` Andreas Schwarzkopf committed Sep 19, 2014 101 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 102 103 104 105 106 107 108 109 `````` /** * Sets the neighbor point search distance limit: * \param maxPointDistanceR Neighbor search distance limit. */ void setMaxPointDistanceR( double maxPointDistanceR ); private: /** `````` 110 111 112 113 `````` * Groups spatial domain points using their group ID that was previously assigned by * a planar cluster detection approoach. It allows to search points of a particular * group ID faster. * \param parameterDomain Parameter domain to fetch planar points. `````` Andreas Schwarzkopf committed Aug 23, 2014 114 `````` */ `````` 115 `````` void groupPointsByGroupID( WKdTreeND* parameterDomain ); `````` Andreas Schwarzkopf committed Sep 19, 2014 116 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 117 118 119 120 121 `````` /** * Splits a single point group that can be spatially disconnected. * \param inputPointCluster Input point group to be further splitted. */ void detectInputCluster( vector* inputPointCluster ); `````` Andreas Schwarzkopf committed Sep 19, 2014 122 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 123 124 125 126 127 128 129 130 `````` /** * Inits the points rotation angles to use boundary detection on two dimensional * basis. The averate normal vector of point's planar formulas in relation to its * neighbors should be approximately parallel to the Z axis. * \param extentPointCluster Point group of which point's planar formula in relation * to its neighbors are similar. */ void initTransformationCoordinateSystem( vector* extentPointCluster ); `````` Andreas Schwarzkopf committed Sep 19, 2014 131 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 132 `````` /** `````` Andreas Schwarzkopf committed Sep 07, 2014 133 134 135 136 137 138 139 `````` * Tells whether a point can reach the last added boundary point. Usually every * point has information about the distance to the n nearest neighbour. If one side * includes the other side point in respect to this distance, then these two points * are able to reach each other. * \param nextPoint Point to be checked whether it can reach the last added boundary * point. * \return last b oundary point can reach the point or not. `````` Andreas Schwarzkopf committed Aug 23, 2014 140 `````` */ `````` Andreas Schwarzkopf committed Sep 07, 2014 141 `````` bool lastBoundaryPointCanReachPoint( WPointDistance nextPoint ); `````` Andreas Schwarzkopf committed Sep 19, 2014 142 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 143 144 145 146 147 `````` /** * Calculates and returns the next point that belongs to the current bound point chain. * \return The next bound chain point. */ WBoundaryDetectPoint* getNextBoundPoint(); `````` Andreas Schwarzkopf committed Sep 19, 2014 148 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 149 150 151 152 153 154 155 156 157 `````` /** * Returns the outer counterclockwise angle of a line of three points. * \param previousPoint First point of the counterclockwise chain; * \param currentPoint Second point of the counterclockwise chain; * \param nextPoint Third point of the counterclockwise chain; * \return The outer edge angle of the current point belonging to the * counterclockwise running bound. */ double getAngleToNextPoint( WBoundaryDetectPoint* previousPoint, WBoundaryDetectPoint* currentPoint, WBoundaryDetectPoint* nextPoint ); `````` Andreas Schwarzkopf committed Sep 19, 2014 158 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 159 160 161 162 163 164 165 166 167 168 169 170 171 `````` /** * The algorithm follows the bound counterclockwise. There may be some difficult * cases. Usually the next boundary point is taken one resulting the smallest angle * (directed to the outer side) between the previous and the next point. Sometimes * previous edges can have angles below 180 degrees. That results that next points * can hit points that lie on the previously detected area. It results bound * intersections with a completely invalit bounds. This method detects whether a * potential next point could result bound intersections. * \param nextPoint Next point that could continue the bound chain. * \return Continuing the bound chain using that point can cause a bound line * intersection or not. */ bool isResultingBoundIntersection( WBoundaryDetectPoint* nextPoint ); `````` Andreas Schwarzkopf committed Sep 19, 2014 172 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 173 174 175 176 177 `````` /** * Calculates a bounding box out of the calculated bound chain points into member * field variables. */ void initAABoundingBoxFromBoundary(); `````` Andreas Schwarzkopf committed Sep 19, 2014 178 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 179 180 181 182 183 184 `````` /** * Initializes an outer point that is a help to detect whether some points are * within a bounded area or not. The principle is based on the theory that every * bound hit changes the state whether a point is inside or outside the area. */ void initOneOutsidePoint(); `````` Andreas Schwarzkopf committed Sep 19, 2014 185 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 186 187 188 189 190 191 192 193 `````` /** * Calculates whether a point belongs to the bounding box of the lastly calculated * cluster's bound chain. It simply speeds up when skipping the slower algorithm * during a potential point is definitely too far away. * \param point Point to be examined whether it is in the bounding box. * \return The point is in the bounding box or not. */ bool pointBelongsToBoundingBox( const vector& point ); `````` Andreas Schwarzkopf committed Sep 19, 2014 194 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 195 196 197 198 199 200 201 `````` /** * Method that accurately but more slowly determines whether a point is spatially inside the bounds * of the current cluster. * \param point Examined point coordinate of being inside the cluster bound chain. * \return The point is in the cluster's bounds or not. */ bool pointIsInBounds( const vector& point ); `````` Andreas Schwarzkopf committed Sep 19, 2014 202 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 203 204 205 206 207 208 209 `````` /** * Tells whether a point lies exactly on a bound or not. * \param point Point to be examined. * \param boundNr Bound part index to be examined. * \return point lies exactly on a bound line of an index or not. */ bool pointLiesOnBound( const vector& point, size_t boundNr ); `````` Andreas Schwarzkopf committed Sep 19, 2014 210 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 211 212 213 214 215 216 217 `````` /** * Tells whether a point hits a bound of an index. * \param point Point to be examined. * \param boundNr Bound part index to be examined. * \return an arbitrary point hits a bound of an index or not. */ bool pointHitsBound( const vector& point, size_t boundNr ); `````` Andreas Schwarzkopf committed Sep 19, 2014 218 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 219 220 221 222 223 224 225 226 227 `````` /** * Tells whether a bound is still valid. The validation begins after the point count * of 10. It works by the principle that exact sequence of same two consecutive * points means that the border runs somewhere in circle and doesn't come to the * start. * \return Boundary chain is valid or not. */ bool boundChainStillValid(); `````` 228 229 230 231 `````` /** * Point classifier to access the spatial and parameter domain. */ WLariPointClassifier* m_classifier; `````` Andreas Schwarzkopf committed Aug 23, 2014 232 233 234 235 236 `````` /** * Spatial domain point set kd tree to be analyzed and its point group IDs modified. */ WKdTreeND* m_spatialDomain; `````` Andreas Schwarzkopf committed Sep 19, 2014 237 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 238 239 240 241 242 243 244 `````` /** * Spatial domain points grouped by their group ID. Previously points are detected * using the peak detection approach oof Lari/Habib. So previously points were * merged with the most widespread point's planar formula in relation to it's * neighbors. And that routine was executed until segmenting every last point. */ vector*>* m_spatialInputClusters; `````` Andreas Schwarzkopf committed Sep 19, 2014 245 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 246 247 248 249 250 `````` /** * Cluster ID counter. This field is incremented every time after detecting a new * spatially connected cluster. */ size_t m_currentClusterID; `````` Andreas Schwarzkopf committed Sep 19, 2014 251 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 252 253 254 255 256 257 `````` /** * First transformation rotation that is done so that points lie in the most optimal * way to analyze them using a two dimensional coordinate system. This first * rotation rotates between Z and X axis. */ double m_transformAngle1zx; `````` Andreas Schwarzkopf committed Sep 19, 2014 258 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 259 260 261 262 263 264 `````` /** * First transformation rotation that is done so that points lie in the most optimal * way to analyze them using a two dimensional coordinate system. This first * rotation rotates between Z and Y axis. */ double m_transformAngle2zy; `````` Andreas Schwarzkopf committed Sep 19, 2014 265 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 266 267 268 269 `````` /** * Boundary point chain of the current spatially connected cluster. */ vector* m_currentBoundary; `````` Andreas Schwarzkopf committed Sep 19, 2014 270 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 271 272 273 274 `````` /** * Point search instance to find points near an arbitrary coordinate. */ WPointSearcher m_clusterSearcher; `````` Andreas Schwarzkopf committed Sep 19, 2014 275 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 276 277 278 279 `````` /** * Points above that distance aren't searched. */ double m_maxPointDistanceR; `````` Andreas Schwarzkopf committed Sep 19, 2014 280 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 281 282 283 284 285 `````` /** * Lower axis aligned bounding box border of the current spatially connected bound * point chain. So the border bounding box is defined by two coordinates. */ vector m_boundaryAABoundingBoxMin; `````` Andreas Schwarzkopf committed Sep 19, 2014 286 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 287 288 289 290 291 `````` /** * Upper axis aligned bounding box border of the current spatially connected bound * point chain. So the border bounding box is defined by two coordinates. */ vector m_boundaryAABoundingBoxMax; `````` Andreas Schwarzkopf committed Sep 19, 2014 292 `````` `````` Andreas Schwarzkopf committed Aug 23, 2014 293 294 295 296 297 298 299 300 301 302 `````` /** * One outer point that helps to detect whether a point is inside a bound or not. * The detection follows the theory that goint across the line the condition changes * every time (whether it is inside or outside the bounds) when hitting a bound * piece. */ vector m_oneOutsidePoint; }; #endif // WLARIBOUNDARYDETECTOR_H``````