多边形的扫描转换 图形学中多边形有两种表示方法：多边形的顶点表示与点阵表示。顶点表示用多边形的顶点序列来刻画多边形；点阵表示则是用位于多边形内的像素的 集合来刻画多边形。 扫描转换多边形或多边形的填充：从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存中相应单元的过程。 x-扫描线算法 基本思想：如下图所示，按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的所有像素。 图5-8 x-扫描线算法填充多边形 算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。 (2)从y=ymin到y=ymax，每次用一条扫描线进行填充。填充过程可分为四个步骤： a.求交：计算扫描线与多边形各边的交点； b.排序：把所有交点按照递增顺序进行排序； c.交点配对：交点两两配对，表示扫描线与多边形的一个相交区间； d.区间填色：将相交区间内的像素置成不同于背景色的填充色。 存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。如下图所示，在扫描线y=1，y=5和y=7时，扫描线过多边形的顶点，若不加以处理，交点配对时会发生错误。
图5-9 与多边形相交的交点的处理 解决方法：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。实际处理时，只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 改进的有效边表算法 由于x-扫描线算法在处理每条扫描线时，需要与多边形所有的边求交，效率很低，因此需要加以改进，形成改进的有效边表算法。 改进原理： (1)处理一条扫描线时，仅对有效边求交。 (2)利用扫描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似。 (3)利用多边形边的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线也相交：若边的直线斜率为k，这样边与两条相邻扫描线的交点有如下关系：xi+1=xi+1/k。 图5-10 与多边形边界相交的两条连续扫描线交点的相关性 有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点为：
正多边形的有关计算 一、素质教育目标 (一)知识教学点 使学生学会将正多边形的边长、半径、边心距和中心角、周长、面积等有关的计算问题转化为解直角三角形的问题． (二)能力训练点 1．通过定理的证明过程培养学生观察能力、推理能力、概括能力； 2．通过一定量的计算，培养学生正确迅速的运算能力； 3．通过用不同方法求正多边形的内角，培养学生的发散思维能力和选优意识； 4．从具体边数的正n边形得到一般正n边形的计算图培养学生化归、转化的数学思想． (三)德育渗透点 1．由具体边数的正多边形计算图过渡到一般计算图，渗透了“从特殊到一般，再由一般到特殊”的辩证唯物主义认识观； 2．正多边形计算图的得出渗透了化繁为简、化难为易二矛盾相互依存、相互转化的思想； 3．通过正多边形的有关计算，培养学生仔细认真、一丝不苟、严谨的科学态度； 4．通过正多边形有关计算公式的推导，培养学生不断探索科学奥秘的创新精神． 二、教学重点、难点、疑点及解决方法 1．重点：1．化正多边形的有关计算为解直角三角形问题定理．2．正多边形计算图及其应用． 2．难点：正确地将正多边形的有关计算问题转化为解直角三角形的问题解决、综合运用几何知识准确计算．
3．疑点及解决方法：学生对只画出正n边形的一部分图形的计算图生疏，用它分析、计算有疑虑．为此计算图的抽象应由具体边数的正多边形计算图逐步过渡． 三、教学步骤 (一)明确目标 前几课我们学习了正多边形的定义、概念、性质，今天我们来学习正多边形的有关计算． (二)整体感知 大家知道正多边形在生产和生活中有广泛的应用性，伴随而来的有关正多边形计算问题必然摆在大家的面前，如何解决正多边形的计算问题，正是本堂课研究的课题． (三)重点、难点的学习与目标完成过程 哪位同学回答，什么叫正多边形．(安排中下生回答：各边相等，各角相等的多边形．) 什么是正多形的边心距、半径？(安排中下生回答：正多边形内切圆的半径叫做边心距．正多边形外接圆的半径叫做正多边形的半径．) 正多边形的边有什么性质、角有什么性质？(安排中下生回答：边都相等，角都相等．) 什么叫正多边形的中心角？(安排中下生回答：正多边形的一边所对正多边形外接圆的圆心角．) 正n边形的中心角度数如何计算？(安排中下生回答：中心角的度数 正n边形的一个外角度数如何计算？(安排中下生回答：一个外角度 哪位同学有所发现？(安排举手学生：正n边形的中心角度数=正n边形的一个外角度数．)
运动目标检测之Lucas-Kanade 光流算法读书笔记 视觉是人类感知自身周围复杂环境最直接有效的手段之一，而在现实生活中大量有意义的视觉信息都包含在运动中，人眼对运动的物体和目标也更敏感，能够快速的发现运动目标。随着计算机技术、通信技术、图像处理技术的不断发展，计算机视觉己成为目前的热 点研究问题之一。而运动目标检测是计算机视觉研究的核心课题之一，融合了图像处理、模式识别、人工智能、自动控制、计算机等众多领域的先进技术，在军事制导、视觉导航、视频监控、智能交通、医疗诊断、工业产品检测等方面有着重要的实用价值和广阔的发展 前景。 一目标检测 运动目标检测运动目标检测是指从序列图像中将运动的前景目标从背景图像中提取出 来。目前,已有的运动目标检测方法按照算法的基本原理可以分为三类:背景差分法，帧间差 分法和光流法。 1 背景差分法 背景差分法又称背景减除法，背景差分法的原理是将当前帧与背景图像进行差分来得到 运动目标区域，但是需要构建一幅背景图像，这幅背景图像必须不含运动目标，并且应该能不断的更新来适应当前背景的变化，构建背景图像的方法有很多，比较常用的有基于单个高 斯模型的背景构建，基于混合高斯模型的背景构建，基于中值滤波器的背景构造，基于卡尔曼滤波器的背景构造，基于核函数密度估计的背景模型构造。 缺点：因为要求背景是静止的，所以背景的变化，场景中有很多干扰，比如场景中 有树枝和叶子在风中晃动、水面的波动等等，还有照明的变化和天气的变化等都可能影响检 测的结果 2 帧间差分法 帧间差分法是一种通过对视频图像序列中相邻两帧作差分运算来获得运动目标轮廓的 方法，它可以很好地适用于存在多个运动目标和摄像机移动的情况。当监控场景中出现异常 物体运动时，帧与帧之间会出现较为明显的差别，两帧相减，得到两帧图像亮度差的绝对值，
运动目标检测之Lucas-Kanade光流算法读书笔记 视觉是人类感知自身周围复杂环境最直接有效的手段之一，而在现实生活中大量有意义的视觉信息都包含在运动中，人眼对运动的物体和目标也更敏感，能够快速的发现运动目标。随着计算机技术、通信技术、图像处理技术的不断发展，计算机视觉己成为目前的热点研究问题之一。而运动目标检测是计算机视觉研究的核心课题之一，融合了图像处理、模式识别、人工智能、自动控制、计算机等众多领域的先进技术，在军事制导、视觉导航、视频监控、智能交通、医疗诊断、工业产品检测等方面有着重要的实用价值和广阔的发展前景。 一目标检测 运动目标检测运动目标检测是指从序列图像中将运动的前景目标从背景图像中提取出来。目前,已有的运动目标检测方法按照算法的基本原理可以分为三类:背景差分法，帧间差分法和光流法。 1背景差分法 背景差分法又称背景减除法，背景差分法的原理是将当前帧与背景图像进行差分来得到运动目标区域，但是需要构建一幅背景图像，这幅背景图像必须不含运动目标，并且应该能不断的更新来适应当前背景的变化，构建背景图像的方法有很多，比较常用的有基于单个高斯模型的背景构建，基于混合高斯模型的背景构建，基于中值滤波器的背景构造，基于卡尔曼滤波器的背景构造，基于核函数密度估计的背景模型构造。 缺点：因为要求背景是静止的，所以背景的变化，场景中有很多干扰，比如场景中有树枝和叶子在风中晃动、水面的波动等等，还有照明的变化和天气的变化等都可能影响检测的结果 2帧间差分法 帧间差分法是一种通过对视频图像序列中相邻两帧作差分运算来获得运动目标轮廓的方法，它可以很好地适用于存在多个运动目标和摄像机移动的情况。当监控场景中出现异常物体运动时，帧与帧之间会出现较为明显的差别，两帧相减，得到两帧图像亮度差的绝对值，
简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前 裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。 三、新算法设计 1、算法的思想 本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。 2、主要数据结构 多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示，
2018年6月图 学 学 报 June2018第39卷第3期JOURNAL OF GRAPHICS V ol.39No.3一种视频微表情检测的改进光流算法 李秋宇1，张玉明2，杨福猛3，詹曙1 (1. 合肥工业大学计算机与信息学院，安徽合肥 230009； 2. 芜湖职业技术学院电气工程学院，安徽芜湖 241000； 3. 安徽信息工程学院，安徽芜湖 241000) 摘要：微表情是人们在试图隐藏自己真实情感时表现出的不受自主神经控制、持续时间短暂，强度十分微弱的面部表情。由于微表情与谎言识别有着密切的联系，其公共安全、侦查讯问、临床医学等领域有很大的应用前景。针对人为识别微表情十分困难的问题，提出一种基于Horn-Schunck (HS)光流法改进并应用于微表情自动检测的方法。使用预条件Gauss-Seidel迭代方法改进了HS光流法，加快了收敛速度。通过在自发微表情数据库CASME中进行实验，该验证方法在微表情检测中有很好的效果。 关键词：微表情检测；光流法；预条件迭代 中图分类号：TP 391 DOI：10.11996/JG.j.2095-302X.2018030448 文献标识码：A 文章编号：2095-302X(2018)03-0448-05 An Improved Optical Flow Algorithm for Micro Expression Detection in the Video Sequence LI Qiuyu1, ZHANG Yuming2, YANG Fumeng3, ZHAN Shu1 (1. School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China; 2. School of Electrical Engineering, Wuhu Institute of Technology, Wuhu Anhui 241000, China; 3. Anhui Institute of Information Technology, Wuhu Anhui 241000, China) Abstract: Micro-expression is a kind of short-duration subtle expression which is not controlled by the autonomic nervous system. Micro-expression appears when a person is attempting to conceal his true emotion. Micro-expression detection boasts great application prospects in many fields, such as public security, investigation and interrogation as well as clinical medicine due to its close relationship with lie detection. Automatic detection of micro-expressions has come to the fore in research, because it is of great difficulty to artificially identify micro-expression . This paper proposes an improved algorithm based on the Horn-Schunck (HS) optical flow for automatic micro-expression detection. In this study, the pre-conditioned Gauss-Seidel iterative method is employed to improve the HS optical flow method, which accelerates the convergence rate. Experiments in the spontaneous micro-expression database CASME show that the propounded method exerts an excellent effect on the detection of micro-expression. Keywords: micro-expression detection; optical flow; preconditioned iteration 第一作者：李秋宇(1993-)，男，安徽霍邱人，硕士研究生。主要研究方向为计算机视觉、深度学习。E-mail：lqy@https://www.doczj.com/doc/137273729.html, 通信作者：詹曙(1968-)，男，安徽合肥人，教授，博士。主要研究方向为三维人脸图像分析和识别、医学影像分析和医学成像系统。 E-mail：shu_zhan@https://www.doczj.com/doc/137273729.html, 万方数据
Weiler－Atherton任意多边形裁剪 Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。 一、Weiler－Atherton任意多边形裁剪算法描述： 在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。 裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称： 1、被裁剪多边形为主多边形，记为A； 2、裁剪窗口为裁剪多边形，记为B。 主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域： 1、A∩B（交：属于A且属于B）； 2、A－B（差：属于A不属于B）； 3、B－A（差：属于B不属于A）； 4、A∪B(并：属于A或属于B，取反；即：不属于A且 不属于B)。 内裁剪即通常意义上的裁剪，取图元位于窗口之内的部 分，结果为A∩B。 外裁剪取图元位于窗口之外的部分，结果为A－B。 观察右图不难发现裁剪结果区域的边界由被裁剪多边形的 部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边 界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界， 或者反之。由于多边形构成一个封闭的区域，所以，如果被裁 剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类： 一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e； 一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。 二、Weiler－Atherton任意多边形裁剪算法思想：
基于变分网格的曲面简化高效算法? 金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江杭州 310027) An Efficient Method for Surface Simplification Based On Variational Shape Approximation* JIN Yong, WU Qing-biao+, LIU Li-gang (Department of Mathematics, Zhejiang University, Hangzhou 310027, China) + Corresponding author: E-mail:qbwu@https://www.doczj.com/doc/137273729.html, Abstract:Providing fast and accurate simplification method for large polygon mesh is one of the most important research focuses in computer graphics. Approximating mesh model with a few polygons can improve the rendering speed, and reduce the storage of the model. The paper presents a local greedy algorithm to minimize the energy defined by variational shape approximation. The algorithm simplifies the mesh by controlling the number of the target polygons, while attempting to get ideal effect by adaptive seed triangles selection. The algorithm has intuitive geometric meaning. The method is efficient enough to be efficiently adopted in the geometric modeling system. Key words: Polygon mesh simplification; variational shape approximation; greedy algorithm; geometric modeling 摘要: 为大型的多边形网格模型提供快速、准确的简化算法是计算机图形学中的一个重要的研究方面.以较少的多边形逼近表示网格模型,能够提高模型的绘制速度,减小模型的存储空间.本文根据变分网格逼近表示所定义的全局误差能量,提出一种局部贪心优化算法,该算法通过控制目标网格分片数来简化网格,通过种子的自适应选取以达到理想的简化效果,具有直观的几何意义.本文方法计算量少,效率较高,能够有效应用于几何造型系统中. 关键词:多边形网格简化;变分网格逼近;贪心算法;几何造型 中图法分类号: TP391文献标识码: A 1 引言 三维多边形网格模型,包括三角形网格、四边形网格等,在计算机辅助几何设计、计算机动画、虚拟现实、计算机游戏和医学影像等领域有着大量的应用.随着三维扫描技术的发展,顶点数为数万的模型已经非常常见, ?Supported by the National Natural Science Foundation of China under Grant No.10871178, 60776799 (国家自然科学基金); Technology Department of Zhejiang Province Grant No. 2008C01048-3(浙江省重大科技创新项目) 作者简介: 金勇(1985－),男,上海人,博士研究生,主要研究领域为数字几何处理和计算机辅助几何设计;吴庆标(1963－),男, 浙江台州人,博士,教授,博士生导师,主要研究领域为图形与图像处理,数值计算方法,高性能并行计算和计算机模拟; 刘利刚(1975－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理.
Lync.in Link the world. Home About Projects SimpleDark 2009-09-24 / Chris posted in A lgorithm / 397 Views / 16 Comments 前些天在考虑一个几何算法，关于如何判断一个点是否在一个给定的多边形内部。这应该是一个比较常规的算法，我以前对几何算法了解的不多，所以既然想到了就稍微研究了一下。 查了一下相关的资料，目前有几个O(N)的算法，其中N是多边形的顶点数。 第一个叫做交替（Alternative）算法。如下图所示 算法检查所给定的点和在该点右边的多边形区域的边界的交点数，若交点数为奇数，则该点在多边形内部，若交点数为偶数，则该点在多边形外部。可以想象成从一个点向右发出一条射线，然后计算这条射线与多边形边界的交点数。从上图中标出的蓝色点向右射出的射线与多边形有1个交点，故判定其在多边形内部，而从标出的白色点向右射出的射线则有偶数个交点，故判定其在多边形外部。 这个算法的叙述起来很平常，但实现起来却有两个略带Tricky的地方。 其一是坐标精度引起的，因为计算机对于坐标的描述是离散的，在计算向右射出的射线与多边形交点的时
候很容易出现射线与多边形的某几条边平行的情况，对于这种情况，我们的算法需要向前多看几个点，以确定射线是确实与多边形相交还是只是“擦过”而已。 其二是对于非常靠近多边形边界的点的判定，你可以认为这些点是在多边形外，也可以认为是在多边形内，但你必须在算法中描述这些情况。 感兴趣的可以了解一下我的算法实现，附在文末。 这个算法在多边形为简单多边形的情况下是没有异议的，但在复杂多边形的情况下会有一些疑问，这涉及到“在多边形内还是多边形外”的定义问题。如下图 图中，如果用Alternative算法，则被多边形包围的那个点被判断为在多边形外部。 如果你认为这种定义不符合你的需要，那么有另外一种算法，称为Winding算法。 Winding算法的思路是这样的，将你置身于所给定的点上，然后让你的视线从多边形边界上的一点开始，选择一个方向绕着多边形的边界转一圈，如果你发现你的身体在这个过程中转了360度的非零整数倍，那么你所站在的这个点在多边形的内部，如果你的身体并没有转动（事实上你转动了，只是正向和逆向的转动抵消了），那么就在多边形的外部。 这个算法我没有去实现，一般来说它要比Alternative算法慢，因为它需要计算每条多边形的边与多给定的点之间的夹角。 关于算法实现： 程序的界面是用WTL写的，如果你想要编译源代码，请在Visual Studio中指定WTL的include文件夹位置。 算法核心代码如下，其中vSelectionPoints是多边形
基于蚁群算法的连续函数优化通用MATLAB源代码 此源码是对人工蚁群算法的一种实现，用于无约束连续函数的优化求解，对于含有约束的情况，可以先使用罚函数等方法，把问题处理成无约束的模型，再使用本源码进行求解。 function [BESTX,BESTY,ALLX,ALLY]=ACOUCP(K,N,Rho,Q,Lambda,LB,UB) %% Ant Colony Optimization for Unconstrained Continuous Problem %% ACOUCP.m %% 无约束连续函数的蚁群优化算法 %% 此函数实现蚁群算法，用于求解无约束连续函数最小化问题 %% 对于最大化问题，请先将其加负号转化为最小化问题 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.doczj.com/doc/137273729.html,/greensim %% 输入参数列表 % K 迭代次数 % N 蚁群规模 % Rho 信息素蒸发系数，取值0～1之间，推荐取值0.7～0.95 % Q 信息素增加强度，大于0，推荐取值1左右 % Lambda 蚂蚁爬行速度，取值0～1之间，推荐取值0.1～0.5 % LB 决策变量的下界，M×1的向量 % UB 决策变量的上界，M×1的向量 %% 输出参数列表 % BESTX K×1细胞结构，每一个元素是M×1向量，记录每一代的最优蚂蚁 % BESTY K×1矩阵，记录每一代的最优蚂蚁的评价函数值 % ALLX K×1细胞结构，每一个元素是M×N矩阵，记录每一代蚂蚁的位置 % ALLY K×N矩阵，记录每一代蚂蚁的评价函数值 %% 测试函数设置 % 测试函数用单独的子函数编写好，在子函数FIT.m中修改要调用的测试函数名即可 % 注意：决策变量的下界LB和上界UB，要与测试函数保持一致 %% 参考设置 % [BESTX,BESTY,ALLX,ALLY]=ACOUCP(50,30,0.95,1,0.5,LB,UB) %% 第一步：初始化 M=length(LB);%决策变量的个数 %蚁群位置初始化 X=zeros(M,N); for i=1:M x=unifrnd(LB(i),UB(i),1,N); X(i,:)=x; end %输出变量初始化 ALLX=cell(K,1);%细胞结构，每一个元素是M×N矩阵，记录每一代的个体 ALLY=zeros(K,N);%K×N矩阵，记录每一代评价函数值
再经典不过的算法了： // 功能：判断点是否在多边形内 // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! //参数： // POINT p 指定的某个点 // LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致） // int nCount 多边形定点的个数 BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount) { int nCross = 0; for (int i = 0; i < nCount; i++) { POINT p1 = ptPolygon[i]; POINT p2 = ptPolygon[(i + 1) % nCount]; // 求解y=p.y 与p1p2 的交点 if ( p1.y == p2.y ) // p1p2 与y=p0.y平行 continue; if ( p.y < min(p1.y, p2.y) ) // 交点在p1p2延长线上 continue; if ( p.y >= max(p1.y, p2.y) ) // 交点在p1p2延长线上 continue; // 求交点的X 坐标-------------------------------------------------------------- double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x; if ( x > p.x ) nCross++; // 只统计单边交点 } // 单边交点为偶数，点在多边形之外--- return (nCross % 2 == 1); }
模型的建立与求解 一、计算凸多边形的重心 对于任意凸多边形，我们以其重心为蛛网的中枢区中心，也即蜘蛛的等待猎物点，以此点出发，先发出放射丝，再织捕丝。 1.计算任意凸多边形重心的理论基础 1. 四边形的重心作法：连接出四边形的一条对角线，这样四边形就变成两个三角形的组合体，分别作出两个三角形的重心，并连接两个重心成一条线段AB ，同样，连接出四边形的另一条对角线，四边形就变成另外两个三角形的组合体，分别作出这两个三角形的重心，并连接两个重心成一条线段CD ，则线段AB ，CD 的交点就是四边形的重心。 2.五边形的重心作法：连接出五边形的任一条对角线，将五边形分为1个三角形与一个四边形组合体，分
别作出三角形的重心，和四边形的重心，并连成线段AB；连接五边形的另外一条对角形，将五边形分为另1个三角形与四边形的组合体，分别作出三角形与四边形的重心，并连接成线段CD；则AB、CD的交点就是五边形的重心。 3、用数学归纳法，对于六边形、七边形，N边形，都可以用上述方法，先连接出一条对角线，将N边形化为一个三角形与(N-1)边形，或四边形与(N-2)边形，然后分别作出重心，并连接成线段，然后再连接另外一条对象线，分别作出两个组合体的重心并连接成线段，两条线段的交点就是N边形的重心。 2．重心计算的算法程序实现： 有了以上理论基础，我们通过C++语言编写了一个计算任意凸多边形的程序，算法思想如下，算法程序见附录一。
○1在平面上取一点(一般取原点)得到N个三角形OP[i]P[i+1](其中点的顺序为逆时针) ○2分别求出这N个三角形的重心Ci和面积Ai(注意此处面积是有向面积, 就是用叉乘求面积时保留其正负号) ○3求出A = A1+A2+...+AN(同样保留正负号的代数相加) ○4重心C = sigma(Ai+Ci)/A; 附录一：任意凸多边形重心C++算法 #include
正多边形的计算之万法归宗解直角三角形 仪陇县银山初级中学董兴胜各边相等、各角也相等的多边形叫做正多边形，正多边形的外接圆和内切圆的圆心重合叫正多边形的中心。外接圆半径叫正多边形的半径.内切圆的半径叫正多边形的边心距。正多边形的每 一边所对的圆心角叫中心角,中心角的度数是 n 360。 笔者在教学中，发现学生对涉及有关正多边形的计算时，比如计算正多边形的边长，半径，正多边形的周长，正多边形的面积，或者是两个正多边形有关比值的计算，往往无从下手，表现在一遇到题就去画图，下手就算，既费时，又方向不清，结果往往是无功而返。通过多年的教学经验总结，提出了化归思想，即任何正多边形的计算问题都可以转化为一个重要的直角三角形，从而将正多边形的问题转化为解直角三角形的问题。 首先来认识一下正多边形的基本知识，仅以N＝３，４５６为例。 一计算正N边形的内角（如下图） 很容易知道正n边形的每个内角都等于 二将正N边形分割成等腰三角形（如下图所示） 设O为各正多边形的中心，即外接圆和内切圆的圆心，正n边形的n条半径分正n边形为n个全等的等腰三角形． 三将正N边形分割成直角三角形（如下图所示）
这一步只需要作正多边形的边心距，边心距又把上一步n 个等腰三角形分成了个２N 个直角三角形，这些直角三角形也是全等 的．因此正n 边形的半径和边心距把正n 边形分成2n 个全等的直角三角形。 通过这三步，实质是把正多边形的问题向直角三角形转化．由于这些直角三角形的斜边都是正n 边形的半径R ，一条直角边是正n 边形的边心距r n ，另一条直角边是正n 边形边长a n 的一半，一 个锐角是正n 边形中心角 的一半，即 ，所以，就把正n 边形的有关计算归结为解直角三角形问题．为了让学生理解深刻，容易记忆，笔者特总结出如下的口诀和图形： 一个中心，两条半径， 两半径之夹角等于中心角之一半，半径夹角之对边等于边长之一半
多边形裁剪的Sutherland—Hodgman算法 1>. Sutherland—Hodgman多边形裁剪算法思想 该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，…，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。 当多边形一个顶点Pi相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）： 1、顶点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列； 2、顶点Pi在内侧，前一顶点Pi-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列； 3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列； 4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。 2>. Sutherland—Hodgman多边形裁剪算法步骤 考虑多边形相对于一条边界及其延长线进行裁剪的算法： 1．从主函数得到待裁剪多边形的顶点序列P[][2]、顶点序列数n、窗口一条边界参数xl（假如为矩形窗口的左边界）； 2．赋初值： 将顶点序列中的最后一个顶点赋给前一顶点S； 设置初始标志flag： if(S在边界内侧)flag=0;
else flag=1； 设新的顶点序列数j=0； 3．对多边形各顶点进行裁剪规则处理，结果放入新的多边形顶点序列 Q[][2]中： for(对第一个顶点直到最后一个顶点，逐一处理）{if(Pi在边界内 侧){if(flag!=0){flag=0; 求交点并放入新的多边形顶点序列Qjxx； j++；}将当前顶点放入新的多边形顶点序列Qj中： Qj=Pi； j++；}else{if(flag==0){flag=1; 求交点并放入新的多边形顶点序列Qjxx； j++；}} 将当前顶点赋给S： S=Pi；} 4．做返回准备： 将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中： P=Q； 将新的多边形顶点数j放回原多边形顶点数n中： n=j； //////////////////////////////////////////////////////////////////////////////////// // //-----多边形裁剪的Sutherland—Hodgman算法---------//
19.3梯形 等腰梯形的性质 【导学目标】 1．知道梯形、等腰梯形、直角梯形的有关概念；能说出并证明等腰梯形的两个性质；等腰梯形同一底上的两个角相等；两条对角线相等。 2．会运用梯形的有关概念和性质进行有关问题的论证和计算。 3．通过添加辅助线，把梯形的问题转化成平行四边形或三角形问题，体会图形变换的方法和转化的思想。 【导学重点】 探索梯形的有关概念、性质及其应用。 【导学难点】 探索等腰梯形的性质。 【导学指导】 学习教材P106-P107相关内容，完成下列问题： 一、自主学习 1.什么是梯形？什么是梯形的上底？什么是梯形的下底？什么是梯形是高？什么是梯形 的腰？ 2.什么是等腰梯形？什么是直角梯形？ 二、合作学习 等腰梯形有哪些性质？你是如何发现的？你能证明它吗？三、训练为能 1、在梯形ABCD中，已知AD∥BC，∠B=50°，∠C=80°，AD=a,BC=b,则DC= 。 2、直角梯形的高为6cm,有一个角是30°，则这个梯形的两腰分别是和。 3、等腰梯形ABCD中，AB∥CD，AC平分∠DAB，∠DAB=60°，若梯形周长为8cm，则AD= . 4、等腰梯形ABCD中，AB=2CD，AC平分∠DAB，AB=4√3， （1）求梯形的各角。 （2）求梯形的面积。 5、如图在等腰梯形ABCD中，AD∥BC，AD=DC=AB，BD=BC，求∠A的度数. D C B A A B C D 6、.①在梯形ABCD中，AD∥BC，对角线AC⊥BD，且AC=5，BD=12，求梯形中位线的长②若AD=2，BC=3，E、F分别为AC、BD中点，求EF. 7、下列命题中，真命题是（） A、有一组对边平行但不相等的四边形是梯形 B、直角梯形中只有一个直角 C、等腰梯形的对角线相等且互相垂直 D、等腰梯形是轴对称图形，有两条对称轴 8、如图,在梯形ABCD中，∠D=90°，AD=DC=4，AB=1，E为AD的中点，则点E到BC的距离为___________. 四、小结反思 本节课你有哪些收获，与同伴交流一下。 五、拓展练习 如图：已知在等腰梯形ABCD中，对角线AC=BC+AD，求∠DBC的度数。 B C
问：土方10m*10m,挖深2m,放坡系数1:0.5,旁边有个土方5m*5m,挖深2m,放坡系数1:0.5,求总体积？ 答：V=(s1+s2+根下s1*s2)h/3 s1上底面积 S2下底面积， V1=（10*10+8*8+12.8）*2/3= V2=(5*5+3*3+5.8)*2/3= V=V1+V2 土方量计算方法 土方量的计算是建筑工程施工的一个重要步骤。工程施工前的设计阶段必须对土石方量进行预算,它直接关系到工程的费用概算及方案选优。在现实中的一些工程项目中，因土方量计算的精确性而产生的纠纷也是经常遇到的。如何利用测量单位现场测出的地形数据或原有的数字地形数据快速准确的计算出土方量就成了人们日益关心的问题。比较经常的几种计算土方量的方法有：方格网法、等高线法、断面法、DTM法、区域土方量平衡法和平均高程法等。 1、断面法 当地形复杂起伏变化较大，或地狭长、挖填深度较大且不规则的地段，宜选择横断面法进行土方量计算。 上图为一渠道的测量图形，利用横断面法进行计算土方量时，可根据渠LL，按一定的长度L设横断面A1、A2、A3……Ai等。 断面法的表达式为 (1) 在（1）式中，Ai-1，Ai分别为第i单元渠段起终断面的填(或挖)方面积；Li为渠段长；Vi为填(或挖)方体积。 土石方量精度与间距L的长度有关，L越小，精度就越高。但是这种方法计算量大, 尤其是在范围较大、精度要求高的情况下更为明显;若是为了减少计算量而加大断面间隔，就会降低计算结果的精度; 所以断面法存在着计算精度和计算速度的矛盾。 2、方格网法计算 对于大面积的土石方估算以及一些地形起伏较小、坡度变化平缓的场地适宜用格网法。
第18卷 第1期1998年2月北京理工大学学报Jo urnal of Beijing Instit ute o f T echnolog y V ol.18 N o.1Feb.1998收稿日期:1996-09-25 确定两个任意多边形的并的算法 周培德 王文明 (北京理工大学计算机科学与工程系,北京 100081) 摘 要 目的 设计并分析求两个任意多边形的并的一种新算法.方法 利用分治思想设 计算法,即根据P ,Q 凸壳及P 与Q 的凸壳的不同位置关系,分6种情况分别求并P ∪Q 的 边界.结果 成功设计出新的算法并分析出该算法的时间复杂性为O (n +m )次判断两条线 段是否相交,其中n ,m 分别是多边形P 与Q 的顶点数.结论 该算法优于逐次判断P 的每 条边是否与Q 的边相交的方法. 关键词 简单多边形;两个多边形的并;复杂度 分类号 T P 301 求两个任意多边形的并是计算几何中的基本问题之一,该问题的一种特殊情况是求两个矩形的并及多个矩形的并[1] .在超大规模集成电路的辅助设计和数据库中的并发控制等领域中常出现上述问题.因此研究这一问题的快速解法具有实际的应用价值.求两个任意多边形的并的一种方法是逐次判断多边形P 的每条边是否与多边形Q 的边相交,这种方法需要nm 次判断两条线段是否相交.本文中提出的算法是基于分治思想设计的,该算法首先求出P ,Q 及P 与Q 的凸壳,然后分6种不同情况分别求P ∪Q 的外围边界及P ∪Q 内空洞的边界.特别是第6种情况,把P 与Q 的凸壳顶点及求出的交点分成两种不同类型来处理.这种方法只需要O (n +m )次判断两条线段是否相交,因而减少了所需要的计算时间.另外,该算法比采用求解线性方程组的方法也优越得多. 给定多边形P 的顶点序列p 1,p 2,…,p n 及多边形Q 的顶点序列q 1,q 2,…,q m ,它们的边界分别为p 1p 2,…,p n -1p n ,p n p 1及q 1q 2,…,q m -1q m ,q m q 1.通常,多边形表示边界和内部区域的并.若简单多边形P 的内部区域是凸集,则此简单多边形是凸的.如果P 和Q 是两个任意简单多边形,那么P 和Q 的并定义为 P ∪Q ={z z ∈P 的内域及边界或者z ∈Q 的内域及边界}1 算法描述 算法1 确定两个任意简单多边形的并的算法 输入 多边形P 的顶点序列(p 1,p 2,…,p n )与多边形Q 的顶点序列(q 1,q 2,…q m ).输出 P ∪Q 的顶点序列