# -*- coding: utf-8 -*-
"""
Created on Mon Dec 03 10:52:27 2018

@author: Administrator
"""

from numpy import array
import numpy as np
import math
import itertools

def QuadSeparateRange(data_range):
    """将某一范围分割成四分"""
    # data_range 某一数据范围，形式为[x_left,x_right,y_bottom,y_top]
    
    x_middle=str((float(data_range[0])+float(data_range[1]))/2.0) # x轴中间值
    y_middle=str((float(data_range[2])+float(data_range[3]))/2.0) # y轴中间值
    one_quadrant_range=[x_middle,data_range[1],y_middle,data_range[3]] # 第一象限范围
    two_quadrant_range=[data_range[0],x_middle,y_middle,data_range[3]] # 第二象限范围
    three_quadrant_range=[data_range[0],x_middle,data_range[2],y_middle] # 第三象限范围
    four_quadrant_range=[x_middle,data_range[1],data_range[2],y_middle] # 第四象限范围
    quadrant_range=[one_quadrant_range,two_quadrant_range,three_quadrant_range,four_quadrant_range]
    
    return quadrant_range
    
def ConstructTree(Raw_data_range,layer_number):
    #""获得四分树中各层各个结点的范围值""
    # Raw_data_range 原始数据范围，形式[x_left,x_right,y_bottom,y_top]
    # layer_number 四分树的高度
    
    range_list=[[] for _ in xrange(layer_number)] # 存放各层结点信息范围
    range_list[0].append(Raw_data_range)
    temp1=[Raw_data_range]
    level=1
    
    while (len(temp1)>0 and level<layer_number):
        for i in temp1:
            temp_list=QuadSeparateRange(i)
            range_list[level].extend(temp_list)
        temp1=range_list[level]
        level=level+1
        
    return range_list  


def GridSeparateRange(data_range,grid_number):
    """网格法分割某一范围"""
    # data_range 某一数据范围，形式为[x_left,x_right,y_bottom,y_top]
    # grid_number 网格个数
    
    number=int(math.sqrt(grid_number)) # x或y轴分割的区间个数
    x_interval=float(float(data_range[1])-float(data_range[0]))/number # x轴区间间隔
    y_interval=float(float(data_range[3])-float(data_range[2]))/number # y轴区间间隔
    
    x_coordinate=[] # 存放x轴区间范围
    y_coordinate=[] # 存放y轴区间范围
    separate_range=[] # 分割后各个范围列表
    
    for i in xrange (number):
        temp1=[float(data_range[0])+i*x_interval,float(data_range[0])+(i+1)*x_interval]
        temp2=[float(data_range[0])+i*y_interval,float(data_range[0])+(i+1)*y_interval]
        x_coordinate.append(temp1)
        y_coordinate.append(temp2)
    
    for z in itertools.product(x_coordinate,y_coordinate):
        temp_list=[z[0][0],z[0][1],z[1][0],z[1][1]]
        separate_range.append(temp_list)
    
    return separate_range,x_coordinate,y_coordinate
        
    
    
    
   