Quad Trees where to start?

[Toddnmal]

Hello, I was tasked by my teacher to make a quad tree in c++ that takes points and says how many points are within the box, but I don't know where a good place to start would be in creating the Quad tree. Would anyone have any tips on how to create a basic quad tree or where to start.

[jonnin]

A very crude starting point..

struct sometype //whatever you want to make a tree OF
{
	int example;	
};

struct qtree
{
    sometype data{};
    vector<qtree*> kids; //4 children, initialize all to null, blah blah
	qtree() : kids(4,nullptr){;}
    bool deleted{}; //you probably want this.  Better to have 'deleted' nodes 
                           //left in place than to pull apart and reinsert them all frequently
	void add(sometype &st); //insert a new one
	void del(sometype &st);  //mark existing one as deleted
        sometype* find(sometype &st); //find one, if exists return a pointer to it else nullptr
};

as with anything you can swap pointers for integers and use a vector index instead of the hands-on memory mess. I highly advise that, actually -- its a little more work to manage the
memory but you can recycle deleted nodes easily and worry not about goofing a pointer.
an easy way to do that is to share static vectors across all the nodes where the real memory lives.

[kigar64551]

Usually, when creating a quadtree, you are given a list of points, each one with an 'x' and 'y' coordinate. So, first of all, you'll have to figure out the full range of 'x' and 'y' values - unless that is known beforehand.

Then you can sub-divide the range of both dimension in 2 halves, resulting in four quadrants: upper left, upper right, lower left, and lower right. Those are the four child-nodes of the "root" node. You then assign each of the given input points to one of those four quadrants (child-nodes), depending on where it is located.

If any of the four quadrants still contains more than one point, then it has to be further sub-divided, again into four sub-quadrants, in a "recursive" fashion. This goes on, until all leaf-node contain at most one point.

See this example:
https://opendsa-server.cs.vt.edu/ODSA/Books/vt/cs3114/spring-2017/Test_1219/html/_images/PRexamp.png

[Toddnmal]

Thank you for the help, the biggest issue now is that I'm having issues getting the code to read into the quad tree.

Quadtree *UL;
cin>>UL;

this is supposed to read in the Upper left corner box of the search but I keep getting an error
no operator ">>" matches these operands

Is there another way to read in the value or a way to fix this error?

[jonnin]

you should not read pointers from the user. The user does NOT know what address the variable is located at in memory. I sure don't know that. You probably don't know it either!

perhaps
cin >>*UL;
will work if you can actually use cin on this object. Did you set that up?
if you don't want to set it up, you can just read the parts:
cin >> *UL.some_field;

if you do want to set it up, look up overloading >> for your object:
https://www.tutorialspoint.com/cplusplus/input_output_operators_overloading.htm

[seeplus]

Quadtree *UL;

This says that UL is a pointer to memory of type Quadtree. However that memory has not yet been specified. Before UL is de-referenced, memory needs to be first allocated so that UL points to valid memory.

[kigar64551]

You can not read entire C++ objects from a file or write them to a file with <iostream> or the like.

At least not directly ;-)

What you need here is called (de)serialization. That is the task of converting an existing C++ object into a sequence of bytes, or to restore a C++ object form its serialized form (byte sequence). Once an object has been converted to its serialized form (byte sequence) you can write it to a file easily. Later, you can read the object from the file in the serialized form (byte sequence) and then de-serialize it into an actual C++ object.

Libraries like Boost can help with this task. See also:
https://www.codeguru.com/cplusplus/an-introduction-to-object-serialization-in-c/