//---------------------------------------------------------------------------
//
// Project: OpenWalnut ( http://www.openwalnut.org )
//
// Copyright 2013-2014 Andreas Schwarzkopf, OpenWalnut Community
// 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"
#include "WLariPointClassifier.h"
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();
/**
* Destroys the instance.
*/
virtual ~WLariBoundaryDetector();
/**
* 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 );
/**
* 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.
* \param classifier Point classifier instance to fetch points of the spatial and
* parameter domain.
*/
void detectBoundaries( WLariPointClassifier* classifier );
/**
* Sets the neighbor point search distance limit:
* \param maxPointDistanceR Neighbor search distance limit.
*/
void setMaxPointDistanceR( double maxPointDistanceR );
private:
/**
* 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.
*/
void groupPointsByGroupID( WKdTreeND* parameterDomain );
/**
* Splits a single point group that can be spatially disconnected.
* \param inputPointCluster Input point group to be further splitted.
*/
void detectInputCluster( vector* inputPointCluster );
/**
* 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 );
/**
* 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.
*/
bool lastBoundaryPointCanReachPoint( WPointDistance nextPoint );
/**
* Calculates and returns the next point that belongs to the current bound point chain.
* \return The next bound chain point.
*/
WBoundaryDetectPoint* getNextBoundPoint();
/**
* 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 );
/**
* 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 );
/**
* Calculates a bounding box out of the calculated bound chain points into member
* field variables.
*/
void initAABoundingBoxFromBoundary();
/**
* 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();
/**
* 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 );
/**
* 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 );
/**
* 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 );
/**
* 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 );
/**
* 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();
/**
* Point classifier to access the spatial and parameter domain.
*/
WLariPointClassifier* m_classifier;
/**
* Spatial domain point set kd tree to be analyzed and its point group IDs modified.
*/
WKdTreeND* m_spatialDomain;
/**
* 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;
/**
* Cluster ID counter. This field is incremented every time after detecting a new
* spatially connected cluster.
*/
size_t m_currentClusterID;
/**
* 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;
/**
* 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;
/**
* Boundary point chain of the current spatially connected cluster.
*/
vector* m_currentBoundary;
/**
* Point search instance to find points near an arbitrary coordinate.
*/
WPointSearcher m_clusterSearcher;
/**
* Points above that distance aren't searched.
*/
double m_maxPointDistanceR;
/**
* 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;
/**
* 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;
/**
* 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