Im supposed to implement a quad tree that will input cities into a fixed format. when the user asks for a particular city, all cities within a certain range will be displayed. i think i have the right method's in place, but for some reason or another, the program wont run. any help would be appreciated. thanks!
this is my def.h file
#include<string>
#include <iostream>
#include <list>
#include <cmath>
using namespace std;
class city
{
public:
string name;
double x;
double y;
};
class quadtree
{
private:
class node
{
public:
city nodecity;
node * NorthEast;
node * NorthWest;
node * SouthEast;
node * SoutWest;
};
//insert thru recursion
void recInsert(double x,double y,string name, node * & p);
//traverse thru recursion
void recTraverse(node * h);
node * head;
void recRange (double x, double y, double radius, node *p, list<city>&CityList);
bool inRange (double X, double X1,double Y, double Y1, double radius);
city nearestCity( double x, double y ) //this should return the city closest to city point (x, y).
city recNearestcity(double x, double y, node *& p, city previous);
city minimumDistance(double x, double y, city current, city previous);
list<city>*inrange(double x, double y, double radius);
public:
quadtree();
void insert( double x, double y, string name); //insert function
void traverse(); //traverse function
};
quadtree::quadtree()
{
head=NULL;
}
//definition of the insert function
void quadtree::insert(double x, double y,string name)
{
recInsert(x, y,name,head);
}
//definition of the traverse function
void quadtree::traverse()
{
recTraverse(head);
}
//definition of the recusive insert function.
void quadtree::recInsert(double x,double y,string name,node * & p)
{
if (p==NULL)
{
p=new node;
p->NorhtEast=NULL;
p->NorthWest=NULL;
p->SouthEast=NULL;
p->SouthWest=NULL;
p->nodecity.name=name;
p->nodecity.x=x;
p->nodecity.y=y;
}
else
if(( x >= p->nodecity.x) &&( y > p->nodecity.y))
{ //NE direction
recInsert(x, y, name,p->NorthEast);
}
else
if( x < p->nodecity.x && y >= p->nodecity.y)
{ // NW direction
recInsert(x, y, name,p->NorthWest);
}
else
if( x > p->nodecity.x && y <= p->nodecity.y)
{ // SE direction
recInsert( x, y, name,p->SouthEast);
}
else
if( x <= p->nodecity.x && y < p->nodecity.y)
{ // SW direction
recInsert(x, y, name, p->SouthWest);
}
}
void quadtree::recTraverse(node * p)
{
if(p==NULL)
return;
else
{
recTraverse(p->NorthWest);
recTraverse(p->NorthEast);
recTraverse(p->SouthWest);
recTraverse(p->SouthEast);
//cout the name of the city
cout<<p->nodecity.name<<" ("<<p->nodecity.x<<","<<p->nodecity.y<<") "<<endl;
}
}
//this will verify whether its inside the range or not.
bool quadtree::inRange(double X, double X1,double Y, double Y1, double radius)
{
//distance formula
double dis = sqrt( pow(X - X1,2.0)+ pow(Y - Y1,2.0));
//check with the radius if greater than or equal to the distance;
//if so return true
if (radius >= dis)
return true;
//else return false
else
return false;
}
//this should return a list with all the cities with the given radius
void quadtree::recRange (double x, double y, double radius, node *p, list<city>&CityList)
{
//since the base case if p=NULL therefore we can start on the general solution
if (p!=NULL)
{
if (p->NorthWest !=NULL)
{
if (inRange(x, p->NorthWest->nodecity.x, y, p->NorthWest->nodecity.y,radius))
{
//if its inside the range, insert to list
{
CityList.push_front(p->NorthEast->nodecity); //insert city unto list
recRange(x, y, radius, p->NorthEast->NorthWest, CityList); //Check the 4 coordinates
recRange(x, y, radius, p->NorthEast->NorthEast, CityList); //of that city
recRange(x, y, radius, p->NorthEast->SouthWest, CityList);
recRange(x, y, radius, p->NorthEast->SouthEast, CityList);
}
}
//if is not in range :
else
{
recRange(x, y, radius, p->NorthEast->NorthWest, CityList); //since the citty is not in
recRange(x, y, radius, p->NorthEast->SouthWest, CityList); //range, just check the 3 nearest
recRange(x, y, radius, p->NorthEast->SouthEast, CityList); //subtrees of that city
}
}
//while NW is not pointing to NULL check all cities in NW direction
if(p->NorthWest!= NULL)
{
//this checks if the city on the NW is inside the range
if (inRange (x, p->NorthWest->nodecity.x, y, p->NorthWest->nodecity.y, radius))
{
CityList.push_front(p->NorthWest->nodecity);
recRange(x, y, radius, p->NorthWest->NorthWest, CityList);
recRange(x, y, radius, p->NorthWeset->NorthEast, CityList);
recRange(x, y, radius, p->NorthWest->SouthWest, CityList);
recRange(x, y, radius, p->NorthWest->SouthEast, CityList);
}
//if is not in range :
else
{
recRange(x, y, radius, p->NorthWest->NorthEast, CityList);
recRange(x, y, radius, p->NorthWest->SouthWest, CityList);
recRange(x, y, radius, p->NorthWest->SouthEast, CityList);
}
}
//while SE is not pointing to NULL check all cities in SE direction
if(p->SouthEast!= NULL)
{
//this checks if the city on the SE is inside the range
if (inRange (x, p->SouthEast->nodecity.x, y, p->SouthEast->nodecity.y, radius))
{
CityList.push_front(p->SouthEast->nodecity); //insert city unto list
recRange(x, y, radius, p->SouthEast->NorthWest, CityList); //check the 4 coordinates
recRange(x, y, radius, p->SouthEast->NorthEast, CityList); //of the subtrees of the
recRange(x, y, radius, p->SouthEast->SouthWest, CityList); //city
recRange(x, y, radius, p->SouthEast->SouthEast, CityList);
}
//if is not in range :
else
{
recRange(x, y, radius, p->SouthEast->NorthWest, CityList); //since that city is not
recRange(x, y, radius, p->SouthEast->SouthWest, CityList); //in range, just check the
recRange(x, y, radius, p->SouthEast->NorthEast, CityList); //nearest tree subtrees of the city
}
}
//while SW is not pointing to NULL check all cities in SW direction
if(p->SouthWest!= NULL)
{
//this if checks if the city on the NE is inside the range
if (inRange (x, p->SouthWest->nodecity.x, y, p->SouthWest->nodecity.y, radius))
{
CityList.push_front(p->SouthWest->nodecity);
recRange(x, y, radius, p->SouthWest->NorthWest, CityList);
recRange(x, y, radius, p->SouthWest->NorthEast, CityList);
recRange(x, y, radius, p->SouthWest->SouthWest, CityList);
recRange(x, y, radius, p->SouthWest->SouthEast, CityList);
}
//if is not in range :
else
{
recRange(x, y, radius, p->SouthWest->NorthWest, CityList);
recRange(x, y, radius, p->SouthWest->NorthEast, CityList);
recRange(x, y, radius, p->SouthWest->SouthEast, CityList);
}
}
}
}
// Calling the function range which checks if the root is inside the range
list<city> quadtree::inRange(double x, double y, double radius)
{
list<city> List;
if (head!=NULL)
{
if (inRange (x, head->nodecity.x, y, head->nodecity.y, radius))
{
List.push_front(head->nodecity);
}
recRange(x,y,radius, head, listname);
}
return List; // to return the list with the names of the cities that
// are within the given range
}
city quadtree::nearestCity(double x, double y)); //this should return the city closest to city point (x, y).
{
city previous;
previous.name = "empty";
previous.x = 83720478;
previous.y = 63829631;
city city;
city nearestCity;
if (head== NULL)
return previous;
else
{
if (x >=head->nodecity.x && y >= head->nodecity.y)
{
previous = head->nodecity;
city = recNearestcity(x, y, head->NorthEast, previous);
}
else if (x < head->nodecity.x && y >= head->nodecity.y)
{
previous = head->nodecity;
city = recNearestcity(x, y, head->NorthWest, previous);
}
else if (x >=head->nodecity.x && y < head->nodecity.y)
{
previous = head->nodecity;
city = recNearestcity(x, y, head->SouthEast, previous);
}
else //if (x < ptr->data.x && y < ptr->data.y)
{
previous = head->nodecity;
city = recNearestcity(x, y, head->SouthWest, previous);
}
nearestCity = minimumDistance(x, y, current, previous);
return nearestCity;
}
}
city quadtree::recNearestcity(double x, double y, node *& p, city previous)
{
city city;
city nearestCity;
if (p == NULL)
return previous;
else
{
if (x >= p->nodecity.x && y >= p->nodecity.y)
{
previous = p->nodecity;
city= recNearestcity(x, y, p->NorthEast, previous);
}
else if (x < p->nodecity.x && y >= p->nodecity.y)
{
previous = p->nodecity;
city = recNearestcity(x, y, p->NorthWest, previous);
}
else if (x >= p->nodecity.x && y < p->nodecity.y)
{
previous = p->nodecity;
city = recNearestcity(x, y, p->SouthEast, previous);
}
else
{
previous = p->nodecity;
city = recNearestcity(x, y, p->SouthWest, previous);
}
nearest = minimumDistance(x, y, current, previous);
return nearestCity;
}
}and this would be the quad implementaion.
#include <iostream>
#include<string>
#include "def.h"
using namespace std;
void
print_citylist (std::list<city> * plist, std::string message)
{
//std::cout << "" << std::endl;
std::cout << "--------- " << message << " BEGIN ---------" << std::endl;
for (std::list<city>::iterator it = plist->begin(); it != plist->end(); it ++) {
std::cout << "City: '" << (*it).name << "'\t(x=" << (*it).x << ", y=" << (*it).y << ")" << std::endl;
}
std::cout << "--------- " << message << " END ---------" << std::endl;
}
int main()
{
pointquadtree citytree;
citytree.insert ( 100, 100, "Chicago");
citytree.insert ( 25, 125, "McAllen");
citytree.insert ( 50, 150, "Los Angeles");
citytree.insert ( 75, 130, "Detroit");
citytree.insert ( 150, 50, "New York");
citytree.insert ( 10, 40, "Austin");
city closestCity = citytree.nearestCity (63, 84);
cout << "The closest city is " << closestCity.name << endl;
double x = 50;
double y = 95;
double r = 100;
std::list<city> * closeCities = citytree.in_range (x, y, r);
if (NULL == closeCities) {
return;
}
print_citylist (closecities, "city list");
delete closecities;
return 0;
}any help would be very much appreciated!! thanks!!
