#include "kdDS.h"
#include <GL/glut.h>
// -------------------------------kdNode Implementation -----------------------
//-----------------------------------------------------------------------------
kdNode::kdNode()
//-----------------------------------------------------------------------------
{
}
//-----------------------------------------------------------------------------
//plist ist die Punktmenge des Knotens
//nrPoints gibt an, wieviel Punkte maximal in einen Knoten (Zelle) gehören
kdNode::kdNode(vector<Point>& plist, int nrPoints)
//-----------------------------------------------------------------------------
{
leaf = false;
unsigned int nrOfElements = plist.size();
//finde die Begrenzungspunkte für diese Zelle/Knoten
pMin = plist.at(0);
pMax = plist.at(0);
for(int i = 0; i < nrOfElements; i++)
{
for(int j = 0; j < 3; j++)
{
//suche nach kleinstem Wert in jeder Dimension
if((plist.at(i)).p[j] < pMin.p[j])
{
pMin.p[j] = (plist.at(i)).p[j];
}
//suche nach größtem Wert in jeder Dimension
if((plist.at(i)).p[j] > pMax.p[j])
{
pMax.p[j] = (plist.at(i)).p[j];
}
}
}
//unterteile, falls mehr Punkte in Knoten als gewünscht
if(plist.size() > nrPoints)
{
Point diff = pMax - pMin;
//printf("Diff: %f/%f/%f\n", diff.p[0], diff.p[1], diff.p[2]);
vector<Point> leftList, rightList;
//Teile Zelle/Knoten entlang der weitesten Ausdehnung
if(diff.p[0] > diff.p[1] && diff.p[0] > diff.p[2])
{
//median cut on x-axis
doMedianCut(plist, leftList, rightList, 0);
} else
if(diff.p[1] > diff.p[2])
{
//median cut on y-axis
doMedianCut(plist, leftList, rightList, 1);
} else
{
//median cut on z-axis
doMedianCut(plist, leftList, rightList, 2);
}
left = new kdNode(leftList, nrPoints);
right = new kdNode(rightList, nrPoints);
} else
//falls Punktmenge des Knotens klein genug, wird Knoten zu einem Blatt
//und die Punkte werden gesichert
{
points = plist;
leaf = true;
}
}
//-----------------------------------------------------------------------------
//berechnet die Entfernung eines Punktes zu dieser Zelle/Knoten
float kdNode::distance(const Point& p)
//-----------------------------------------------------------------------------
{
Point a = pMin - p;
Point b = p - pMax;
int i;
for(i = 0; i < 3; i++)
{
//prüfe, wo p[i] liegt - Annahme: 'links' von pMin
//Abstand Zelle-Punkt: pMin - p
if(a.p[i] < 0.0)
//p[i] liegt 'rechts' von pMin - aber wo genau? (Annahme revidiert)
{
if(b.p[i] < 0.0)
//p[i] liegt zwischen pMin und pMax - Abstand Zelle-Punkt: 0
{
a.p[i] = 0.0;
}
else
//p[i] liegt 'rechts' von pMax - Abstand Zelle-Punkt: p - pMax
{
a.p[i] = b.p[i];
}
}
}
//printf("Distance function finished!\n");
return a.length();
}
//-----------------------------------------------------------------------------
void kdNode::collectInRadius(vector<Point>& plist, Point& p, float radius)
//-----------------------------------------------------------------------------
{
if(distance(p) <= radius)
{
if(!leaf)
{
left->collectInRadius(plist, p, radius);
right->collectInRadius(plist, p, radius);
} else
{
Point distVect;
float dist;
for(int i = 0; i < points.size(); i++)
{
//use distance funktion
//temporal verwende einfache Distanzberechnung
distVect = p - points.at(i);
dist = distVect.length();
if(dist <= radius)
{
plist.push_back(points.at(i));
}
}
}
}
}
//-----------------------------------------------------------------------------
//berechnet die Entfernung eines Punktes zu dieser Zelle/Knoten
float kdNode::distance2D(const Point& p)
//-----------------------------------------------------------------------------
{
Point a = pMin - p;
Point b = p - pMax;
int i;
for(i = 0; i < 2; i++)
{
//prüfe, wo p[i] liegt - Annahme: 'links' von pMin
//Abstand Zelle-Punkt: pMin - p
if(a.p[i] < 0.0)
//p[i] liegt 'rechts' von pMin - aber wo genau? (Annahme revidiert)
{
if(b.p[i] < 0.0)
//p[i] liegt zwischen pMin und pMax - Abstand Zelle-Punkt: 0
{
a.p[i] = 0.0;
}
else
//p[i] liegt 'rechts' von pMax - Abstand Zelle-Punkt: p - pMax
{
a.p[i] = b.p[i];
}
}
}
a.p[2] = 0.0;
//printf("Distance function finished!\n");
return a.length();
}
//-----------------------------------------------------------------------------
void kdNode::collectInRadius2D(vector<Point>& plist, Point& p, float radius)
//-----------------------------------------------------------------------------
{
if(distance2D(p) <= radius)
{
if(!leaf)
{
left->collectInRadius2D(plist, p, radius);
right->collectInRadius2D(plist, p, radius);
} else
{
Point distVect;
float dist;
for(int i = 0; i < points.size(); i++)
{
//use distance funktion
//temporal verwende einfache Distanzberechnung
distVect = p - points.at(i);
distVect.p[2] = 0.0;
dist = distVect.length();
if(dist <= radius)
{
plist.push_back(points.at(i));
}
}
}
}
}
//-----------------------------------------------------------------------------
Point kdNode::getMin()
//-----------------------------------------------------------------------------
{
return pMin;
}
//-----------------------------------------------------------------------------
Point kdNode::getMax()
//-----------------------------------------------------------------------------
{
return pMax;
}
//-----------------------------------------------------------------------------
void kdNode::draw(bool colored)
//-----------------------------------------------------------------------------
{
//zeichne den kdTree rekursiv
if(!leaf){
left->draw(colored);
right->draw(colored);
} else
{
//glEnable(GL_LIGHTING);
glDisable(GL_LIGHTING);
glColor3f(1.0, 1.0, 0.0);
if(colored)
{
Point col = pMin;
col.normalize();
col = col / 2.0;
glColor3f(0.5 + col.p[0], 0.5 + col.p[1], 0.5 + col.p[2]);
}
glBegin(GL_POINTS);
//start painting model
for(int i = 0; i < points.size(); i++)
{
//set point of triangle
glVertex3fv(points.at(i).p);
} //end painting model
glEnd();
glEnable(GL_LIGHTING);
}
}
//-----------------------------------------------------------------------------
void kdNode::sort(vector<Point>& pts, int key)
//-----------------------------------------------------------------------------
{
int minIndex;
Point p;
int i;
for(i = 0; i < pts.size() - 1; i++)
{
minIndex = i;
for(int j = i + 1; j < pts.size(); j++)
{
if(pts.at(j).p[key] < pts.at(minIndex).p[key])
{
minIndex = j;
}
}
p = pts.at(i);
pts.at(i) = pts.at(minIndex);
pts.at(minIndex) = p;
/*
if(i!=minIndex)
printf("Punkte vertauscht: i=%d minIndex=%d\nmin(%f/%f/%f), anderer (%f/%f/%f)\n",
i, minIndex, pts.at(minIndex).p[0], pts.at(minIndex).p[1], pts.at(minIndex).p[2],
pts.at(i).p[0], pts.at(i).p[1], pts.at(i).p[2]);
*/
}
}
// -------------------------------kdDS Implementation -------------------------
//-----------------------------------------------------------------------------
kdDS::kdDS()
//-----------------------------------------------------------------------------
{
cellSize = 10;
}
//-----------------------------------------------------------------------------
kdDS::kdDS(int size)
//-----------------------------------------------------------------------------
{
cellSize = size;
}
//-----------------------------------------------------------------------------
kdDS::~kdDS()
//-----------------------------------------------------------------------------
{
}
//-----------------------------------------------------------------------------
vector<Point> kdDS::collectKNearest(Point& p, int knearest)
//-----------------------------------------------------------------------------
{
vector<Point> pts;
//berechne Diagonalenlänge der BigBox
Point diff = root->getMax() - root->getMin();
float dimension = diff.length();
//berechne Entfernung des ggb. Punktes zur Punktmenge (BigBox)
float dist = root->distance(p);
//falls mehr Pkte gefordert als vorhanden, gib gleich zurück
if(knearest >= nrOfPoints)
{
root->collectInRadius(pts, p, dist + dimension);
//Sortierung wird für korrekte Frameworkdarstellung gebraucht
//quickSortDistance(pts, p, 0, pts.size());
return pts;
}
//extra secret speed code!!!
float multiplikator;
if(dist == 0)
{
Point middle = root->getMin() + (diff / 2);
diff = p - middle;
multiplikator = 0.5 + 0.8 * diff.length() / (dimension);
} else
{
multiplikator = 1.0;
}
float aspect;
//printf("Im searching k-nearest Pts! Distance: %f Size: %d\n Dimension: %f Aspect: %f\n",
// dist, pts.size(), dimension, aspect);
int range;
//Schleife, um günstig viele (ausreichend) Punkte zu erhalten
do {
//prozentualer Anteil von gesuchten Punkten zu Gesamtpunkten
//ist Grundlage für die Radiusbestimmung
aspect = multiplikator * (knearest - pts.size()) / nrOfPoints;
//falls p ausserhalb, vergrößere Suchradius
//if(dist > 0) aspect = 2.0 * aspect;
//vergrößere den Radius schrittweise
dist = dist + dimension * aspect;
pts.clear();
root->collectInRadius(pts, p, dist);
//root->collectKNearest(pts, p, dist);
//verkleinere den zu durchsuchenden Raum
//dimension = dimension - dimension * aspect;
//printf("Im in the k-Nearest Loop! Distance: %f Size: %d\n", dist, pts.size());
} while((range = pts.size() - knearest) < 0);
//sortiere die Liste ...
quickSortDistance(pts, p, 0, pts.size());
//printf("Did Distance-Quicksort!\n");
//...um überschüssige rauszuschmeissen!
//(bessere implemtierung!?);
for(int i = 0; i < range; i++)
{
pts.pop_back();
}
return pts;
}
//-----------------------------------------------------------------------------
vector<Point> kdDS::collectInRadius(Point& p, float radius)
//-----------------------------------------------------------------------------
{
vector<Point> pts;
root->collectInRadius(pts, p, radius);
return pts;
}
//-----------------------------------------------------------------------------
vector<Point> kdDS::collectInRadius2D(Point& p, float radius)
//-----------------------------------------------------------------------------
{
vector<Point> pts;
root->collectInRadius2D(pts, p, radius);
return pts;
}
//-----------------------------------------------------------------------------
void kdDS::draw()
//-----------------------------------------------------------------------------
{
draw(false);
}
//-----------------------------------------------------------------------------
void kdDS::draw(bool colored)
//-----------------------------------------------------------------------------
{
root->draw(colored);
}
//-----------------------------------------------------------------------------
void kdDS::draw(const vector<Point>& plist)
//-----------------------------------------------------------------------------
{
//glEnable(GL_LIGHTING);
glDisable(GL_LIGHTING);
glColor3f(1.0, 1.0, 1.0);
glBegin(GL_POINTS);
//start painting model
for(int i = 0; i < plist.size(); i++)
{
//set point of triangle
glVertex3fv(plist.at(i).p);
} //end painting model
glEnd();
glEnable(GL_LIGHTING);
}
//-----------------------------------------------------------------------------
int kdDS::size()
//-----------------------------------------------------------------------------
{
return nrOfPoints;
}
//-----------------------------------------------------------------------------
void kdDS::setPoints(const vector<Point>& pt)
//-----------------------------------------------------------------------------
{
nrOfPoints = pt.size();
vector<Point> points = pt;
//clock_t start, stop;
//start = clock();
root = new kdNode(points, cellSize);
/*
stop = clock();
clock_t diff = stop - start;
printf("Es dauerte %f sekunden.\n", 1.0 * diff / CLOCKS_PER_SEC);
*/
}
//-----------------------------------------------------------------------------
void kdDS::setCellsize(int size)
//-----------------------------------------------------------------------------
{
cellSize = size;
}
Point kdDS::getMin()
{
return root->getMin();
}
Point kdDS::getMax()
{
return root->getMax();
}
vector<Point> kdDS::getPoints(void)
{
Point p(0,0,0);
return collectKNearest(p, size());
}