From aa6960f50b6a9e20e5361b4dc87ac03a33dab1fc Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 25 Nov 2016 15:06:20 +0000 Subject: splitters.h added git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1787 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 751f595daf4fb8a53a3a4aada2f591418ddf909b --- .../include/gudhi/CGAL/Splitters.h | 313 +++++++++++++++++++++ 1 file changed, 313 insertions(+) create mode 100644 src/Bottleneck_distance/include/gudhi/CGAL/Splitters.h (limited to 'src/Bottleneck_distance/include/gudhi/CGAL') diff --git a/src/Bottleneck_distance/include/gudhi/CGAL/Splitters.h b/src/Bottleneck_distance/include/gudhi/CGAL/Splitters.h new file mode 100644 index 00000000..e58a593d --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/CGAL/Splitters.h @@ -0,0 +1,313 @@ +// Copyright (c) 2002-2011 Utrecht University (The Netherlands). +// All rights reserved. +// +// This file is part of CGAL (www.cgal.org). +// You can redistribute it and/or modify it under the terms of the GNU +// General Public License as published by the Free Software Foundation, +// either version 3 of the License, or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// +// Author(s) : Hans Tangelder () + +// Defines rules used for constructing a split node. That is, it implements, +// in several ways, the concept +// Boxtree_splitter. + +#ifndef CGAL_SPLITTERS_H +#define CGAL_SPLITTERS_H + +#include +#include + +namespace CGAL { + + template + class Splitter_base { + private: + unsigned int the_bucket_size; + FT the_aspect_ratio; + + public: + //default bucket_size should be 10 + Splitter_base(unsigned int bucket_size = 10, + FT aspect_ratio = FT(3)) + : the_bucket_size(bucket_size), + the_aspect_ratio(aspect_ratio) + {} + + FT + aspect_ratio() const + { + return the_aspect_ratio; + } + + unsigned int + bucket_size() const + { + return the_bucket_size; + } + + }; + + + template > + class Median_of_max_spread + : public Splitter_base + { + + typedef Splitter_base Base; + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + Median_of_max_spread() + : Base() + {} + + Median_of_max_spread(unsigned int bucket_size) + : Base(bucket_size) + {} + + void + operator() (Separator& sep, + Container& c0, + Container& c1) const + { + sep=Separator(c0.max_tight_span_coord(),FT(0)); + sep.set_cutting_value(c0.median(sep.cutting_dimension())); + c0.split(c1,sep,true); + } + }; + + template > + class Fair + : public Splitter_base + { + + typedef Splitter_base Base; + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + Fair() + : Base() + {} + + Fair(unsigned int bucket_size, + FT aspect_ratio=FT(3)) + : Base(bucket_size, aspect_ratio) + {} + + void + operator()(Separator& sep, Container& c0, Container& c1) const + { + // find legal cut with max spread + sep=Separator(c0.max_tight_span_coord_balanced(this->aspect_ratio()), + FT(0)); + sep.set_cutting_value(c0.balanced_fair(sep.cutting_dimension(), + this->aspect_ratio())); + c0.split(c1,sep); + } + }; + + template > + class Sliding_fair + : public Splitter_base + { + + typedef Splitter_base Base; + + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + Sliding_fair() + : Base() + {} + + Sliding_fair(unsigned int bucket_size, + FT aspect_ratio=FT(3)) + : Base(bucket_size, aspect_ratio) + {} + + void + operator() (Separator& sep, Container& c0, Container& c1) const + { + // find legal cut with max spread + + sep = Separator(c0.max_tight_span_coord_balanced(this->aspect_ratio()), + FT(0)); + + sep.set_cutting_value(c0.balanced_sliding_fair(sep.cutting_dimension(), + this->aspect_ratio())); + c0.split(c1,sep,true); + } + }; + + + template > + class Sliding_midpoint + : public Splitter_base + { + + typedef Splitter_base Base; + + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + Sliding_midpoint() + : Base() + {} + + Sliding_midpoint(unsigned int bucket_size) + : Base(bucket_size) + {} + + void + operator()(Separator& sep, Container& c0, Container& c1) const + { + CGAL_assertion(c0.is_valid()); + CGAL_assertion(c1.is_valid()); + int cutdim = c0.max_span_coord(); + + //Bugfix: avoid linear tree in degenerated cases + if(c0.tight_bounding_box().min_coord(cutdim) != c0.tight_bounding_box().max_coord(cutdim)){ + sep = Separator(cutdim, + (c0.max_span_upper() + c0.max_span_lower())/FT(2)); + } + else{ + cutdim = c0.max_tight_span_coord(); + sep = Separator(cutdim, + (c0.max_tight_span_upper() + c0.max_tight_span_lower())/FT(2)); + } + + FT max_span_lower = + c0.tight_bounding_box().min_coord(cutdim); + + CGAL_assertion(max_span_lower >= c0.bounding_box().min_coord(cutdim)); + FT max_span_upper = + c0.tight_bounding_box().max_coord(cutdim); + + CGAL_assertion(max_span_upper <= c0.bounding_box().max_coord(cutdim)); + if (max_span_upper <= sep.cutting_value()) { + sep.set_cutting_value(max_span_upper); + }; + if (max_span_lower >= sep.cutting_value()) { + sep.set_cutting_value(max_span_lower); + }; + c0.split(c1,sep,true); + } + }; + + template > + class Median_of_rectangle + : public Splitter_base + { + + typedef Splitter_base Base; + + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + + Median_of_rectangle() + : Base() + {} + + Median_of_rectangle(unsigned int bucket_size) + : Base(bucket_size) + {} + + void + operator() (Separator& sep, Container& c0, Container& c1) const + { + sep = Separator(c0.max_span_coord(),FT(0)); + sep.set_cutting_value(c0.median(sep.cutting_dimension())); + c0.split(c1,sep,true); + } + }; + + template > + class Midpoint_of_max_spread + : public Splitter_base + { + typedef Splitter_base Base; + + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + + Midpoint_of_max_spread() + : Base() + {} + + Midpoint_of_max_spread(unsigned int bucket_size) + : Base(bucket_size) + {} + + void + operator()(Separator& sep, Container& c0, Container& c1) const + { + sep = Separator(c0.max_tight_span_coord(), + (c0.max_tight_span_upper() + c0.max_tight_span_lower())/FT(2)); + c0.split(c1,sep); + } + }; + + template > + class Midpoint_of_rectangle + : public Splitter_base + { + + typedef Splitter_base Base; + public: + typedef typename SearchTraits::FT FT; + typedef Point_container Container; + typedef Separator_ Separator; + + + Midpoint_of_rectangle() + : Base() + {} + + Midpoint_of_rectangle(unsigned int bucket_size) + : Base(bucket_size) + {} + + void + operator()(Separator& sep, Container& c0, Container& c1) const + { + sep = Separator(c0.max_span_coord(), + (c0.max_span_upper() + c0.max_span_lower())/FT(2)); + c0.split(c1,sep); + } + + }; + +} // namespace CGAL +#endif // CGAL_SPLITTERS -- cgit v1.2.3