NearestRectangleFinder.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/geometry.h>
 
#include <ostream>
 
namespace ogdf {
template<class E>
class List;
 
class OGDF_EXPORT NearestRectangleFinder {
public:
    struct PairCoordId;
    struct PairRectDist;
    struct RectRegion;
 
    explicit NearestRectangleFinder(double mad = 20, double td = 5) {
        m_maxAllowedDistance = mad;
        m_toleranceDistance = td;
    }
 
    // the maximal allowed distance between a rectangle and a point
    // rectangles with a greater distance are not considered
    void maxAllowedDistance(double mad) { m_maxAllowedDistance = mad; }
 
    double maxAllowedDistance() const { return m_maxAllowedDistance; }
 
    // the tolerance in which rectangles are considered to be ambigous, i.e.
    // if the rectangle with the minimum distance to point p has distance mindist
    // and there is another rectangle with distance dist such that
    // dist <= minDist + toleranceDistance, we say that the closest rectangle is not unique.
    void toleranceDistance(double td) { m_toleranceDistance = td; }
 
    double toleranceDistance() const { return m_toleranceDistance; }
 
    // finds the nearest rectangles for a given set of points
    // The nearest rectangles are passed in a list. If the list is empty, there
    // is no rectangle within the ,aximal allowed distance. If the list contains
    // more than one element, the nearest rectangle is not unique for the
    // given tolerance.
    void find(const Array<RectRegion>& region, // given rectangles
            const Array<DPoint>& point, // given points
            Array<List<PairRectDist>>& nearest); // nearest rectangles
 
    // trivial implementation of find(). Can be used in order to check
    // correctness. Computes only rectangle with minimum distance without
    // considering maxAllowedDistance and toleranceDistance.
    void findSimple(const Array<RectRegion>& region, const Array<DPoint>& point,
            Array<List<PairRectDist>>& nearest);
 
private:
    class CoordComparer;
    class YCoordComparer;
 
    double m_maxAllowedDistance;
    double m_toleranceDistance;
};
 
struct NearestRectangleFinder::RectRegion {
    friend std::ostream& operator<<(std::ostream& os, const RectRegion& rect) {
        os << "(" << rect.m_x << "," << rect.m_y << ":" << rect.m_width << "," << rect.m_height
           << ")";
        return os;
    }
 
    double m_x, m_y, m_width, m_height;
};
 
struct OGDF_EXPORT NearestRectangleFinder::PairRectDist {
    PairRectDist() { }
 
    PairRectDist(int index, double distance) {
        m_index = index;
        m_distance = distance;
    }
 
    friend std::ostream& operator<<(std::ostream& os, const PairRectDist& p) {
        os << "(" << p.m_index << "," << p.m_distance << ")";
        return os;
    }
 
    int m_index;
    double m_distance;
};
 
 
}