// UQuadTree.cpp: implementation of the UQuadTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Simulator.h"
#include "UQuadTree.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

UQuadTree::UQuadTree()
{
    _Construct();

    Colors[0] = RGB(0,0,0);
    Colors[1] = RGB(255,0,0);
    Colors[SNAPCOLOR] = RGB(0,255,0);
    ColorPens[0].CreatePen(PS_SOLID,1,Colors[0]);
    ColorPens[1].CreatePen(PS_SOLID,1,Colors[1]);
    ColorPens[2].CreatePen(PS_SOLID,1,Colors[2]);

    ColorBrush[0].CreateSolidBrush(Colors[0]);
    ColorBrush[1].CreateSolidBrush(Colors[1]);
    ColorBrush[2].CreateSolidBrush(Colors[2]);
    
    int XYOffset = 1000;

    
    DefaultLinesinArc = 50;  

    SensorRenderingScale = 3;

  /*  CPoint tempbox;
    tempbox.x=XYOffset + 4750;
    tempbox.y= XYOffset + 250;
    AddBox(tempbox,1000);
    tempbox.x=XYOffset + 250;
    tempbox.y= XYOffset + 4750;
    AddBox(tempbox,1000);
    tempbox.x=XYOffset + 8750;
    tempbox.y= XYOffset + 4750;
    AddBox(tempbox,1000);
    tempbox.x=XYOffset + 4750;
    tempbox.y= XYOffset + 8750;
    AddBox(tempbox,1000);
    tempbox.x=XYOffset + 4251;
    tempbox.y= XYOffset + 4251;
    AddBox(tempbox,2000);
    tempbox.x=XYOffset + 1;
    tempbox.y= XYOffset + 1;
    AddBox(tempbox,10500);

    CPoint Start,Middle,End;

    Start.x = 3000;
    Start.y = 3000;
    Middle.x = 5000;
    Middle.y = 5000;
    End.x = 7000;
    End.y = 3000;
    AddArc(Start,Middle,End);

    LGroupPtr tPtr = AddLine(Start,End);
   //DeleteGroup(tPtr);

    Start.x = 1;
    Start.y = 120;
    End.x = 400;
    End.y = 120;

    ULinearAlgebra::Matrix2X2 Line = LAUtils.PointstoLine(Start,End);

    Start.x = 75;
    Start.y = 100;
    Middle.x = 100;
    Middle.y = 75;
    End.x = 125;
    End.y = 100;

    ULinearAlgebra::Circle circle = LAUtils.GetCircle(Start,Middle,End);

    CPoint inter = LAUtils.FindIntersection(Line,circle,Start);*/


 
}

UQuadTree::~UQuadTree()
{
    _Destruct();
}


/* these two functions are used to create the tree*/
void UQuadTree::InitializeQuadTree()
{
    if (HeadQuadPtr == NULL)
    {
        HeadQuadPtr = new TreeStruct;
        DebugNewCount++;
        HeadQuadPtr->QuadRect.top = QUADYSTART;
        HeadQuadPtr->QuadRect.left = QUADXSTART;
        HeadQuadPtr->QuadRect.right = QUADXBOUND;
        HeadQuadPtr->QuadRect.bottom = QUADYBOUND;
        HeadQuadPtr->Objects = NULL;
        HeadQuadPtr->PrevQuad = NULL;
        for (int ix = 0; ix < QUAD; ix ++)
        {
            HeadQuadPtr->NextQuad[ix] = NULL;
        }
        InitializeQuadTree(HeadQuadPtr);
    }

}



void UQuadTree::InitializeQuadTree(TreePtr Head)
{
    // recursive code that can't be used because it blows up the stack.
/*    TreePtr temp;
    
    for (int ix = 1; ix <= 4; ix ++)
    {
        temp = new TreeStruct;
        DebugNewCount++;
        temp->Objects=NULL;
        temp->QuadRect = GetQuad(Head->QuadRect,ix);
        for (int iy = 0; iy < 4; iy++)
        {
            temp->NextQuad[iy] = NULL;
        }
        Head->NextQuad[ix-1]=temp;

        // keep on going until the bottom is reached (heigh and width = 1);
        if (-temp->QuadRect.Width() > 1 && DebugNewCount<16000)
        {
            InitializeQuadTree(temp);
        }
    }*/

    TreePtr curr,next;
    int index;
    curr = HeadQuadPtr;

    do
    {
        // keep on going until the bottom is reached (heigh and width = 1);
        if (curr->QuadRect.Width() > 0)
        {
            index = InitFindNull(curr);
            if (index != -1)
            {
                next = new TreeStruct;
                DebugNewCount++;
                curr->NextQuad[index] = next;
                next->Objects = NULL;
                next->PrevQuad = curr;
                next->QuadRect = InitGetQuad(curr->QuadRect,index+1);
                for (int ix = 0; ix <= 3; ix ++)
                {
                    next->NextQuad[ix] = NULL;
                }
                curr = next;
            }
            else
            {
                curr=curr->PrevQuad;
            }
        }
        else
        {
            curr=curr->PrevQuad;
        }
            
    } while ((curr->PrevQuad != NULL) || (InitFindNull(curr) != -1) );



    

}

/************************************************************************
* Function CRect InitGetQuad(CRect toSplit, int index)
* 
* PURPOSE
* to recieve a rectange with a quadrants and return the rectange of only the quadrant,
* The quadrants are split up just like a cartesion coordinate system, with 1 being
* top right, 2 being top left, 3 being bottom left, and 4 being bottom right.
* USAGE
* for the initialization routine only
* INPUTS
* toSplit, the rectange to split into quadrants
* index, the cartesian quadrant that wants to be returned
* OUTPUTS
* returns a rectange of the quadrant
*
*************************************************************************/

CRect UQuadTree::InitGetQuad(CRect toSplit, int index)
{
    CRect temp;
    if (index == 1)
    {
        temp.top = toSplit.top;
        temp.bottom = toSplit.top+(toSplit.bottom-toSplit.top+1)/2-1;
        temp.left = toSplit.right-(toSplit.right-toSplit.left+1)/2+1;
        temp.right = toSplit.right;
    }
    else if (index == 2)
    {
        temp.top = toSplit.top;
        temp.bottom = toSplit.top+(toSplit.bottom-toSplit.top+1)/2-1;
        temp.left = toSplit.left;
        temp.right = toSplit.left+(toSplit.right-toSplit.left-1)/2;
    }
    else if (index == 3)
    {
        temp.top = toSplit.bottom - (toSplit.bottom-toSplit.top+1)/2+1;
        temp.bottom = toSplit.bottom;
        temp.left = toSplit.left;
        temp.right = toSplit.left+(toSplit.right-toSplit.left-1)/2;
    }
    else if (index == 4)
    {
        temp.top = toSplit.bottom - (toSplit.bottom-toSplit.top+1)/2+1;
        temp.bottom = toSplit.bottom;
        temp.left = toSplit.right-(toSplit.right-toSplit.left+1)/2+1;
        temp.right = toSplit.right;
    }

    return temp;

}

/************************************************************************
* Function int InitFindNull(UQuadTree::TreePtr temp)
* 
* PURPOSE
* This functions finds a null child in a quadtree node, and returns the id of it
* USAGE
* It is a helper function for the initialization routine
* INPUTS
* TreePtr temp the tree pointer to find the null
* OUTPUTS
* int quad of null, returns the index of the null, -1 if there isn't one
*
*************************************************************************/
int UQuadTree::InitFindNull(UQuadTree::TreePtr temp)
{
    for (int ix = 0; ix < 4; ix++)
    {
        if (temp->NextQuad[ix] == NULL)
        {
            return ix;
        }
    }
    return -1;
}

/************************************************************************
* Function DeleteQuadTree
* 
* Destructor functions
*
*************************************************************************/
void UQuadTree::DeleteQuadTree()
{
    DeleteQuadTree(HeadQuadPtr);

}

void UQuadTree::DeleteQuadTree(UQuadTree::TREESTRUCT *Head)
{  
    TreePtr curr,next;
    curr = Head;

    if (curr != NULL)
    {
        int index;

        do
        {
            index = DeleteFindNonNull(curr);
            if (index != -1)
            {
                curr = curr->NextQuad[index];
            }
            else
            {
                next = curr;
                curr=curr->PrevQuad;
                for (int ix = 0; ix < QUAD; ix++)
                {
                    if (curr != NULL)
                    {
                        if (curr->NextQuad[ix] == next)
                        {
                            if (next != NULL) // just in case
                            {
                                DeleteObjectList(next); // delete any object in the quadrant
                                delete next;
                                next = NULL;
                                DebugDeleteCount++;
                                curr->NextQuad[ix] = NULL;
                                break;
                            }
                        }
                    }
                }
                

            }        
            
        } while ((curr != NULL));


        DeleteObjectList(HeadQuadPtr);
        delete HeadQuadPtr;
        HeadQuadPtr = NULL;
        HeadQuadPtr = NULL;
        DebugDeleteCount++;
    }

}


/************************************************************************
* Function int DeleteFindNonNull(UQuadTree::TreePtr temp)
* 
* PURPOSE
* This functions finds a non null child in a quadtree node, and returns the id of it
* USAGE
* It is a helper function for the delete routine
* INPUTS
* TreePtr temp the tree pointer to find the null
* OUTPUTS
* int quad of non null, returns the index of the null, -1 if there isn't one
*
*************************************************************************/
int UQuadTree::DeleteFindNonNull(UQuadTree::TreePtr temp)
{
    for (int ix = 0; ix < QUAD; ix++)
    {
        if (temp->NextQuad[ix] != NULL)
        {
            return ix;
        }
    }
    return -1;


}

/************************************************************************
* Function TreePtr UQuadTree::AddFindQuad(CPoint point)
* 
* PURPOSE
* to return the leaf node of the quadrant which the point belongs to.
* NOTE The quadrant has to be in meters not cm.
* USAGE
* Originally used for the addline function, it is now used by a lot of other functions
* INPUTS
* point, the quadrant of which to return from 1-128, 1-128
* OUTPUTS
* returns a point to the quadrant
*
*************************************************************************/
UQuadTree::TreePtr UQuadTree::AddFindQuad(CPoint point)
{
    TreePtr temp = HeadQuadPtr;

    // wrong formating of point, so format it here
    if (point.x > QUADXBOUND || point.y > QUADYBOUND)
    {
        point.x = point.x/100+1;
        point.y = point.y/100+1;
    }

    // this is an interitive descent to find the leaf note (quad) where the point is in
    while (temp->QuadRect.Width() != 0)
    {
        int quad = AddFindQuad(temp->QuadRect,point);
        if (quad == -1) // should not happen
        {
            return NULL;
        }
        else 
        {
            temp = temp->NextQuad[quad-1];
        }
    }
    return temp;

}

// wrapper for above function
UQuadTree::TreePtr UQuadTree::AddFindQuad(int x, int y)
{
    CPoint tempo;
    tempo.x = x;
    tempo.y = y;
    return AddFindQuad(tempo);
}

/************************************************************************
* Function TreePtr AddFindQuad(CPoint point, TreePtr Level)
* 
* PURPOSE
* to return the sibling node of the quadrant which the point belongs to.
* NOTE The quadrant has to be in meters not cm.
* USAGE
* Originally used to optimize the quadtree to all levels
* INPUTS
* point, the quadrant of which to return from 1-128, 1-128
* Level the level at which to look for the sibling
* OUTPUTS
* returns a point to the quadrant
*
*************************************************************************/
UQuadTree::TreePtr UQuadTree::AddFindQuad(CPoint point, UQuadTree::TREESTRUCT *Level)
{
    // just in case
    if (Level == NULL)
    {
        return NULL;
    }
    // can't be the root node.
    if (Level->PrevQuad == NULL)
    {
        return NULL;
    }
    // this happens but even ia null isn't sent back it shouldn't be a big deal
    if ((point.x == -1) || (point.y == -1))
    {
        return NULL;
    }

    // wrong formating of point, so format it here
    if (point.x > QUADXBOUND || point.y > QUADYBOUND)
    {
        // because there is no zero point use -1
        point.x = (point.x-1)/100+1;
        point.y = (point.y-1)/100+1;
    }

    int count = 0;

    TreePtr temp = Level;

    // have to go all the way up, and then all the way down.
    while (temp->PrevQuad != NULL)
    {
        count++;
        temp = temp->PrevQuad;
    }

    // time to visit the sibling
    for (int ix = 0; ix < count; ix++)
    {
        int quad = AddFindQuad(temp->QuadRect,point);
        if (quad != -1) // shouldn't occur
        {
            if (temp == NULL)
            {
                return NULL; // error
            }
            temp=temp->NextQuad[quad-1];
        }
        else
        {
            return NULL; // error 
        }
            
    }

    return temp;

/*



    TreePtr temp;

    // second level, still a special case
    if (Level->PrevQuad->PrevQuad == NULL)
    {
        temp = Level->PrevQuad;
        int quad = AddFindQuad(temp->QuadRect,point);
        if (quad != -1)
            return temp->NextQuad[quad-1];
        else
            return NULL;
    }

    temp = Level->PrevQuad->PrevQuad; // two levels are required to get to the next quadrant
    
    // should find the sibling where the point is in.
    int quad = AddFindQuad(temp->QuadRect,point);
    temp = temp->NextQuad[quad-1]; // O.K get one level back

    // get the other level back
    quad = AddFindQuad(temp->QuadRect,point);
    if (quad != -1)
        return temp->NextQuad[quad-1];
    else
        return NULL;

*/
}



/************************************************************************
* Function int AddFindQuad(CRect quad, CPoint point)
* 
* PURPOSE
* to find which cartesian quadrant a given point is inside of a rectangle
* INPUTS
* quad = the rectangle to reference the input point
* point = the pint at which to find which quadrant it is in.
* OUTPUTS
* returns int = the quadrants that the point is in 1-4. or -1 if it isn't divisible anymore
*
*************************************************************************/
int UQuadTree::AddFindQuad(CRect quad, CPoint point)
{
    int midX,midY;
    midX = quad.left+(quad.right-quad.left+1)/2;
    midY = quad.top+(quad.bottom-quad.top+1)/2;

    // at a leaf node, can't go any further
    if (quad.right == quad.left)
    {
        return -1;
    }

    if ((point.x >= midX) && (point.y < midY))
    {
        return 1;
    }
    else if ((point.x < midX) && (point.y < midY))
    {
        return 2;
    }
    else if ((point.x < midX) && (point.y >= midY))
    {
        return 3;
    }
    else if ((point.x >= midX) && (point.y >= midY))
    {
        return 4;
    }
    return -1;

}

/************************************************************************
* Function  AddToObjectList(UQuadTree::TREESTRUCT *tTreePtr, UQuadTree::OBJECT *tObjectPtr)
* 
* PURPOSE
* to add an object to a quad leaf node object list
* INPUTS
* tTreePtr, the node to add the object
* tObjectPtr, the object to add to the node.
* OUTPUTS
*
*************************************************************************/
void UQuadTree::AddToObjectList(UQuadTree::TREESTRUCT *tTreePtr, UQuadTree::OBJECT *tObjectPtr)
{

    // check if there is a list already
    if (tTreePtr->Objects == NULL)
    {
        tTreePtr->Objects = new OBJECTLIST;
        tTreePtr->Objects->Next=NULL;
        tTreePtr->Objects->Prev=NULL;
        tTreePtr->Objects->Data=tObjectPtr;
    }
    // insert to front of list.
    else
    {
        ObjectListPtr temp = new OBJECTLIST;
        temp->Data=tObjectPtr;
        temp->Next = tTreePtr->Objects;
        tTreePtr->Objects->Prev = temp;
        temp->Prev = NULL;
        tTreePtr->Objects = temp;
    }
       

}

/************************************************************************
* Function  DeleteObjectList(UQuadTree::TREESTRUCT *tTreePtr)
* 
* PURPOSE
* To delete the object list of a quad tree node
* INPUTS
* tTreePtr, the node to delete all of its objects
*
*************************************************************************/
void UQuadTree::DeleteObjectList(UQuadTree::TREESTRUCT *tTreePtr)
{
    ObjectListPtr temp,temp1;
    temp = tTreePtr->Objects;
    while (temp != NULL)
    {
        temp1=temp;
        temp=temp->Next;
        delete temp1;
    }
}


/************************************************************************
* Function  CPoint AddFindPoint(CPoint Start, CPoint End)
* 
* PURPOSE
* To find the quadrants which contain a line
* INPUTS
* Start, the start of the line
* End, the end of the line
* OUTPUTS
* A point in the next quadrant
*************************************************************************/
CPoint UQuadTree::AddFindPoint(CPoint Start, CPoint End)
{
    CPoint toReturn;    
    
    float slope;
        
    // in case the slope is infinite.
    if (End.x != Start.x)
    {
         slope = (float)(End.y-Start.y)/(float)(End.x-Start.x);
    }
    else
    {
         slope = (float)(End.y-Start.y)/1;
    }

    int XQuad = Start.x/100;
    int YQuad = Start.y/100;

    int newX = Start.x;
    int oldY = Start.y;
    int newY;

    if (End.x >= Start.x)
    {
        for (int ix = 0; ix < 110; ix++)
        {
            newX++;
            newY = (int)slope*(ix+1) + oldY;
            // in a new quadrant?  if yes return with the points.
            if ((newX/100 != XQuad) || (newY/100 != YQuad))
            {
                toReturn.x = newX;
                toReturn.y = newY;
                return toReturn;
            }
            // line ended without going into another quadrant
            if (newX >= End.x)
            {
                toReturn.x=-1;
                toReturn.y=-1;
                return toReturn;
            }
            else if ((slope > 0) && (newY >= End.y))
            {
                toReturn.x=-1;
                toReturn.y=-1;
                return toReturn;
            }
        }
    }
    else
    {
        for (int ix = -1; ix > -110; ix--)
        {
            newX--;
            newY = (int)slope*(ix+1) + oldY;
            // in a new quadrant?  if yes return with the points.
            if ((newX/100 != XQuad) || (newY/100 != YQuad))
            {
                toReturn.x = newX;
                toReturn.y = newY;
                return toReturn;
            }
                        // line ended without going into another quadrant
            if (newX <= End.x)
            {
                toReturn.x=-1;
                toReturn.y=-1;
                return toReturn;
            }
            else if ((slope < 0) && (newY >= End.y))
            {
                toReturn.x=-1;
                toReturn.y=-1;
                return toReturn;
            }
        }
    }

    // should never get here.
    toReturn.x=-1;
    toReturn.y=-1;
    return toReturn;
    

}


/************************************************************************
* Function  AddToBigObjectList(UQuadTree::OBJECT *tObjectPtr)
* 
* PURPOSE
* Adds an object to a main list, to make the destruction easier
* INPUTS
* tObjectPtr, the pointer to the object to add
*
*************************************************************************/
void UQuadTree::AddToBigObjectList(UQuadTree::OBJECT *tObjectPtr)
{
    if (BigObjectList == NULL)
    {
        BigObjectList = new OBJECTLIST;
        BigObjectList->Next=NULL;
        BigObjectList->Prev=NULL;
        BigObjectList->Data = tObjectPtr;
    }
    // add it to the front of the list
    else
    {
        ObjectListPtr temp = new OBJECTLIST;
        temp->Data = tObjectPtr;
        temp->Prev=NULL;
        temp->Next = BigObjectList;
        BigObjectList->Prev = temp;
        BigObjectList = temp;
    }

}


/************************************************************************
* Function  DeleteObjects()
* 
* PURPOSE
* To delete all of the objects, uses the BigObjectList.
*
*************************************************************************/
void UQuadTree::DeleteObjects()
{
    ObjectListPtr temp;

    while (BigObjectList != NULL)
    {
        temp = BigObjectList;
        BigObjectList = BigObjectList->Next;
        DeleteGroupList(temp->Data->GroupPtr); 
        delete temp->Data;
        delete temp;
    }

}

/************************************************************************
* Function  Render(CDC &memDC, CRect Quad, CRect Screen)
* 
* PURPOSE
* To render the quadtree
* USAGE
* by the OnPaint functions of the view class
* INPUTS
* memDC the device context to draw to
* Quad the area in which to render, (in quad coords)
* Screen, the area in which to draw to.
*************************************************************************/
void UQuadTree::Render(CDC &DBufferDC, FRect Quad, CRect Screen)
{

    if (!RenderingStats.doNotRender)
    {
        RenderingStats.IsRendering = true;
        // the offset is only using during the blitting to tScreen should be used otherwise
        CRect tScreen;
        tScreen.right = Screen.Width();
        tScreen.bottom = Screen.Height();
        tScreen.top = 0;
        tScreen.left = 0;
    

      /*  CDC DBufferDC;
        DBufferDC.CreateCompatibleDC(&memDC);
        CBitmap DBufferBitmap;
	    DBufferBitmap.CreateCompatibleBitmap(&memDC,tScreen.Width(),tScreen.Height());
	    CBitmap *pOldBitmap = DBufferDC.SelectObject(&DBufferBitmap);

  */

        CBrush Brush(RGB(255,255,255));
        DBufferDC.FillRect(&tScreen,&Brush);
        CPen Green(PS_SOLID,3,RGB(0,255,0));
        CPen *OldPen = DBufferDC.SelectObject(&Green);
        DBufferDC.Rectangle(&tScreen);
        DBufferDC.SelectObject(OldPen);

    
    
        float XScale = (float)tScreen.Width()/(float)Quad.Width();
        float YScale = (float)tScreen.Height()/(float)Quad.Height();

        // tranform e.i where to start the lines
        float XTransform = Quad.left;
        float YTransform = Quad.top;


        ObjectPtr object = NULL;
        // reset the stat
        RenderingStats.NRendered = 0;

        // create a list of objects to render.  This has to be done before any calls to RenderEnumObjects
        RenderCreateList((CCRect)Quad);

        // extract objects out of the list and draw them
        while (RenderEnumObjects(object))
        {
            if (object->objecttype == LINE)
            {
                // select the right colored pen
                CPen *OldPen = DBufferDC.SelectObject(&ColorPens[object->objectColor]);
                long XStart = (long)((object->start.x-XTransform)*XScale);
                long YStart = (long)((object->start.y-YTransform)*YScale);
                long XEnd = (long)((object->end.x-XTransform)*XScale);
                long YEnd = (long)((object->end.y-YTransform)*YScale);

                // fix a GDI scaling problem
                LAUtils.ClipLine(Screen,XStart,YStart,XEnd,YEnd);

                DBufferDC.MoveTo(XStart,YStart);
                DBufferDC.LineTo(XEnd,YEnd);
            
                if (object->objectColor == SELECTCOLOR)
                {
                    CRect SelectRect; // a rectange at the endpoints indicating it could be moved
                    SelectRect.left = XStart-SELECTRECTSIZE;
                    SelectRect.right = XStart+SELECTRECTSIZE;
                    SelectRect.top = YStart-SELECTRECTSIZE;
                    SelectRect.bottom = YStart+SELECTRECTSIZE;
                    DBufferDC.Rectangle(&SelectRect);
                    SelectRect.left = XEnd-SELECTRECTSIZE;
                    SelectRect.right = XEnd+SELECTRECTSIZE;
                    SelectRect.top = YEnd-SELECTRECTSIZE;
                    SelectRect.bottom = YEnd+SELECTRECTSIZE;
                    DBufferDC.Rectangle(&SelectRect);
                }

                // increment the rendering count
                RenderingStats.NRendered++;
                // select the old pen to free up memory (I think)
                DBufferDC.SelectObject(OldPen);
            }
            // same as a line except there is a third vertices to put up.
            else if (object->objecttype == ARCLINE)
            {
                 // select the right colored pen
                CPen *OldPen = DBufferDC.SelectObject(&ColorPens[object->objectColor]);
                int XStart = (int)((object->start.x-XTransform)*XScale);
                int YStart = (int)((object->start.y-YTransform)*YScale);
                int XEnd = (int)((object->end.x-XTransform)*XScale);
                int YEnd = (int)((object->end.y-YTransform)*YScale);
                DBufferDC.MoveTo(XStart,YStart);
                DBufferDC.LineTo(XEnd,YEnd);
            
                if (object->objectColor == SELECTCOLOR)
                {
                    if (object->GroupPtr != NULL)
                    {
                        // find the header object for the arcline
                        ObjectPtr Header = object->GroupPtr->Next->Data;
                        if (Header != NULL)
                        {
                            int XStart = (int)((Header->start.x-XTransform)*XScale);
                            int YStart = (int)((Header->start.y-YTransform)*YScale);
                            int XEnd = (int)((Header->end.x-XTransform)*XScale);
                            int YEnd = (int)((Header->end.y-YTransform)*YScale);
                            int XMiddle = (int)((Header->middle.x-XTransform)*XScale);
                            int YMiddle = (int)((Header->middle.y-YTransform)*YScale);

                            CRect SelectRect; // a rectange at the endpoints indicating it could be moved
                            SelectRect.left = XStart-SELECTRECTSIZE;
                            SelectRect.right = XStart+SELECTRECTSIZE;
                            SelectRect.top = YStart-SELECTRECTSIZE;
                            SelectRect.bottom = YStart+SELECTRECTSIZE;
                            RenderDrawRectangle(SelectRect,DBufferDC);
                            SelectRect.left = XEnd-SELECTRECTSIZE;
                            SelectRect.right = XEnd+SELECTRECTSIZE;
                            SelectRect.top = YEnd-SELECTRECTSIZE;
                            SelectRect.bottom = YEnd+SELECTRECTSIZE;
                            RenderDrawRectangle(SelectRect,DBufferDC);
                            SelectRect.left = XMiddle-SELECTRECTSIZE;
                            SelectRect.right = XMiddle+SELECTRECTSIZE;
                            SelectRect.top = YMiddle-SELECTRECTSIZE;
                            SelectRect.bottom = YMiddle+SELECTRECTSIZE;
                            RenderDrawRectangle(SelectRect,DBufferDC);

                        }
                    }
                }

                // increment the rendering count
                RenderingStats.NRendered++;
                // select the old pen to free up memory (I think)
                DBufferDC.SelectObject(OldPen);
            }
            else if (object->objecttype == BUMPSENSOR)
            {
                // change the colors if selected
                CPen *OldPen = DBufferDC.SelectObject(&ColorPens[object->objectColor]);
                DBufferDC.SetTextColor(Colors[object->objectColor]);

                int Height = abs(object->end.y - object->start.y);
                int Width = abs(object->end.x - object->start.x);

                BOOL isVertical;

                if (Height > Width)
                    isVertical = true;
                else
                    isVertical = false;                

                RenderBumpSensor(DBufferDC,XScale,YScale,(long)XTransform,(long)YTransform,object->middle,object->objectColor,isVertical);

                // change back the colors
                DBufferDC.SetTextColor(Colors[0]); // back to black
                DBufferDC.SelectObject(OldPen);
                // increment the rendering count
                RenderingStats.NRendered++;

            }
            else if (object->objecttype == IRSENSOR)
            {
                // change the colors if selected
                CPen *OldPen = DBufferDC.SelectObject(&ColorPens[object->objectColor]);
                RenderIRSensor(DBufferDC,XScale,YScale,(long)XTransform,(long)YTransform,object->middle,object->end.x,object->objectColor);
                DBufferDC.SelectObject(OldPen);

            }
            else if (object->objecttype == SONARSENSOR)
            {
                 // change the colors if selected
                CPen *OldPen = DBufferDC.SelectObject(&ColorPens[object->objectColor]);
                RenderSonarSensor(DBufferDC,XScale,YScale,(long)XTransform,(long)YTransform,object->middle,object->objectColor);
                DBufferDC.SelectObject(OldPen);

            }
            else if (object->objecttype == ROOF3D)
            {
                 // change the colors if selected
                 // select the right colored pen
             /*   CPen *OldPen = DBufferDC.SelectObject(&ColorPens[object->objectColor]);
                long XStart = (long)((object->start.x-XTransform)*XScale);
                long YStart = (long)((object->start.y-YTransform)*YScale);
                long XEnd = (long)((object->end.x-XTransform)*XScale);
                long YEnd = (long)((object->end.y-YTransform)*YScale);

                // fix a GDI scaling problem
                LAUtils.ClipLine(Screen,XStart,YStart,XEnd,YEnd);

                DBufferDC.MoveTo(XStart,YStart);
                DBufferDC.LineTo(XEnd,YEnd);*/

            } 
        }

        // draw the snap point if applicable
        if (RenderApeture.x != -1)
        {
            CPen *OldPen = DBufferDC.SelectObject(&ColorPens[SNAPCOLOR]);

            int XStart = (int)((RenderApeture.x-XTransform)*XScale);
            int YStart = (int)((RenderApeture.y-YTransform)*YScale);
       

            CRect SelectRect; // a rectange at the endpoints indicating it could be moved
            SelectRect.left = XStart-RenderApetureSize;
            SelectRect.right = XStart+RenderApetureSize;
            SelectRect.top = YStart-RenderApetureSize;
            SelectRect.bottom = YStart+RenderApetureSize;
            RenderDrawRectangle(SelectRect,DBufferDC);

            DBufferDC.SelectObject(OldPen);
        }


        // put the buffer into the drawing device
       // memDC.BitBlt(Screen.left,Screen.top,Screen.Width(),Screen.Height(),&DBufferDC,0,0,SRCCOPY);
       // DBufferDC.SelectObject(pOldBitmap);

        RenderingStats.IsRendering=false;
    }    
        



}


/************************************************************************
* Function BOOL RenderEnumObjects(ObjectPtr &object)
* 
* PURPOSE
* To return an object to render
* USAGE
* by the Render function
* INPUTS
* None, it has its own pointer to keep track of an objectlist, curtesy of the 
* RenderSetupEnum function which must be called first.
* OUTPUTS
* object, an object which is contained in the area to be rendered
* Returns true if it returns a valid object, false if the object is not valid
*************************************************************************/
BOOL UQuadTree::RenderEnumObjects(UQuadTree::OBJECT *&object)
{

    if (RenderObjectListPtr == NULL)
    {
        return false;
    }
    else
    {
        ObjectListPtr old;
        object = RenderObjectListPtr->Data;
        old = RenderObjectListPtr;
        RenderObjectListPtr = RenderObjectListPtr->Next;
        delete old;
        old = NULL;
        return true;
    }


}



/* garbage debug function*/
void UQuadTree::AddBox(CPoint start, int Size)
{
    CPoint tempo;
    Object temp; // the temperary line object used in adding to the box.


    tempo = start; 
    temp.start = tempo;
    tempo.x=start.x+Size;
    tempo.y=start.y+Size;
    temp.end =tempo;
    temp.objecttype=1;
    // diagnal down
    AddLine(temp.start,temp.end);

    tempo.x=start.x;
    tempo.y=start.y+Size;
 
    temp.start = tempo;
    tempo.x = start.x + Size;
    tempo.y=start.y;
    temp.end =tempo;
    temp.objecttype=1;
    //diagnal up
    AddLine(temp.start,temp.end);

        tempo.x=start.x;
    tempo.y=start.y;
 
    temp.start = tempo;
    tempo.x = start.x+Size;
    tempo.y=start.y;
    temp.end =tempo;
    temp.objecttype=1;
    // upper
    AddLine(temp.start,temp.end);

    
    tempo.x=start.x+Size;
    tempo.y=start.y+Size;
 
    temp.start = tempo;
    tempo.x = start.x;
    tempo.y=start.y+Size;
    temp.end =tempo;
    temp.objecttype=1;
    // lower
    AddLine(temp.start,temp.end);

    
        tempo.x=start.x+Size;
    tempo.y=start.y+Size;
 
    temp.start = tempo;
    tempo.x = start.x+Size;
    tempo.y=start.y;
    temp.end =tempo;
    temp.objecttype=1;
    // right
    AddLine(temp.start,temp.end);

    tempo.x=start.x;
    tempo.y=start.y;
 
    temp.start = tempo;
    tempo.x = start.x;
    tempo.y=start.y+Size;
    temp.end =tempo;
    temp.objecttype=1;
    // left
    AddLine(temp.start,temp.end);

}

/************************************************************************
* Function BOOL AddLine(CPoint Start, CPoint End)
*
* PURPOSE
* To add a line in the quadtree
* Algoritm
* A new object Ptr is first formatted as a line,
* Then it has to be added to every node that it runs through on every level for a tree.
* This is done by descent, and in every level following the line along its path to see what quadrents it is in
* INPUTS
* the start and end points
* RESULT
* A line is added in the quadtree
*
*************************************************************************/
UQuadTree::GROUPSTRUCT* UQuadTree::AddLine(CPoint Start, CPoint End)
{
    // do some error checking
    if (!AddCheckifPointValid(Start))
        return NULL;
    if (!AddCheckifPointValid(End))
        return NULL;
        

    ObjectPtr temp;
    TreePtr tTreePtr,tLevelTreePtr;
    temp = new Object;    
    CPoint next,divnext;

    // copy all the information to a new pointer.
    temp->end = End;
    temp->middle = 0;
    temp->objectID = IDList.GetNewID();
    temp->objecttype = LINE;
    temp->renderflag = 0;
    temp->start = Start;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    // add the object to the root node
    AddToObjectList(HeadQuadPtr,temp);

    tLevelTreePtr = HeadQuadPtr;    

    int quadrant;

    CPoint DivPoint;
    DivPoint.x = Start.x/100+1;
    DivPoint.y = Start.y/100+1;
    quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);

    // at a leaf node, time to go.
    while (quadrant!=-1)
    {
        next = Start;  // reset the starting position for every level
        // tranlate the points into quadrants for the function       
        
        if (quadrant > 0) // just in case
             tLevelTreePtr = tLevelTreePtr->NextQuad[quadrant-1];
        tTreePtr = tLevelTreePtr;
        while ((next.x != -1) && (tTreePtr != NULL))
        {

            AddToObjectList(tTreePtr,temp);
            next = LAUtils.FindIntersection(next,End,tTreePtr->QuadRect);
            tTreePtr = AddFindQuad(next,tTreePtr);
        }
        // will output -1 when at the last level.

        quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
    } 

    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;
    

    // create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;

}

/************************************************************************
* Function SelectObject(CPoint Point, int Range)
*
* INPUTS
* Point = the starting point to look for the line
* Range = the distance away from the starting point to extend the search for an object
* Select, wheather the object should be selected or disselected.
* OUTPUTS
* returns int ID = the ID of the object selected, -1 if no object selected
*
*************************************************************************/
BOOL UQuadTree::SelectObject(CPoint Point, float Range, BOOL Select)
{

    // check if the user is really trying to grab and endpoint of the prevuisly selected line
    if (DraftingCheckifPrevSelEndPoint(Point,Range,Select))
    {
    }
    else
    {
        // initialize the closest object paramters
        ObjectPtr ClosestObject = NULL;
        float SmallestDistance = (float)Range;

        // get all of the quadrants inside of the range
        CRect QuadLimit;
        SelectGetAllQuadrants(Point,(int)Range,QuadLimit);


        for (int ix = QuadLimit.left; ix <= QuadLimit.right; ix++)
        {
            for (int iy = QuadLimit.top; iy <=QuadLimit.bottom; iy++)
            {
                // get the object list for that quadrant
                TreePtr Quad = AddFindQuad(ix,iy);
                ObjectListPtr Curr = Quad->Objects;
                while(Curr != NULL)
                {
                    /* formula used to find the distance from the line to a point 
                    d = (Ax1+By1+C)/sqrt(A*A+B*B) where Ax + By + C = 0 is the equation of the line
                    */
                    float slope,A,B,C,Distance;

                    // special case if slope is infinity
                    if ((Curr->Data->end.x-Curr->Data->start.x) == 0)
                    {
                        B= 0;
                        A = 1;
                        C = (float)-Curr->Data->start.x;
                    }
                    else
                    {
                        slope = (float)(Curr->Data->end.y-Curr->Data->start.y)/(float)(Curr->Data->end.x-Curr->Data->start.x);
                        B = 1;
                        A = -slope;  
                        C = -Curr->Data->start.y+Curr->Data->start.x*slope;
                    }

                   /* if (Curr->Data->objecttype == BUMPSENSOR)
                    {
                        // the sensors have a middle point
                        CRect Border;
                        Border.top = Curr->Data->middle.y - (long)(5*RenderingStats.OldBumperScaleY);
                        Border.bottom = Curr->Data->middle.y + (long)(5*RenderingStats.OldBumperScaleY);
                        Border.left = Curr->Data->middle.x - (long)(10*RenderingStats.OldBumperScaleX);
                        Border.right = Curr->Data->middle.x + (long)(10*RenderingStats.OldBumperScaleX);
                        if(LAUtils.InRect(Point,Border))
                        {
                            Distance = 0; // easiest way to do it.  A bump sensor always takes proirity over lines
                            DraftingFlushAll();
                        }
                        else
                        {
                            Distance = (float)99999999.0; // have to make it equal to something
                        }
                    }
                    else
                    {    */           
                        Distance = ((A*(float)Point.x+B*(float)Point.y+C))/(float)sqrt(A*A+B*B);
                   // }
                
                    // get rid of negatives
                    if (Distance < 0)
                    {
                        Distance = - Distance;
                    }
                    // a smaller then previous object has been found.
                    if (Distance < SmallestDistance)
                    {
                        ClosestObject = Curr->Data;
                        SmallestDistance = Distance;

                    }
                    Curr = Curr->Next;

                }
            }
        }
        if (ClosestObject != NULL)
        {
            if (Select) // select the object
            {
                 SelectAddtoList(ClosestObject);
                 // a sensor is not a draft point
                 if ((ClosestObject->objecttype != BUMPSENSOR) || (ClosestObject->objecttype != IRSENSOR) || (ClosestObject->objecttype != SONARSENSOR))
                    SelectCheckIfDraftPoint(ClosestObject,Point,Range);
            }
            else // deselect the object.
            {
                SelectRemovefromList(ClosestObject);
            }
            return true;
        }
   }
 
    return false;
}

/************************************************************************
* SelectGetAllQuadrants(CPoint Point, int Range, CRect &Rect)
*
* INPUTS
* Point = the point that is used to find the closest object
* Range = the distance away from the starting point to extend the search for an object
* OUTPUTS
* a Rect of all the quadrants relevant to the search
*
*************************************************************************/
void UQuadTree::SelectGetAllQuadrants(CPoint Point, int Range, CRect &Rect)
{
    // in case rounding happened
    if (Range == 0)
        Range = 1;
    
    Rect.top = (Point.y-Range)/100+1;
    if (Rect.top < QUADYSTART)
    {
        Rect.top = QUADYSTART;
    }
    Rect.bottom = (Point.y+Range)/100+1;
    if (Rect.bottom > QUADYBOUND)
    {
        Rect.bottom = QUADYBOUND;
    }
    Rect.left = (Point.x-Range)/100+1;
    if (Rect.left < QUADXSTART)
    {
        Rect.left = QUADXSTART;
    }
    Rect.right = (Point.x+Range)/100+1;
    if (Rect.right > QUADXBOUND)
    {
        Rect.right = QUADXBOUND;
    }

}


/************************************************************************
* SelectAddtoList(UQuadTree::OBJECT *theObject)
* SelectRemovefromList(UQuadTree::OBJECT *theObject)
*
* PURPOSE
* To add a object to the selected linked list.
* USAGE
* Used by the SelectObject function
* INPUTS
* A Pointer to an object
*
*
*************************************************************************/
void UQuadTree::SelectAddtoList(UQuadTree::OBJECT *theObject)
{  
    
    // don't double select objects
    if (theObject->objectColor != SELECTCOLOR)
    {

    // check if there is a list already
        if (SelectedObjectPtr == NULL)
        {
            SelectedObjectPtr = new SelectStruct;
            SelectedObjectPtr->Prev=SelectedObjectPtr->Next=NULL;  

            // get the highest group object to put into the list
            LGroupPtr tempo = theObject->GroupPtr;
            while (tempo->ParentPtr != NULL)
            {
                tempo = tempo->ParentPtr;
            }
            SelectedObjectPtr->data=tempo;
            
        }
        // insert to front of list.
        else
        {
            SelectPtr temp = new SelectStruct;

            // get the highest group object to put into the list
            LGroupPtr tempo = theObject->GroupPtr;
            while (tempo->ParentPtr != NULL)
            {
                tempo = tempo->ParentPtr;
            }
            temp->data=tempo;

            temp->Next = SelectedObjectPtr;
            SelectedObjectPtr->Prev = temp;
            temp->Prev = NULL;
            SelectedObjectPtr = temp;
        }
        SelectChangeSelectStatus(theObject->GroupPtr,true);

    }

}

/************************************************************************
* SelectChangeSelectStatus(LGroupPtr GroupPtr, bool Selec
*
* PURPOSE
* To change the select status of a group, e.i change its color
* USAGE
* Used by Select Add and Delete to list
* INPUTS
* A Pointer to the group object
*
*
*************************************************************************/
void UQuadTree::SelectChangeSelectStatus(UQuadTree::GROUPSTRUCT *GroupPtr, bool Select)
{
    // extra check
    if (GroupPtr == NULL)
        return;

    // find the top level group
    while (GroupPtr->ParentPtr != NULL)
    {
        GroupPtr = GroupPtr->ParentPtr;
    }

    SelectChangeSelectStatus1(GroupPtr,Select);

}

// recursive function used above
void UQuadTree::SelectChangeSelectStatus1(UQuadTree::GROUPSTRUCT *GroupPtr, bool Select)
{
    // call the function for all of its children
    if (GroupPtr->Child != NULL)
    {
        SelectChangeSelectStatus1(GroupPtr->Child, Select);
    }
    if (GroupPtr->Sibling != NULL)
    {
        SelectChangeSelectStatus1(GroupPtr->Sibling, Select);
    }

    ObjectListPtr curr = GroupPtr->Next;

    // change the select status, e.g change the color
    while (curr != NULL)
    {
        if (Select)
        {
             curr->Data->objectColor = SELECTCOLOR;
        }
        else
        {
            if ((curr->Data->objecttype == ROOF3D) || (curr->Data->objecttype == TRIANGLE3D))
                curr->Data->objectColor = 2;
            else
                curr->Data->objectColor = NEUTRALCOLOR;
        }
        curr = curr->Next;
    }        
        

}

/************************************************************************
* SelectRemovefromList(UQuadTree::OBJECT *theObject)
*
* PURPOSE
* To remove a group from the select list
* USAGE
* By the selectobject, but more precisly when the user left-ctrl clicks on an object
* INPUTS
* A pointer to the object that was selected
* ALGORITHM
* Check to see if the object was in the select list.  This search will used the top
* level group pointer of the object.  If it is, break out the pointer out of the list,
* and disselect the group.
*
*
*************************************************************************/
void UQuadTree::SelectRemovefromList(UQuadTree::OBJECT *theObject)
{
    if (SelectedObjectPtr != NULL)
    {

        SelectPtr temp;

        temp = SelectedObjectPtr;
    
        // is the object selected in the first place?
        if (theObject->objectColor != NEUTRALCOLOR)
        {
        // make sure the topgroup pointer is used.  Don't want to do a full search
            // so by using the convention I save time
            LGroupPtr topPointer = temp->data;
            while (topPointer->ParentPtr != NULL)
            {
                topPointer = topPointer->ParentPtr;
            }
            // check to see if its group is on the list
            while (temp != NULL)
            {
                // group ptr in the list
                if (topPointer == temp->data)
                {
                    // found the group, break the group out of the chain
                    if ((temp->Next != NULL) && (temp->Prev != NULL))
                    {
                        // break the object out of the chain.
                        temp->Next->Prev = temp->Prev;
                        temp->Prev->Next = temp->Next;
                    }
                    // the object is at the end of the list
                    else if (temp->Next == NULL)
                    {
                        if (temp->Prev != NULL)
                        {
                            temp->Prev->Next = NULL;
                        }
                        else
                        {
                            SelectedObjectPtr = NULL;
                        }
                    }
                    // the object is at the begining of the list
                    else
                    {
                        SelectedObjectPtr = temp->Next;
                        if (temp->Next->Prev != NULL)
                        {
                            temp->Next->Prev = NULL;
                        }
                    }

                    // change the select status of a group
                    SelectChangeSelectStatus(theObject->GroupPtr,false);
  
                    // delete the select pointer.
                    delete temp;
                    temp = NULL;                
                }    
                else if (temp != NULL) // because of above where temp = NULL to get out of the loop
                {
                    temp = temp->Next;
                }
            }// end while

         }// enc color check
    }// end null check

}

/************************************************************************
* SelectDeleteList()
*
* PURPOSE
* Deletes the list of currently selected objects. 
*
* USAGE
* to flush a list, used in various places, non user related
*
*
*************************************************************************/
void UQuadTree::SelectDeleteList()
{
    SelectPtr next;

    next = SelectedObjectPtr;
    
    // nuke the list
    while (SelectedObjectPtr != NULL)
    {
        next = SelectedObjectPtr->Next;    
        delete SelectedObjectPtr;
        SelectedObjectPtr = NULL;
        SelectedObjectPtr = next;
    }
}



/************************************************************************
* DeleteObject(ObjectPtr theObject)
*
* PURPOSE
* This function deletes every instants of an object
* USAGE
* various
* INPUT
* a pointer to the object.
*
*************************************************************************/
void UQuadTree::DeleteObject(UQuadTree::OBJECT *theObject)
{
    if (theObject != NULL) // why not add an extra check
    {

        // delete the reference to the object in all of the nodes it is in.
        // this function is nearly identicle to the add line one.
        TreePtr tTreePtr,tLevelTreePtr;
        CPoint next,Start,End;

        if ((theObject->objecttype == BUMPSENSOR) || (theObject->objecttype == SONARSENSOR) || (theObject->objecttype == IRSENSOR))
        {
            Start = theObject->middle;
            End = theObject->middle;
        }
        else
        {
            Start = theObject->start;
            End = theObject->end;
        }

        CPoint DivPoint;

        DivPoint.x = Start.x/100+1;
        DivPoint.y = Start.y/100+1;

        tLevelTreePtr = HeadQuadPtr;    

        int quadrant;   
        
        if ((theObject->objecttype == BUMPSENSOR) || (theObject->objecttype == SONARSENSOR) || (theObject->objecttype == IRSENSOR))
        {
            // recursivly go down the quadtree adding the sensor to varoius quadrants
            int Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
            while (Quadrant != -1)
            {
                tLevelTreePtr = tLevelTreePtr->NextQuad[Quadrant-1];
                DeleteFromObjectList(tLevelTreePtr,theObject);
                Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
            }

        }
        else
        {            
            quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);

            // at a leaf node, time to go.
            while (quadrant!=-1)
            {
                next = Start;  // reset the starting position for every level
                // tranlate the points into quadrants for the function       
        
                if (quadrant > 0) // just in case
                     tLevelTreePtr = tLevelTreePtr->NextQuad[quadrant-1];
                tTreePtr = tLevelTreePtr;
                while ((next.x != -1) && (tTreePtr != NULL))
                {

                    DeleteFromObjectList(tTreePtr,theObject);
                    next = LAUtils.FindIntersection(next,End,tTreePtr->QuadRect);
                    tTreePtr = AddFindQuad(next,tTreePtr);
                }
                // will output -1 when at the last level.
                quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
            }
        } 

        // delete the object from the root node
        DeleteFromObjectList(HeadQuadPtr,theObject);

        // now all the refernces to the object are gone, now delete it from the biglist
        DeleteObjectReal(theObject);
    }
}

/************************************************************************
* DeleteFromObjectList(UQuadTree::TREESTRUCT *tTreePtr, UQuadTree::OBJECT *theObject)
*
* PURPOSE
* This function deletes the object from the quadtree object list
* USAGE
* The DeleteObject function
* INPUT
* The relevant object, and a pointer to the tree node.
*
*************************************************************************/
void UQuadTree::DeleteFromObjectList(UQuadTree::TREESTRUCT *tTreePtr, UQuadTree::OBJECT *theObject)
{

    ObjectListPtr temp;
    temp = tTreePtr->Objects;

    while (temp != NULL)
    {
        if (temp->Data == theObject)
        {
            if ((temp->Next != NULL) && (temp->Prev != NULL))
            {
                // break the object out of the chain.
                temp->Next->Prev = temp->Prev;
                temp->Prev->Next = temp->Next;
            }
            // the object is at the end of the list
            else if (temp->Next == NULL)
            {
                if (temp->Prev != NULL)
                {
                    temp->Prev->Next = NULL;
                }
                else
                {
                    tTreePtr->Objects = NULL;
                }
            }
            // the object is at the begining of the list
            else
            {
                tTreePtr->Objects = temp->Next;
                if (temp->Next->Prev != NULL)
                {
                    temp->Next->Prev = NULL;
                }
            }
            delete temp;
            temp = NULL;
        }
        else
        {
            temp = temp->Next;
        }
    }

}


/************************************************************************
* DeleteObjectReal(ObjectPtr theObject)
*
* PURPOSE
* This function deletes the object from the big list, and actually deletes the object
* USAGE
* The DeleteObject function
* INPUT
* The relevant object
*
*************************************************************************/
void UQuadTree::DeleteObjectReal(UQuadTree::OBJECT *theObject)
{
    ObjectListPtr temp;
    temp = BigObjectList;

    while (temp != NULL)
    {
        if (temp->Data == theObject)
        {
            if ((temp->Next != NULL) && (temp->Prev != NULL))
            {
                // break the object out of the chain.
                temp->Next->Prev = temp->Prev;
                temp->Prev->Next = temp->Next;
            }
            // the object is at the end of the list
            else if (temp->Next == NULL)
            {
                if (temp->Prev != NULL)
                {
                    temp->Prev->Next = NULL;
                }
                else
                {
                    BigObjectList = NULL;
                }
            }
            // the object is at the begining of the list
            else
            {
                BigObjectList = temp->Next;
                if (temp->Next->Prev != NULL)
                {
                    temp->Next->Prev = NULL;
                }
            }
            if (temp->Data->objecttype == BUMPSENSOR)
            {
                BumpSensorIDList.AddBackID(temp->Data->objectID);
            }
            else if (temp->Data->objecttype == IRSENSOR)
            {
                IRSensorIDList.AddBackID(temp->Data->objectID);
            }
            else if (temp->Data->objecttype == SONARSENSOR)
            {
            }
            else
            {                
                IDList.AddBackID(temp->Data->objectID); // put back the ID in the pool.
            }
            // actually delete the object
            delete temp->Data;
            temp->Data = NULL;
            delete temp;  // delete the objectlist part of it.
            temp = NULL;
        }
        else
        {
            temp = temp->Next;
        }
    }

}


/************************************************************************
* RenderAddtoList(UQuadTree::TREESTRUCT *toRender)
*
* PURPOSE
* This function is used by the recursive render list call, to add a the objects of a node
* onto the rendering list.
* USAGE
* RenderCreateList (the recursive one)
* INPUT
* TREESTRUCT *toRender, a pointer to the node which is being rendered.
*
*************************************************************************/
void UQuadTree::RenderAddtoList(UQuadTree::TREESTRUCT *toRender)
{
    // create a temporary pointer to traverse the list
    ObjectListPtr tObjectListPtr = toRender->Objects;
    ObjectListPtr tPtr;

    // a quadrant is being rendered
    RenderingStats.NQuadRendered++;
    // there has to be some elements in the nodes list, to add them to the list
    if (tObjectListPtr != NULL)
    {
        // no elements, insert in top
        if (RenderObjectListPtr == NULL)
        {
            RenderObjectListPtr = new OBJECTLIST;
            // since it is the first element, I don't have to take into acount of the object
            // already has been added to this list.
            RenderObjectListPtr->Data = tObjectListPtr->Data;
            RenderObjectListPtr->Next = NULL; // note only using a single linked list.
            RenderObjectListPtr->Data->renderflag = RenderingStats.RenderCycle; // flag is so it isn't placed in the list again.             
            tObjectListPtr = tObjectListPtr->Next;
        }
        while (tObjectListPtr != NULL)
        {
            // check to see if it has been added to the list yet.
            if (tObjectListPtr->Data->renderflag != RenderingStats.RenderCycle)
            {
                tPtr = new OBJECTLIST;
                tPtr->Data = tObjectListPtr->Data;
                tPtr->Data->renderflag = RenderingStats.RenderCycle; // flag is so it isn't placed in the list again.            
                tPtr->Next = RenderObjectListPtr; // note only using a single linked list.
                RenderObjectListPtr = tPtr;
                
            }
            tObjectListPtr = tObjectListPtr->Next;
        }
    }

}

/************************************************************************
* RenderCreateList(CRect Quad, CRect Screen)
*
* PURPOSE
* The non recursive call which calls the recursive one (same name).  It initializes 
* the rendering list, and calls the recursive function
* USAGE
* Render (used by the onpaint)
* INPUT
* CRect RenderingBound, the area which needs to be rendered
*
*************************************************************************/
void UQuadTree::RenderCreateList(CRect RenderingBound)
{
       // now find the quadrants that should be rendered.
    CRect tRenderingBound;
    RenderingStats.XQuadStart = tRenderingBound.left = (RenderingBound.left-1)/100+1;
    RenderingStats.YQuadStart = tRenderingBound.top = (RenderingBound.top-1)/100+1;
    RenderingStats.XQuadEnd = tRenderingBound.right = (RenderingBound.right-1)/100+1;
    RenderingStats.YQuadEnd = tRenderingBound.bottom = (RenderingBound.bottom-1)/100+1;

    // make sure all quadrants are in bounds (1-128)
    if (tRenderingBound.left < QUADXSTART)
        tRenderingBound.left = QUADXSTART;
    if (tRenderingBound.right > QUADXBOUND)
        tRenderingBound.right = QUADXBOUND;
    if (tRenderingBound.top < QUADYSTART)
        tRenderingBound.top = QUADYSTART;
    if (tRenderingBound.bottom > QUADYBOUND)
        tRenderingBound.bottom = QUADYBOUND;

    RenderObjectListPtr = NULL; // just in case

    // reset the counter
    RenderingStats.NQuadRendered = 0;
    // increment the cycle
    RenderingStats.RenderCycle++;

    RenderCreateList(tRenderingBound,HeadQuadPtr);


}

/************************************************************************
* RenderCreateList(CRect Quad, CRect Screen)
*
* PURPOSE
* The call which does a decent of the quad tree, which finds the minimum number
* of nodes that need to be rendered
* USAGE
* RenderCreateList (non recursive version)
* INPUT
* CRect RenderingBound, the area which needs to be rendered
* TREESTRUCT *toRender the node in the tree which is being looked at.
*************************************************************************/
void UQuadTree::RenderCreateList(CRect RenderingBound, UQuadTree::TREESTRUCT *toRender)
{
    // check if current node, is completely contained in the rendering bounds
    if ((toRender->QuadRect.bottom <= RenderingBound.bottom)
        && (toRender->QuadRect.top >= RenderingBound.top)
        && (toRender->QuadRect.left >= RenderingBound.left)
        && (toRender->QuadRect.right <= RenderingBound.right))
    {
        RenderAddtoList(toRender);
        return;
    }
    // check if none of the current node is contained in the rendering bounds
    else if ((toRender->QuadRect.top > RenderingBound.bottom)
        || (toRender->QuadRect.bottom < RenderingBound.top)
        || (toRender->QuadRect.right < RenderingBound.left)
        || (toRender->QuadRect.left > RenderingBound.right))
    {
        return;
    }
    // O.K there is a partial match, lets render each quad of this node
    else
    {
        // note there should never be a case that we are here, and the NextQuad is NULL,
        // so this isn't taken into account.
        for (int ix = 0; ix < QUAD; ix++)
        {
            RenderCreateList(RenderingBound,toRender->NextQuad[ix]);

        }
    }
    return;



}


/************************************************************************
* RenderCreateList(CRect Quad, CRect Screen)
*
* PURPOSE
* This is called when SelectObject function finds a close object.  This function
* is supposed to check if a drafting point (start/end point of a line) was clicked on
* to select this point and object, so that it could be dragged.
* USAGE
* by SelectObject
* INPUT
* theObject the object selected
* thePoint the point clicked on
* range the maximum the click could be away from the draft point to drag it.
*************************************************************************/
void UQuadTree::SelectCheckIfDraftPoint(UQuadTree::OBJECT *theObject, CPoint thePoint, float range)
{
    float StartDistance,EndDistance,MiddleDistance;

    // checks to make sure the object is alone, so it won't effect anything else
    if ((theObject->GroupPtr->GroupType == NonSeperable) && (theObject->GroupPtr->ParentPtr == NULL))
    {

        if (theObject->objecttype == LINE)
        {
            StartDistance = LAUtils.GetDistance(thePoint,theObject->start);
            EndDistance = LAUtils.GetDistance(thePoint,theObject->end);
            MiddleDistance = (float)999999999.9;
        }
        else if (theObject->objecttype == ARCLINE)
        {
            StartDistance = LAUtils.GetDistance(thePoint,theObject->GroupPtr->Next->Data->start);
            EndDistance = LAUtils.GetDistance(thePoint,theObject->GroupPtr->Next->Data->end);
            MiddleDistance = LAUtils.GetDistance(thePoint,theObject->GroupPtr->Next->Data->middle);
        }

        // check which distance is shorter to check out
        if ((StartDistance < EndDistance) && (StartDistance < MiddleDistance))
        {
            if (theObject->objecttype == LINE)
            {
                DraftingObject.theObject=theObject;
            }
            else if (theObject->objecttype == ARCLINE)
            {
                 //point to the header
                DraftingObject.theObject = theObject->GroupPtr->Next->Data;
            }
            if (StartDistance < range)
            {
                DraftingObject.valid = true;
                DraftingObject.changed = false;
                DraftingObject.isMoving = true;
                DraftingObject.WhatPoint = 0;
            }
            // If not make sure it gets priority over the next click if its end point
            // matches up with another line
            else
            {
                DraftingObject.selected=true;
                DraftingObject.valid = false;
            }
            
        }
        else if ((EndDistance < StartDistance) && (EndDistance < MiddleDistance))
        {
            if (theObject->objecttype == LINE)
            {
                DraftingObject.theObject=theObject;
            }
            else if (theObject->objecttype == ARCLINE)
            {
                // point to the header
                DraftingObject.theObject = theObject->GroupPtr->Next->Data;
            }
            if (EndDistance < range)
            {
                DraftingObject.valid = true;
                DraftingObject.changed = false;
                DraftingObject.isMoving = true;
                DraftingObject.WhatPoint = 1;
            }
            // If not make sure it gets priority over the next click if its end point
            // matches up with another line
            else
            {
                DraftingObject.selected=true;
                DraftingObject.valid = false;
            }
        }
        // gotta be the middle point
        else
        {
            if (theObject->objecttype == LINE)
            {
                DraftingObject.theObject=theObject;
            }
            else if (theObject->objecttype == ARCLINE)
            {
                // point to the header
                DraftingObject.theObject = theObject->GroupPtr->Next->Data;
            }
            if (MiddleDistance < range)
            {
                DraftingObject.valid = true;
                DraftingObject.changed = false;
                DraftingObject.isMoving = true;
                DraftingObject.WhatPoint = 2;
            }
            // If not make sure it gets priority over the next click if its end point
            // matches up with another line
            else
            {
                DraftingObject.selected=true;
                DraftingObject.valid = false;
            }
        }
    }


}


/************************************************************************
* DraftingOnMouseMoved(CPoint Point)
*
* PURPOSE
* This is called by the mainview, when the mouse has moved
* It checks if there is drafting feature that need to be updated
* Such as a line being pulled by it vertex
* Algorithm
* If it is only one object (LINE) then the reference to the lines point could be changed
* and then when the mouse is released, it is deleted then added to requadratize it.
* When and ARCLINE happens the entire arc must be deleted and created here which takes 
* more time, but can't be avoided.
* USAGE
* by parent class, the drafting object is entered by the selectobject
* INPUT
* Point, the new points in the real coord system of where the mouse is.
*************************************************************************/
void UQuadTree::DraftingOnMouseMoved(CPoint Point)
{
    // an object is selected and valid
    if (DraftingObject.valid && (DraftingObject.theObject != NULL) && AddCheckifPointValid(Point))
    {
        if (DraftingObject.theObject->objecttype == LINE)
        {           

            // be sure not to change the drafting object itself,
            // create new points to store the new data.
            CPoint Start,End;    

            // check if the start point
            if (DraftingObject.WhatPoint == 0)
            {
                Start = Point; 
                End = DraftingObject.theObject->end;
                DraftingObject.changed = true;
            }
            // check if the end line is selected
            else if (DraftingObject.WhatPoint == 1)
            {
                End = Point;
                Start = DraftingObject.theObject->start;
                DraftingObject.changed = true;
            }      

            // now delete the line, and recreate it in the new position
            SelectRemovefromList(DraftingObject.theObject);
            // now totally delete it         
            DeleteGroup(DraftingObject.theObject->GroupPtr);
            
            LGroupPtr GroupPtr = AddLine(Start,End);

            if (GroupPtr != NULL)
            {
                SelectAddtoList(GroupPtr->Next->Data);
                DraftingObject.theObject=GroupPtr->Next->Data;
            }
            else
            {
                DraftingObject.valid = false;
            }  

        }
        else if (DraftingObject.theObject->objecttype == ARCLINE)
        {
            CPoint Middle,Start,End;
            Middle = DraftingObject.theObject->middle;
            Start = DraftingObject.theObject->start;
            End = DraftingObject.theObject->end;
            // check if the start point
            if (DraftingObject.WhatPoint == 0)
            {
                if (AddCheckifPointValid(Point))
                   Start = Point;           
            }
            // check if the end line is selected
            else if (DraftingObject.WhatPoint == 1)
            {
                if (AddCheckifPointValid(Point))
                     End = Point;
            }
            else if (DraftingObject.WhatPoint == 2)
            {
                if (AddCheckifPointValid(Point))
                    Middle = Point; 
            }

            // delete the Arc
            DeleteGroup(DraftingObject.theObject->GroupPtr);
            SelectDeleteList();  // nukes the list too, it should be the only member,
            // may have problems if the arc is grouped, and moved.


            // Re Create the Arc with the new points
            LGroupPtr GroupPtr = AddArc(Start,Middle,End);
            SelectAddtoList(GroupPtr->Next->Data);
            DraftingObject.theObject=GroupPtr->Next->Data;

                        
            DraftingObject.changed = true;
        }
    }    
}
        
/************************************************************************
* DraftingOnMouseUp()
*
* PURPOSE
* Releases the drafting object.
* ALGORITHM
* Easiest way to do this was to use the exiting functions of add and delete line.
* USAGE
* by parent class
*************************************************************************/


void UQuadTree::DraftingOnMouseUp()
{
 
    if (DraftingObject.valid && (DraftingObject.theObject != NULL) && DraftingObject.changed)
    {
        if (!DraftingState.Arc1 && !DraftingState.Arc2 && !DraftingState.Line1 && !DraftingState.Move1)
        {   
            // unselect it.            
            SelectRemovefromList(DraftingObject.theObject);
            DraftingObject.changed = false;
            DraftingObject.theObject = NULL;
            DraftingObject.valid = false;
            DraftingObject.isMoving = false;
            DraftingObject.WhatPoint = 0;

           
        }
    }

}

/************************************************************************
* BOOL DraftingCheckifPrevSelEndPoint(CPoint Point, int range, BOOL select)
*
* PURPOSE
* This function was made in the case where several object intersect, one is selected,
* and the user tries to move of vertix of the one selected.  Without some search, any one
* of the lines could be selected for the move
* USAGE
* select line
*************************************************************************/
BOOL UQuadTree::DraftingCheckifPrevSelEndPoint(CPoint Point, float range, BOOL select)
{
    // to take care of the case to do nothing. if the user is trying to release a vertices
    if (DraftingObject.isMoving)
    {
        return true;
    }
    // check if there is a drafting object selected
    if (DraftingObject.selected && DraftingObject.theObject != NULL && DraftingObject.valid)
    {
        if (select)
        {
            float StartDistance = LAUtils.GetDistance(Point,DraftingObject.theObject->start);
            float EndDistance = LAUtils.GetDistance(Point,DraftingObject.theObject->end);

            if (StartDistance < EndDistance)
            {            
                if (StartDistance < range)
                {
                    DraftingObject.valid = true;
                    DraftingObject.changed = false;
                    DraftingObject.WhatPoint = 0;
                    DraftingObject.selected = false;
                    DraftingObject.isMoving = true;
                    return true;
                }           
            }
            else
            {
                if (EndDistance < range)
                {
                    DraftingObject.valid = true;
                    DraftingObject.changed = false;
                    DraftingObject.WhatPoint = 1;
                    DraftingObject.selected = false;
                    DraftingObject.isMoving = true;
                    return true;
                }           
            }

        }
        else
        {
                SelectRemovefromList(DraftingObject.theObject);
               // DraftingObject.selected = false;
                return true;
        }
    }

    return false;
}

/************************************************************************
* BOOL AddArc(CPoint Start, CPoint Middle, CPoint End)
*
* PURPOSE
* To Add an Arc composed of the primative (lines) to the quadtree
* USAGE
* by the draw class
* ALGORITHM
* 1) The function first calls a linear algebra function which returns a bunch of points
*    which make up the Arc
* 2) The return lists is entered into the quadtree
* 3) All of the lines are entered is as type arcline, with them all having a common group 
*    Pointer
* 4) A dummy header is added to the front of the group pointer, offering overall information on the Arc
*************************************************************************/
UQuadTree::GROUPSTRUCT* UQuadTree::AddArc(CPoint Start, CPoint Middle, CPoint End)
{
    // check if the points are in the valid range
    if (!AddCheckifPointValid(Start))
        return NULL;
    if (!AddCheckifPointValid(Middle))
        return NULL;
    if (!AddCheckifPointValid(End))
        return NULL;

       
    // calls a linear algebra with returns a bunch of points that resemble a circle.
    ULinearAlgebra::PointListPtr temp = LAUtils.GetPointsofCircle(Start,Middle,End,DefaultLinesinArc);

    ULinearAlgebra::PointListPtr prev;
    CPoint Prev;

    // create the group pointer
    LGroupPtr tGroupPtr = new GROUPSTRUCT;

    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL; // no children groups
    tGroupPtr->ParentPtr = NULL; // no parents group for now
    tGroupPtr->Sibling = NULL;
    tGroupPtr->Next = NULL; // just for initialization sake.
    tGroupPtr->GroupType = NonSeperable; // can't seperate the group
    tGroupPtr->NumofObjects = DefaultLinesinArc;
    


    int ID = IDList.GetNewID();

    // traverse the list, adding each line to the quad tree.
    if (temp != NULL)
    {
        Prev = temp->thePoint;
        prev = temp;
        temp = temp->Next;
        delete prev;
    }
    while (temp != NULL)
    {
        AddArcLine(Prev,temp->thePoint,tGroupPtr,ID);
        Prev = temp->thePoint;
        prev = temp;
        temp = temp->Next;
        delete prev;
    }   

    // create the dummy header
    ObjectPtr Header = new Object;
    Header->end = End;
    Header->start = Start;
    Header->middle = Middle;
    Header->GroupPtr = tGroupPtr;
    //Header->GroupPtr = NULL;
    Header->objectID = ID;
    Header->objecttype = ARCLINE;
    Header->renderflag = 0;
    Header->objectColor = NEUTRALCOLOR;

    // note this is only a single link list, add the header to the front of it.
    ObjectListPtr tempo = new OBJECTLIST;
    tempo->Data = Header;
    tempo->Prev = NULL; // always for every node
    tempo->Next = tGroupPtr->Next; // insert into start of the group ptr.
    tGroupPtr->Next = tempo;

    return tGroupPtr;


}


/************************************************************************
* BOOL AddCheckifPointValid(CPoint thePoint)
*
* PURPOSE
* Checks if the point is valid
* RETURNs
* true or false;
*
*************************************************************************/
BOOL UQuadTree::AddCheckifPointValid(CPoint thePoint)
{
    if ((thePoint.x <= QUADXBOUND*99-1) &&
        (thePoint.x >= QUADXSTART+1) &&
        (thePoint.y <= QUADYBOUND*99-1) &&
        (thePoint.y >= QUADYSTART+1))
        return true;

    return false;

}

/************************************************************************
* Function BOOL AddArcLine(CPoint Start, CPoint End, UQuadTree::OBJECTLIST *GroupPtr)
*
* PURPOSE
* To add an arc line to the quadtree
* An arc is created as a bunch of lines, however each one of these lines
* has to link up to form a group for selection.  This is done by having an extra group ptr,
* which links up to all of them.
* Note the first node in the arcline list, is the dummy node containing the real end middle and start points
* INPUTS
* the start and end points, and the group pointer
* RESULT
* A line is added in the quadtree
*
*************************************************************************/
 BOOL UQuadTree::AddArcLine(CPoint Start, CPoint End,  UQuadTree::GROUPSTRUCT *GroupPtr, int ArcID)
{

    // do some error checking
    if (!AddCheckifPointValid(Start))
        return false;
    if (!AddCheckifPointValid(End))
        return false;

    ObjectPtr temp;
    TreePtr tTreePtr,tLevelTreePtr;
    temp = new Object;    
    CPoint next,divnext;

  
    // copy all the information to a new pointer.
    temp->end = End;
    temp->middle = 0;
    temp->objectID = IDList.GetNewID();/*ArcID*/
    temp->objecttype = ARCLINE;
    temp->renderflag = 0;
    temp->start = Start;
    temp->objectColor = NEUTRALCOLOR;
    temp->GroupPtr = GroupPtr; // a pointer to the pointer of the group list

    // note this is only a single link list.
    ObjectListPtr tempo = new OBJECTLIST;
    tempo->Next = GroupPtr->Next;
    tempo->Data = temp;
    tempo->Prev = NULL; // always for every node
    GroupPtr->Next = tempo;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    // add the object to the root node
    AddToObjectList(HeadQuadPtr,temp);

    tLevelTreePtr = HeadQuadPtr;    

    int quadrant;

    CPoint DivPoint;
    DivPoint.x = Start.x/100+1;
    DivPoint.y = Start.y/100+1;
    quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);

    // at a leaf node, time to go.
    while (quadrant!=-1)
    {
        next = Start;  // reset the starting position for every level
        // tranlate the points into quadrants for the function       
        
        if (quadrant > 0) // just in case
             tLevelTreePtr = tLevelTreePtr->NextQuad[quadrant-1];
        tTreePtr = tLevelTreePtr;
        while ((next.x != -1) && (tTreePtr != NULL))
        {

            AddToObjectList(tTreePtr,temp);
            next = LAUtils.FindIntersection(next,End,tTreePtr->QuadRect);
            tTreePtr = AddFindQuad(next,tTreePtr);
        }
        // will output -1 when at the last level.

        quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
    } 

    return true;

}

/************************************************************************
* Function DeleteGroupList(OBJECTLIST **GroupPtr)
*
* PURPOSE
* To delete the list holding the group, and any header.  The actual objects,
* are deleted with the big object list.
* USAGE
* the only group now is the arc
* INPUTS
* The group ptr
* RESULT
* a group list is deleted
*
*************************************************************************/
void UQuadTree::DeleteGroupList(UQuadTree::GROUPSTRUCT *&GroupPtr)
{   

    if (GroupPtr != NULL)
    {
        LGroupPtr tGroupPtr;
        tGroupPtr = GroupPtr;

        // find the top level group
        while (GroupPtr->ParentPtr != NULL)
        {
            GroupPtr = GroupPtr->ParentPtr;
        }

        // call the recursive function
        DeleteGroupList1(GroupPtr);
    }


}

// recursive function used above
void UQuadTree::DeleteGroupList1(UQuadTree::GROUPSTRUCT *GroupPtr)
{

    // delete all of the children
    if (GroupPtr->Child != NULL)
    {
        DeleteGroupList1(GroupPtr->Child);
    }
    // delete all of its siblings
    if (GroupPtr->Sibling != NULL)
    {
        DeleteGroupList1(GroupPtr->Sibling);
    }

    // delete this one

    ObjectListPtr curr,prev;
    curr = GroupPtr->Next;
  
    // check if there is a dummy header
    if ((GroupPtr->GroupType == NonSeperable) && (GroupPtr->NumofObjects != 1))
    {
        // this may not happen
        if (curr != NULL)
        {
            prev=curr;
            curr=curr->Next;
            delete prev->Data;
            prev->Data = NULL;
            delete prev;
            prev = NULL;
        }
    }

    while (curr != NULL)
    {
        prev=curr;
        curr = curr->Next;
        prev->Data->GroupPtr = NULL;
        delete prev;
        prev = NULL;
    }
    // kill the group ptr
    GroupIDList.AddBackID(GroupPtr->GroupID);
    delete GroupPtr;
    GroupPtr = NULL;

}


/************************************************************************
* Function DeleteGroup(UQuadTree::OBJECTLIST **GroupPtr)
*
* PURPOSE
* Nuke the group and every thing to do with the group
* USAGE
* Used to delete virtually everything
* NOTE
* That is deletes the objects and the group list.  The deletegrouplist function
* can't be used because the groupptr is deleted during deleting the objects.
* INPUTS
* The group ptr
* RESULT
* a group list is deleted
*
*************************************************************************/
void UQuadTree::DeleteGroup(UQuadTree::GROUPSTRUCT *&GroupPtr)
{
    LGroupPtr tGroupPtr;
    tGroupPtr = GroupPtr;

    // find the top level group
    while (GroupPtr->ParentPtr != NULL)
    {
        GroupPtr = GroupPtr->ParentPtr;
    }

    // call the recursive function
    DeleteGroup1(GroupPtr);
   

}

// recursive call used above
void UQuadTree::DeleteGroup1(UQuadTree::GROUPSTRUCT *GroupPtr)
{
     // delete all of the children
    if (GroupPtr->Child != NULL)
    {
        DeleteGroup1(GroupPtr->Child);
    }
    if (GroupPtr->Sibling != NULL)
    {
        DeleteGroup1(GroupPtr->Sibling);
    }


    // delete this one

    ObjectListPtr curr,prev;
    curr = GroupPtr->Next; 
     
    // check if there is a dummy header
    if ((GroupPtr->GroupType == NonSeperable) && (GroupPtr->NumofObjects != 1))
    {
        if (curr != NULL)
        {
            prev=curr;
            curr=curr->Next;
            delete prev->Data;
            prev->Data = NULL;
            delete prev;
            prev = NULL;
        }
    }

    while (curr != NULL)
    {
        prev=curr;
        curr = curr->Next;
        prev->Data->GroupPtr = NULL;
        DeleteObject(prev->Data); // this deletes every reference to it.
        delete prev;
        prev = NULL;
    }
    // kill the group ptr
    GroupIDList.AddBackID(GroupPtr->GroupID);
    delete GroupPtr;
    GroupPtr = NULL;

}


/************************************************************************
* Function SelectCreateGroup()
*
* PURPOSE
* To create a new group out of all objects that are selected
* USAGE
* By the draw class
* RESULT
* The select group is converted into a real group
*
*************************************************************************/
void UQuadTree::SelectCreateGroup()
{
    // check to see that there is at least two elements in the select list
    if (SelectedObjectPtr != NULL)
    {
         if (SelectedObjectPtr->Next != NULL)
         {
             // O.K create a new group
             LGroupPtr tGroupPtr = new GROUPSTRUCT;
             tGroupPtr->GroupID = GroupIDList.GetNewID();
             tGroupPtr->ParentPtr = NULL;
             tGroupPtr->Next = NULL;
             tGroupPtr->GroupType = Seperable;
             tGroupPtr->NumofObjects = 0;
             tGroupPtr->Sibling = NULL;

             LGroupPtr prev = NULL;

             SELECTSTRUCT* tOLPtr = SelectedObjectPtr;

             // link the selected list to a new group object, first object to the last node.
             while (tOLPtr != NULL)
             {
                 tGroupPtr->NumofObjects += tOLPtr->data->NumofObjects;  // increment number of objects
                 tOLPtr->data->ParentPtr = tGroupPtr; // set the parent to the new groupptr
                 tOLPtr->data->Sibling = prev; // link with the prevuis node
                 prev = tOLPtr->data;
                 tOLPtr = tOLPtr->Next;
             }
             tGroupPtr->Child = prev;

             SelectDeleteList();
             SelectAddGrouptoList(tGroupPtr);

            //Clean up the drafting object
            DraftingObject.theObject = NULL;
            DraftingObject.valid = false;
            DraftingObject.WhatPoint = 0;

         }
    }


             

}

/************************************************************************
* Function SelectDeleteGroup()
*
* PURPOSE
* To delete the group (top layer), thus seperating the objects
* USAGE
* By the draw class
* RESULT
* The select group is ungrouped
*
*************************************************************************/
void UQuadTree::SelectDeleteGroup()
{
    SelectPtr tSelectObjectPtr = SelectedObjectPtr;
    // check to make sure there is only one group selected
    if (tSelectObjectPtr != NULL)
    {
        while (tSelectObjectPtr != NULL)
        {

            LGroupPtr tempo,prev;
            tempo = tSelectObjectPtr->data;

            // can't be NULL if a group exists
            if (tempo->Child != NULL)
            {
                // O.K first unselect the group
                SelectChangeSelectStatus(tempo,false);
                // find child group level, and release it from the top pointer
                tempo=tempo->Child;
                while (tempo != NULL)
                {
                    tempo->ParentPtr = NULL;
                    prev=tempo;
                    tempo = tempo->Sibling;
                    prev->Sibling = NULL;
                }
            }

            // extra for roof 3D, this isn't a base group delete the normal way
            if (tSelectObjectPtr->data != NULL && tSelectObjectPtr->data->Child != NULL)
            {
                 SelectChangeSelectStatus(tSelectObjectPtr->data,false);
            }
            // In case a base group was selected, don't want to delete it
            else if (tSelectObjectPtr->data != NULL && tSelectObjectPtr->data->GroupType != NonSeperable)
            {
                delete tSelectObjectPtr->data;
                tSelectObjectPtr->data = NULL;
            }            
            // special case, a single line is "trying" to be ungrouped
            // might as well unselect it
            else
            {
                SelectChangeSelectStatus(tSelectObjectPtr->data,false);
            }

            tSelectObjectPtr = tSelectObjectPtr->Next;
        }
        // clean up list
        SelectDeleteList();
    }
}

/************************************************************************
* Function SelectAddGrouptoList(LGroupPtr theGroup)
*
* PURPOSE
* To add a group to the select list.  Still need because the individual members
* are selected, so the normal SelectAddtoList doesn't work.
* USAGE
* By the create group function
* RESULT
* Adds the group to the list
*
*************************************************************************/
void UQuadTree::SelectAddGrouptoList(UQuadTree::GROUPSTRUCT *theGroup)
{
    // check if there is a list already
    if (SelectedObjectPtr == NULL)
    {
        SelectedObjectPtr = new SelectStruct;
        SelectedObjectPtr->Prev=SelectedObjectPtr->Next=NULL;          
        SelectedObjectPtr->data=theGroup;
        
    }
    // insert to front of list.
    else
    {
        SelectPtr temp = new SelectStruct;
        temp->data = theGroup;
        temp->Next = SelectedObjectPtr;
        SelectedObjectPtr->Prev = temp;
        temp->Prev = NULL;
        SelectedObjectPtr = temp;
    }

}

/************************************************************************
* Function SelectPrintStats(CDC &MemDC)
*
* PURPOSE
* To display the statistics of the selected objects on the screen.
* USAGE
* By the render function during a rendering loop
* RESULT
* The stats of the selected objects are printed on the screen
*
*************************************************************************/
void UQuadTree::SelectPrintStats(CDC &MemDC, int x, int y)
{
    char tempo[100];

    //  clear out the drawing space
    CBrush WhiteBrush(RGB(255,255,255));
    CRect Clearing;
    Clearing.top = y;
    Clearing.bottom = y + 47;
    Clearing.left = x;
    Clearing.right = x + 300;
    MemDC.FillRect(&Clearing,&WhiteBrush);

    if (SelectedObjectPtr != NULL)
    {   
        // O.K something must be selected
        if (SelectedObjectPtr->Next == NULL)
        {         

            if (SelectedObjectPtr->data->GroupType == NonSeperable)
            {
                // a line or arc is selected
                if (SelectedObjectPtr->data->Next == NULL && SelectedObjectPtr->data->NumofObjects == 4)
                {
                    // a triangle is selected
                    sprintf(tempo,"3DTriangle Selected");
                    MemDC.TextOut(x,y,tempo);
                }
                else if (SelectedObjectPtr->data->Next->Data->objecttype == LINE)
                {
                    // a line is selected
                    sprintf(tempo,"Line Selected");
                    MemDC.TextOut(x,y,tempo); 
                    sprintf(tempo,"Position (%d,%d) to (%d,%d)",
                        SelectedObjectPtr->data->Next->Data->start.x,
                        SelectedObjectPtr->data->Next->Data->start.y,
                        SelectedObjectPtr->data->Next->Data->end.x,
                        SelectedObjectPtr->data->Next->Data->end.y);                    
                    MemDC.TextOut(x,y+15,tempo);

                    sprintf(tempo,"Delta of (%d,%d)",
                        SelectedObjectPtr->data->Next->Data->end.x - 
                        SelectedObjectPtr->data->Next->Data->start.x,
                        SelectedObjectPtr->data->Next->Data->end.y - 
                        SelectedObjectPtr->data->Next->Data->start.y);
                    MemDC.TextOut(x,y+30,tempo);
                }
                else if (SelectedObjectPtr->data->Next->Data->objecttype == ARCLINE)
                {
                    // a arc is selected
                    sprintf(tempo,"Arc Selected");
                    MemDC.TextOut(x,y,tempo);
                    sprintf(tempo,"Position (%d,%d) to (%d,%d)                              ", 
                        SelectedObjectPtr->data->Next->Data->start.x,
                        SelectedObjectPtr->data->Next->Data->start.y,
                        SelectedObjectPtr->data->Next->Data->end.x,
                        SelectedObjectPtr->data->Next->Data->end.y);
                    MemDC.TextOut(x,y+15,tempo);

                    sprintf(tempo,"With a middle of (%d,%d)                                  ",
                        SelectedObjectPtr->data->Next->Data->middle.x,
                        SelectedObjectPtr->data->Next->Data->middle.y);
                    MemDC.TextOut(x,y+30,tempo);
                }    
                else if ((SelectedObjectPtr->data->Next->Data->objecttype == BUMPSENSOR))
                {
                     // a bump sensor is selected
                    sprintf(tempo,"Bump Sensor %d Selected",SelectedObjectPtr->data->Next->Data->objectID);
                    MemDC.TextOut(x,y,tempo);
                    sprintf(tempo,"Range of (%d,%d) to (%d,%d)                              ", 
                        SelectedObjectPtr->data->Next->Data->start.x,
                        SelectedObjectPtr->data->Next->Data->start.y,
                        SelectedObjectPtr->data->Next->Data->end.x,
                        SelectedObjectPtr->data->Next->Data->end.y);
                    MemDC.TextOut(x,y+15,tempo);

                    sprintf(tempo,"With a Display Point Center of (%d,%d)                                  ",
                        SelectedObjectPtr->data->Next->Data->middle.x,
                        SelectedObjectPtr->data->Next->Data->middle.y);
                    MemDC.TextOut(x,y+30,tempo);
                }
                else if ((SelectedObjectPtr->data->Next->Data->objecttype == IRSENSOR))
                {
                      // a IR sensor is selected
                    sprintf(tempo,"IR Sensor %d Selected",SelectedObjectPtr->data->Next->Data->objectID);
                    MemDC.TextOut(x,y,tempo);
                    sprintf(tempo,"Range of %d to %d cm                             ", 
                        SelectedObjectPtr->data->Next->Data->start.x,
                        SelectedObjectPtr->data->Next->Data->start.y);
                    MemDC.TextOut(x,y+15,tempo);

                    sprintf(tempo,"Angle of %d                           ", 
                        SelectedObjectPtr->data->Next->Data->end.x);
                    MemDC.TextOut(x,y+30,tempo);

                    sprintf(tempo,"With a Display Point Center of (%d,%d)                                  ",
                        SelectedObjectPtr->data->Next->Data->middle.x,
                        SelectedObjectPtr->data->Next->Data->middle.y);
                    MemDC.TextOut(x,y+45,tempo);
                }
                else if ((SelectedObjectPtr->data->Next->Data->objecttype == SONARSENSOR))
                {

                    sprintf(tempo,"Sonar Sensor Selected",SelectedObjectPtr->data->Next->Data->objectID);
                    MemDC.TextOut(x,y,tempo);                   

                    sprintf(tempo,"With a Display Point Center of (%d,%d)                                  ",
                        SelectedObjectPtr->data->Next->Data->middle.x,
                        SelectedObjectPtr->data->Next->Data->middle.y);
                    MemDC.TextOut(x,y+30,tempo);
                }
            }
            else
            {
                // one group of objects, easy
                sprintf(tempo,"Group Selected");
                MemDC.TextOut(x,y,tempo);
                sprintf(tempo,"Contains %d Elements  ",SelectedObjectPtr->data->NumofObjects);
                MemDC.TextOut(x,y+15,tempo);       
            }  
        }
        else
        {
            // hard part, a lot of objects are selected, but not in one group
            sprintf(tempo,"Many Objects Selected");
            MemDC.TextOut(x,y,tempo);

            // count up the objects
            SELECTSTRUCT* temp;
            temp = SelectedObjectPtr;
            int count = 0;
            while (temp != NULL)
            {
                count += temp->data->NumofObjects;
                temp = temp->Next;
            }
            sprintf(tempo,"Contains %d Elements",count);
            MemDC.TextOut(x,y+15,tempo);

        }


    }
    else
    {
        sprintf(tempo,"No Objects Selected");
        MemDC.TextOut(x,y,tempo);
    }

}

/************************************************************************
* Function SelectDeleteAll()
*
* PURPOSE
* To delete the list, and all elements in the list including groups
* USAGE
* When the user presses the delete key
* RESULT
*
*************************************************************************/
void UQuadTree::SelectDeleteAll()
{
    // Traverse the selected list, deleteing it, and all of the elements in the grouping
    SELECTSTRUCT *prev;

    // create an undo state of something is actually deleted
    if (SelectedObjectPtr != NULL)
    {
        ::SendMessage(ParentHandle,WM_SAVE_STATE,0,0);
    }
    while (SelectedObjectPtr != NULL)
    {
        DeleteGroup(SelectedObjectPtr->data);
        prev = SelectedObjectPtr;
        SelectedObjectPtr = SelectedObjectPtr->Next;
        delete prev;
        prev = NULL;
    }   

}

/************************************************************************
* Function DraftingSnaptoEndpoint(Cpoint Point, int range)
*
* PURPOSE
* If an Endpoint is within the range, this function returns that endpoint
* USAGE
* For drawing functionality, to snap to an endpoint
* ALGORITHM
* First get the quadrants that would be in the range
* Next check out if they contains any lines in the range, if so 
* return the line point with the minimum range
*
*************************************************************************/
CPoint UQuadTree::DraftingSnaptoEndpoint(CPoint Point, int range)
{
 // initialize the closest object paramters
    ObjectPtr ClosestObject = NULL;
    float SmallestDistance = (float)range;
    CPoint tReturn;
    tReturn.x = -1;
    tReturn.y = -1;

    // get all of the quadrants inside of the range
    CRect QuadLimit;
    SelectGetAllQuadrants(Point,range,QuadLimit);


    for (int ix = QuadLimit.left; ix <= QuadLimit.right; ix++)
    {
        for (int iy = QuadLimit.top; iy <=QuadLimit.bottom; iy++)
        {
            // get the object list for that quadrant
            TreePtr Quad = AddFindQuad(ix,iy);
            ObjectListPtr Curr = Quad->Objects;
            while(Curr != NULL)
            {
                // uhh make sure it doesn't snap to itself!!
                if (Curr->Data != DraftingObject.theObject)
                {
                
                    float StartDistance,EndDistance;
           
                    StartDistance = (float)(sqrt((double)(Curr->Data->start.x-Point.x)*(double)(Curr->Data->start.x-Point.x)+
                                (double)(Curr->Data->start.y - Point.y)*(double)(Curr->Data->start.y - Point.y)));
                    EndDistance = (float)(sqrt((double)(Curr->Data->end.x-Point.x)*(double)(Curr->Data->end.x-Point.x)+
                                (double)(Curr->Data->end.y - Point.y)*(double)(Curr->Data->end.y - Point.y)));                                                        

                    // might as well pick the smaller one now
                    if (StartDistance < EndDistance)
                    {
                        if (StartDistance < SmallestDistance)
                        {
                            tReturn = Curr->Data->start;
                            SmallestDistance = StartDistance;
                        }
                    }
                    else
                    {
                        if (EndDistance < SmallestDistance)
                        {
                            tReturn = Curr->Data->end;
                            SmallestDistance = EndDistance;
                        }
                    }
                }
                
                Curr = Curr->Next;
            }
        }
    }

    RenderApeture = tReturn;

    return tReturn;       

}
/************************************************************************
* Function RenderDrawRectangle(CRect Rectangle, CDC &MemDC)
*
* PURPOSE
* To draw a rectangle by drawing four lines.  This is to make up for 
* the fact that CDC doesn't have a draw rect without filling it in.
* USAGE
* For the Render Function

*************************************************************************/
void UQuadTree::RenderDrawRectangle(CRect Rectangle, CDC &MemDC)
{
    MemDC.MoveTo(Rectangle.left, Rectangle.top);
    MemDC.LineTo(Rectangle.right, Rectangle.top); // top line
    MemDC.LineTo(Rectangle.right, Rectangle.bottom); // right line
    MemDC.LineTo(Rectangle.left, Rectangle.bottom); // bottom line
    MemDC.LineTo(Rectangle.left, Rectangle.top); // left line
}

/************************************************************************
* FileSaveMap(CString FileName)
*
* PURPOSE
* To open a file and then call the function that does all the work
* USAGE
* When the user tries to save a file
*************************************************************************/
void UQuadTree::FileSaveMap(CString FileName, CRect CurrView,BOOL AllLine)
{
    
    
    CFile NewFile;
    NewFile.Open(FileName,CFile::modeWrite|CFile::typeBinary|CFile::modeCreate ,NULL);
    FileSaveMap(NewFile, CurrView, AllLine);
    NewFile.Close();
}

/************************************************************************
* Function FileIsInTable(UQuadTree::LGroupPtr Table[], UQuadTree::LGroupPtr Key)
*
* PURPOSE
* To check if a Group pointer is already index, done by looking in an array
* USAGE
* by the save/load file functions
*************************************************************************/
int UQuadTree::FileIsInTable(UQuadTree::LGroupPtr Table[], UQuadTree::LGroupPtr Key)
{
    for (int ix = 0; ix < MAXGROUPS; ix++)
    {
        if (Table[ix] == NULL)
        {
            return -1;
        }
        else if (Table[ix] == Key)
        {
            return ix;
        }        
    }
    return -1;


}

/************************************************************************
* Function FileLongtoChar(long &toCopy, unsigned char *ptr)
*
* PURPOSE
* Copies information that is in a long to a byte array.
* USAGE
* by the save/load file functions
*************************************************************************/
void UQuadTree::FileLongtoChar(long &toCopy, unsigned char *&ptr)
{

    unsigned char *ptr1 = &(unsigned char &)(toCopy);
    for (int ix = 0; ix < 4; ix++)
    {
        *ptr = *ptr1;
        ptr++;
        ptr1++;
    }

}

/************************************************************************
* Function FileChartoLong(long &toRecieve, unsigned char *&ptr)
*
* PURPOSE
* Copies information that is in a byte array to a long
* USAGE
* by the save/load file functions
*************************************************************************/
void UQuadTree::FileChartoLong(long &toRecieve, unsigned char *&ptr)
{
    
    unsigned char *ptr1 = &(unsigned char &)(toRecieve);
    for (int ix = 0; ix < 4; ix++)
    {
        *ptr1 = *ptr;
        ptr++;
        ptr1++;
    }

}

/************************************************************************
* FileOpenMap(CString FileName)
*
* PURPOSE
* To open a file and then call the function that does all the work
* USAGE
* When the user tries to open a file
* returns the saved viewable rectange
*************************************************************************/
CRect UQuadTree::FileOpenMap(CString FileName)
{
           
    CFile NewFile;
    NewFile.Open(FileName,CFile::modeRead|CFile::typeBinary ,NULL);
    CRect CurrentView = FileOpenMap(NewFile); // call the function to do the work.
    NewFile.Close();

    return CurrentView;  

}

/************************************************************************
* Function _Construct()
*
* PURPOSE
* Initilizes the QuadTree
* USAGE
* Constructer, new file, etc.
*************************************************************************/
void UQuadTree::_Construct()
{
    DebugDeleteCount = 0;
    DebugNewCount = 0;
    HeadQuadPtr = NULL;
    BigObjectList = NULL;
    SelectedObjectPtr = NULL;
    RenderObjectListPtr = NULL;
    CopyPtr = NULL;

    // reset the drafting object
    DraftingFlushAll();

    // reset the apeture
    RenderApetureSize = 5;
    RenderApeture.x = -1;
    RenderApeture.y = -1;    

    // reset the stats.
    RenderingStats.RenderCycle = 0;
    RenderingStats.NRendered = 0;
    RenderingStats.XQuadStart = 0;
    RenderingStats.YQuadStart = 0;
    RenderingStats.XQuadEnd = 0;
    RenderingStats.YQuadEnd = 0;
    RenderingStats.NQuadRendered = 0;
    RenderingStats.doNotRender = false;
    RenderingStats.IsRendering = false;

    
    // get a fresh ID list
    GroupIDList.DestructIDList();
    GroupIDList.CreateIDList();

    IDList.DestructIDList();
    IDList.CreateIDList();

    BumpSensorIDList.DestructIDList();
    BumpSensorIDList.CreateIDList();

    IRSensorIDList.DestructIDList();
    IRSensorIDList.CreateIDList();

    InitializeQuadTree();



}

/************************************************************************
* Function _Destruct()
*
* PURPOSE
* Initilizes the QuadTree
* USAGE
* Destructer, new file, etc.
*************************************************************************/
void UQuadTree::_Destruct()
{

    DuplicateFlushCopyList(); // isn't needed anymore
    SelectDeleteList(); // this one will delete any objects selected.  Note, it has to be called first.
                    // it needs to be called because it deletes the selected list ctrl structer.
    DeleteQuadTree();  
    DeleteObjects();



}

/************************************************************************
* Function FileAddLinkstoArray
*
* PURPOSE
* Adds a group pointers links to a link array
* USAGE
* When constructing the group links during a file save.
*************************************************************************/
void UQuadTree::FileAddLinkstoArray(UQuadTree::GROUPSTRUCT *toAdd, UQuadTree::GROUPLIST *theArray[])
{
    // traverse the list upwards while adding link entrys
    long PrevID = toAdd->GroupID;
    
    while (toAdd->ParentPtr != NULL)
    {
        toAdd = toAdd->ParentPtr;
        // first check if it is in the list already
        GROUPLIST *tempo = theArray[toAdd->GroupID];
        while (tempo != NULL)
        {
            if (tempo->ID == PrevID)
                return;
            else
            {
                tempo=tempo->Next;
            }
        }

        
        if (theArray[toAdd->GroupID] == NULL)
        {
            theArray[toAdd->GroupID] = new GROUPLIST;
            theArray[toAdd->GroupID]->ID = PrevID;
            theArray[toAdd->GroupID]->Next = NULL;
        }
        else
        {

            GROUPLIST *temp = new GROUPLIST;
            temp->ID = PrevID;
            temp->Next = theArray[toAdd->GroupID];
            theArray[toAdd->GroupID] = temp;
        }
        PrevID = toAdd->GroupID;
    }

}


/************************************************************************
* Function DraftingAddLine(CPoint Point)
*
* PURPOSE
* This is the function that the outside world uses to draw a line
* USAGE
* By the draw class
*************************************************************************/
void UQuadTree::DraftingAddLine(CPoint Point)
{

    if (DraftingState.Line1 == false)
    {
        // first point of the line
        DraftingFlushAll(); // just in case

        LGroupPtr GroupPtr = AddLine(Point,Point);

        if (GroupPtr != NULL)
        {
            SelectAddtoList(GroupPtr->Next->Data);
            DraftingObject.theObject=GroupPtr->Next->Data;
            DraftingObject.WhatPoint = 1; // set the end point to be the one moved around            
            DraftingState.Line1 = true;
            DraftingObject.valid = true;
        }
        else
        {
            DraftingObject.valid = false;
        }  
    }
    else
    {
        // the draftingonmousemove handles the redrawing,
        // this just tells it to stop
        SelectRemovefromList(DraftingObject.theObject);
        DraftingFlushAll();

    }  

}

/************************************************************************
* Function DraftingFlushAll()
*
* PURPOSE
* This function clears all drafting commands
* USAGE
* Internal
*************************************************************************/
void UQuadTree::DraftingFlushAll()
{
    DraftingState.Arc1 = false;
    DraftingState.Arc2 = false;
    DraftingState.Line1 = false;
    DraftingState.Move1 = false;

    DraftingState.Bump1 = false;
    DraftingState.Bump2 = false;

    // clean up drafting object
    DraftingObject.theObject = NULL;
    DraftingObject.valid = false;
    DraftingObject.WhatPoint = 0;
    DraftingObject.isMoving = false;
    DraftingObject.changed = false;


}


/************************************************************************
* Function DraftingAddArc(CPoint Point)
*
* PURPOSE
* This is the function that the outside world uses to draw a arc
* USAGE
* By the draw class
* ALGORITHM
* First draws a line from the start point, to the start point, which is then
* moved just line the addline
* after the second click an arc is constructed instead.
*************************************************************************/
void UQuadTree::DraftingAddArc(CPoint Point)
{
    if (DraftingState.Arc1)
    {
        CPoint Start,End;

        Start = DraftingObject.theObject->start;
        End = DraftingObject.theObject->end;

        // nuke the old line, we want an arc now
        SelectRemovefromList(DraftingObject.theObject);
        // now totally delete it         
        DeleteGroup(DraftingObject.theObject->GroupPtr);

        // create the arc
        LGroupPtr GroupPtr = AddArc(Start,End,End);

        if (GroupPtr != NULL)
        {
            SelectAddtoList(GroupPtr->Next->Data);
            DraftingObject.theObject=GroupPtr->Next->Data;
            DraftingObject.WhatPoint = 2; // set the middle point to be the one moved around            
            DraftingState.Arc1 = false;
            DraftingState.Arc2 = true;
            DraftingObject.valid = true;
        }
        else
        {
            DraftingObject.valid = false;
        }  

        
    }
    else if (DraftingState.Arc2)
    {
        // the draftingonmousemove handles the redrawing,
        // this just tells it to stop
        SelectRemovefromList(DraftingObject.theObject);
        DraftingFlushAll();
    }
    else
    {        
        // first point of the line
        DraftingFlushAll(); // just in case

        LGroupPtr GroupPtr = AddLine(Point,Point);

        if (GroupPtr != NULL)
        {
            SelectAddtoList(GroupPtr->Next->Data);
            DraftingObject.theObject=GroupPtr->Next->Data;
            DraftingObject.WhatPoint = 1; // set the end point to be the one moved around            
            DraftingState.Arc1 = true;
            DraftingObject.valid = true;
        }
        else
        {
            DraftingObject.valid = false;
        }  

    }  

}

/************************************************************************
* Function DraftingMoveGroup(CPoint Point)
*
* PURPOSE
* This function is used to move a group of objects.
* USAGE
* By the draw class
* INPUT
* Point -> the dx and dy in which to move the object
*************************************************************************/
void UQuadTree::DraftingMoveGroup(CPoint Point)
{
    if (DraftingState.Move1)
    {
        // second point
        CPoint Delta;
        Delta.x = Point.x - DraftingState.PrevPos.x;
        Delta.y =  Point.y - DraftingState.PrevPos.y;
        DuplicateMoveGroup(Delta); 
        DraftingState.Move1 = false;
    }
    else
    {
        // first point
        // clear all
        DraftingFlushAll();
        DraftingState.PrevPos = Point;
        DraftingState.Move1 = true;
    }
   
}

/************************************************************************
* Function DuplicateTraverseList(UQuadTree::GROUPSTRUCT *OldList, UQuadTree::GROUPSTRUCT *NewList, UQuadTree::DUPLICATESTATE Command, CPoint Delta)
*
* PURPOSE
* This function is used to make a copy of a group, it has three options
* 1) To move the list, e.i create a new list with all the members offseted by Delta
* 2) To copy a list, create the objects in object form only, don't add them to the quadtree
* 3) To paste a list
* USAGE
* Internal, by the DuplicateList(UQuadTree::DUPLICATESTATE Command, CPoint Delta) function
* INPUT
* Command, the option, see above
* Delta, if the move option is on, this is the displacement in which to move it.
*************************************************************************/
void UQuadTree::DuplicateTraverseList(UQuadTree::GROUPSTRUCT *OldList, UQuadTree::GROUPSTRUCT *&NewList, enum DUPLICATESTATE Command, CPoint Delta)
{    

    BOOL DontAdd = false;
    // First create the new group pointer object
    LGroupPtr tGroupPtr;

    // it contains an object.
    if (OldList->Next != NULL)
    {      
        CPoint Start,Middle,End;

        // get/make the new points
        Start = OldList->Next->Data->start;
        End = OldList->Next->Data->end;
        Middle = OldList->Next->Data->middle;
        if ((Command == Move) || (Command == Paste))
        {
            Start.x +=Delta.x;
            Start.y +=Delta.y;
            End.x +=Delta.x;
            End.y +=Delta.y;
            Middle.x +=Delta.x;
            Middle.y +=Delta.y;            
        }

        // check if ALL the points are valid
        if ((OldList->Next->Data->objecttype == ARCLINE) || (OldList->Next->Data->objecttype == BUMPSENSOR))
        {
            if (!AddCheckifPointValid(Start) || !AddCheckifPointValid(End) || !AddCheckifPointValid(Middle))
            {
                Start = OldList->Next->Data->start;
                End = OldList->Next->Data->end;
                Middle = OldList->Next->Data->middle;
            }
        }
        else if ((OldList->Next->Data->objecttype == IRSENSOR) || (OldList->Next->Data->objecttype == BUMPSENSOR))
        {
            if (!AddCheckifPointValid(Middle))
            {
                Middle = OldList->Next->Data->middle;
            }
        }    
        else if ((OldList->Next->Data->objecttype == TRIANGLE3D))
        {
            if (!AddCheckifPointValid(Start) || !AddCheckifPointValid(End) || !AddCheckifPointValid(Middle))
            {
                Start = OldList->Next->Data->start;
                End = OldList->Next->Data->end;
                Middle = OldList->Next->Data->middle;
            }
        }
        else if (!AddCheckifPointValid(Start) || !AddCheckifPointValid(End))
        {
            Start = OldList->Next->Data->start;
            End = OldList->Next->Data->end;
        }       

        // create the new object
        if (OldList->Next->Data->objecttype == LINE) 
        {
        // create the new object
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddLine(Start,End);   
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddLine(Start,End);
            }

        }
        else if (OldList->Next->Data->objecttype == ARCLINE)
        {
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddArc(Start,Middle,End); 
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddArc(Start,Middle,End);
            }
        }      
        else if (OldList->Next->Data->objecttype == BUMPSENSOR)
        {
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddBumpSensor(OldList->Next->Data->start,OldList->Next->Data->end,Middle);
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddBumpSensor(OldList->Next->Data->start,OldList->Next->Data->end,Middle);
            }
        }
        else if (OldList->Next->Data->objecttype == IRSENSOR)
        {
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddIRSensor(Middle,OldList->Next->Data->start.x,OldList->Next->Data->start.y,OldList->Next->Data->end.x);
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddIRSensor(Middle,OldList->Next->Data->start.x,OldList->Next->Data->start.y,OldList->Next->Data->end.x);
            }
        }
        else if (OldList->Next->Data->objecttype == SONARSENSOR)
        {
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddSonarSensor(Middle);
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddSonarSensor(Middle);
            }
        }
        else if (OldList->Next->Data->objecttype == ROOF3D)
        {
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddRoof3D3(Start,End);
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddRoof3D2(Start,End);
            }
        }
        else if (OldList->Next->Data->objecttype == TRIANGLE3D)
        {
            if ((Command == Move) || (Command == Paste))
            {
                // Move the object, create it with the offset
                tGroupPtr = AddRoof3D2(Start,Middle,End);
            }
            else if (Command == Copy)
            {
                // create an object, but don't enter it into a list
                tGroupPtr = DuplicateAddRoof3D(Start,Middle,End);
            }
        }
    
        // special case if this is the is only one element being copied
        if (NewList->GroupID == -1)
        {                
           // GroupIDList.AddBackID(NewList->GroupID);
            delete NewList;
            NewList = tGroupPtr;  
            return; // there isn't anything else to do.
        }
        else
        {
              // add this group to the parent pointer.             
              tGroupPtr->ParentPtr = NewList;
        }
    }

    // need to create a group pointer for below
    else
    {
        if (NewList->GroupID == -1)
        {
            // this is the head ptr, which was created outside the recursive function
             // add this group to the parent pointer. 
            NewList->GroupType = OldList->GroupType;
            NewList->GroupID = GroupIDList.GetNewID();
            NewList->NumofObjects = OldList->NumofObjects;
            tGroupPtr = NewList;
        }
        else
        {
            tGroupPtr = new GROUPSTRUCT;

            // add this group to the parent pointer. 
            tGroupPtr->ParentPtr = NewList;
            tGroupPtr->Child = NULL;
            tGroupPtr->GroupType = OldList->GroupType;;
            tGroupPtr->Next = NULL;
            tGroupPtr->Sibling = NULL;
            tGroupPtr->GroupID = GroupIDList.GetNewID();
            tGroupPtr->NumofObjects = OldList->NumofObjects;
        }


    }  

    // Link the new group ptr to the main list.
    if (tGroupPtr->ParentPtr != NULL)
    {
        if (tGroupPtr->ParentPtr->Child == NULL)
        {
            tGroupPtr->ParentPtr->Child = tGroupPtr;
        
        }
        // nope, it must then be a sibling
        else
        {
            LGroupPtr tempo;
            tempo = tGroupPtr->ParentPtr->Child;
            // note the original sibling shouldn't be null but just in case
            if (tempo != NULL)
            {
                while (tempo->Sibling != NULL)
                {
                    tempo = tempo->Sibling;
                }
                tempo->Sibling = tGroupPtr;
            }            
        
        }
    }
    // it is the head pointer, make it so
    else
    {
        NewList = tGroupPtr;
    }

    // call the function recursivly
    if (OldList->Sibling != NULL)
    {        
        DuplicateTraverseList(OldList->Sibling,NewList,Command,Delta);
    }  
    if (OldList->Child != NULL)
    {   
        // for the recursive call, Newlist must be the most recent one.
        if (NewList->Child != NULL)
        {
            DuplicateTraverseList(OldList->Child,tGroupPtr,Command,Delta);           
        } 
        else // only happens on the head pointer
        {
            DuplicateTraverseList(OldList->Child,NewList,Command,Delta);    
        }        
    }

}   
        
/************************************************************************
* Function DuplicateMoveGroup(CPoint Delta)
*
* PURPOSE
* This function is used to move a group
* It does so by creating a new one that is offset, and then deleting the old one.
* USAGE
* by DraftingMoveGroup
* INPUT
* Point -> the dx and dy in which to move the object
*************************************************************************/
void UQuadTree::DuplicateMoveGroup(CPoint Delta)
{

    SelectPtr newSelectList,TraversalPtr;
    CPoint Start,Middle,End;

    TraversalPtr = SelectedObjectPtr;

    newSelectList = NULL;

    while (TraversalPtr != NULL)
    {
        LGroupPtr HeadPtr = new GROUPSTRUCT;
        HeadPtr->Child = NULL;
        HeadPtr->ParentPtr = NULL;
        HeadPtr->Sibling = NULL;
        HeadPtr->Next = NULL;
        HeadPtr->GroupID = -1;

        DuplicateTraverseList(TraversalPtr->data,HeadPtr,Move,Delta);

        SelectChangeSelectStatus(HeadPtr,true);
        
        SelectPtr temp = new SELECTSTRUCT;
        temp->data = HeadPtr;
        temp->Next = NULL;
        temp->Prev = NULL;

        if (newSelectList == NULL)
        {
            // insert in the front of the list
            newSelectList = temp;
        }
        else
        {
            SelectPtr Traversal = newSelectList;

            while (Traversal->Next != NULL)
            {
                Traversal = Traversal->Next;
            }
            Traversal->Next = temp;
            temp->Prev = Traversal;
        }     

        TraversalPtr = TraversalPtr->Next;
    }
    // delete the old group
    SelectDeleteAll();
    // link to the new one
    SelectedObjectPtr = newSelectList;
}

/************************************************************************
* Function GROUPSTRUCT* DuplicateAddLine(CPoint Start, CPoint End)
*
* PURPOSE
* This function creates a Line object which isn't added to any list 
* USAGE
* Internally by DuplicateTraverseList
*************************************************************************/
UQuadTree::GROUPSTRUCT* UQuadTree::DuplicateAddLine(CPoint Start, CPoint End)
{
        // create the group pointer
    LGroupPtr tGroupPtr = new GROUPSTRUCT;

    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL; // no children groups
    tGroupPtr->ParentPtr = NULL; // no parents group for now
    tGroupPtr->Sibling = NULL;
    tGroupPtr->Next = NULL; // just for initialization sake.
    tGroupPtr->GroupType = NonSeperable; // can't seperate the group
    tGroupPtr->NumofObjects = 1;

      // create the header
    ObjectPtr Header = new Object;
    Header->end = End;
    Header->start = Start;
    Header->middle.x = 0;
    Header->middle.y = 0;
    Header->GroupPtr = tGroupPtr;
    Header->objectID = IDList.GetNewID();
    Header->objecttype = LINE;
    Header->renderflag = 0;
    Header->objectColor = NEUTRALCOLOR;

    // note this is only a single link list, add the header to the front of it.
    ObjectListPtr tempo = new OBJECTLIST;
    tempo->Data = Header;
    tempo->Prev = NULL; // always for every node
    tempo->Next = tGroupPtr->Next; // insert into start of the group ptr.
    tGroupPtr->Next = tempo;

    return tGroupPtr;

}

/************************************************************************
* Function GROUPSTRUCT* DuplicateAddArc(CPoint Start, CPoint Middle, CPoint End)
*
* PURPOSE
* This function creates a ArcLine object which isn't added to any list 
* USAGE
* Internally by DuplicateTraverseList
*************************************************************************/
UQuadTree::GROUPSTRUCT* UQuadTree::DuplicateAddArc(CPoint Start, CPoint Middle, CPoint End)
{
    // create the group pointer
    LGroupPtr tGroupPtr = new GROUPSTRUCT;

    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL; // no children groups
    tGroupPtr->ParentPtr = NULL; // no parents group for now
    tGroupPtr->Sibling = NULL;
    tGroupPtr->Next = NULL; // just for initialization sake.
    tGroupPtr->GroupType = NonSeperable; // can't seperate the group
    tGroupPtr->NumofObjects = DefaultLinesinArc;

      // create the dummy header
    ObjectPtr Header = new Object;
    Header->end = End;
    Header->start = Start;
    Header->middle = Middle;
    Header->GroupPtr = tGroupPtr;
    Header->objectID = IDList.GetNewID();
    Header->objecttype = ARCLINE;
    Header->renderflag = 0;
    Header->objectColor = NEUTRALCOLOR;

    // note this is only a single link list, add the header to the front of it.
    ObjectListPtr tempo = new OBJECTLIST;
    tempo->Data = Header;
    tempo->Prev = NULL; // always for every node
    tempo->Next = tGroupPtr->Next; // insert into start of the group ptr.
    tGroupPtr->Next = tempo;

    return tGroupPtr;



}

/************************************************************************
* Function DuplicateCopyGroup(BOOL toCut)
*
* PURPOSE
* This function is used to copy/paste a group
* It copies the group selected into a new group that is pointed to with the copy pointer.
* USAGE
* by DraftingCopyGroup
* INPUT
* toCut, if it is a copy or cut operation
*************************************************************************/
void UQuadTree::DuplicateCopyGroup(BOOL toCut)
{
    // destroy the old copy list if it exists.
    DuplicateFlushCopyList();

    SelectPtr newSelectList,TraversalPtr;

    // dummy delta for function call.
    CPoint Delta;
    Delta.x = 0;
    Delta.y = 0;

    TraversalPtr = SelectedObjectPtr;

    newSelectList = NULL;

    while (TraversalPtr != NULL)
    {
        LGroupPtr HeadPtr = new GROUPSTRUCT;
        HeadPtr->Child = NULL;
        HeadPtr->ParentPtr = NULL;
        HeadPtr->Sibling = NULL;
        HeadPtr->Next = NULL;
        HeadPtr->GroupID = -1;

        DuplicateTraverseList(TraversalPtr->data,HeadPtr,Copy,Delta);

        SelectChangeSelectStatus(HeadPtr,true);
        
        SelectPtr temp = new SELECTSTRUCT;
        temp->data = HeadPtr;
        temp->Next = NULL;
        temp->Prev = NULL;

        if (newSelectList == NULL)
        {
            // insert in the front of the list
            newSelectList = temp;
        }
        else
        {
            SelectPtr Traversal = newSelectList;

            while (Traversal->Next != NULL)
            {
                Traversal = Traversal->Next;
            }
            Traversal->Next = temp;
            temp->Prev = Traversal;
        }     

        TraversalPtr = TraversalPtr->Next;
    }    
    // link to the new one
    CopyPtr = newSelectList;

    if (toCut)
    {
        // delete the selection group
        SelectDeleteAll();
    }
    else
    {
        // unselect the selected group
        SelectCancelList();
    }

}

/************************************************************************
* Function DuplicateFlushCopyList()
*
* PURPOSE
* Destroys the a copied group.
* USAGE
* by varouis Duplicate functions
************************************************************************/
void UQuadTree::DuplicateFlushCopyList()
{
    SelectPtr tempo;
    while (CopyPtr != NULL)
    {
        DuplicateDeleteGroup(CopyPtr->data);
        tempo = CopyPtr;
        CopyPtr = CopyPtr->Next;
        delete tempo;
        tempo = NULL;
    }
}

/************************************************************************
* Function DuplicateDeleteGroup(LGroupPtr GroupPtr)
*
* PURPOSE
* Used by the DuplicateFlushCopyList() to recursivly destroy a group made by the 
* DuplicateCopy functionality
************************************************************************/
void UQuadTree::DuplicateDeleteGroup(UQuadTree::GROUPSTRUCT *GroupPtr)
{
    // delete all of the children
    if (GroupPtr->Child != NULL)
    {
        DuplicateDeleteGroup(GroupPtr->Child);
    }
    if (GroupPtr->Sibling != NULL)
    {
        DuplicateDeleteGroup(GroupPtr->Sibling);
    }

    
    // There will only be one object in the group

    // delete the object, which is not contained in every group pointer.
    if (GroupPtr->Next != NULL)
    {
        if (GroupPtr->Next->Data != NULL)
        {
            IDList.AddBackID(GroupPtr->Next->Data->objectID);
            delete GroupPtr->Next->Data;
            GroupPtr->Next->Data= NULL;

            // delete the objectlist
            delete GroupPtr->Next;
        }
    }
       
    // kill the group ptr
    GroupIDList.AddBackID(GroupPtr->GroupID);
    delete GroupPtr;
    GroupPtr = NULL;

}

/************************************************************************
* Function DuplicatePasteGroup(CPoint Point)
*
* PURPOSE
* This function is used to copy/paste a group
* It takes the Copy Pointer information and adds it to the quadtree
* USAGE
* by DraftingPasteGroup
*************************************************************************/
void UQuadTree::DuplicatePasteGroup(CPoint Point)
{

    SelectPtr newSelectList,TraversalPtr;

    // dummy delta for function call.
    CPoint Delta;
    Delta.x = 300;
    Delta.y = 300;

    TraversalPtr = CopyPtr;

    newSelectList = NULL;

    while (TraversalPtr != NULL)
    {
        LGroupPtr HeadPtr = new GROUPSTRUCT;
        HeadPtr->Child = NULL;
        HeadPtr->ParentPtr = NULL;
        HeadPtr->Sibling = NULL;
        HeadPtr->Next = NULL;
        HeadPtr->GroupID = -1;

        DuplicateTraverseList(TraversalPtr->data,HeadPtr,Paste,Delta);

        SelectChangeSelectStatus(HeadPtr,true);
        
        SelectPtr temp = new SELECTSTRUCT;
        temp->data = HeadPtr;
        temp->Next = NULL;
        temp->Prev = NULL;

        if (newSelectList == NULL)
        {
            // insert in the front of the list
            newSelectList = temp;
        }
        else
        {
            SelectPtr Traversal = newSelectList;

            while (Traversal->Next != NULL)
            {
                Traversal = Traversal->Next;
            }
            Traversal->Next = temp;
            temp->Prev = Traversal;
        }     

        TraversalPtr = TraversalPtr->Next;
    }    

    SelectDeleteGroup();

    // link to the new one
    SelectedObjectPtr = newSelectList;
    // create one big group to make it easier to use
    SelectCreateGroup();

}

/************************************************************************
* Function DraftingCopyGroup()
*
* PURPOSE
* Just a wrapper, copies the selected group
* USAGE
* by the Draw class
*************************************************************************/
void UQuadTree::DraftingCopyGroup()
{
    DuplicateCopyGroup(false);

}

/************************************************************************
* Function DraftingPasteGroup(CPoint Point)
*
* PURPOSE
* Called by the draw class to paste a group.
* USAGE
* by the Draw class
*************************************************************************/
void UQuadTree::DraftingPasteGroup(CPoint Point)
{
    DuplicatePasteGroup(Point);

}

/************************************************************************
* Function DraftingCopyGroup()
*
* PURPOSE
* Called by the draw class to cut a group.
* USAGE
* by the Draw class
*************************************************************************/
void UQuadTree::DraftingCutGroup()
{
     DuplicateCopyGroup(true);

}


/************************************************************************
* Function DraftingGetStartPoint()
*
* PURPOSE
* Called by the draw class for polar snapping, to get the point of the last
* click
* USAGE
* by the Draw class
*************************************************************************/
CPoint UQuadTree::DraftingGetStartPoint()
{
    if (DraftingObject.valid && (DraftingObject.theObject != NULL))
    {
        // return the end point
        if (DraftingObject.WhatPoint == 1)
        {
            return DraftingObject.theObject->start;
        }
        else if (DraftingObject.WhatPoint == 2)
        {
            return DraftingObject.theObject->end;
        }
    }
    
    // none of the above, send the fail code
    CPoint tempo;
    tempo.x = -1;
    tempo.y = -1;
    return tempo;
}


/************************************************************************
* Function DrafingCancelCommand()
*
* PURPOSE
* Called by the base class when a command is canceled, delete the drafting
* object
* USAGE
* by the Draw or View  class
*************************************************************************/
void UQuadTree::DraftingCancelCommand()
{
    SelectCancelList();

    if (DraftingObject.valid && (DraftingObject.theObject != NULL))
         DeleteGroup(DraftingObject.theObject->GroupPtr);

    DraftingFlushAll();
    


}

/************************************************************************
* SelectCancelList()
*
* PURPOSE
* To delete the list, and unselect all of the object in the list.
*
* USAGE 
* By the DraftingCancelCommand
*
*************************************************************************/
void UQuadTree::SelectCancelList()
{
     SelectPtr next;

    next = SelectedObjectPtr;
    
    // nuke the list
    while (SelectedObjectPtr != NULL)
    {
        SelectChangeSelectStatus(SelectedObjectPtr->data,false);
        next = SelectedObjectPtr->Next;    
        delete SelectedObjectPtr;
        SelectedObjectPtr = NULL;
        SelectedObjectPtr = next;
    }
    

}

/************************************************************************
* DepthFindEndPoints(CPoint &Start, CPoint &End, int Tolerance)
*
* PURPOSE
* To traverse the selected group at see if there is one end and start point
* If there is return the start and end, and return true; else return false
* ALGORITHM
* This function looks for loops or two open points
* 1) get a list of all of the objects under the selected object list. 
* 2) Then it takes the start and end point out of the the first object. 
* 3) Then It searches for any points matching the end point.  If there is one
*    make a new end point
* 4) Do this for the start point tpoino
* 5) Either the points will loop meaning there won't be any unique points or there
*    will be two free points.  If this is the case and all of the objects have been looked at
*    (use the render flag) there is a loop
* USAGE 
* By the CreateDepth Algorithm
*
*************************************************************************/
BOOL UQuadTree::DepthFindEndPoints(CPoint &Start, CPoint &End, int Tolerance)
{
    SelectPtr Traverse = SelectedObjectPtr;

    ObjectListPtr AllObjects = NULL;

    // initilize them to not found
    Start.x = -1;
    End.x = -1;
    
    // generate an object list of all the objects selected, (Traverse the group pointers)
    while (Traverse != NULL)
    {
        DepthReturnPointList(Traverse->data,AllObjects);
        Traverse = Traverse->Next;
    }

    if (AllObjects == NULL)
        return false;

    // now that we have an object list, go through it looking for any unique points
    Start = AllObjects->Data->start;
    End = AllObjects->Data->end;

    ObjectPtr StartObject = AllObjects->Data;
    ObjectPtr EndObject = AllObjects->Data;

    // set the render flag to check if all objects are ran through in this test
    int RenderNumber = AllObjects->Data->renderflag+50;
    AllObjects->Data->renderflag = RenderNumber;

 

    // This loops until a point is found that does not continue the chain, or
    // a loop is found

    BOOL Found,Loop;

    Loop = false;
    Found = true;

    while (Found && !Loop)
    {
        Found = false;
        
        ObjectListPtr TranverseObjects = AllObjects;
        while (TranverseObjects != NULL)
        {
           
            if (Start == End)
            {
                //A loop is found
                Found = true;
                Loop = true;
                StartObject->renderflag = RenderNumber;
                TranverseObjects = NULL;
            }             
            // don't go in loops
            else if (TranverseObjects->Data->renderflag != RenderNumber)
            {
                if (Start == TranverseObjects->Data->start)
                {
                    Start = TranverseObjects->Data->end;
                    StartObject = TranverseObjects->Data;
                    StartObject->renderflag = RenderNumber;
                    TranverseObjects = NULL;
                    Found = true;
                }
                else if (Start == TranverseObjects->Data->end)
                {
                    Start = TranverseObjects->Data->start;
                    StartObject = TranverseObjects->Data;
                    StartObject->renderflag = RenderNumber;
                    TranverseObjects = NULL;
                    Found = true;
                }
            }
            // used as an exit condition so watch it.
            if (TranverseObjects != NULL)
            {
                TranverseObjects = TranverseObjects->Next;
            }
        }
    }

    // no loop found, lets do the same thing with the end point
    if (!Loop)
    {
        Found = true;
        while (Found)
        {
            Found = false;
        
            ObjectListPtr TranverseObjects = AllObjects;
            while (TranverseObjects != NULL)
            {
           
                
                // don't go in loops
                if (TranverseObjects->Data->renderflag != RenderNumber)
                {
                    if (End == TranverseObjects->Data->start)
                    {
                        End = TranverseObjects->Data->end;
                        EndObject = TranverseObjects->Data;
                        EndObject->renderflag = RenderNumber;
                        TranverseObjects = NULL;
                        Found = true;
                    }
                    else if (End == TranverseObjects->Data->end)
                    {
                        End = TranverseObjects->Data->start;
                        EndObject = TranverseObjects->Data;
                        EndObject->renderflag = RenderNumber;
                        TranverseObjects = NULL;
                        Found = true;
                    }
                }
                // used as an exit condition so watch it.
                if (TranverseObjects != NULL)
                {
                    TranverseObjects = TranverseObjects->Next;
                }
            }
        }
    }

    // While deleteing the list, check if there are any objects which haven't been looked at,
    // if so there is no loop

    BOOL tReturn = true;  

    // destory the created object list.
    while (AllObjects != NULL)
    {
        if (AllObjects->Data->renderflag != RenderNumber)
        {
            tReturn = false;
        }
        ObjectListPtr temp = AllObjects;
        AllObjects = AllObjects->Next;
        delete temp;
        temp = NULL;
    }

    return tReturn;



}

/************************************************************************
* DepthReturnPointList(LGroupPtr theGroup)
*
* PURPOSE
* To traverse a group list and return an objectlist with all of the objects in the group
* USAGE 
* By the DepthFindEndPoints internally
*
*************************************************************************/
void UQuadTree::DepthReturnPointList(UQuadTree::GROUPSTRUCT *GroupPtr, UQuadTree::OBJECTLIST *&ObjectList)
{
        // delete all of the children
    if (GroupPtr->Child != NULL)
    {
        DepthReturnPointList(GroupPtr->Child,ObjectList);
    }
    // delete all of its siblings
    if (GroupPtr->Sibling != NULL)
    {
        DepthReturnPointList(GroupPtr->Sibling,ObjectList);
    }   
  
    // does this group pointer cotain any information?
    if (GroupPtr->Next != NULL)
    {
    
        // create the new objectlist object
        ObjectListPtr temp = new OBJECTLIST;
        temp->Next = NULL;
        temp->Prev = NULL;
        temp->Data = GroupPtr->Next->Data;

        // link it to the object
        temp->Next = ObjectList;
        ObjectList = temp;
    }
  

}

/************************************************************************
* DraftingCreateDepth(int Depth, BOOL Reverse)
*
* PURPOSE
* To add depth to a chain of lines.
* USAGE 
* By the console, or draw
* NOTES
* This is a horibly long function, but there was no other way.  There are a lot of 
* things to do.
* ALGORITHM
* 1) Find the start and end points (call DepthFindEndPoints)
* 2) if it retuns true get the list of all objects selected
* 3) Find the first three points so a 3 point center points could be found, so the inside
* 4) or outside parameter could be used.  In I/O will always change the orientation but
*    often not the right way
* 5) Start up the chain, starting in the start point, to add the depth.   
*     a) the trick to transposing a line in the right direction, lies in knowing its,
*        quadrant and the prevuis quadrant.  Then a determination could be made, as to 
*        whether to +/- X/Y.  A lot of care has been put into initlizeing the PrevLine parameter
*        for the first line, which is used for all other lines.
* DOES IT WORK?
* 1) Some problems when the arc function itself doesn't draw correctliy
* 2) No support for arcs near end points or start points.
* NOTES
* 
*************************************************************************/
void UQuadTree::DraftingCreateDepth(int Depth, BOOL Reverse)
{
    CPoint Start,End;

    LGroupPtr GroupPtr,tempGP;

    // initialize the group pointer that groups all of the depth lines
    GroupPtr = new GROUPSTRUCT;
    GroupPtr->Child = NULL;
    GroupPtr->GroupID = GroupIDList.GetNewID();
    GroupPtr->GroupType = Seperable;
    GroupPtr->Next = NULL;
    GroupPtr->NumofObjects = 0;
    GroupPtr->ParentPtr = NULL;
    GroupPtr->Sibling = NULL;

    if (DepthFindEndPoints(Start,End,0))
    {
        // first get a list of all the points
        SelectPtr Traverse = SelectedObjectPtr;

        ObjectListPtr AllObjects = NULL;
    
        // generate an object list of all the objects selected, (Traverse the group pointers)
        while (Traverse != NULL)
        {
            DepthReturnPointList(Traverse->data,AllObjects);
            Traverse = Traverse->Next;
        }

        if (AllObjects == NULL)
            return;
       
        // need three points to find the starting orientation
        CPoint Point1,Point2,Point3;

        // here is the first
        Point1 = Start;

        ObjectListPtr TranverseObjects = AllObjects;

        ObjectPtr First,Second;

        // find the second
        while (TranverseObjects != NULL)
        {
            if (TranverseObjects->Data->start == Start)
            {
                Point2 = TranverseObjects->Data->end;
                First = TranverseObjects->Data;
                TranverseObjects = NULL;
            }
            else if (TranverseObjects->Data->end == Start)
            {
                Point2 = TranverseObjects->Data->start;
                First = TranverseObjects->Data;
                TranverseObjects = NULL;
            }
            if (TranverseObjects != NULL)
            {
                TranverseObjects = TranverseObjects->Next;
            }
        }

        TranverseObjects = AllObjects;
        // find the third
        while (TranverseObjects != NULL)
        {
            if (TranverseObjects->Data != First)
            {
                if ((TranverseObjects->Data->start == Point2) || (TranverseObjects->Data->start == Point1))
                {
                    Point3 = TranverseObjects->Data->end;
                    Second = TranverseObjects->Data;
                    TranverseObjects = NULL;
                }
                else if ((TranverseObjects->Data->end == Point2) || (TranverseObjects->Data->end == Point1))
                {
                    Point3 = TranverseObjects->Data->start;
                    Second = TranverseObjects->Data;
                    TranverseObjects = NULL;
                }
            }
            if (TranverseObjects                      != NULL)
            {
                TranverseObjects = TranverseObjects->Next;
            }
        }

        CPoint NewStart,NewEnd,NewMiddle,NewPrevMiddle;

        // find the starting orientation
        CPoint Center = LAUtils.GetInsidePoint(Point1,Point2,Point3);


        // First->Start should be equal to start, if not swap.
        if (!(Start == First->start))
        {
            CPoint tempo;
            tempo = First->start;
            First->start = First->end;
            First->end = tempo;
        }

        // get the first transposed line, this is the basis for all of the other lines, wether they are inside or outside.
        LAUtils.TransposeLine(First->start,First->end,NewStart,NewEnd,Center,!Reverse,Depth);
        
        ULinearAlgebra::PREVLINE PrevLine;
        // set the inside/outside parameters.
        // the Reverse is there becuase the >= are different from inside or outside,
        // on 90degree lines. (I don't know why, it just works)
      

      //  if (!Reverse)
       // {
            // changed to > from >= on 02-05-08.  Didn't work the old way
             if (NewStart.x >  First->start.x)
            {
                PrevLine.x = 1;
            }
            else
            {
                PrevLine.x = -1;
            }
            if (NewStart.y >  First->start.y)
            {
                PrevLine.y = -1;
            }
            else
            {
                PrevLine.y = 1;
            } 
            
            // Here is how the next part works.  This algorithm doesn't have enough information
            // on 90 degree lines. so it has to look at the next point to see which way is should go
            if (NewStart.x == First->start.x)
            {
                // it is a horizontal line                
                if (First->start.y < Point3.y)
                {
                    if (PrevLine.y > 0)
                        PrevLine.x = -1;
                    else
                        PrevLine.x = 1;
                }
                else
                {
                    if (PrevLine.y < 0)
                        PrevLine.x = 1;
                    else
                        PrevLine.x = -1;                
                }
            }
            if (NewStart.y == First->start.y)
            {
                   //It is a vertical line                     
                    if (First->start.x >  Point3.x)
                    {
                        if (PrevLine.x > 0)
                            PrevLine.y = -1;
                        else
                            PrevLine.y = 1;
                    }
                    else
                    {
                        if (PrevLine.x > 0)
                            PrevLine.y = -1;
                        else
                            PrevLine.y = 1;
                    }
   
            }
            


        // find the intial quadrants for reference for the next transpose.
        double Angle = LAUtils.GetAngle(First->end, First->start);
        if (Angle < 90)
            PrevLine.Quad = 1;
        else if (Angle < 180)
            PrevLine.Quad = 2;
        else if (Angle < 270)
            PrevLine.Quad = 3;
        else                    
            PrevLine.Quad = 4; 


        // start looking at the chain
        int RenderNumber = AllObjects->Data->renderflag + 50;

        // start off by getting the first line, and point        
        ULinearAlgebra::Matrix2X2 Prevline = LAUtils.PointstoLine(NewStart,NewEnd);        
        ULinearAlgebra::Matrix2X2 CurrLine;

        CPoint Prev, Curr;
        if (Start == First->start) 
        {
            Prev = NewStart;
            PrevLine.PrevStart = First->start;
            PrevLine.PrevEnd = First->end;
        }
        else if (Start == First->end)
        {
             Prev = NewEnd;
             // reverse 
             CPoint tempo;
             tempo = NewStart;
             NewStart = NewEnd;
             NewEnd = tempo;
             PrevLine.PrevStart = First->end;
             PrevLine.PrevEnd = First->start;
        }

        // extra variables in case of a loop
        ULinearAlgebra::Matrix2X2 LoopLine;
        BOOL isLoop,IgnoreFirst;
        CPoint LoopStart,LoopStart2;

        // to do the 3D part at the end
        ObjectPtr LoopStartObject = First;

        // check against the loop
        if (Start != End)
        {
            isLoop = false;
            IgnoreFirst = false;

            if (Start == First->start)
            {
                tempGP = AddLine(Start,NewStart);
            }
            else
            {
                tempGP = AddLine(Start,NewEnd);
            }

            tempGP->ParentPtr = GroupPtr;
            tempGP->Sibling = GroupPtr->Child;
            GroupPtr->Child = tempGP;
            GroupPtr->NumofObjects++;
        }
        else
        {        
            // There is a loop.  Don't draw the extra line above, and store the old line,
            // for when it is intersected with the last one
            LoopLine = LAUtils.PointstoLine(NewStart,NewEnd);
            Prevline = LoopLine;
            isLoop = true;
            IgnoreFirst = true;
            LoopStart = NewStart;
            First->renderflag = RenderNumber;

            Prev = NewEnd;
        }

        // not interested in the first line, goto the second one.
        if (Start == First->end)
            Start = First->start;
        else
            Start = First->end;
        First->renderflag = RenderNumber;

        
        BOOL Found,Loop;

        ObjectPtr StartObject,OldObject;

        ULinearAlgebra::Circle PrevCircle;

        StartObject = OldObject = First;
        
        BOOL PrevArc = false;
        Loop = false;
        Found = true;
        // should be changed if I ever add support when an arc starts the chain
        NewMiddle.x = 0;
        NewMiddle.y = 0;

        // run through the loop adding the depth
        while (Found && !Loop)
        {
            Found = false;
        
            TranverseObjects = AllObjects;
            while (TranverseObjects != NULL)
            {    
                // don't go in reverse
                if (TranverseObjects->Data->renderflag != RenderNumber)
                {
                    // is this object the next to extend?
                    if ((Start == TranverseObjects->Data->start) || (Start == TranverseObjects->Data->end))
                    {                
                        if (Start == TranverseObjects->Data->start)
                            Start = TranverseObjects->Data->end;
                        else
                            Start = TranverseObjects->Data->start;

                        OldObject = StartObject;
                        StartObject = TranverseObjects->Data;
                        StartObject->renderflag = RenderNumber; 
                        Found = true;      
                        NewPrevMiddle = NewMiddle;
                        LAUtils.TransposeLine(TranverseObjects->Data->start,TranverseObjects->Data->end,TranverseObjects->Data->middle,NewStart,NewEnd,NewMiddle,PrevLine,Depth);                                                                                               
                        CurrLine = LAUtils.PointstoLine(NewStart,NewEnd);

                        if (TranverseObjects->Data->objecttype == ARCLINE)
                        {
                            float NEWD = LAUtils.GetDistance(NewStart,TranverseObjects->Data->middle) +
                                LAUtils.GetDistance(NewEnd,TranverseObjects->Data->middle);
                            float OLDD = LAUtils.GetDistance(TranverseObjects->Data->start,TranverseObjects->Data->middle) +
                                LAUtils.GetDistance(TranverseObjects->Data->end,TranverseObjects->Data->middle);

                            int RInc;
                            if (NEWD > OLDD)
                            {   
                                // radius -5;
                                RInc = -Depth;
                            }
                            else
                            {
                                RInc = Depth;
                            }    
                           
                            PrevCircle = LAUtils.GetCircle(TranverseObjects->Data->start,TranverseObjects->Data->middle,TranverseObjects->Data->end,RInc,NewMiddle);                                             
                            Curr = LAUtils.FindIntersection(Prevline,PrevCircle,NewEnd);
                            PrevArc = true;

                            // have to set the PrevLine stuff
                            if (Start == TranverseObjects->Data->start)
                            {
                                PrevLine.PrevStart = TranverseObjects->Data->start;
                                PrevLine.PrevEnd = TranverseObjects->Data->end;
                            }
                            else
                            {
                                PrevLine.PrevStart = TranverseObjects->Data->end;
                                PrevLine.PrevEnd = TranverseObjects->Data->start;
                            }

                        }
                        else if (PrevArc)
                        {
                            PrevArc = false;
                            Curr = LAUtils.FindIntersection(CurrLine,PrevCircle,NewEnd);
                        }
                        else
                        {   
                            Curr = LAUtils.FindIntersection(CurrLine,Prevline);
                        }
                        if (!IgnoreFirst)
                        {                        
                            if (OldObject->objecttype == LINE)
                            {
                                tempGP = AddLine(Prev,Curr);  
                                // add the 3D roof stuff
                                AddRoof3D(Prev,Curr,OldObject->end);
                                if (!isLoop)
                                    AddRoof3D(Prev,OldObject->start,OldObject->end);
                                else
                                    AddRoof3D(Curr,OldObject->start,OldObject->end);
                                if (tempGP != NULL)
                                {                                   
                                    tempGP->ParentPtr = GroupPtr;
                                    tempGP->Sibling = GroupPtr->Child;
                                    GroupPtr->Child = tempGP;
                                    GroupPtr->NumofObjects++;
                                }
                            }
                            else if (OldObject->objecttype == ARCLINE)
                            {      
                                tempGP = AddArc(Prev,NewPrevMiddle,Curr);                                 
                                if (tempGP != NULL)
                                {
                                    tempGP->ParentPtr = GroupPtr;
                                    tempGP->Sibling = GroupPtr->Child;
                                    GroupPtr->Child = tempGP;
                                    GroupPtr->NumofObjects++;
                                }

                            }
                        }
                        else
                        {
                            LoopStart2 = Curr;
                            IgnoreFirst = false;
                        } 
                        Prev = Curr;
                        Prevline = CurrLine;
                        TranverseObjects = NULL;
                    }
                }
                // used as an exit condition so watch it.
                if (TranverseObjects != NULL)
                {
                    TranverseObjects = TranverseObjects->Next;
                }
            }
        }

        // add the closing line, or in the case of a loop add the first and last line
        if (!isLoop)
        {
            // I really don't know why I have to do this, but obvoisly, the closer one
            // to the end is the one that is the Ends, trasposed point.
            CPoint TheEnd;
            float D1 = LAUtils.GetDistance(NewEnd,End);
            float D2 = LAUtils.GetDistance(NewStart,End);
            if (D1 < D2)
            {
                TheEnd = NewEnd;
            }
            else
            {
                TheEnd = NewStart;
            }

            // draw the last line.
            tempGP = AddLine(TheEnd,Prev);
            // add the 3D roof stuff
            AddRoof3D(TheEnd,End,StartObject->start);
            AddRoof3D(TheEnd,Prev,StartObject->start);
            if (tempGP != NULL)
            {
                tempGP->ParentPtr = GroupPtr;
                tempGP->Sibling = GroupPtr->Child;
                GroupPtr->Child = tempGP;
                GroupPtr->NumofObjects++;
            }
            
            // draw the line from the end to the end of the depth line
            tempGP =  AddLine(End,TheEnd);
            if (tempGP != NULL)
            {
                tempGP->ParentPtr = GroupPtr;
                tempGP->Sibling = GroupPtr->Child;
                GroupPtr->Child = tempGP;
                GroupPtr->NumofObjects++;
            }
        }
        else
        {
            // now that we now all of the lines, draw the first and end line.
            Curr = LAUtils.FindIntersection(LoopLine,Prevline);
            tempGP = AddLine(Prev,Curr);                        
            // add the 3D roof stuff
            AddRoof3D(Prev,Curr,StartObject->end);
            AddRoof3D(Curr,StartObject->end,StartObject->start);       
            if (tempGP != NULL)
            {
                tempGP->ParentPtr = GroupPtr;
                tempGP->Sibling = GroupPtr->Child;
                GroupPtr->Child = tempGP;
                GroupPtr->NumofObjects++;
            }              
            tempGP = AddLine(Curr,LoopStart2);    
            // add the 3D roof stuff
            AddRoof3D(LoopStart2,Curr,LoopStartObject->end);
            AddRoof3D(Curr,LoopStartObject->end,LoopStartObject->start);
            if (tempGP != NULL)
            {
                tempGP->ParentPtr = GroupPtr;
                tempGP->Sibling = GroupPtr->Child;
                GroupPtr->Child = tempGP;
                GroupPtr->NumofObjects++;
            } 


        }

        // destory the created object list.
        while (AllObjects != NULL)
        {                   
            ObjectListPtr temp = AllObjects;
            AllObjects = AllObjects->Next;
            delete temp;
        }
        
    }
}


/************************************************************************
* SelectArea(CRect Area)
*
* PURPOSE
* To select all objects in and area as specified by area
* USAGE 
* By the draw function
* INPUTS
* Area, the area in which to use, in real coordinates
* AllIn, if true the object has to be completely incompassed by the Area.
* NOTE
* Reused a lot of the rendering functions
*
*************************************************************************/
void UQuadTree::SelectArea(CRect Area, BOOL AllIn)
{

    if (!RenderingStats.IsRendering)
    {
        RenderingStats.doNotRender = true;

         RenderCreateList(Area);

         ObjectPtr object = NULL;

        // extract objects out of the list and draw them
        while (RenderEnumObjects(object))
        {
            // have to rectify it
            CPoint BorderTopLeft;
            CPoint BorderBottomRight;

            // setup of bound of the intersection
            if (object->start.x > object->end.x)
            {
                BorderTopLeft.x = object->end.x;
                BorderBottomRight.x = object->start.x;
            }
            else
            {
                BorderTopLeft.x = object->start.x;
                BorderBottomRight.x = object->end.x;
            }

            if (object->start.y > object->end.y)
            {
                BorderTopLeft.y = object->end.y;
                BorderBottomRight.y = object->start.y;
            }
            else
            {
                BorderTopLeft.y = object->start.y;
                BorderBottomRight.y = object->end.y;
            }

            // doesn't really matter what these numbers are, it just centers the point around the display point
            if ((object->objecttype == BUMPSENSOR) || (object->objecttype == IRSENSOR) || (object->objecttype == SONARSENSOR))
            {
                BorderTopLeft.y = object->middle.y - 10;
                BorderBottomRight.y = object->middle.y + 10;
                BorderTopLeft.x = object->middle.x - 5;
                BorderBottomRight.x = object->middle.x + 5;
            }            

             if ((BorderTopLeft.x > Area.left) && (BorderTopLeft.y > Area.top)
                 && (BorderBottomRight.x < Area.right) && (BorderBottomRight.y < Area.bottom))
                SelectAddtoList(object);
             else if (!AllIn)
             {
                 // because the rendercreatelist, looks at quadrants, not exact coordinates
                 // an extra check is needed.  Only implemented for lines, to much work for the 
                 // benifit to do it with arcs
                 if (object->objecttype == LINE || object->objecttype == ROOF3D || object->objecttype == TRIANGLE3D) 
                 {           
                     
                     if (LAUtils.CheckifLineGoesinRect(object->start,object->end,Area))
                         SelectAddtoList(object);
                 }
                 else if ((object->objecttype == BUMPSENSOR) || (object->objecttype == IRSENSOR) || (object->objecttype == SONARSENSOR))
                 {
                     if (LAUtils.InRect(object->middle,Area))
                        SelectAddtoList(object);
                 }
                 else
                     SelectAddtoList(object);

             }

        }

        RenderingStats.doNotRender=false;
    }


}
/************************************************************************
* Function DuplicateTraverseList(UQuadTree::GROUPSTRUCT *OldList, UQuadTree::GROUPSTRUCT *&NewList, CPoint RotateCenter, int Angle)
*
* PURPOSE
* This function is used to make a copy of a group, but instead of a delta, an angle
* and center point is specified.
* USAGE
* By the rotate command
* INPUT
* Angle, the rotation angle
* Center, the center point at which to rotate it.
*************************************************************************/
void UQuadTree::DuplicateTraverseList(UQuadTree::GROUPSTRUCT *OldList, UQuadTree::GROUPSTRUCT *&NewList, CPoint RotateCenter, int Angle)
{
    // First create the new group pointer object
    LGroupPtr tGroupPtr;

    BOOL DontAdd = false;

    // it contains an object.
    if (OldList->Next != NULL)
    {      
        CPoint Start,Middle,End;

        // preform the rotation
        Start = LAUtils.RotatePoint(OldList->Next->Data->start,RotateCenter,Angle);
        End = LAUtils.RotatePoint(OldList->Next->Data->end,RotateCenter,Angle);
        Middle = LAUtils.RotatePoint(OldList->Next->Data->middle,RotateCenter,Angle);       

        // check if ALL the points are valid
        if ((OldList->Next->Data->objecttype == ARCLINE) || (OldList->Next->Data->objecttype == TRIANGLE3D))
        {
            if (!AddCheckifPointValid(Start) || !AddCheckifPointValid(End) || !AddCheckifPointValid(Middle))
            {
                Start = OldList->Next->Data->start;
                End = OldList->Next->Data->end;
                Middle = OldList->Next->Data->middle;
            }
        }
        else if ((OldList->Next->Data->objecttype == IRSENSOR) || (OldList->Next->Data->objecttype == BUMPSENSOR))
        {
             if (!AddCheckifPointValid(Middle))
             {
                  Middle = OldList->Next->Data->middle;
            }
        }
        else if (!AddCheckifPointValid(Start) || !AddCheckifPointValid(End))
        {
            Start = OldList->Next->Data->start;
            End = OldList->Next->Data->end;
        }       

        // create the new object
        if (OldList->Next->Data->objecttype == LINE) 
        {
            // create the new object
            tGroupPtr = AddLine(Start,End);   
           

        }
        else if (OldList->Next->Data->objecttype == ARCLINE)
        {        
            // create the new object
            tGroupPtr = AddArc(Start,Middle,End); 
           
        }       
        else if (OldList->Next->Data->objecttype == BUMPSENSOR)
        {
            tGroupPtr = AddBumpSensor(OldList->Next->Data->start,OldList->Next->Data->end,Middle);
        }
        else if (OldList->Next->Data->objecttype == IRSENSOR)
        {
            tGroupPtr = AddIRSensor(Middle,OldList->Next->Data->start.x,OldList->Next->Data->start.y,OldList->Next->Data->end.x+Angle);
        }
        else if (OldList->Next->Data->objecttype == SONARSENSOR)
        {
            tGroupPtr = AddSonarSensor(Middle);
        }
        else if (OldList->Next->Data->objecttype == ROOF3D)
        {
            tGroupPtr = AddRoof3D3(Start,End);
        }
        else if (OldList->Next->Data->objecttype == TRIANGLE3D)
        {
            tGroupPtr = AddRoof3D2(Start,Middle,End);
        }    

            // special case if this is the is only one element being copied
            if (NewList->GroupID == -1)
            {                
                GroupIDList.AddBackID(NewList->GroupID);
                delete NewList;
                NewList = tGroupPtr;  
                return; // there isn't anything else to do.
            }
            else
            {
                  // add this group to the parent pointer. 
                  tGroupPtr->ParentPtr = NewList;
            }
        }

    // need to create a group pointer for below
    else
    {        
        if (NewList->GroupID == -1)
        {
            // this is the head ptr, which was created outside the recursive function
             // add this group to the parent pointer. 
            NewList->GroupType = OldList->GroupType;;
            NewList->GroupID = GroupIDList.GetNewID();
            NewList->NumofObjects = OldList->NumofObjects;
            tGroupPtr = NewList;
        }
        else
        {
            tGroupPtr = new GROUPSTRUCT;

            // add this group to the parent pointer. 
            tGroupPtr->ParentPtr = NewList;
            tGroupPtr->Child = NULL;
            tGroupPtr->GroupType = OldList->GroupType;;
            tGroupPtr->Next = NULL;
            tGroupPtr->Sibling = NULL;
            tGroupPtr->GroupID = GroupIDList.GetNewID();
            tGroupPtr->NumofObjects = OldList->NumofObjects;
        }        
    }

    // Link the new group ptr to the main list.
    if (tGroupPtr->ParentPtr != NULL)
    {
        if (tGroupPtr->ParentPtr->Child == NULL)
        {
            tGroupPtr->ParentPtr->Child = tGroupPtr;
        
        }
        // nope, it must then be a sibling
        else
        {
            LGroupPtr tempo;
            tempo = tGroupPtr->ParentPtr->Child;
            // note the original sibling shouldn't be null but just in case
            if (tempo != NULL)
            {
                while (tempo->Sibling != NULL)
                {
                    tempo = tempo->Sibling;
                }
                tempo->Sibling = tGroupPtr;
            }            
        
        }
    }
    // it is the head pointer, make it so
    else
    {
        NewList = tGroupPtr;
    }
    
    // call the function recursivly
    if (OldList->Sibling != NULL)
    {        
        DuplicateTraverseList(OldList->Sibling,NewList,RotateCenter,Angle);
    }  
    if (OldList->Child != NULL)
    {        
        // for the recursive call, Newlist must be the most recent one.
        if (NewList->Child != NULL)
        {
            DuplicateTraverseList(OldList->Child,tGroupPtr,RotateCenter,Angle);           
        } 
        else // only happens on the head pointer
        {
            DuplicateTraverseList(OldList->Child,NewList,RotateCenter,Angle);    
        }
        
    }

}

/************************************************************************
* Function :DraftingRotate(CPoint CenterPoint, int Angle)
*
* PURPOSE
* This is the function that the draw class calls to rotate an object about a center point
* USAGE
* By the draw class
* INPUT
* Angle, the rotation angle
* CenterPoint, the center point at which to rotate it.
*************************************************************************/
void UQuadTree::DraftingRotate(CPoint CenterPoint, int Angle)
{
    SelectPtr newSelectList,TraversalPtr;
    CPoint Start,Middle,End;

    TraversalPtr = SelectedObjectPtr;

    newSelectList = NULL;

    while (TraversalPtr != NULL)
    {
        LGroupPtr HeadPtr = new GROUPSTRUCT;
        HeadPtr->Child = NULL;
        HeadPtr->ParentPtr = NULL;
        HeadPtr->Sibling = NULL;
        HeadPtr->Next = NULL;
        HeadPtr->GroupID = -1;

        DuplicateTraverseList(TraversalPtr->data,HeadPtr,CenterPoint,Angle);

        SelectChangeSelectStatus(HeadPtr,true);
        
        SelectPtr temp = new SELECTSTRUCT;
        temp->data = HeadPtr;
        temp->Next = NULL;
        temp->Prev = NULL;

        if (newSelectList == NULL)
        {
            // insert in the front of the list
            newSelectList = temp;
        }
        else
        {
            SelectPtr Traversal = newSelectList;

            while (Traversal->Next != NULL)
            {
                Traversal = Traversal->Next;
            }
            Traversal->Next = temp;
            temp->Prev = Traversal;
        }     

        TraversalPtr = TraversalPtr->Next;
    }
    // delete the old group
    SelectDeleteAll();
    // link to the new one
    SelectedObjectPtr = newSelectList;

}

/************************************************************************
* Function DraftingAddBumpSensor(CPoint thePoint)
*
* PURPOSE
* This is the function that the outside world uses to place a bump sensor
* USAGE
* By the draw class
*************************************************************************/
void UQuadTree::DraftingAddBumpSensor(CPoint thePoint)
{
    if (DraftingState.Bump1)
    {
        DraftingState.Bump1 = false;
        DraftingState.Bump2 = true;

        DraftingState.BumpEnd = thePoint;

    }
    else if (DraftingState.Bump2)
    {
        DraftingFlushAll(); // just in case
        AddBumpSensor(DraftingState.BumpStart,DraftingState.BumpEnd,thePoint);
    }
    else
    {
         // start of the bump sensor
        DraftingFlushAll(); // just in case

        DraftingState.Bump1 = true;
        DraftingObject.valid = true;

        DraftingState.BumpStart = thePoint;

    }

}

/************************************************************************
* Function BOOL AddBumpSensor(CPoint Start, CPoint End, CPoint Display)
*
* PURPOSE
* To add a bump sensor to the quadtree
* INPUTS
* The start, end point and display point of the bump sensor
* RESULT
* A Bump Sensor is added in the quadtree
*
*************************************************************************/
UQuadTree::GROUPSTRUCT*  UQuadTree::AddBumpSensor(CPoint Start, CPoint End, CPoint Display)
{
     // do some error checking
    if (!AddCheckifPointValid(Start))
        return NULL;
    if (!AddCheckifPointValid(End))
        return NULL;
    if (!AddCheckifPointValid(Display))
        return NULL;

    ObjectPtr temp;
    TreePtr tLevelTreePtr;
    temp = new Object;    

    // copy all the information to a new pointer.
    temp->end = End;
    temp->middle = Display;
    temp->objectID = BumpSensorIDList.GetNewID();
    temp->objecttype = BUMPSENSOR;
    temp->renderflag = 0;
    temp->start = Start;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    // add the object to the root node
    AddToObjectList(HeadQuadPtr,temp);

    // only need to add it to 1 treeptr per level
    tLevelTreePtr = HeadQuadPtr;    

    Display.x = Display.x/100+1;
    Display.y = Display.y/100+1;

    // recursivly go down the quadtree adding the sensor to varoius quadrants
    int Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,Display);
    while (Quadrant != -1)
    {
        tLevelTreePtr = tLevelTreePtr->NextQuad[Quadrant-1];
        AddToObjectList(tLevelTreePtr,temp);
        Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,Display);
    }

    // create the group pointer for the object

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}

/************************************************************************
* Function RenderBumpSensor(CDC &MemDC, float XScale, float YScale, int XTransform, int YTransform, CPoint Center, int color, BOOL isVertica)
*
* PURPOSE
* Since the bump sensor isn't a primitive the purpose it to draw a bump sensor
* INPUTS
* The Drawing context, the scaleing and translation stuff, and the center point
* RESULT
* A Bump Sensor is drawn
*************************************************************************/
void UQuadTree::RenderBumpSensor(CDC &MemDC, float XScale, float YScale, int XTransform, int YTransform, CPoint Center, int color, BOOL isVertical)
{
    // get the center point (screen coordinates) of which to render
     int XReference = (int)((Center.x-XTransform)*XScale);
     int YReference = (int)((Center.y-YTransform)*YScale);

     CPoint RealCenter;
     RealCenter.x = XReference;
     RealCenter.y = YReference;

     float Scale = SensorRenderingScale/0.5f; // to adjust the size
     RenderingStats.OldBumperScaleX = XScale = XScale/Scale;
     RenderingStats.OldBumperScaleY = YScale = YScale/Scale;
     float CircleRadius = 1;

     CBrush *OldBrush;
    
     CRect Border;
     if (isVertical)
     {

          // create the outline

         Border.top = YReference - (long)(YScale*10);
         Border.bottom = YReference + (long)(YScale*10);
         Border.left = XReference - (long)(XScale*5);
         Border.right = XReference + (long)(XScale*5);     
         // change the scale for selection
         RenderingStats.OldBumperScaleX =  RenderingStats.OldBumperScaleX/2;
         RenderingStats.OldBumperScaleY = RenderingStats.OldBumperScaleY*2; 
     }
     else
     {
         // create the outline
         Border.top = YReference - (long)(YScale*5);
         Border.bottom = YReference + (long)(YScale*5);
         Border.left = XReference - (long)(XScale*10);
         Border.right = XReference + (long)(XScale*10);
     }

      MemDC.Rectangle(&Border);

     // get a color brush to fill in the circles
     OldBrush = MemDC.SelectObject(&ColorBrush[color]);

     // create the switch look.
     // first to the left

     CPoint Point;
     Point.x = XReference - (long)(XScale*9);
     Point.y = YReference + (long)(YScale*2);
     if (isVertical)
         Point = LAUtils.RotatePoint(Point,RealCenter,90);
     MemDC.MoveTo(Point);

     Point.x = XReference - (long)(XScale*3);
     Point.y = YReference + (long)(YScale*2);
    if (isVertical)
         Point = LAUtils.RotatePoint(Point,RealCenter,90);
     MemDC.Ellipse(Point.x-(long)(CircleRadius*XScale),Point.y-(long)(CircleRadius*YScale),Point.x+(long)(CircleRadius*XScale),Point.y+(long)(CircleRadius*YScale));
     MemDC.LineTo(Point);

     Point.x = XReference + (long)(XScale*2);
     Point.y = YReference - (long)(YScale*3);
     if (isVertical)
         Point = LAUtils.RotatePoint(Point,RealCenter,90);
     MemDC.LineTo(Point);

     Point.x = XReference + (long)(XScale*3);
     Point.y = YReference + (long)(YScale*2);
     if (isVertical)
         Point = LAUtils.RotatePoint(Point,RealCenter,90);
     MemDC.Ellipse(Point.x-(long)(CircleRadius*XScale),Point.y-(long)(CircleRadius*YScale),Point.x+(long)(CircleRadius*XScale),Point.y+(long)(CircleRadius*YScale));
     MemDC.MoveTo(Point);

     Point.x = XReference + (long)(XScale*9);
     Point.y = YReference + (long)(YScale*2);
     if (isVertical)
         Point = LAUtils.RotatePoint(Point,RealCenter,90);
     MemDC.LineTo(Point);    


     MemDC.SelectObject(OldBrush);


     /*char tempo[30];
     sprintf(tempo,"BS");
     MemDC.TextOut(XReference,YReference,tempo);*/


}

/************************************************************************
* Function RenderIRSensor(CDC &MemDC, float XScale, float YScale, int XTransform, int YTransform, CPoint Center, int color, BOOL isVertica)
*
* PURPOSE
* Since the bump sensor isn't a primitive the purpose it to draw a bump sensor
* INPUTS
* The Drawing context, the scaleing and translation stuff, and the center point
* RESULT
* A IR Sensor is drawn
* Sensors are normally 5x2 cms in real life.
*************************************************************************/
void UQuadTree::RenderIRSensor(CDC &MemDC, float XScale, float YScale, int XTransform, int YTransform, CPoint Center, long Angle, int color)
{
    // get the center point (screen coordinates) of which to render
     int XReference = (int)((Center.x-XTransform)*XScale);
     int YReference = (int)((Center.y-YTransform)*YScale);

     Angle += 90;//?

     CPoint RealCenter;
     RealCenter.x = XReference;
     RealCenter.y = YReference;

     float Scale = SensorRenderingScale/(float)3.0; // to adjust the size to display size
     RenderingStats.OldBumperScaleX = XScale = XScale/Scale;
     RenderingStats.OldBumperScaleY = YScale = YScale/Scale;

     // draw the border (5 by 2 units)
    CRect Border;

    // create the outline (dx = 5 dy = 2)
    Border.top = RealCenter.y - (long)(YScale*1);
    Border.bottom = RealCenter.y + (long)(YScale*1);
    Border.left = RealCenter.x - (long)(XScale*2.5);
    Border.right = RealCenter.x + (long)(XScale*2.5);

    CPoint TopLeft,TopRight,BottomLeft,BottomRight;

    TopLeft.x = Border.left;
    TopLeft.y = Border.top;

    TopRight.x = Border.right;
    TopRight.y = Border.top;

    BottomLeft.x = Border.left;
    BottomLeft.y = Border.bottom;

    BottomRight.x = Border.right;
    BottomRight.y = Border.bottom;

    TopLeft = LAUtils.RotatePoint(TopLeft,RealCenter,Angle);
    TopRight = LAUtils.RotatePoint(TopRight,RealCenter,Angle);
    BottomLeft = LAUtils.RotatePoint(BottomLeft,RealCenter,Angle);
    BottomRight = LAUtils.RotatePoint(BottomRight,RealCenter,Angle);
    
    // draw the border
    MemDC.MoveTo(TopLeft);
    MemDC.LineTo(TopRight);
    MemDC.LineTo(BottomRight);
    MemDC.LineTo(BottomLeft);
    MemDC.LineTo(TopLeft);

    // now draw the two cicles for the emmittor/detector
    CPoint Emitter,Detector,Center10;
    // times 10 so decimal values could occur
    Emitter.x = (long)(RealCenter.x - 1.3*XScale);
    Emitter.y = RealCenter.y;
    Detector.x = (long)(RealCenter.x + 1.3*XScale);
    Detector.y = RealCenter.y;

    // old, just in case *10 is needed to "floatize" the integer arithmetic.
    Center10.x = RealCenter.x;
    Center10.y = RealCenter.y;   

    // now rotate the points about the center
    Emitter = LAUtils.RotatePoint(Emitter,Center10,Angle);
    Detector = LAUtils.RotatePoint(Detector,Center10,Angle);

    // divide
    Emitter.x = Emitter.x;
    Emitter.y = Emitter.y;
    Detector.x = Detector.x;
    Detector.y = Detector.y;

    float CircleRadius = (float)0.8;

    MemDC.Ellipse(Emitter.x-(long)(CircleRadius*XScale),Emitter.y-(long)(CircleRadius*YScale),Emitter.x+(long)(CircleRadius*XScale),Emitter.y+(long)(CircleRadius*YScale));
    MemDC.Ellipse(Detector.x-(long)(CircleRadius*XScale),Detector.y-(long)(CircleRadius*YScale),Detector.x+(long)(CircleRadius*XScale),Detector.y+(long)(CircleRadius*YScale));

    // create little arrow to show which direction the beam goes (foward/backwards?)
    CPoint Point1,Point2,Point3;

    float TriangleSize = CircleRadius/(float)1.5;

    // bottom left
    Point1.x = (long)(RealCenter.x - TriangleSize*XScale);
    Point1.y = (long)(RealCenter.y - TriangleSize*XScale);
    // bottom right
    Point2.x = (long)(RealCenter.x + TriangleSize*XScale);
    Point2.y = (long)(RealCenter.y - TriangleSize*XScale);
    // top middle
    Point3.x = (long)(RealCenter.x);
    Point3.y = (long)(RealCenter.y + TriangleSize*XScale);

    Point1 = LAUtils.RotatePoint(Point1,Center10,Angle);
    Point2 = LAUtils.RotatePoint(Point2,Center10,Angle);
    Point3 = LAUtils.RotatePoint(Point3,Center10,Angle);

     // draw the triangle
    MemDC.MoveTo(Point1);
    MemDC.LineTo(Point2);
    MemDC.LineTo(Point3);
    MemDC.LineTo(Point1);
      
}

/************************************************************************
* Function RenderSonarSensor(CDC &MemDC, float XScale, float YScale, int XTransform, int YTransform, CPoint Center, int color, BOOL isVertica)
*
* PURPOSE
* Since the bump sensor isn't a primitive the purpose it to draw a bump sensor
* INPUTS
* The Drawing context, the scaleing and translation stuff, and the center point
* RESULT
* A Bump Sensor is drawn
*************************************************************************/
void UQuadTree::RenderSonarSensor(CDC &MemDC, float XScale, float YScale, int XTransform, int YTransform, CPoint Center, int color)
{
    // get the center point (screen coordinates) of which to render
     int XReference = (int)((Center.x-XTransform)*XScale);
     int YReference = (int)((Center.y-YTransform)*YScale);

     CPoint RealCenter;
     RealCenter.x = XReference;
     RealCenter.y = YReference;

     float Scale = SensorRenderingScale; // to adjust the size
     RenderingStats.OldBumperScaleX = XScale = XScale/Scale;
     RenderingStats.OldBumperScaleY = YScale = YScale/Scale;
     int CircleRadius = 3;

     CBrush *OldBrush;
    
     CRect Border;   
       
     Border.top = YReference - (long)(YScale*5);
     Border.bottom = YReference + (long)(YScale*5);
     Border.left = XReference - (long)(XScale*5);
     Border.right = XReference + (long)(XScale*5);


     MemDC.Rectangle(&Border);

     // get a color brush to fill in the circles
     OldBrush = MemDC.SelectObject(&ColorBrush[color]);

     // create the cone (cheaply)
     MemDC.Ellipse(RealCenter.x-(long)(CircleRadius*XScale),RealCenter.y-(long)(CircleRadius*YScale),RealCenter.x+(long)(CircleRadius*XScale),RealCenter.y+(long)(CircleRadius*YScale));


     MemDC.SelectObject(OldBrush);
}


/************************************************************************
* Function CRect FileOpenMap(CString FileName)
*
* PURPOSE
* To read from the file to the current map
* ALGORITHM
* Run through the first part which is objects, and load up the group pointer later
* Later on in the object link part, link up the pointer
* This unfortunatly has to be done interativly, because it can't be guarenteed that all
* the lower level link pointers are ready when the high level ones need to link, so 
* sometime interativly the lower level one get created, and then the higher ones have to 
* get created on another loop
* USAGE
* Indirectly by the user by calling FileOpenMap(CString Filename) and by the undo
* which has its own file.
* RETURNS
* The initial position of the robot
*************************************************************************/
CRect UQuadTree::FileOpenMap(CFile &theFile)
{
     _Destruct();
    _Construct();

    CRect CurrentView,RobotPlacement;

	RobotPlacement.top = 6000;
	RobotPlacement.left = 6000;

    unsigned char buffer[MAXFILESIZE]; // should allow for around 4000 objects to be saved
    unsigned char *bufferptr = buffer;

    LGroupPtr GroupList[MAXGROUPS];  // used to store groups

    // initialize the pointer table
    for (int ix = 0; ix < MAXGROUPS; ix++)
    {
        GroupList[ix] = NULL;
    }

    long index = theFile.Read(buffer,200000);

    CPoint Start,Middle,End;
    long GroupID;
    LGroupPtr tGroupPtr;

    // first load up the objects
    while ((index > 0) && (*bufferptr != 0xff))
    {
        int color = *bufferptr;  // it handles the conversion correctly without any fancy stuff
        bufferptr++;
        int objecttype = *bufferptr; // it handles the conversion correctly without any fancy stuff
        bufferptr++;
        FileChartoLong(Start.x,bufferptr);
        FileChartoLong(Start.y,bufferptr);
        FileChartoLong(Middle.x,bufferptr);
        FileChartoLong(Middle.y,bufferptr);
        FileChartoLong(End.x,bufferptr);
        FileChartoLong(End.y,bufferptr);
        FileChartoLong(GroupID,bufferptr);

        if (objecttype == LINE)
        {
            tGroupPtr = AddLine(Start,End);
        }
        else if (objecttype == ARCLINE)
        {
            tGroupPtr = AddArc(Start,Middle,End);
        }
        else if (objecttype == BUMPSENSOR)
        {
            long OldID;
           // tGroupPtr = AddBumpSensor(Start,End,Middle);
            FileChartoLong(OldID,bufferptr);
            // need to give it the right ID
            tGroupPtr->Next->Data->objectID = OldID;
            index -= 4;
        }
        else if (objecttype == IRSENSOR)
        {
            long OldID;
           // tGroupPtr = AddIRSensor(Middle,Start.x,Start.y,End.x);
            FileChartoLong(OldID,bufferptr);
            // need to give it the right ID
            tGroupPtr->Next->Data->objectID = OldID;
            index -= 4;
        }
        else if (objecttype == SONARSENSOR)
        {
          //  tGroupPtr = AddSonarSensor(Middle);            
        }
        else if (objecttype == TRIANGLE3D)
        {
            tGroupPtr = AddRoof3D2(Start,Middle,End);
        }
        else if (objecttype == ROOF3D)
        {
            tGroupPtr = AddRoof3D3(Start,End);
        }
		else if (objecttype == ROBOTPLACEMENT)
		{
			RobotPlacement.top = Middle.y;
			RobotPlacement.left = Middle.x;
			RobotPlacement.right = Start.x;
			GroupID = 0; // see bellow
		}
        // should never happen, but why not.
        if ((GroupID >= 0) && (GroupID < MAXGROUPS))
        {
            ASSERT (tGroupPtr != NULL);
                GroupList[GroupID] = tGroupPtr; // link the array entry to the group ptr
        }

        index -= OBJECTSIZE;
    }

    index-= 1; // for the 0xff characters
    bufferptr++;	

    // now extract the current view
    FileChartoLong(CurrentView.top,bufferptr);
    FileChartoLong(CurrentView.right,bufferptr);
    FileChartoLong(CurrentView.bottom,bufferptr);
    FileChartoLong(CurrentView.left,bufferptr);

    index-=16;

    // o.k now time to link up the group table
    long ChildID;

    // because the array may have to be travered many times
    BOOL done = false;
    BOOL prevdone ;

    // because the array is travered linearly, and the grouping according
    // to the index may be non linear, it may have to be traversed several times.
    while (!done)
    {
        done = true;
        unsigned char *gbufferptr = bufferptr;
        int gindex = index;

        while (gindex > 0)
        {
             FileChartoLong(GroupID,gbufferptr); // get the parent group pointer ID
             gindex -= 4; 

             prevdone = true;

             LGroupPtr tGroupPtr;

             if (GroupList[GroupID] == NULL) // only do this once, may be traversed a few times
             {

                 tGroupPtr = new GROUPSTRUCT;
                 GroupList[GroupID] = tGroupPtr;
                 tGroupPtr->GroupID = GroupIDList.GetNewID();
                 tGroupPtr->GroupType = Seperable;
                 tGroupPtr->Next = NULL;
                 tGroupPtr->Child = NULL;
                 tGroupPtr->ParentPtr = NULL;
                 tGroupPtr->Sibling = NULL;
                 tGroupPtr->NumofObjects = 0;
             }
             else 
             {
                 tGroupPtr = GroupList[GroupID];
             }
         
             // first case, there must be at least 1 child otherwise no entry.  Add it
             // to be the child.
             FileChartoLong(ChildID,gbufferptr);
             gindex -= 4;

             // just in case
             if (GroupList[ChildID] != NULL)
             {
                 // might already be done
                 if (tGroupPtr->Child != GroupList[ChildID])
                 {
                     tGroupPtr->Child = GroupList[ChildID];
                     tGroupPtr->NumofObjects += tGroupPtr->Child->NumofObjects;
                     tGroupPtr->Child->ParentPtr = tGroupPtr;
                 }
                 tGroupPtr = tGroupPtr->Child;
             }
             else
             {
                 done = false; // missed this one, have to try again
                 prevdone = false;
             }

             // now look for sibling pointers
             FileChartoLong(ChildID,gbufferptr);
             gindex -= 4;
             while (ChildID != SEPERATOR)
             {
                 // don't do anything if the first entry wasn't created properly
                 if (prevdone)
                 {
                     if (GroupList[ChildID] != NULL)
                     {
                         // might have been already entered
                         if (tGroupPtr->Sibling != GroupList[ChildID])
                         {
                             tGroupPtr->Sibling = GroupList[ChildID];
                             GroupList[GroupID]->NumofObjects += GroupList[ChildID]->NumofObjects;
                             tGroupPtr->Sibling->ParentPtr = GroupList[GroupID];
                         }
                     }
                     else
                     {
                         done = false;
                     }
                     ASSERT (tGroupPtr != NULL);
                     if (tGroupPtr == NULL)
                         break;
                     LGroupPtr tempo = tGroupPtr;

                     // do not increment otherwise this algorithm could lock up
                     if (tGroupPtr->Sibling != NULL)
                     {
                        tGroupPtr = tGroupPtr->Sibling;
                     }
                      
                     // this happens if the entry wasn't created yet.  Break out,
                     // and it will work after the list is traversed again.
                     if (tGroupPtr == NULL)
                     {
                         //AfxMessageBox("NULL");
                         break;
                     }
                 }

                 // next
                 FileChartoLong(ChildID,gbufferptr);
                 gindex -= 4;
             }
        }  
    }
    return RobotPlacement;

}

/************************************************************************
* Function FileSaveMap(CString FileName)
*
* PURPOSE
* To save the current map to a file
* ALGORITHM
* Place all of the objects in the buffer, and load up the pointer table with
* there group IDs, later create a buffer that references the pointers.

*************************************************************************/
void UQuadTree::FileSaveMap(CFile &theFile, CRect CurrView, BOOL AllLines)
{
    unsigned char buffer[MAXFILESIZE]; // should allow for 4000 objects to be saved
    unsigned char *bufferptr = buffer;

    GroupListPtr GroupList[MAXGROUPS];  // used to store groups
    long index = 0;

    RenderingStats.RenderCycle++; // eh use this again to only store one arc, per all of its characters.

    // initialize the pointer table
    for (int ix = 0; ix < MAXGROUPS; ix++)
    {
        GroupList[ix] = NULL;
    }


    // first traverse the biglist, adding entries into the file buffer
    // also add links in the link array
    ObjectListPtr Traversal = BigObjectList;

    while (Traversal != NULL)
    {

        if ((Traversal->Data->objecttype == LINE) || (Traversal->Data->objecttype == BUMPSENSOR)
            || (Traversal->Data->objecttype == IRSENSOR) || (Traversal->Data->objecttype == SONARSENSOR)
            || (Traversal->Data->objecttype == TRIANGLE3D) || (Traversal->Data->objecttype == ROOF3D))

        {
            *bufferptr = Traversal->Data->objectColor;
            bufferptr++;
            *bufferptr = Traversal->Data->objecttype;
            bufferptr++;
            FileLongtoChar(Traversal->Data->start.x,bufferptr);
            FileLongtoChar(Traversal->Data->start.y,bufferptr);
            FileLongtoChar(Traversal->Data->middle.x,bufferptr);
            FileLongtoChar(Traversal->Data->middle.y,bufferptr);
            FileLongtoChar(Traversal->Data->end.x,bufferptr);
            FileLongtoChar(Traversal->Data->end.y,bufferptr); 
            FileLongtoChar(Traversal->Data->GroupPtr->GroupID,bufferptr);
            FileAddLinkstoArray(Traversal->Data->GroupPtr,GroupList);

            // need to adds its ID for the bump sensor.
            if ((Traversal->Data->objecttype == BUMPSENSOR) || (Traversal->Data->objecttype == IRSENSOR))
            {
                long tempID = Traversal->Data->objectID;
                FileLongtoChar(tempID,bufferptr);
                index+=4;
            }

            index+=OBJECTSIZE;
        }
        // recover the information in the dummy header
        else if (Traversal->Data->objecttype == ARCLINE)
        {
            if (Traversal->Data->GroupPtr->Next->Data->renderflag != RenderingStats.RenderCycle)
            {

                if (AllLines)
                {
                    Traversal->Data->GroupPtr->Next->Data->renderflag=RenderingStats.RenderCycle;
                    // save the arc as a bunch of lines, not as an arc
                    // get by the dummy header
                    OBJECTLIST *Traverse = Traversal;//->Next;
                    while (Traverse != NULL)
                    {
                        *bufferptr = Traverse->Data->objectColor;
                        bufferptr++;
                        *bufferptr = LINE;
                        bufferptr++;
                        CPoint Start,Middle,End;
                        Start = Traverse->Data->start;
                        Middle = Traverse->Data->middle;
                        End = Traverse->Data->end;
                        FileLongtoChar(Start.x,bufferptr);
                        FileLongtoChar(Start.y,bufferptr);
                        FileLongtoChar(Middle.x,bufferptr);
                        FileLongtoChar(Middle.y,bufferptr);
                        FileLongtoChar(End.x,bufferptr);
                        FileLongtoChar(End.y,bufferptr); 
                        long ID = GroupIDList.GetNewID();
                        FileLongtoChar(ID,bufferptr);
                        // might as well add it back here
                        GroupIDList.AddBackID(ID);                        
                        index+=OBJECTSIZE;
                        Traverse = Traverse->Next;
                    }
                }
                else
                {
                    *bufferptr = Traversal->Data->objectColor;
                    bufferptr++;
                    *bufferptr = Traversal->Data->objecttype;
                    bufferptr++;
                    CPoint Start,Middle,End;
                    Start = Traversal->Data->GroupPtr->Next->Data->start;
                    Middle = Traversal->Data->GroupPtr->Next->Data->middle;
                    End = Traversal->Data->GroupPtr->Next->Data->end;
                    Traversal->Data->GroupPtr->Next->Data->renderflag=RenderingStats.RenderCycle;
                    FileLongtoChar(Start.x,bufferptr);
                    FileLongtoChar(Start.y,bufferptr);
                    FileLongtoChar(Middle.x,bufferptr);
                    FileLongtoChar(Middle.y,bufferptr);
                    FileLongtoChar(End.x,bufferptr);
                    FileLongtoChar(End.y,bufferptr); 
                    FileLongtoChar(Traversal->Data->GroupPtr->GroupID,bufferptr);
                    FileAddLinkstoArray(Traversal->Data->GroupPtr,GroupList);
                    index+=OBJECTSIZE;
                }
            }
        }       
        
        Traversal = Traversal->Next;        
    }

    // add the 0xff to signal the end of the objects
    *bufferptr = 0xff;
    bufferptr++;
    index+=1;    

    FileLongtoChar(CurrView.top,bufferptr); 
    FileLongtoChar(CurrView.right,bufferptr); 
    FileLongtoChar(CurrView.bottom,bufferptr); 
    FileLongtoChar(CurrView.left,bufferptr); 
    index+=16;

    // now save the current view
    long seperator = SEPERATOR;

    // traversal done.. now add the link array information
    for (long iy = 0; iy < MAXGROUPS; iy++)
    {
        if (GroupList[iy] != NULL)
        {
            // first add the Group ID
            FileLongtoChar(iy,bufferptr);
            index+=4;

            // next add all of its children links, while deleteing the list
            GROUPLIST *prev;                
            while (GroupList[iy] != NULL)
            {                
                prev = GroupList[iy];
                FileLongtoChar(GroupList[iy]->ID,bufferptr);
                index+=4;
                GroupList[iy] = GroupList[iy]->Next;
                delete prev;
                prev = NULL;
            }
            FileLongtoChar(seperator,bufferptr); // put a seperator in.
            index+=4;
        }       

    }

    theFile.Write(buffer,index);

}

/************************************************************************
* Function DraftingEditProperties()
*
* PURPOSE
* To Change the properties of an object.  Currently only works for the bump sensor
*************************************************************************/
void UQuadTree::DraftingEditProperties()
{
  /*  if (SelectedObjectPtr != NULL)
    {   
        // O.K something must be selected
        if (SelectedObjectPtr->Next == NULL)        {
           

            if (SelectedObjectPtr->data->GroupType == NonSeperable)
            {
                // put up the bump sensor property screen
                if (SelectedObjectPtr->data->Next->Data->objecttype == BUMPSENSOR)
                {
                    UBumpSensorOptions tOptions;
                    tOptions.m_ID = SelectedObjectPtr->data->Next->Data->objectID;
                    tOptions.m_StartX = SelectedObjectPtr->data->Next->Data->start.x;
                    tOptions.m_StartY = SelectedObjectPtr->data->Next->Data->start.y;
                    tOptions.m_EndX = SelectedObjectPtr->data->Next->Data->end.x;
                    tOptions.m_EndY = SelectedObjectPtr->data->Next->Data->end.y;

                    if (tOptions.DoModal() == IDOK)
                    {

                        SelectedObjectPtr->data->Next->Data->objectID = tOptions.m_ID;

                        CPoint tempo;
                        tempo.x = tOptions.m_StartX;
                        tempo.y = tOptions.m_StartY;
                        if (AddCheckifPointValid(tempo))
                        {
                            SelectedObjectPtr->data->Next->Data->start.x = tOptions.m_StartX;
                            SelectedObjectPtr->data->Next->Data->start.y = tOptions.m_StartY;
                        }

                        tempo.x = tOptions.m_EndX;
                        tempo.y = tOptions.m_EndY;
                        if (AddCheckifPointValid(tempo))
                        {
                            SelectedObjectPtr->data->Next->Data->end.x = tOptions.m_EndX;
                            SelectedObjectPtr->data->Next->Data->end.y = tOptions.m_EndY;
                        }
                    }
                }
                // put up the ir sensor property screen
                else if (SelectedObjectPtr->data->Next->Data->objecttype == IRSENSOR)
                {
                    UIRSensorOptions tOptions;
                    tOptions.m_BeamAngle = SelectedObjectPtr->data->Next->Data->end.x;
                    tOptions.m_MaxRange = SelectedObjectPtr->data->Next->Data->start.y;
                    tOptions.m_MinRange = SelectedObjectPtr->data->Next->Data->start.x;
                    tOptions.m_SensorID = SelectedObjectPtr->data->Next->Data->objectID;

                    if (tOptions.DoModal() == IDOK)
                    {
                        SelectedObjectPtr->data->Next->Data->end.x = tOptions.m_BeamAngle;
                        SelectedObjectPtr->data->Next->Data->start.y = tOptions.m_MaxRange;
                        SelectedObjectPtr->data->Next->Data->start.x = tOptions.m_MinRange;
                        SelectedObjectPtr->data->Next->Data->objectID = tOptions.m_SensorID;
                    }


                }
            }
        }
    }*/
}


/************************************************************************
* Function BOOL DuplicateAddBumpSensor(CPoint Start, CPoint End, CPoint Display)
*
* PURPOSE
* To create a bump sensor object but not to add it to the quadtree
* INPUTS
* The start, end point and display point of the bump sensor
* RESULT
* A Bump Sensor groupptr is returned
*
*************************************************************************/
UQuadTree::GROUPSTRUCT*  UQuadTree::DuplicateAddBumpSensor(CPoint Start, CPoint End, CPoint Display)
{
     // do some error checking
    if (!AddCheckifPointValid(Start))
        return NULL;
    if (!AddCheckifPointValid(End))
        return NULL;
    if (!AddCheckifPointValid(Display))
        return NULL;

    ObjectPtr temp;
    temp = new Object;    

    // copy all the information to a new pointer.
    temp->end = End;
    temp->middle = Display;
    temp->objectID = BumpSensorIDList.GetNewID();
    temp->objecttype = BUMPSENSOR;
    temp->renderflag = 0;
    temp->start = Start;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;  

    // create the group pointer for the object

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}

/************************************************************************
* Function LGroupPtr AddIRSensor(CPoint DisplayPoint, long MinRange, long MaxRange, long Angle)
*
* PURPOSE
* To add a bump sensor to the quadtree
* INPUTS
* The display point, the minimum range, the max range, the beam angle
* RESULT
* A IR Sensor is added in the quadtree
*
*************************************************************************/
UQuadTree::LGroupPtr UQuadTree::AddIRSensor(CPoint DisplayPoint, long MinRange, long MaxRange, long Angle)
{
       // do some error checking
    if (!AddCheckifPointValid(DisplayPoint))
        return NULL;

    ObjectPtr temp;
    TreePtr tLevelTreePtr;
    temp = new Object;    

    // copy all the information to a new pointer.    
    temp->middle = DisplayPoint;
    temp->objectID = IRSensorIDList.GetNewID();
    temp->objecttype = IRSENSOR;
    temp->renderflag = 0;
    temp->start.x = MinRange;
    temp->start.y = MaxRange;
    temp->end.x = Angle;
    temp->end.y = Angle;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    // add the object to the root node
    AddToObjectList(HeadQuadPtr,temp);

    // only need to add it to 1 treeptr per level
    tLevelTreePtr = HeadQuadPtr;    

    DisplayPoint.x = DisplayPoint.x/100+1;
    DisplayPoint.y = DisplayPoint.y/100+1;

    // recursivly go down the quadtree adding the sensor to varoius quadrants
    int Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DisplayPoint);
    while (Quadrant != -1)
    {
        tLevelTreePtr = tLevelTreePtr->NextQuad[Quadrant-1];
        AddToObjectList(tLevelTreePtr,temp);
        Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DisplayPoint);
    }

    // create the group pointer for the object

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}

/************************************************************************
* Function LGroupPtr DuplicateAddIRSensor(CPoint DisplayPoint, long MinRange, long MaxRange, long Angle)
*
* PURPOSE
* To Create a IR sensor object
* INPUTS
* The display point, the minimum range, the max range, the beam angle
* RESULT
* A IR Sensor group ptr is returned
*
*************************************************************************/
UQuadTree::LGroupPtr UQuadTree::DuplicateAddIRSensor(CPoint DisplayPoint, long MinRange, long MaxRange, long Angle)
{
           // do some error checking
    if (!AddCheckifPointValid(DisplayPoint))
        return NULL;

    ObjectPtr temp;
    temp = new Object;    

    // copy all the information to a new pointer.    
    temp->middle = DisplayPoint;
    temp->objectID = IRSensorIDList.GetNewID();
    temp->objecttype = IRSENSOR;
    temp->renderflag = 0;
    temp->start.x = MinRange;
    temp->start.y = MaxRange;
    temp->end.x = Angle;
    temp->end.y = Angle;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;    

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}


/************************************************************************
* Function LGroupPtr AddSonarSensor(CPoint DisplayPoint)
*
* PURPOSE
* To add a Sonar sensor to the quadtree
* INPUTS
* The display point
* RESULT
* A Sonar Sensor is added in the quadtree
*
*************************************************************************/
UQuadTree::LGroupPtr UQuadTree::AddSonarSensor(CPoint DisplayPoint)
{
    // do some error checking
    if (!AddCheckifPointValid(DisplayPoint))
        return NULL;

    ObjectPtr temp;
    TreePtr tLevelTreePtr;
    temp = new Object;    

    // copy all the information to a new pointer.    
    temp->middle = DisplayPoint;
    temp->objectID = 0;
    temp->objecttype = SONARSENSOR;
    temp->renderflag = 0;
    temp->start.x = 0;
    temp->start.y = 0;
    temp->end.x = 0;
    temp->end.y = 0;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    // add the object to the root node
    AddToObjectList(HeadQuadPtr,temp);

    // only need to add it to 1 treeptr per level
    tLevelTreePtr = HeadQuadPtr;    

    DisplayPoint.x = DisplayPoint.x/100+1;
    DisplayPoint.y = DisplayPoint.y/100+1;

    // recursivly go down the quadtree adding the sensor to varoius quadrants
    int Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DisplayPoint);
    while (Quadrant != -1)
    {
        tLevelTreePtr = tLevelTreePtr->NextQuad[Quadrant-1];
        AddToObjectList(tLevelTreePtr,temp);
        Quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DisplayPoint);
    }

    // create the group pointer for the object

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}


/************************************************************************
* Function LGroupPtr AddSonarSensor(CPoint DisplayPoint)
*
* PURPOSE
* To create a bump sensor object but not to add it to the quadtree
* INPUTS
* The start, end point and display point of the bump sensor
* RESULT
* A Bump Sensor groupptr is returned
*
*************************************************************************/
UQuadTree::LGroupPtr UQuadTree::DuplicateAddSonarSensor(CPoint DisplayPoint)
{
        // do some error checking
    if (!AddCheckifPointValid(DisplayPoint))
        return NULL;

    ObjectPtr temp;
    temp = new Object;    

    // copy all the information to a new pointer.    
    temp->middle = DisplayPoint;
    temp->objectID = 0;
    temp->objecttype = SONARSENSOR;
    temp->renderflag = 0;
    temp->start.x = 0;
    temp->start.y = 0;
    temp->end.x = 0;
    temp->end.y = 0;
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // create the group pointer for the object

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}


/************************************************************************
* Function DraftingAddSonarSensor(CPoint thePoint)
*
* PURPOSE
* This is the function that the outside world uses to place a sonar sensor
* USAGE
* By the draw class
*************************************************************************/
void UQuadTree::DraftingAddSonarSensor(CPoint thePoint)
{
    DraftingFlushAll();
    AddSonarSensor(thePoint);
}

/************************************************************************
* Function DraftingAddIRSensor(CPoint thePoint, long MinRange, long MaxRange, long Angle)
*
* PURPOSE
* This is the function that the outside world uses to place a IR sensor
* USAGE
* By the draw class
*************************************************************************/
void UQuadTree::DraftingAddIRSensor(CPoint thePoint, long MinRange, long MaxRange, long Angle)
{
    DraftingFlushAll();
    AddIRSensor(thePoint,MinRange,MaxRange,Angle);
}


/************************************************************************
* Function AddRoof3D(CPoint Point1, Point2, Point3)
*
* PURPOSE
* Adds a roof to a add depth area.
* ALGORITHM
* A roof is a triangle therefore has three lines.  Create the three lines
* then group them
* USAGE
* By the draw class
*************************************************************************/
UQuadTree::GROUPSTRUCT*  UQuadTree::AddRoof3D(CPoint Point1, CPoint Point2, CPoint Point3)
{
     // do some error checking
    if (!AddCheckifPointValid(Point1))
        return NULL;
    if (!AddCheckifPointValid(Point2))
        return NULL;
    if (!AddCheckifPointValid(Point3))
        return NULL;
        

    ObjectPtr temp;
    TreePtr tTreePtr,tLevelTreePtr;       
    CPoint next,divnext;

    // create a grouplist for every line
    LGroupPtr BigGroup = new GROUPSTRUCT;
    BigGroup->GroupID = GroupIDList.GetNewID();
    BigGroup->Child = NULL;
    BigGroup->ParentPtr = NULL;
    BigGroup->Sibling = NULL;
    BigGroup->GroupType = NonSeperable;
    BigGroup->Next = NULL;
    BigGroup->NumofObjects = 4;

       // add the triangle line
    temp = new Object; 
    temp->start = Point1;
    temp->middle = Point2;
    temp->end = Point3;
    temp->objectID = IDList.GetNewID();
    temp->objecttype = TRIANGLE3D;
    temp->renderflag = 0;        
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;


    // create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = BigGroup;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;
    BigGroup->Child = tGroupPtr;


    for (int ix = 0; ix < 3; ix++)
    {

        temp = new Object; 

        // copy all the information to a new pointer.
        if (ix == 0)
        {
            temp->end = Point1;
            temp->start = Point2;
        }
        else if (ix == 1)
        {
            temp->end = Point2;
            temp->start = Point3;
        }
        else if (ix == 2)
        {
            temp->end = Point1;
            temp->start = Point3;
        }

        temp->middle = 0;
        temp->objectID = IDList.GetNewID();
        temp->objecttype = ROOF3D;
        temp->renderflag = 0;        
        temp->objectColor = 2;
        temp->GroupPtr = NULL;

        // add the object to the big object list.
        AddToBigObjectList(temp);

        // add the object to the root node
        AddToObjectList(HeadQuadPtr,temp);

        tLevelTreePtr = HeadQuadPtr;    

        int quadrant;

        CPoint DivPoint;
        DivPoint.x = temp->start.x/100+1;
        DivPoint.y = temp->start.y/100+1;
        quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);

        // at a leaf node, time to go.
        while (quadrant!=-1)
        {
            next = temp->start;  // reset the starting position for every level
            // tranlate the points into quadrants for the function       
        
            if (quadrant > 0) // just in case
                 tLevelTreePtr = tLevelTreePtr->NextQuad[quadrant-1];
            tTreePtr = tLevelTreePtr;
            while ((next.x != -1) && (tTreePtr != NULL))
            {

                AddToObjectList(tTreePtr,temp);
                next = LAUtils.FindIntersection(next,temp->end,tTreePtr->QuadRect);
                tTreePtr = AddFindQuad(next,tTreePtr);
            }
            // will output -1 when at the last level.

            quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
        } 

        ObjectListPtr tObjectList= new OBJECTLIST;
        tObjectList->Next = NULL;
        tObjectList->Prev = NULL;
        tObjectList->Data = temp;
    

        // create a grouplist for every line
        LGroupPtr tGroupPtr = new GROUPSTRUCT;
        tGroupPtr->GroupID = GroupIDList.GetNewID();
        tGroupPtr->Child = NULL;
        tGroupPtr->ParentPtr = BigGroup;
        tGroupPtr->Sibling = NULL;
        tGroupPtr->GroupType = NonSeperable;
        tGroupPtr->Next = tObjectList;
        tGroupPtr->NumofObjects = 1;
        temp->GroupPtr = tGroupPtr;

        if (ix == 0)
        {
            BigGroup->Child->Sibling = tGroupPtr;
        }
        else if (ix == 1)
        {
            BigGroup->Child->Sibling->Sibling = tGroupPtr;
        }
        else if (ix == 2)
        {
            BigGroup->Child->Sibling->Sibling->Sibling = tGroupPtr;
        }            
    }

    return BigGroup;

}

/************************************************************************
* Function LGroupPtr DuplicateAddRoof3D(CPoint Point1, Point2, Point3)
*
* PURPOSE
* To create a 3D triangle roof object but not to add it to the quadtree
* INPUTS
* The three points
* RESULT
* A duplicate roof3D is returned
*
*************************************************************************/
UQuadTree::LGroupPtr UQuadTree::DuplicateAddRoof3D(CPoint Point1, CPoint Point2, CPoint Point3)
{

        // do some error checking
    if (!AddCheckifPointValid(Point1))
        return NULL;
    if (!AddCheckifPointValid(Point2))
         return NULL;
    if (!AddCheckifPointValid(Point3))
        return NULL;


    ObjectPtr temp;
    temp = new Object;    

    // copy all the information to a new pointer.    
    temp->middle = Point2;
    temp->objectID = 0;
    temp->objecttype = TRIANGLE3D;
    temp->renderflag = 0;
    temp->start = Point1;
    temp->end = Point3;  
    temp->objectColor = 2;
    temp->GroupPtr = NULL;

    // create the group pointer for the object

    // first the object list pointer for the group pointer
    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;   

    // now create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;
}

/************************************************************************
* Function LGroupPtr AddRoof3D2(CPoint Point1, CPoint Point2, CPoint Point3)
*
* PURPOSE
* Adds a roof to a add depth area.  This one only does the triangle and not
* all four objects
* USAGE
* By copy paste and save not generation
*************************************************************************/
UQuadTree::GROUPSTRUCT*  UQuadTree::AddRoof3D2(CPoint Point1, CPoint Point2, CPoint Point3)
{
      // do some error checking
    if (!AddCheckifPointValid(Point1))
        return NULL;
    if (!AddCheckifPointValid(Point2))
        return NULL;
    if (!AddCheckifPointValid(Point3))
        return NULL;
        

    ObjectPtr temp;    
    CPoint next,divnext;   

       // add the triangle line
    temp = new Object; 
    temp->start = Point1;
    temp->middle = Point2;
    temp->end = Point3;
    temp->objectID = IDList.GetNewID();
    temp->objecttype = TRIANGLE3D;
    temp->renderflag = 0;        
    temp->objectColor = 0;
    temp->GroupPtr = NULL;

    // add the object to the big object list.
    AddToBigObjectList(temp);

    ObjectListPtr tObjectList= new OBJECTLIST;
    tObjectList->Next = NULL;
    tObjectList->Prev = NULL;
    tObjectList->Data = temp;


    // create a grouplist for every line
    LGroupPtr tGroupPtr = new GROUPSTRUCT;
    tGroupPtr->GroupID = GroupIDList.GetNewID();
    tGroupPtr->Child = NULL;
    tGroupPtr->ParentPtr = NULL;
    tGroupPtr->Sibling = NULL;
    tGroupPtr->GroupType = NonSeperable;
    tGroupPtr->Next = tObjectList;
    tGroupPtr->NumofObjects = 1;
    temp->GroupPtr = tGroupPtr;

    return tGroupPtr;

}

/************************************************************************
* Function LGroupPtr AddRoof3D2(CPoint Point1, CPoint Point2, CPoint Point3)
*
* PURPOSE
* Adds a roof object.  This one only generates one roof3d object
* USAGE
* By copy paste and save not generation
*************************************************************************/
UQuadTree::GROUPSTRUCT*  UQuadTree::AddRoof3D3(CPoint Point1, CPoint Point2)
{
        ObjectPtr temp;
        TreePtr tTreePtr,tLevelTreePtr;       
        CPoint next,divnext;
        temp = new Object; 

        temp->end = Point1;
        temp->start = Point2;    
        temp->middle = 0;
        temp->objectID = IDList.GetNewID();
        temp->objecttype = ROOF3D;
        temp->renderflag = 0;        
        temp->objectColor = 2;
        temp->GroupPtr = NULL;

        // add the object to the big object list.
        AddToBigObjectList(temp);

        // add the object to the root node
        AddToObjectList(HeadQuadPtr,temp);

        tLevelTreePtr = HeadQuadPtr;    

        int quadrant;

        CPoint DivPoint;
        DivPoint.x = temp->start.x/100+1;
        DivPoint.y = temp->start.y/100+1;
        quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);

        // at a leaf node, time to go.
        while (quadrant!=-1)
        {
            next = temp->start;  // reset the starting position for every level
            // tranlate the points into quadrants for the function       
    
            if (quadrant > 0) // just in case
                 tLevelTreePtr = tLevelTreePtr->NextQuad[quadrant-1];
            tTreePtr = tLevelTreePtr;
            while ((next.x != -1) && (tTreePtr != NULL))
            {

                AddToObjectList(tTreePtr,temp);
                next = LAUtils.FindIntersection(next,temp->end,tTreePtr->QuadRect);
                tTreePtr = AddFindQuad(next,tTreePtr);
            }
            // will output -1 when at the last level.

            quadrant = AddFindQuad(tLevelTreePtr->QuadRect,DivPoint);
        } 

        ObjectListPtr tObjectList= new OBJECTLIST;
        tObjectList->Next = NULL;
        tObjectList->Prev = NULL;
        tObjectList->Data = temp;


        // create a grouplist for every line
        LGroupPtr tGroupPtr = new GROUPSTRUCT;
        tGroupPtr->GroupID = GroupIDList.GetNewID();
        tGroupPtr->Child = NULL;
        tGroupPtr->ParentPtr = NULL;
        tGroupPtr->Sibling = NULL;
        tGroupPtr->GroupType = NonSeperable;
        tGroupPtr->Next = tObjectList;
        tGroupPtr->NumofObjects = 1;
        temp->GroupPtr = tGroupPtr;

        return tGroupPtr;

}

/************************************************************************
* Function LGroupPtr DuplicateAddRoof3D2(CPoint Start, CPoint End)
*
* PURPOSE
* Creates a Roof3D object but does not add it to the quadtree
* USAGE
* By copy paste and save not generation
*************************************************************************/
UQuadTree::GROUPSTRUCT* UQuadTree::DuplicateAddRoof3D2(CPoint Start, CPoint End)
{
        ObjectPtr temp;
        temp = new Object; 

        temp->end = Start;
        temp->start = End;    
        temp->middle = 0;
        temp->objectID = IDList.GetNewID();
        temp->objecttype = ROOF3D;
        temp->renderflag = 0;        
        temp->objectColor = 2;
        temp->GroupPtr = NULL;

        ObjectListPtr tObjectList= new OBJECTLIST;
        tObjectList->Next = NULL;
        tObjectList->Prev = NULL;
        tObjectList->Data = temp;


        // create a grouplist for every line
        LGroupPtr tGroupPtr = new GROUPSTRUCT;
        tGroupPtr->GroupID = GroupIDList.GetNewID();
        tGroupPtr->Child = NULL;
        tGroupPtr->ParentPtr = NULL;
        tGroupPtr->Sibling = NULL;
        tGroupPtr->GroupType = NonSeperable;
        tGroupPtr->Next = tObjectList;
        tGroupPtr->NumofObjects = 1;
        temp->GroupPtr = tGroupPtr;

        return tGroupPtr;

}
