3 Replies - 494 Views - Last Post: 01 August 2014 - 09:27 AM Rate Topic: -----

#1 xnewix  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 2
  • View blog
  • Posts: 204
  • Joined: 23-May 09

Linked List and QuadTrees

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:
	Node *head; // correct for list but what about quadtree? 
	std::vector<Point3d> point3d; // a place to store points.

	/* Concerns of data duplication whilst subdividing 
	to be added in Class QuadTree/private

			std::vector<BoundingBox> boundingbox; 

	to be added in Class QuadTree/public
		  
		  // 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:
	QuadTree() {
		head = NULL;
	};
	~QuadTree() {};
	
	void Print();
	void AppendBack  (unsigned int arrayposition, unsigned int index);
	void AppendFront (unsigned int arrayposition, unsigned int index);
	void Delete();
};

void QuadTree::Print() {
	Node *tmp = head;
	
	// 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
	Node *tmp = head; // head is NULL on 1st run;
	
	// Nodes already exist
	// 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 {
		head = newNode;
	}
}
void QuadTree::AppendFront(unsigned int arrayposition, unsigned int index) {
	// Create new node
	Node *newNode = new Node();

	newNode->setindex(arrayposition, index);
	newNode->setchild(head);

	head = newNode;


}
int main() {
	QuadTree quadtree;
	
	quadtree.AppendBack(0,1);
	quadtree.AppendBack(0,2);

	quadtree.AppendFront(0,17);

	quadtree.Print();
	std::string a;
	std::cin >> a;
	return (1);
}


Is This A Good Question/Topic? 0
  • +

Replies To: Linked List and QuadTrees

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3667
  • View blog
  • Posts: 11,499
  • Joined: 05-May 12

Re: Linked List and QuadTrees

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.
Was This Post Helpful? 0
  • +
  • -

#3 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1432
  • View blog
  • Posts: 4,968
  • Joined: 19-February 09

Re: Linked List and QuadTrees

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

Wiki - 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.
Was This Post Helpful? 0
  • +
  • -

#4 xnewix  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 2
  • View blog
  • Posts: 204
  • Joined: 23-May 09

Re: Linked List and QuadTrees

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1