#include <iostream>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/opencv.hpp>
#include <opencv2/core/core.hpp>
#include <malloc.h>
using namespace std;
using namespace cv;



int pointmax = 63;
int i =0;
int x = 0;
struct kdtree
{
    Point2d midpoint;
    kdtree* kdtreeleft;
    kdtree* kdtreeright;
    kdtree* kdtreefather;
    int dimension;
};
kdtree* tree;
vector<Point2d> database;




kdtree* buildtrees(int dimension,vector<Point2d> &data,int beginIndex,int endIndex);
void on_mouse(int EVENT, int x, int y, int flags, void* userdata);
void adddata(Point x);
kdtree* findpoint(int demension,int x , int y,kdtree* KdTree);
Point2d getpoint(kdtree* KdTree,int x,int y);
void backpoint(kdtree* kdTree,Point2d* answer,long* distance);
void backpoint(kdtree* kdTree,Point2d* answer,long* distance)
{
    if (kdTree==nullptr)
    {
        return;
    }
    long dis = (kdTree->midpoint.x-x)*(kdTree->midpoint.x-x)+(kdTree->midpoint.y-y)*(kdTree->midpoint.y-y);
    if (dis<(*distance))
    {
        (*answer).x = kdTree->midpoint.x;
        (*answer).y = kdTree->midpoint.y;
        (*distance) = dis;
    }
    backpoint(kdTree->kdtreeright,answer,distance);
    backpoint(kdTree->kdtreeleft,answer,distance);
    return;
}
Point2d getpoint(kdtree* KdTree,int x,int y)
{
    Point2d answer = Point(x,y);
    long distance = (KdTree->midpoint.x-x)*(KdTree->midpoint.x-x) + (KdTree->midpoint.y-y)*(KdTree->midpoint.y-y);
    kdtree* father = KdTree->kdtreefather;
    kdtree* grandfather = father->kdtreefather;
    if (father->dimension==0)
    {
        if ((x-father->midpoint.x)*(x-father->midpoint.x)<distance)
        {
           backpoint(father,&answer,&distance);
        }
        
    }
    else
    {
        if ((y-father->midpoint.y)*(y-father->midpoint.y)<distance)
        {
            backpoint(father,&answer,&distance);
        }
    }
    if(grandfather->dimension==0)
    {
        if ((x-father->midpoint.x)*(x-father->midpoint.x)<distance)
        {
           backpoint(grandfather,&answer,&distance);
        }
    }
    else
    {
        if ((y-father->midpoint.y)*(y-father->midpoint.y)<distance)
        {
            backpoint(grandfather,&answer,&distance);
        }
    }
    
    return answer;
    
}
void adddata(Point x) 
{
    database.push_back(x);
}
kdtree* findpoint(int dimension,int x ,int y,kdtree* KdTree)
{
    //查找紧邻点
    kdtree* findkdtree;
    if(dimension == 0)
    {
        if (x>=KdTree->midpoint.x)
        {
            if (KdTree->kdtreeright==nullptr)
            {
                return KdTree;
            }
            else
            {
                findkdtree = findpoint(!dimension,x,y,KdTree->kdtreeright);
            }
            
        }
        else
        {
           if (KdTree->kdtreeleft==nullptr)
            {
                return KdTree;
            } 
            else
            {
                findkdtree = findpoint(!dimension,x,y,KdTree->kdtreeleft);
            }
            
        }    
    }
    else
    {
         if (y>=KdTree->midpoint.y)
        {
            if (KdTree->kdtreeright==nullptr)
            {
                return KdTree;
            }
            else
            {
                findkdtree = findpoint(!dimension,x,y,KdTree->kdtreeright);
            }
            
        }
        else
        {
            
           if (KdTree->kdtreeleft==nullptr)
            {
                return KdTree;
            } 
            else
            {
                findkdtree = findpoint(!dimension,x,y,KdTree->kdtreeleft);
            }
            
        }
    }
    return findkdtree;
}
kdtree* buildtrees(int dimension,vector<Point2d> &data,int beginIndex,int endIndex,kdtree* father)
{
   
    
    if(beginIndex >= endIndex) return nullptr;
    //先根据当前划分维度来排序[beginIndex,endIndex)区域的点
    if (dimension == 0) {
      std::sort(data.begin() + beginIndex, data.begin() + endIndex, 
      [](Point2d & a, Point2d & b) {return a.x < b.x;});
    }
    else if (dimension == 1) {
      std::sort(data.begin() + beginIndex, data.begin() + endIndex,
      [](Point2d & a, Point2d & b) {return a.y < b.y; });
    }
    //中值选择
    int midValueIndex = (endIndex+beginIndex) / 2;
    //以该中值创建一个划分节点
    kdtree* node = new kdtree;
    node->kdtreefather = father;
    if(x==0)
    {
        tree = node;
        tree->kdtreefather = nullptr;
        x=1;
    }
    node->midpoint = data[midValueIndex];
    //递归构建子树
    //左子树为较小值，区间应该为[beginIndex,midValueIndex)
    node->kdtreeleft = buildtrees(!dimension, data, beginIndex, midValueIndex,node);
    //左子树为较大值，区间应该为[midValueIndex+1,endIndex)
    node->kdtreeright = buildtrees(!dimension, data, midValueIndex + 1, endIndex,node);


    return node;
}       
void on_mouse(int EVENT, int x, int y, int flags, void* userdata) {
    Mat hh;
    hh = *(Mat *) userdata;
    if(EVENT==EVENT_FLAG_LBUTTON)
    {
        if (i!=-1)
        {
        Point p(x, y);
        circle(hh,p,2, Scalar(0, 255, 0));
        cout<<x<<"   "<< y<<endl;
        adddata(p); 
        i++;
        cout<<i<<"次"<<endl;
        }
        else
        {
            kdtree* gettree = findpoint(0,x,y,tree);
            Point2d answer = getpoint(gettree,x,y);
             circle(hh,answer,3, Scalar(0, 0, 255));
        }
        
        
    }
     if(EVENT==EVENT_FLAG_RBUTTON)
    {
     tree = buildtrees(0,database,0,database.size());
     i=-1;
    }
}
    int main() {
       
        
        namedWindow("【display】");
        Mat src;
        src = imread("/home/hoshino/下载/opencvstudy/peixun/peixun.PNG");
        //cvtColor(src, src, COLOR_RGB2GRAY);
        setMouseCallback("【display】", on_mouse, &src);
        //以40ms刷新显示
        while (1) {
            imshow("【display】", src);
            waitKey(40);
        }     

    }