2016-07-21 ruki
The algorithm is based on libtess2 here and we optimizated some implementation and fixed some bugs. The differents between our algorithm and libtess2's algorithm: We change the coordinate system and the sweep direction (sweep line by horizontal here). We need not project the vertices because our graphic engine is 2d, 继续阅读 »
2015-04-24 刘太华
游戏服务端碰撞检测 最近看了一些游戏碰撞检测相关的一些内容,然后开始读了一些我们游戏里关于碰撞检测的代码,我们游戏里现在的碰撞检测按我暂时阅读完的代码, 应该分为2块,相对来说我们基本的碰撞检测算法是比较简单的, 后面也记录一下网上看到的关于分离轴多边形的碰撞检测。 继续阅读 »
2016-08-20 craneyuan
最近在研究算法,发现其实算法也并不是特别难,只要抓住算法的核心思想,再静下心来,都可以自己实现的。在计算机领域,有一些常见的而且又经常使用的算法,这些算法我们应该掌握,比如常见的排序算法;还有一些算法就是特定领域中经常使用的算法了,这些算法我们只有必须使用时再去学习使用就行了,比如图像处理中的快速傅里叶变换算法。 算法定义 让我们来看看算法的定义吧。(以下定义摘自中文维基百科) 在数学和计算机科学/算学之中,算法/演算法/算则法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。 算法中的指令描述的是一个计算,当其运 继续阅读 »
2014-01-17 W.Y.
最近整理了一些常见的排序算法,资料基本上都来自网上,大部分参考了维基百科,分析了常见算法的原理,并举例分步说明,有的还给出了排序动画演示,但没有涉及算法复杂度等方面的概念,最后对每一种排序算法都给出了至少一种 JavaScript 的实现方法(因为我是做前端方面的,所以只给出了 JavaScript 代码)。 由于自己能力和经验有限,难免出现某些纰漏和错误,欢迎指正。 日本程序员 norahiko,写了一个排序算法的动画演示,非常有趣。另外,今天一同事告诉我有一个排序算法的舞蹈,请点击【程序员的艺术:排序算法舞蹈】。 常见排序算法 - 冒泡排序 (Bubble Sort) 常见排序算法 - 快速排序 (Quick Sort) 继续阅读 »
2016-09-16 craneyuan
题目描述 给定一个已排序的数组,去除数组中的重复元素,只保留一个重复的元素,并且返回新的数组长度。 要求: 不要给数组分配额外的空间,你必须使用常量的内存大小进行原地操作。 例如: 给出数组A=[1,1,2],你的函数调用之后必须返回长度length=2,并且A现在变成[1,2]。 输入 一个已排序的数组,例如[1,1,2]。 输出 返回数组新的长度,例如length=2。 快慢指针法 设置fast指针遍历数组,slow指针指向不重复元素的下一位。 more java public static int removeDuplicates(int[] nums) { if (nums.length < 1) 继续阅读 »
2016-10-10 craneyuan
基本问题 如何将单链表反转? 单链表结构定义 ``` java /** 单链表定义 * * @author: crane-yuan * @date: 2016-9-17 下午12:11:13 */ public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } } ``` more 算法实现 java /** 单链表反转 * * @param head * @return ListNode */ public static ListNode rever 继续阅读 »
2016-08-29 craneyuan
定义 插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 more 算法步骤 插入排序算法的运作如下: 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复 继续阅读 »
2016-08-28 craneyuan
定义 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 more 算法步骤 冒泡排序算法的运作如下: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 伪代码如下: 继续阅读 »
2016-09-03 craneyuan
定义 快速排序(英语:Quick Sort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。 more 算法步骤 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为"基准"(pivot), 重新排序数列 继续阅读 »
2016-09-02 craneyuan
定义 希尔排序(英语:Shell sort),也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 more 算法步骤 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。 选择步长 按照选择的步长对序列进 继续阅读 »