算法系列（九） 计算几何与图形学有关的几种常用算法（二）

2017年02月05日 51 阅读

算法系列（九） 计算几何与图形学有关的几种常用算法（二）2014-04-30 csdn博客 吹泡泡的小猫3.6 用矢量的叉积判断直线段是否有交矢量叉积计算的另一个常用用途是直线段求交。求交算 法是计算机图形学的核心算法，也是体现速度和稳定性的重要标志，高效并且稳定的求交算法是任何 一个CAD软件都必需要重点关注的。求交包含两层概念，一个是判断是否相交，另一个是求出交点。直 线（段）的求交算法相对来说是比较简单的，首先来看看如何判断两直线段是否相交。常规的 ...

算法系列（十） 直线生成算法

2017年02月05日 52 阅读

算法系列（十） 直线生成算法2014-04-30 csdn博客 吹泡泡的小猫在欧氏几何空间中，平面方程就是一个三元一次方程，直线就是两个非平行平面的交线，所以直线 方程就是两个三元一次方程组联立。但是在平面解析几何中，直线的方程就简单的多了。平面几何中 直线方程有多种形式，一般式直线方程可用于描述所有直线：Ax+By+C = 0 （A、B不同 时为0）当知道直线上一点坐标（X0，Y0）和直线的斜率K存在时，可以用点斜式方程：Y-Y0 = K（X &ndas...

算法系列（十一） 圆生成算法

2017年02月05日 49 阅读

算法系列（十一） 圆生成算法2014-04-30 csdn博客 吹泡泡的小猫在平面解析几何中，圆的方程可以描述为（x – x0）2 + （y – y0）2 = R2，其中（x0, y0）是圆心坐 标，R是圆的半径，特别的，当（x0, y0）就是坐标中心点时，圆方程可以简化为x2 + y2 = R2。在计算 机图形学中，圆和直线一样，也存在在点阵输出设备上显示或输出的问题，因此也需要一套光栅扫描 转换算法。为了简化，我们先考虑圆心在原...

算法系列（十二） 多边形区域填充算法－－递归种子填充算法

2017年02月05日 48 阅读

算法系列（十二） 多边形区域填充算法－－递归种子填充算法2014-04-30 csdn博客 吹泡泡的小猫平面区域填充算法是计算机图形学领域的一个很重要的算法，区域填充即给出一个区域的边界（也 可以是没有边界，只是给出指定颜色），要求将边界范围内的所有象素单元都修改成指定的颜色（也 可能是图案填充）。区域填充中最常用的是多边形填色，本文中我们就讨论几种多边形区域填充算法 。一、种子填充算法（Seed Filling）如果要填充的区域是以图像元数据方式给出的 ...

算法系列（十二） 多边形区域填充算法－－扫描线种子填充算法

2017年02月05日 56 阅读

算法系列（十二） 多边形区域填充算法－－扫描线种子填充算法2014-04-30 csdn博客 吹泡泡的小猫1.3扫描线种子填充算法1.1和1.2节介绍的两种种子填充算法的优点是非常简单，缺点是使 用了递归算法，这不但需要大量栈空间来存储相邻的点，而且效率不高。为了减少算法中的递归调用 ，节省栈空间的使用，人们提出了很多改进算法，其中一种就是扫描线种子填充算法。扫描线种子填 充算法不再采用递归的方式处理“4-联通”和“8-...

算法系列（十二）多边形区域填充算法：扫描线填充算法（有序边表法）

2017年02月05日 52 阅读

算法系列（十二）多边形区域填充算法：扫描线填充算法（有序边表法）2014-04-30 csdn博客 吹泡泡的小猫二、扫描线算法（Scan-Line Filling）扫描线算法适合对矢量图形进行区域填充，只需要 直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电 脑游戏和三维CAD软件的渲染等等。对矢量多边形区域填充，算法核心还是求交。《计算几何 与图形学有关的几种常用算法》一文给出了判断点与多边形关系的算法――扫描交点...

算法系列（十二） 多边形区域填充算法：改进的扫描线填充算法

2017年02月05日 53 阅读

算法系列（十二） 多边形区域填充算法：改进的扫描线填充算法2014-04-30 csdn博客 吹泡泡的小猫三、改进的扫描线填充算法扫描线填充算法的原理和实现都很简单，但是因为要同时维护 “活动边表（AET）”和“新边表（NET）”，对存储空间的要求比较高。这两张表的部分内容是重复 的，而且“新边表”在很多情况下都是一张稀疏表，如果能对其进行改进，避免出现两张表，就可以 节省存储空间，同...

算法系列（十二） 多边形区域填充算法：几种边标志填充算法

2017年02月05日 51 阅读

算法系列（十二） 多边形区域填充算法：几种边标志填充算法2014-04-30 csdn博客 吹泡泡的小猫四、边界标志填充算法在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一 个闭合区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边界标志填充 算法就是在逐行处理时，利用边界或边界颜色作为标志来进行填充的。准确地说，边界标志填充算法 不是指某种具体的填充算法，而是一类利用扫描线连贯性思想的填充算法的总称。这类算法有很多种 ，本篇...

算法系列（十三） 椭圆的生成算法

2017年02月05日 54 阅读

算法系列（十三） 椭圆的生成算法2014-04-30 csdn博客 吹泡泡的小猫椭圆和直线、圆一样，是图形学领域中的一种常见图元，椭圆的生成算法（光栅转换算法）也是图 形学软件中最常见的生成算法之一。在平面解析几何中，椭圆的方程可以描述为（x – x0）2 / a2+ （y – y0）2 / b2 = 1，其中（x0, y0）是圆心坐标，a和b是椭圆的长短轴，特别的，当（x0, y0）就是坐标 中心点时，椭圆方程可以简化为x2 / ...

算法系列（十四） 狼、羊、菜和农夫过河问题

2017年02月05日 53 阅读

算法系列（十四） 狼、羊、菜和农夫过河问题2014-04-30 csdn博客 吹泡泡的小猫题目描述：农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农 夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。 请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。这个题目考察人的快速逻辑运算和短期记忆力。分析一下，在狼－》羊－》菜这个食物链条中 ，“羊”处在关键位置，解决...

算法系列（十五） 循环和递归在算法中的应用

2017年02月05日 51 阅读

算法系列（十五） 循环和递归在算法中的应用2014-05-24 csdn 吹泡泡的小猫一、递归和循环的关系1、 递归的定义顺序执行、循环和跳转是冯·诺依曼计算机体 系中程序设计语言的三大基本控制结构，这三种控制结构构成了千姿百态的算法，程序，乃至整个软件世 界。递归也算是一种程序控制结构，但是普遍被认为不是基本控制结构，因为递归结构在一般情况下都可 以用精心设计的循环结构替换，因此可以说，递归就是一种特殊的循环结构。因为递归方法会直接或间接 ...

算法系列（十六） 使用穷举法解猜结果游戏

2017年02月05日 50 阅读

算法系列（十六） 使用穷举法解猜结果游戏2014-05-24 csdn博客 吹泡泡的小猫一、 引言穷举是解决问题的一种常用思路，当对一个问题无从下手的时候，可以考虑在问题 域允许的范围内将所有可能的结果穷举出来，然后根据正确结果的判断规则对这些结果逐个验证，从而找 出正确的结果。采用穷举的方法求解问题的答案比较适合计算机做，对这种体力活它们没有怨言，本文就 以常见的两个猜结果的题目为例，介绍一下如何通过计算机程序解决此类问题，顺便介绍一下穷举法常见 的算法...

算法系列（十七） 日历生成算法-中国公历（格里历）（上）

2017年02月05日 54 阅读

算法系列（十七） 日历生成算法-中国公历（格里历）（上）2014-05-24 csdn博客 吹泡泡的小猫日历在我们的生活中扮演着十分重要的角色，上班、上学、约会都离不开日历。每年新年开始，人们 都要更换新的日历，你想知道未来一年的这么多天是怎么被确定下来的吗？为什么去年的国庆节是星期五 而今年的国庆节是星期三？那就来研究一下日历算法吧。本文将介绍日历的编排规则，确定某日是星期几 的计算方法，以及如何在计算机上打印某一年的年历。要研究日 历算法，首先要知道日...

算法系列（十七） 日历生成算法-中国公历（格里历）（下）

2017年02月05日 51 阅读

算法系列（十七） 日历生成算法-中国公历（格里历）（下）2014-05-24 csdn博客 吹泡泡的小猫【接上篇】上述计算星期的方法虽然步骤简单，但是每次都要计算两个日期的时间差，不是非 常方便。如果能够有一个公式可以直接根据日期计算出对应的星期岂不是更好？幸运的是，这样的公式是 存在的。此类公式的推导原理仍然是通过两个日期的时间差来计算星期，只是通过选择一个特殊的日期来 简化公式的推导。这个所谓的特殊日期指的是某一年的12月31日这天刚好是星期日这种情况...

算法系列（十八） 用天文方法计算二十四节气（上）

2017年02月05日 48 阅读

算法系列（十八） 用天文方法计算二十四节气（上）2014-05-24 csdn博客 吹泡泡的小猫二十四节气在中国古代历法中扮演着非常重要的角色，本文将介绍二十四节气的基本知识，以及如何 使用VSOP82/87行星运行理论计算二十四节气发生的准确时间。中国古代历法都是以月亮运行规律 为主，严格按照朔望月长度定义月，但是由于朔望月长度和地球回归年长度无法协调，会导致农历季节和 天气的实际冷暖无法对应，因此聪明的古人将月亮运行规律和太阳运行规律相结合制定了中国农...

算法系列（十八） 用天文方法计算二十四节气（下）

2017年02月05日 47 阅读

算法系列（十八） 用天文方法计算二十四节气（下）2014-05-24 csdn博客 吹泡泡的小猫【接上篇】经过上述计算转换得到坐标值是理论值，或者说是天体的几何位置，但是FK5系统 是一个目视系统，也就是说体现的是人眼睛观察效果（光学位置），这就需要根据地球的物理环境、大气 环境等信息做进一步的修正，使其和人类从地球上观察星体的观测结果一致。首先需要进行章动 修正。章动是指地球沿自转轴的指向绕黄道极缓慢旋转过程中，由于地球上物质分布不均匀性和月球及其 它行...

算法系列（十九） 用天文方法计算日月合朔（新月）

2017年02月05日 49 阅读

算法系列（十九） 用天文方法计算日月合朔（新月）2014-05-24 csdn博客 吹泡泡的小猫中国农历的朔望月是农历历法的基础，而朔望月又是严格以日月合朔发生的那一天作为月首，因此日 月合朔时间的计算是制定农历历法的关键。本文将介绍ELP-2000/82月球运行理论，以及如何用ELP- 2000/82月球运行理论计算日月合朔时间。要计算日月合朔时间， 首先要对日月合朔这一天文现象进行数学定义。朔望月是在地球上观察到的月相周期，平均长度约等于 29.530...

算法系列（二十） 计算中国农历（一）

2017年02月05日 54 阅读

算法系列（二十） 计算中国农历（一）2014-05-24 csdn博客 吹泡泡的小猫世界各国的日历都是以天为最小单位，但是关于年和月的算法却各不相同，大致可以分为三类：阳历--以天文年作为日历的主要周期，例如：中国公历（格里历）阴历--以天文月作为日 历的主要周期，例如：伊斯兰历阴阳历--以天文年和天文月作为日历的主要周期，例如：中国农 历我国古人很早就开始关注天象，定昼夜交替为“日”，月轮盈亏为“月”，寒暑...

算法系列（二十） 计算中国农历（二）

2017年02月05日 52 阅读

算法系列（二十） 计算中国农历（二）2014-05-24 csdn博客 吹泡泡的小猫所谓的“天文算法”，就是利用经典力学定律推导行星运转轨道，对任意时刻的行星位置进行精确计 算，从而获得某种天文现象发生时的时间，比如日月合朔这一天文现象就是太阳和月亮的地心黄经（视黄 经）差为0的那一瞬间。能够计算任意时刻行星位置的一套理论就被称为星历表，比较著名的星历表有美 国国家航空航天局下属的喷气推进实验室发布的DE系列星历表，还有瑞士天文台在...

哈弗曼树与哈弗曼编码

2017年02月05日 51 阅读

哈弗曼树与哈弗曼编码2014-05-24 iteye cq520哈弗曼，一个在几乎所有讲数据结构的书中都有出现过的人物，他的鼎鼎大名想必就不用我多说了。 这一次来给大家讲解一下哈弗曼树的构建与哈弗曼编码的基本原理，有什么用呢？别急，还是先学会创建 一棵哈弗曼树吧。哈弗曼树又称最优二叉树，最优二叉树就是带权路径长度WPL最小的二叉树，那么我们就得搞清几个概 念：1. 路径长度：从树中的一个结点到另一个结点之间的分支构成这两个结点的路径，路径上的分支数目 称为...