Page 1 of 1

## 3 Replies - 898 Views - Last Post: 01 August 2014 - 09:27 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=351313&amp;s=51834cb93d3a14ce21b46aa072da819d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 xnewix

Reputation: 2
• Posts: 207
• Joined: 23-May 09

Posted 30 July 2014 - 01:35 PM

Okay, whilst the code for a linked list below seams to work I would be pleased if someone could critique it.

I plan to use a QuadTree for my terrain project i'm working on, and felt knowledge of this linked list stuff would be needed. I have a few ideas how to translate this into a QuadTree but if anyone could provide an hints that would be cool.

Not to deviate too much from the main topic, but the current structure that I use for creating a mesh is to have a vector for all the points in the terrain and then have another vector to store all the triangles, which store the indexs of the points. I can post it if that's not to clear.

anyway, here is my linked list code.

```#include <iostream>
#include <string>
#include <vector>

class Point3d {
private:
double x,y,z; // or double coord[3];
public:
Point3d(double nx, double ny, double nz) : x(nz), y(ny), z(nz) {
};
~Point3d() {};
void setx(double nx) { x = nx; }
void sety(double ny) { y = ny; }
void setz(double nz) { z = nz; }

double getx() { return x; }
double gety() { return y; }
double getz() { return z; }
};

class Node {
private:
unsigned int pointindices[4]; // indices, but how to prevent duplication of point3d data?
Node *child;
public:
Node() {};
~Node() {};

void setindex(unsigned int arrayposition, unsigned int index) {
//.....
pointindices[arrayposition] = index;
}
void setchild(Node *nchild) {
child = nchild;
}
unsigned int getindex(unsigned int arrayposition) {
//.....
return pointindices[arrayposition];
}
Node *getChild() {
return child;
}
};

class QuadTree { // basically a list for now.
private:
std::vector<Point3d> point3d; // a place to store points.

/* Concerns of data duplication whilst subdividing

std::vector<BoundingBox> boundingbox;

// nw,ne,se,sw are index's for the point3d vector.

void addboundingbox(int nw, int ne, int se, int sw) {
boundingbox.push_back(BoundingBox(nw, ne, se, sw));
}

to be added in Class Node
replace pointindices[4] with unsigned int boundingboxindex;
does this prevent point3d duplicates
*/
public:
};

void Print();
void AppendBack  (unsigned int arrayposition, unsigned int index);
void AppendFront (unsigned int arrayposition, unsigned int index);
void Delete();
};

// head was NULL so the list is empty
if(tmp==NULL) {
std::cout << "This list is empty" << std::endl;
return;
}
// there is only one node present in the list
if(tmp->getChild() ==NULL) {
std::cout << "index: " << tmp->getindex(0) << std::endl;
}
else {
while(tmp->getChild() !=NULL) {
std::cout << "index: " << tmp->getindex(0) << std::endl;
tmp = tmp->getChild();
}
// child of the last node.
if(tmp->getChild() ==NULL) {
std::cout << "index: " << tmp->getindex(0) << std::endl;
}
}
}
void QuadTree::AppendBack(unsigned int arrayposition, unsigned int index) {
// Create new node
Node *newNode = new Node(); // constructor?? Node(.....);

// To be moved to ^^/> constructor.
newNode->setindex(arrayposition, index);
newNode->setchild(NULL);

// tmp

// if ignored on 1st run, move to else.
if(tmp !=NULL) {

// what is the point of this commented section
// will it ever be true?
/*
while(tmp->getChild() !=NULL) {
tmp = tmp->getChild();
}
*/

// Point last node to new node
tmp->setchild(newNode);
}
else {
}
}
void QuadTree::AppendFront(unsigned int arrayposition, unsigned int index) {
// Create new node
Node *newNode = new Node();

newNode->setindex(arrayposition, index);

}
int main() {

std::string a;
std::cin >> a;
return (1);
}
```

Is This A Good Question/Topic? 0

### #2 Skydiver

• Code herder

Reputation: 4265
• Posts: 13,651
• Joined: 05-May 12

Posted 31 July 2014 - 07:57 AM

My first thought was, why implement your own linked list when one already exists in the standard library: std::list<>

... but I see that you are using it as a stepping stone for learning how to implement a quad tree. I've got some thoughts about this but need some time to organize them. I'll post a bit later today, but more of them center around it looks like you are using the quad tree the wrong way. I don't know if that's an attribute of the linked list you are trying to make into a quad tree or a flaw in understanding of what a quad tree is used for.

### #3 #define

• Duke of Err

Reputation: 1616
• Posts: 5,680
• Joined: 19-February 09

Posted 31 July 2014 - 08:24 AM

Hi. Since you are using 3d points I was wondering if you need an Octree.

A binary tree has two pointers to left and right, a quadtree has four, possibly called northwest, northeast, southwest and southeast.

Quite a good description - QuadTree

A few people don't separate the tree and node classes, I usually like a tree class and a node class as you already have.

When sub-dividing both sets of data are pushed to lower levels, so duplication should not be a problem.

### #4 xnewix

Reputation: 2
• Posts: 207
• Joined: 23-May 09

Posted 01 August 2014 - 09:27 AM

thanks for the replies.

Quote

Hi. Since you are using 3d points I was wondering if you need an Octree.

I had considered it, but after doing a bit of reading decided that I would first like to implement the quadtree. If i'm honest my knowledge of pointers isn't too great, so one step at a time although i do not think that there is a vast difference between the two.