ext/OGDF/ogdf/basic/NearestRectangleFinder.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class NearestRectangleFinder
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48
  49 #ifndef OGDF_NEAREST_RECTANGLE_FINDER_H
  50 #define OGDF_NEAREST_RECTANGLE_FINDER_H
  51
  52
  53 #include <ogdf/basic/Array.h>
  54 #include <ogdf/basic/geometry.h>
  55
  56
  57 namespace ogdf {
  58
  59
  60 //---------------------------------------------------------
  61 // NearestRectangleFinder
  62 // finds in a given set of rectangles for each point in a given
  63 // set of points the nearest rectangle
  64 //---------------------------------------------------------
  65 class OGDF_EXPORT NearestRectangleFinder
  66 {
  67 public:
  68         struct RectRegion;
  69         struct PairRectDist;
  70         struct PairCoordId;
  71
  72         NearestRectangleFinder(double mad = 20, double td = 5) {
  73                 m_maxAllowedDistance = mad;
  74                 m_toleranceDistance = td;
  75         }
  76
  77         // the maximal allowed distance between a rectangle and a point
  78         // rectangles with a greater distance are not considered
  79         void maxAllowedDistance(double mad) { m_maxAllowedDistance = mad; }
  80         double maxAllowedDistance() const { return m_maxAllowedDistance; }
  81
  82         // the tolerance in which rectangles are considered to be ambigous, i.e.
  83         // if the rectangle with the minimum distance to point p has distance mindist
  84         // and there is another rectangle with distance dist such that
  85         // dist <= minDist + toleranceDistance, we say that the closest rectangle is not unique.
  86         void toleranceDistance(double td) { m_toleranceDistance = td; }
  87         double toleranceDistance() const { return m_toleranceDistance; }
  88
  89
  90         // finds the nearest rectangles for a given set of points
  91         // The nearest rectangles are passed in a list. If the list is empty, there
  92         // is no rectangle within the ,aximal allowed distance. If the list contains
  93         // more than one element, the nearest rectangle is not unique for the
  94         // given tolerance.
  95         void find(
  96                 const Array<RectRegion> &region, // given rectangles
  97                 const Array<DPoint> &point,      // given points
  98                 Array<List<PairRectDist> > &nearest); // nearest rectangles
  99
 100         // trivial implementation of find(). Can be used in order to check
 101         // correctness. Computes only rectangle with minimum distance without
 102         // considering maxAllowedDistance and toleranceDistance.
 103         void findSimple(
 104                 const Array<RectRegion> &region,
 105                 const Array<DPoint> &point,
 106                 Array<List<PairRectDist> > &nearest);
 107
 108 private:
 109         class CoordComparer;
 110         class YCoordComparer;
 111
 112         double m_maxAllowedDistance;
 113         double m_toleranceDistance;
 114 };
 115
 116
 117 //---------------------------------------------------------
 118 // RectRegion
 119 // represents a rectangle given by center point, width and height
 120 //---------------------------------------------------------
 121 struct NearestRectangleFinder::RectRegion
 122 {
 123         friend ostream &operator<<(ostream &os, const RectRegion &rect) {
 124                 os << "(" << rect.m_x << "," << rect.m_y << ":" <<
 125                         rect.m_width << "," << rect.m_height << ")";
 126                 return os;
 127         }
 128
 129         double m_x, m_y, m_width, m_height;
 130 };
 131
 132
 133 //---------------------------------------------------------
 134 // PairRectDist
 135 // represents a rectangle (given by its index) and a
 136 // distance value
 137 //---------------------------------------------------------
 138 struct OGDF_EXPORT NearestRectangleFinder::PairRectDist
 139 {
 140         PairRectDist() { }
 141
 142         PairRectDist(int index, double distance) {
 143                 m_index = index;
 144                 m_distance = distance;
 145         }
 146
 147         friend ostream &operator<<(ostream &os, const PairRectDist &p) {
 148                 os << "(" << p.m_index << "," << p.m_distance << ")";
 149                 return os;
 150         }
 151
 152         int m_index;
 153         double m_distance;
 154 };
 155
 156
 157
 158 } // end namespace ogdf
 159
 160
 161 #endif