1。确定照相机在世界坐标中的观察方向为 m_kCamDirection
 
2。确定被观察物体的世界位置为kTarget
 
3。将照相机沿着观察方向后退N给单位   - N * m_kCamDirection
 
4。将 kTarget加上   :      kTarget - N * m_kCamDirection

 
 
 

读书笔记
学习书目：《蝴蝶效应之谜：走近分形与混沌》-张天蓉;

分数维


在经典几何中，是用拓扑的方法来定义维数的，也就是说，空间的维数等于决定空间中任何一点位置所需要变量的数目。例如，所谓我们生活在三维空间，是因为我们需要三个数值：经度、纬度和高度来确定我们在空间的位置。


如上面所定义的拓扑维数，如何用分数维数才能解释像皮亚诺图形、科赫雪花、分形龙这些奇怪的几何图形呢？ 维数概念的扩展，要归功于德国数学家费利克斯·豪斯多夫。豪斯多夫在1919年给出了维数新定义，为维数的非整数化提供了理论基础。


在分形几何中，我们将拓扑方法定义的维数，扩展成用与自相似性有关的度量方法定义的维数。我们在之前的Blog中已经介绍了分形龙的自相似性，其实，经典整数维的几何图形，诸如一条线段、一个长方形、一个立方体，也具有这种自相似性，只不过，它们的自相似性太平凡而不起眼，被人忽略了而已。也就是说：线、面、体……这些我们常见的整数维几何形状，也算是分形.就像实数中包括了整数一样，扩展了的分形维数定义当然也包括了整数维在内。


用自相似性来定义维数，可以这么理解，首先将图形按照N∶1的比例缩小，然后，如果原来的图形可以由M个缩小之后的图形拼成的话，这个图形的维数d，也叫豪斯多夫维数，就等于：

$d=ln(M)/ln(N)$


我们以线、面、体为例，来解释豪斯多夫维数：




(a)中一条线段是由两个与原线段相似、长度一半的线段接成的；(b)中长方形自身可以看成是由4个与自己相似的，大小为四分之一的部分组成的；(c )中一个立方体，则可以看成是由8个大小为自身八分之一的小立方体组成的。
计算他们的豪斯多夫维数，分别为1维、2维、3维。


现在我们以同样的方法来计算科赫曲线的维数：




首先，将科赫曲线的尺寸缩小至原来的三分之一；然后，用4个这样的小科赫曲线，便能构成与原来一模一样的科赫曲线。因此，我们得到科赫曲线的维数$d＝ln4/ln3＝1.2618…$，这就说明了，科赫曲线的维数不是一个整数，而是一个小数，或分数……

快速排序

一、快排算法有什么优点，为什么称之为“快”排？

QuickSort是对归并排序算法的优化，继承了归并排序的优点，同样应用了分治思想。

1.如何“分”？（如何缩小问题的规模）

2.如何“治”？（如何解决子问题）

快排的前身是归并，归并的最大问题是需要额外的存储空间，并且由于合并过程不确定，致使每个元素在序列中的最终位置上不可预知的。针对这一点，快速排序提出了新的思路：把更多的时间用在“分”上，而把较少的时间用在“治”上。从而解决了额外存储空间的问题，并提升了算法效率。

快排之所以被称为“快”排，是因为它在平均时间上说最快的，主要原因是每趟快排需要指定一个“基准值”（也就是作为分界点的值），一趟中涉及的所有比较都是与这个“基准值”来进行比较的，效率自然大大提高。除此之外，快排的高效率与分治思想也是分不开的。

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

二、如何“分”？（即如何确定“基准值”）

确定一个“基准值”，将数组分为两个部分（比基准值小的 | 比基准值大的）

如何确定这个基准值呢？

1、随机

在所要排序的数组中，随机选取一个数来作为基准值，需要将其交换到最边上。

2、直接取最边上的值（任选左右）。

3、三数取中法

因为前两种取值方法，有大概率取到要排数组的最大值或者最小值，导致所分的两部分的其中一侧没有元素（选取最边上的元素作为基准值，并且数组已经有序或数组逆序，都是最坏情况），为了避免出现这种情况，我们采用三数取中法。

在[ left, left +(right -left)/2, right ] 中，通过判断，选取其中大小为 中 的元素。

例如：9 8 3 4 5 7 2  其下标 0~6  ，left = 0,mid = 3,right = 6; 比较array[left] ,array[mid] ,array[right],得到基准值为“4”。这样就有效避免了取到 极值 的可能。

代码如下：

private static int 三数取中(int[] array,int left, int right) {
        int mid = left +(right -left)/2;
        if (array[left] > array[right]){

            if(array[left] < array[mid]){

                return left;
            }else if (array[mid] > array[right]){

                return mid;
            }else{

                return right;
            }
        }else{
            if (array[right] < array[mid]){

                return right;
            }else if(array[mid] > array[left]){

                return mid;
            }else{

                return left;
            }
        }
    }

 

 如何将比基准值小的放左，大的放右？

1、Hover



代码如下：

//1、Hover
    private static int parition_01(int[] array,int left,int right){
        int begin = left;
        int end = right;
        int pivot = array[right];
        while (begin < end){
            while (begin <end && array[begin] < pivot){
                begin++;
            }

            while (begin < end && array[end] >= pivot){
                end--;
            }
            Swap(array,begin,end);
        }

        Swap(array,begin,right);

        return begin;
    }

Swap：

private static void Swap(int array[],int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }

 

2、挖坑法



代码如下：

//2、挖坑法
    private static int parition_02(int[] array,int left,int right){
        int begin = left;
        int end = right;
        int pivot = array[right];
        while (begin < end){
            while (begin <end && array[begin] < pivot){
                begin++;
            }
            array[end] = array[begin];

            while (begin < end && array[end] >= pivot){
                end--;
            }
            array[begin] = array[end];
        }

        array[begin] = pivot;

        return begin;
    }

3、前后下标



代码如下：

//3、前后下标
    private static int parition_03(int[] array,int left,int right){

        int back = left;
        int pivot = array[right];
        for (int i = left; i <= right; i++){
            if(array[i] < pivot){
                Swap(array,back,i);
                back++;
            }
        }

        Swap(array,back,right);
        return back;
    }

三、如何“治”？（怎么处理已经分好了的区间）



代码如下：

private static void quickSortInner(int[] array, int left, int right) {
        // 直到 size == 1 || size == 0
        if (left == right) {
            // size == 1
            return;
        }

        if (left > right) {
            // size == 0
            return;
        }

        // 要排序的区间是 array [left, right]
        // 1. 找基准值，array[right];
        int originIndex = sanShuQuZhong(array, left, right);
        swap(array, originIndex, right);

        // 2. 遍历整个区间，把区间分成三部分
        int pivotIndex = partition3(array, left, right);
        // 比基准值小的 [left, pivotIndex - 1]
        // 比基准值的 [pivotIndex + 1, right]

        // 3. 分治算法
        // 处理比基准值小的区间
        quickSortInner(array, left, pivotIndex - 1);
        // 处理比基准值大的区间
        quickSortInner(array, pivotIndex + 1, right);
    }

    public static void quickSort(int[] array) {
        quickSortInner(array, 0, array.length - 1);
    }


快速排序总结：

1.时空复杂度：快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。

实际应用中，快速排序的平均时间复杂度为O(nlogn)。快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度为      O(log（n）)。但需要注意递归栈上需要花费最少logn最多n的空间。

2.稳定性：不稳定