C++ point quad tree 알고리즘


#include <iostream>
#include <cmath>
#include <string>
#include <fstream>
#include <sstream>

using namespace std;

ifstream fin("sample2.inp");
enum { NONLEAF = 0, LEAF };

class treeNode; class Rectangle;

//------------------------------------------------------------------------------------------------------------------
class Point {
    double x;
    double y;
public:
    Point() {};
    Point(double _x, double _y) : x(_x), y(_y) {};
    double getX() const { return x; }
    double getY() const { return y; }
};
int FindIndex(Point parentCenter, Point childCenter) {
    bool indexX = parentCenter.getX() < childCenter.getX();
    bool indexY = parentCenter.getY() < childCenter.getY();
    if (indexX && indexY)
        return 1;
    else if (indexX && !indexY)
        return 2;
    else if (!indexX && indexY)
        return 0;
    else if (!indexX && !indexY)
        return 3;

    return -1;
}
//--------------------------------POINT----------------------------------------------------------------------------------
class Rectangle {
    friend class Tree;
    friend double calculate(Tree tree, Rectangle rect, char value);
    friend double calculate(treeNode* treePtr, Rectangle rect, char value);
    Point rightUpper;
    Point leftLower;

public:
    Rectangle();
    Rectangle(double rx1, double ry1, double rx2, double ry2);
    double operator*(const Rectangle& rect);
};
Rectangle::Rectangle()
    : rightUpper(0, 0)
    , leftLower(0, 0) {};
double Rectangle::operator*(const Rectangle& rect) {
    return 0;
}
Rectangle::Rectangle(double rx1, double ry1, double rx2, double ry2) {
    double rightX = (rx1 > rx2) ? rx1 : rx2;
    double leftX = (rx1 > rx2) ? rx2 : rx1;
    double upperY = (ry1 > ry2) ? ry1 : ry2;
    double lowerY = (ry1 > ry2) ? ry2 : ry1;

    Point rightupper(rightX, upperY);
    Point leftlower(leftX, lowerY);
    rightUpper = rightupper;
    leftLower = leftlower;
};

//------------------------------------------------Rectangle------------------------------------------------------------------

class NonLeafNode {
    friend class Tree;
    friend class treeNode;
    friend double calculate(treeNode* treePtr, Rectangle rect, char value);

    treeNode* mChildNode[4];
    Point mCenterPoint;
public:
    NonLeafNode();
    NonLeafNode(Point _centerpoint);

};

NonLeafNode::NonLeafNode()
    : mCenterPoint(0, 0) {
    for (int i = 0; i < 4; i++)
        mChildNode[i] = nullptr;

};
NonLeafNode::NonLeafNode(Point _centerpoint)
    : mCenterPoint(_centerpoint) {
    for (int i = 0; i < 4; i++)
        mChildNode[i] = nullptr;
}
//--------------------------------------NonLeafNode----------------------------------------------------------------------------

class treeNode {
    friend class Tree;
    friend class Rectangle;
    friend double calculate(treeNode* treePtr, Rectangle rect, char value);

    bool flag; // NONLEAF = 0 or LEAF = 1
    union {
        NonLeafNode* mNonLeafNode; // center point and 4 treeNode pointers ->   // treeNode* mChildNode[4];
                                                                                // Point centerPoint;   
        char mValue; // 'a' or 'b'
    };
    treeNode* parentNode;


public:
    treeNode();
    treeNode(char _value);
    treeNode(Point _centerPoint);

};

treeNode::treeNode()
    : flag(LEAF)
    , mNonLeafNode(nullptr) 
    , parentNode(nullptr){
};
treeNode::treeNode(char _value)
    : flag(LEAF)
    , mValue(_value) 
    , parentNode(nullptr) {
}

treeNode::treeNode(Point _centerPoint)
    : flag(NONLEAF)
    , parentNode(nullptr) {
    mNonLeafNode = new NonLeafNode(_centerPoint);
}
//-------------------------------------------treeNode-----------------------------------------------------------------------

class Tree {
    friend class treeNode;
    friend class Rectangle;
    friend double calculate(Tree tree, Rectangle rect, char value);
    friend double calculate(treeNode* treePtr, Rectangle rect, char value);

    treeNode* mRoot; // Root is not Leaf Node!!
public:
    Tree();
    void getData();
    void insert(double centerX, double centerY, char value1, char value2, char value3, char value4);
    void insert(treeNode* parentPtr, double centerX, double centerY, char value1, char value2, char value3, char value4);
    void insertChildNode(treeNode* parentPtr, char value1, char value2, char value3, char value4);

};

Tree::Tree()
    : mRoot(nullptr) {}

void Tree::insertChildNode(treeNode* parentPtr, char value1, char value2, char value3, char value4) {
    if (parentPtr->flag == LEAF) {
        parentPtr->mNonLeafNode = new NonLeafNode();
    }
    parentPtr->flag = NONLEAF;

    treeNode* child1 = new treeNode(value1);
    treeNode* child2 = new treeNode(value2);
    treeNode* child3 = new treeNode(value3);
    treeNode* child4 = new treeNode(value4);

    parentPtr->mNonLeafNode->mChildNode[0] = child1;
    parentPtr->mNonLeafNode->mChildNode[1] = child2;
    parentPtr->mNonLeafNode->mChildNode[2] = child3;
    parentPtr->mNonLeafNode->mChildNode[3] = child4;
    for (int i = 0; i < 4; i++) {
        parentPtr->mNonLeafNode->mChildNode[i]->parentNode = parentPtr;
    }
}
void Tree::insert(double centerX, double centerY, char value1, char value2, char value3, char value4) {
    insert(mRoot, centerX, centerY, value1, value2, value3, value4);
}
void Tree::insert(treeNode* parentPtr, double centerX, double centerY, char value1, char value2, char value3, char value4) {
    Point parentCenterPoint(parentPtr->mNonLeafNode->mCenterPoint);
    int index = FindIndex(parentCenterPoint, Point(centerX, centerY));
    treeNode* currentPtr = parentPtr->mNonLeafNode->mChildNode[index];
    if (parentPtr->mNonLeafNode->mChildNode[index]->flag == NONLEAF) {
        insert(currentPtr, centerX, centerY, value1, value2, value3, value4);
    }
    else {
        insertChildNode(currentPtr, value1, value2, value3, value4);

        currentPtr->mNonLeafNode->mCenterPoint = Point(centerX, centerY);


    }
}
void Tree::getData() {
    string sData;
    stringstream ss;
    char comma, valueA, valueB, valueC, valueD;
    int numOfInsertion;
    double centerX, centerY;


    getline(fin, sData);
    ss.str(sData);
    ss >> numOfInsertion;

    while (numOfInsertion) {
        getline(fin, sData);
        stringstream ss2;
        ss2.str(sData);
        ss2 >> centerX >> comma >> centerY >> comma >> valueA >> comma >> valueB >> comma >> valueC >> comma >> valueD;

        //0.2, 0.7, a, b, a, b

        if (mRoot == nullptr) { // when First
            mRoot = new treeNode(Point(centerX, centerY));
            insertChildNode(mRoot, valueA, valueB, valueC, valueD);
        }
        else { // when not first
            insert(mRoot, centerX, centerY, valueA, valueB, valueC, valueD);
        }

        cout << centerX << " " << centerY << " "
            << valueA << " " << valueB << " " << valueC << " " << valueD << endl;
        numOfInsertion--;
    }
}

//------------------------------------------------Tree------------------------------------------------------------------

Rectangle getRect() {
    double x1, x2, y1, y2;
    string forRect;
    char comma;
    stringstream ss;

    getline(fin, forRect);
    ss.str(forRect);
    ss >> x1 >> comma >> y1 >> comma >> x2 >> comma >> y2;

    Rectangle rect(x1, y1, x2, y2);
    return rect;
}

char getRectValue() {
    string str;
    stringstream ss;

    char rectValue;
    getline(fin, str);

    ss.str(str);
    ss >> rectValue;

    cout << rectValue << endl;
    return rectValue;
}

double calculate(Tree tree, Rectangle rect, char value) {

    double result = 0;
    result = result + calculate(tree.mRoot, rect, value);
    return 0;
}
double calculate(treeNode* treePtr, Rectangle rect, char value) {
    double result = 0;
    for (int i = 0; i < 4; i++) {
        if (treePtr->flag == LEAF) {

        }
        else {
            return result + calculate(treePtr->mNonLeafNode->mChildNode[i], rect, value);
        }

    }
    return 0;
}
//---------------------------------global function------------------------------------------
int main() {
    Rectangle rect = getRect();
    char rectValue = getRectValue();

    Tree tree;
    tree.getData();

    return 0;
}

코드가 너무길어 약간의 설명 드리자면, (0,0) (1,1)의 사각형을 쪼개어 값을 저장한 후 ('a' or 'b')트리에 저장합니다. main에서 한 사각형의 정보와, 'a' or 'b'의 값을 받아서, 트리의 사각형중 main에서 받은 사각형의 value('a' or 'b')와 같은 사각형 중 서로 겹치는 넓이를 구하는 프로그램입니다.

사각형을 쪼개는 형식은 인풋 파일에서 0.7, 0.7, b, a, b, a 이런 식으로 주어지고, 0.7, 0.7은 중앙점, b, a, b, a는 중앙 점으로 나누어 지는 4개의 사각형의 각각의 value입니다. (왼쪽 위부터 시계방향)

어떻게 어떻게 고생해서.. 인풋파일에 해당하는 정보를 tree에 저장 하긴 했습니다 사각형과 사각형의 겹치는 넓이를 구하는 algorithm도 해본 적이 있습니다.

하지만, 트리에 저장된 사각형의 정보는 각각의 모서리가 아니라, 자신을 나누는 부모의 center Point 밖에 없는데 어떻게 그 것만 가지고 한 사각형과 tree안의 사각형과의 겹치는 넓이를 구할 수 있는지 도저히 생각이 안나네요..ㅠㅠ 3일째 고민중이지만 잘 모르겠습니다. 일일이 케이스를 나누어 treeNode에 사각형의 모서리 좌표를 저장했지만, 주어진 형식에 어긋나네요

참 염치없는 질문 인것 압니다ㅠㅠ 예상 하시겠지만 이건 학교 과제지만, 마땅히 여쭈어 볼 곳이 없어서 여기다가 글을 올리네요.. 마음 같아선 과제 홈페이지를 올려드리고 싶지만 차마 그건 너무 염치가... 부탁드립니다!!..

ps. 입력양식은 이런식입니다.

0.1, 0.1, 0.5, 0.9 // 사각형의 정보

a // 사각형의 value

7 // 입력갯수

0.5, 0.5, a, b, b, a // 중앙점과, 그 중앙점으로 부터 나누어지는 4개의 사각형의 각각의 value

0.2, 0.2, a, a, b, b

0.2, 0.7, b, b, a, a

0.7, 0.7, b, a, b, a

0.7, 0.2, b, a, a, b

0.1, 0.4, b, b, b, b

0.3, 0.6, a, a, a, a

  • 2016년 11월 27일에 작성됨
    컴퓨터공학과 재학중인 학생입니다.

조회수 50


로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close