#include <conio.h>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <time.h>
#include <vector>
#include <algorithm>
using namespace std;
// A few notes...
// Make sure all points are unique before inserting them into the Kdtree.
// The only functions you should call are the constructor and searchtree:
// Kdtree(const vector<Point> &P)
// vector<Point> searchtree(float x0, float y0, float x1, float y1)
struct Point {
float x, y;
bool operator==(const Point &p2)
{
return (x == p2.x && y == p2.y);
}
Point(float x, float y)
{
this->x = x;
this->y = y;
}
Point()
{
}
};
class Kdtree {
struct Node
{
Point p;
Node *left, *right;
Node(const Point &p)
{
this->p = p;
this->left = NULL;
this->right = NULL;
}
};
Node *root;
public:
Kdtree(const vector<Point> &P)
{
root = buildkdtreemain(P);
}
vector<Point> searchtree(float x0, float y0, float x1, float y1)
{
vector<Point> pointoutputvector;
searchkdtree(root, Range(x0, y0, x1, y1), pointoutputvector);
return pointoutputvector;
}
~Kdtree()
{
deleteallnodes(root);
}
private:
bool lessthanx(const Point &p1, const Point &p2)
{
if (p1.x != p2.x) return (p1.x < p2.x);
else return (p1.y < p2.y);
}
bool lessthany(Point &p1, Point &p2)
{
if (p1.y != p2.y) return (p1.y < p2.y);
else return (p1.x < p2.x);
}
struct PointSortX
{
bool operator () (const Point& p1, const Point &p2)
{
if (p1.x != p2.x) return (p1.x < p2.x);
else return (p1.y < p2.y);
}
};
struct PointSortY
{
bool operator () (const Point& p1, const Point &p2)
{
if (p1.y != p2.y) return (p1.y < p2.y);
else return (p1.x < p2.x);
}
};
struct Range {
float x0, y0;
float x1, y1;
Range(float x0, float y0, float x1, float y1)
{
this->x0 = x0;
this->y0 = y0;
this->x1 = x1;
this->y1 = y1;
}
Range(void)
{
}
};
// depth is 0 for an x level
// depth is 1 for a y level
Node* buildkdtree(vector<Point> &xsorted, vector<Point> &ysorted, int depth)
{
if (xsorted.size()==0) return NULL;
else if (xsorted.size()==1) return new Node(xsorted[0]);
int n = xsorted.size();
int medianindex = (n-1)/2;
if (!depth) {
Point L = xsorted[medianindex];
vector<Point> P1newxsorted(xsorted.begin(), xsorted.begin()+medianindex+1);
vector<Point> P2newxsorted(xsorted.begin()+medianindex+1, xsorted.end());
vector<Point> P1newysorted, P2newysorted;
vector<Point>::iterator i = ysorted.begin();
while (i != ysorted.end())
{
Point p = *i++;
if (lessthanx(p, L) || p == L) P1newysorted.push_back(p);
else P2newysorted.push_back(p);
}
Node *v = new Node(L);
v->left = buildkdtree(P1newxsorted, P1newysorted, !depth);
v->right = buildkdtree(P2newxsorted, P2newysorted, !depth);
return v;
}
else {
Point L = ysorted[medianindex];
vector<Point> P1newysorted(ysorted.begin(), ysorted.begin()+medianindex+1);
vector<Point> P2newysorted(ysorted.begin()+medianindex+1, ysorted.end());
vector<Point> P1newxsorted, P2newxsorted;
vector<Point>::iterator i = xsorted.begin();
while (i != xsorted.end())
{
Point p = *i++;
if (lessthany(p, L) || p == L) P1newxsorted.push_back(p);
else P2newxsorted.push_back(p);
}
Node *v = new Node(L);
v->left = buildkdtree(P1newxsorted, P1newysorted, !depth);
v->right = buildkdtree(P2newxsorted, P2newysorted, !depth);
return v;
}
}
Node* buildkdtreemain(const vector<Point> &P)
{
if (P.size()==0) return NULL;
else if (P.size()==1) return new Node(P[0]);
vector<Point> xsorted(P);
sort(xsorted.begin(), xsorted.end(), PointSortX());
vector<Point> ysorted(P);
sort(ysorted.begin(), ysorted.end(), PointSortY());
return buildkdtree(xsorted, ysorted, 0);
}
bool pointinregion(const Point &p, const Range &r)
{
if (
p.x >= r.x0
&& p.x <= r.x1
&& p.y >= r.y0
&& p.y <= r.y1) return true;
else return false;
}
bool isfullycontained(const Range &small, const Range &big)
{
if (small.x0 >= big.x0
&& small.y0 >= big.y0
&& small.x1 <= big.x1
&& small.y1 <= big.y1) return true;
else return false;
}
bool intersects(const Range &r0, const Range &r1)
{
if (r0.x0 > r1.x1) return false;
else if (r1.x0 > r0.x1) return false;
else if (r0.y0 > r1.y1) return false;
else if (r1.y0 > r0.y1) return false;
else return true;
}
void reportsubtree(Node *v, vector<Point> &pointoutputvector)
{
if (v == NULL) return;
reportsubtree(v->left, pointoutputvector);
reportsubtree(v->right, pointoutputvector);
if (!v->right && !v->left) pointoutputvector.push_back(v->p);
}
// depth will be 0 if we're at an x partition and 1 if we're at a y partition
void searchkdtree(Node *v, const Range &R, int depth, const Range ®ionv, vector<Point> &pointoutputvector)
{
if (!v->left && !v->right)
{
if (pointinregion(v->p, R)) pointoutputvector.push_back(v->p);
return;
}
Range leftregion = regionv;
if (!depth) leftregion.x1 = v->p.x;
else leftregion.y1 = v->p.y;
if (isfullycontained(leftregion, R)) reportsubtree(v->left, pointoutputvector);
else if (intersects(leftregion, R)) searchkdtree(v->left, R, !depth, leftregion, pointoutputvector);
Range rightregion = regionv;
if (!depth) rightregion.x0 = v->p.x;
else rightregion.y0 = v->p.y;
if (isfullycontained(rightregion, R)) reportsubtree(v->right, pointoutputvector);
else if (intersects(rightregion, R)) searchkdtree(v->right, R, !depth, rightregion, pointoutputvector);
}
void searchkdtree(Node *v, Range R, vector<Point> &pointoutputvector)
{
if (v == NULL) return;
Range regionv;
float infinity = std::numeric_limits< float >::infinity();
regionv.x0 = -infinity;
regionv.y0 = -infinity;
regionv.x1 = infinity;
regionv.y1 = infinity;
searchkdtree(v, R, 0, regionv, pointoutputvector);
}
void deleteallnodes(Node *root)
{
if (root == NULL) return;
deleteallnodes(root->left);
deleteallnodes(root->right);
delete root;
}
};
code critique
Please let me know what you think of my kdtree code:
mike
http://www.coolgroups.com/kdtree
[Edited by - mike74 on August 30, 2005 6:13:27 AM]
Replace <code> and </code> with [source] and [/source] respectively, more people will bother to read it if it's nicely formatted in a source box [smile]
Hey,
1. 'using namespace std' is a bad idea. Just 'using' what you need when you need it.
2. For the constructor:
Point(float x, float y)
{
this->x = x;
this->y = y;
}
In your struct, initialise the variables in the initialisation list like this:
Point(float x, float y)
:
x(x), y(y)
{
}
3. Make sure all of the paths in your functions return. So where you have
if(...){...}
else return false;
make it:
if (...){...}
return;
This makes for easier reading.
4. Not a problem really but i can never get on with your the coding style of this:
class MyClass {
};
I much prefer reading and debugging code that looks like this:
class MyClass
{
};
This way it is easier to match up the scope brackets for quicker debugging.
4. Here you are returning a variable by value and in this case if the vector becomes huge then this will get slower.
vector<Point> searchtree(float x0, float y0, float x1, float y1)
{
vector<Point> pointoutputvector;
searchkdtree(root, Range(x0, y0, x1, y1), pointoutputvector);
return pointoutputvector;
}
I suggest passing a reference to the output vector as a parameter to the method.
5. On line 147 i would suggest rewriting this code with a for loop,
while (i != ysorted.end())
{
Point p = *i++;
if (lessthanx(p, L) || p == L) P1newysorted.push_back(p);
else P2newysorted.push_back(p);
}
to:
for ( i = ysorted.begin();
i != ysorted.end();
++i )
{
...
}
It is important to note that i am using ++i here rather than i++ it is faster.
Hope these points help,
ace
1. 'using namespace std' is a bad idea. Just 'using' what you need when you need it.
2. For the constructor:
Point(float x, float y)
{
this->x = x;
this->y = y;
}
In your struct, initialise the variables in the initialisation list like this:
Point(float x, float y)
:
x(x), y(y)
{
}
3. Make sure all of the paths in your functions return. So where you have
if(...){...}
else return false;
make it:
if (...){...}
return;
This makes for easier reading.
4. Not a problem really but i can never get on with your the coding style of this:
class MyClass {
};
I much prefer reading and debugging code that looks like this:
class MyClass
{
};
This way it is easier to match up the scope brackets for quicker debugging.
4. Here you are returning a variable by value and in this case if the vector becomes huge then this will get slower.
vector<Point> searchtree(float x0, float y0, float x1, float y1)
{
vector<Point> pointoutputvector;
searchkdtree(root, Range(x0, y0, x1, y1), pointoutputvector);
return pointoutputvector;
}
I suggest passing a reference to the output vector as a parameter to the method.
5. On line 147 i would suggest rewriting this code with a for loop,
while (i != ysorted.end())
{
Point p = *i++;
if (lessthanx(p, L) || p == L) P1newysorted.push_back(p);
else P2newysorted.push_back(p);
}
to:
for ( i = ysorted.begin();
i != ysorted.end();
++i )
{
...
}
It is important to note that i am using ++i here rather than i++ it is faster.
Hope these points help,
ace
Thanks for the comments. Can you explain why ++i is faster than i++ and maybe point me to a confirmation? I haven't heard of that, and I don't really see why.
mike
http://www.coolgroups.com/kdtree
mike
http://www.coolgroups.com/kdtree
The reason that ++i is faster is because of the implementation of the increment and what it returns.
The code for i++
const T operator++(T)
{
T temp(*this); // EDIT: Added '*this'
++(*this);
return temp;
}
and the code for ++i
T& operator++(T)
{
(*this) += 1;
return *this;
}
Not entirely sure about the second.
The first is called post increment and the second is called preincrement. As you can see from the implementation of post increment it creates a temporary variable, this is slower that preincrement and should be avoided as good practice. Imagine having your own complicated class where you have overloaded the ++ operator, the creation of another huge class object might well be slow.
It is covered in Exceptional C++ by Herb Sutter (great book) [smile]
ace
[Edited by - ace_lovegrove on August 30, 2005 4:48:40 AM]
The code for i++
const T operator++(T)
{
T temp(*this); // EDIT: Added '*this'
++(*this);
return temp;
}
and the code for ++i
T& operator++(T)
{
(*this) += 1;
return *this;
}
Not entirely sure about the second.
The first is called post increment and the second is called preincrement. As you can see from the implementation of post increment it creates a temporary variable, this is slower that preincrement and should be avoided as good practice. Imagine having your own complicated class where you have overloaded the ++ operator, the creation of another huge class object might well be slow.
It is covered in Exceptional C++ by Herb Sutter (great book) [smile]
ace
[Edited by - ace_lovegrove on August 30, 2005 4:48:40 AM]
Interesting. So, this is just true for most iterators? Is it true for any other objects in general? I'm guessing it's not the case for incrementing integers.
mike
http://www.coolgroups.com/
mike
http://www.coolgroups.com/
Even for incementing integers it is slower. But on todays computers the difference is negligable on standard types. I would suggest getting into the habit though, its a good one to maintain, and knowing the difference is a good one to know at job interviews.
I would suggest doing it for iterators of the standard containers as well.
[smile]
ace
EDIT: Edited the code for post and pre increment operators posted above.
I would suggest doing it for iterators of the standard containers as well.
[smile]
ace
EDIT: Edited the code for post and pre increment operators posted above.
One more thing. For the following function, do you think I need to check if the node v is NULL? It seems like it is on VERY rare occasions, and I'm not sure if that means I did something else wrong.
// depth will be 0 if we're at an x partition and 1 if we're at a y partition
void searchkdtree(Node *v, const Range &R, int depth, const Range ®ionv, vector<Point> &pointoutputvector)
{
if (!v->left && !v->right)
{
if (pointinregion(v->p, R)) pointoutputvector.push_back(v->p);
return;
}
Range leftregion = regionv;
if (!depth) leftregion.x1 = v->p.x;
else leftregion.y1 = v->p.y;
if (isfullycontained(leftregion, R)) reportsubtree(v->left, pointoutputvector);
else if (intersects(leftregion, R)) searchkdtree(v->left, R, !depth, leftregion, pointoutputvector);
Range rightregion = regionv;
if (!depth) rightregion.x0 = v->p.x;
else rightregion.y0 = v->p.y;
if (isfullycontained(rightregion, R)) reportsubtree(v->right, pointoutputvector);
else if (intersects(rightregion, R)) searchkdtree(v->right, R, !depth, rightregion, pointoutputvector);
}
mike
http://www.coolgroups.com/kdtree
// depth will be 0 if we're at an x partition and 1 if we're at a y partition
void searchkdtree(Node *v, const Range &R, int depth, const Range ®ionv, vector<Point> &pointoutputvector)
{
if (!v->left && !v->right)
{
if (pointinregion(v->p, R)) pointoutputvector.push_back(v->p);
return;
}
Range leftregion = regionv;
if (!depth) leftregion.x1 = v->p.x;
else leftregion.y1 = v->p.y;
if (isfullycontained(leftregion, R)) reportsubtree(v->left, pointoutputvector);
else if (intersects(leftregion, R)) searchkdtree(v->left, R, !depth, leftregion, pointoutputvector);
Range rightregion = regionv;
if (!depth) rightregion.x0 = v->p.x;
else rightregion.y0 = v->p.y;
if (isfullycontained(rightregion, R)) reportsubtree(v->right, pointoutputvector);
else if (intersects(rightregion, R)) searchkdtree(v->right, R, !depth, rightregion, pointoutputvector);
}
mike
http://www.coolgroups.com/kdtree
It is good practice to always confirm the validity of pointers passed as parameters to functions. You can then exit gracefully if the user provides corrupt information to the function.
ace
ace
Quote:Original post by ace_lovegrove
Even for incementing integers it is slower. But on todays computers the difference is negligable on standard types.
That's funny, I actually wrote a benchmark a long time back in Turbo C/c++ and did an assembly output and it WAS true that the i++ uses a temporary and the ++i didn't, HOWEVER if you do an assembly output via msvc 6, or similar recent compiler it generates identical code in both cases. The moral of the story, for general cases it makes no difference whatsoever, but a few cases it is still true. That being said, I still prefer to use the pre-increment/decrement just so I am in the habbit for when it could actually be useful, and the fact that I use some not-so-up-to-date compilers for PIC programming, etc, it is still faster in some cases.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement