STL set with custom data type

[cata.1972]

Hi,

I have structure representing a 2 dimesional point:

struct K2dCoords
{
K2dCoords(void):m_x(0), m_y(0){};
K2dCoords(double x, double y):m_x(x), m_y(y){};
K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
double getX() const {return m_x;}
double getY() const {return m_y;}
double m_x;
double m_y;
};

I want to store pointers to instances of this in a STL set.
So I define the sorting criterion, such that two points are considered
equal
if the distance between them is negligeble (less than a tolerance):

struct eq
{
bool operator() (const K2dCoords* p1, const K2dCoords* p2) const
{
const double tol = 0.25 / 1E3;
return sqrt((p1->getX() - p2->getX()) * (p1->getX() - p2->getX
()) + (p1->getY() - p2->getY()) * (p1->getY() - p2->getY())) > tol;
}
};

The problem is that after I've inserted some point in my set, I cannot
find them:

// some initialisation data
const double inc = 0.25;
const double deckLength = 1.0;
const double deckWidth = 0.48;
double x = 0;
double y = 0;
const double PI = 3.1415926;
std::set<K2dCoords*, eq> stlMap;

// create some points and add them to my set
while (x <= deckLength)
{
while (y <= deckWidth)
{
const double xSp = x * cos(30.0 * PI / 180.0) - y * sin
(30.0 * PI / 180.0);
const double ySp = x * sin(30.0 * PI / 180.0) + y * cos
(30.0 * PI / 180.0);
stlMap.insert(new K2dCoords(xSp, ySp));
y += inc;
}
x += inc;
y = 0;
}

// check if I've got them; the test point are created in the same
way as they were created for insertion
x = 0;
y = 0;
while (x <= deckLength)
{
while (y <= deckWidth)
{
const double xSp = x * cos(30.0 * PI / 180.0) - y * sin
(30.0 * PI / 180.0);
const double ySp = x * sin(30.0 * PI / 180.0) + y * cos
(30.0 * PI / 180.0);
std::set<K2dCoords*, eq>::iterator it = stlMap.find(new
K2dCoords(xSp, ySp));
if (it == stlMap.end())
{
ASSERT(FALSE); // suerly this should not assert, but
it does (when x=0.25 and y=0)!!!
}
y += inc;
}
x += inc;
y = 0;
}

What am I doing wrong? Thanks.

 

[joecook]

Hi,

I have structure representing a 2 dimesional point:

I want to store pointers to instances of this in a STL set.
So I define the sorting criterion, such that two points are considered
equal
if the distance between them is negligeble (less than a tolerance):

struct eq
{
    bool operator() (const K2dCoords* p1, const K2dCoords* p2) const
    {
        const double tol = 0.25 / 1E3;
        return sqrt((p1->getX() - p2->getX()) * (p1->getX() - p2->getX
()) + (p1->getY() - p2->getY()) * (p1->getY() - p2->getY())) > tol;
    }

What am I doing wrong? Thanks.

Your sorting criteria doesn't allow for proper sorting. It just
returns if two elements are near each other. std::set relies on a
strict weak ordering. Your function therefore should never return A
< B is true as well as B < A is also true.
For elements that you want to consider equal, operator(A,B) and
operator(B,A) should both return false. For elements not equal,
operator(A,B) _must_ return the logically opposite value of operator
(B,A).

HTH,
Joe

 

[Bart van Ingen Schenau]

Hi,

I have structure representing a 2 dimesional point:

struct K2dCoords
{
    K2dCoords(void):m_x(0), m_y(0){};
    K2dCoords(double x, double y):m_x(x), m_y(y){};
    K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
    double getX() const {return m_x;}
    double getY() const {return m_y;}
    double m_x;
    double m_y;

};

I want to store pointers to instances of this in a STL set.
So I define the sorting criterion, such that two points are considered
equal
if the distance between them is negligeble (less than a tolerance):

What am I doing wrong? Thanks.

You are using a sorting criterion that std::set<> can't handle.
std::set<> does not care about the equality of two points, it wants to
know if P1 comes before P2 or not. Only if neither P1 comes before P2
nor P2 comes before P1, then P1 and P2 are considered to be equal.

Another problem is your use of tolerances. std::set<> also requires
that the following equation holds:
if P1 == P2 && P2 == P3 then P1 == P3
When using tolerances, there is a big chance that this equation does
not hold for all points in the set, and that is bad.

Bart v Ingen Schenau

 

[SG]

Hi,

I have structure representing a 2 dimesional point:

struct K2dCoords
{
    K2dCoords(void):m_x(0), m_y(0){};
    K2dCoords(double x, double y):m_x(x), m_y(y){};
    K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
    double getX() const {return m_x;}
    double getY() const {return m_y;}
    double m_x;
    double m_y;
};

I want to store pointers to instances of this in a STL set.
So I define the sorting criterion, such that two points are considered
equal
if the distance between them is negligeble (less than a tolerance):

struct eq

As others have pointed out std::set needs a "strict weak order"-
predicate.

Also, why do you go through the trouble of using pointers? Is there a
need for pointers here?

stlMap.insert(new K2dCoords(xSp, ySp));

You know that you could also write

set<K2dCoords> myset;
myset.insert(K2dCoords(3.14,23.0));

Right?


The problem you want to solve is to detect whether a new point is
"close enough" to another point that's already in the data structure
("set") and if not, to add the point to the data structure, right?
This usually calls for something like a kd-tree:

http://en.wikipedia.org/wiki/Kd-tree
http://en.wikipedia.org/wiki/Nearest_neighbour_search

The alternative is to use a lexical ordering and to compare the new
point with every other point of the set's relevant subrange. Of
course a NNS won't be as fast as with a kd-tree but for 2D it's
probably still ok to do it that way (assuming the number of points is
not too big). You could write a functions like this:

/// any simple p-metric for p=1...infinity
double distance(const K2dCoords& a, const K2dCoords& b);

/// checks whether the set contains a point q with
/// distance(q,pnew) < epsilon
bool has_neighbour(const set<K2dCoords>& points,
const K2dCoords& pnew, double epsilon)
{
typedef set<K2dCoords>::const_iterator iter_t;
const K2dCoords corner1 (pnew.getX()-epsilon, pnew.getY()-
epsilon);
const K2dCoords corner2 (pnew.getX()+epsilon, pnew.getY()
+epsilon);
iter_t beg = points.lower_bound(corner1);
iter_t end = points.upper_bound(corner2);
while (beg!=end) {
if (distance(pnew,*beg) < epsilon) return true;
++beg;
}
return false;
}

This should work for a lexical ordering and an epsilon>0. I didn't
test it, though. You get the idea.


Cheers!
SG

 

[cata.1972]

As others have pointed out std::set needs a "strict weak order"-
predicate.

Also, why do you go through the trouble of using pointers?  Is there a
need for pointers here?


You know that you could also write

   set<K2dCoords> myset;
   myset.insert(K2dCoords(3.14,23.0));

Right?

The problem you want to solve is to detect whether a new point is
"close enough" to another point that's already in the data structure
("set") and if not, to add the point to the data structure, right?
This usually calls for something like a kd-tree:

 http://en.wikipedia.org/wiki/Kd-tree
 http://en.wikipedia.org/wiki/Nearest_neighbour_search

The alternative is to use a lexical ordering and to compare the new
point with every other point of the set's relevant subrange.  Of
course a NNS won't be as fast as with a kd-tree but for 2D it's
probably still ok to do it that way (assuming the number of points is
not too big).  You could write a functions like this:

  /// any simple p-metric for p=1...infinity
  double distance(const K2dCoords& a, const K2dCoords& b);

  /// checks whether the set contains a point q with
  /// distance(q,pnew) < epsilon
  bool has_neighbour(const set<K2dCoords>& points,
    const K2dCoords& pnew, double epsilon)
  {
    typedef set<K2dCoords>::const_iterator iter_t;
    const K2dCoords corner1 (pnew.getX()-epsilon, pnew.getY()-
epsilon);
    const K2dCoords corner2 (pnew.getX()+epsilon, pnew.getY()
+epsilon);
    iter_t beg = points.lower_bound(corner1);
    iter_t end = points.upper_bound(corner2);
    while (beg!=end) {
      if (distance(pnew,*beg) < epsilon) return true;
      ++beg;
    }
    return false;
  }

This should work for a lexical ordering and an epsilon>0.  I didn't
test it, though.  You get the idea.

Cheers!
SG- Hide quoted text -

- Show quoted text -

Thank you all.
That's right, I want a data structure able to return me a point that's
close enough to a given point. I see now why the STL set won't work
and this problem is a lot more complicated than I initially thought.
There's no chance of getting one of this data structure into STL or
Boost in future, is there?