十字线结构光光条提取方法的研究

在结构光视觉检测系统中,光条中心的提取精度直接影响到整个测量系统的测量精度.文章根据红色激光光条的RGB值与背景的差异,提取激光光条,结合像素连通性,采用最小外接矩形法将光条分割,在每个距形区域内采用高斯曲线拟合法提取光条中心,利用最小二乘法拟合光条直线.实验表明该方法具有数据存储量小、实现速度快的特点,且具有一定的抗噪声和断线修补能力.     

简单多边形集凸包的快速算法

提出了一个简单多边形集凸包的快速算法.先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线.应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包.算法的时间复杂度为线性O(n),并且给出一个例子进行了验证.     

基于端点与交点编码的矩形窗口多边形裁剪新算法

从矩形窗口裁剪任意多边形的本质特征出发,提出多边形各边端点编码技术。通过对多边形各边端点的一次及二次编码,可快速得到所有窗内边并舍弃绝大部分窗外边,还可快速判断该端点是内点还是外点。在已获取的窗内边、相交边的交点以及交点编码的基础上,可以得到正确的裁剪结果。同时考虑了矩形窗口与多边形相互包容的特殊情形。实验结果表明,新算法稳定可靠,实现了对任意凹凸多边形的裁剪,具有通用性强、算法简捷、裁剪效率较高的优点。     

确定任意多边形的核的算法

本文提出确定任意简单多边形Ｌ的核的算法，该算法的时间复杂性是Ｏ（ｌｎ）次乘法，其中ｎ是多边形的Ｌ的顶点数，ｌ是多边形Ｌ中凹点的数目。     

计算两凸多边形的并集多边形及其面积的计算机算法与实现

提出计算两平面凸多边形的并集(多边形)及其面积的计算机算法，并对算法实现给出详细的计算过程。程序实现中，文中将算法分为判定点是否在多边形内部、求两多边形交点、求并集多边形及其面积三部分。引入利用向量叉积符号判定三角形的方向，进而判别平面上一点是否在凸多边形内的方法，简化了计算。还进一步提出了运用“区间分割”求两相交线段交点的新颖方法。     

基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法

对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算。笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用“假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为)(nO,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次。该算法原理直观简单,实现容易。实际运行结果表明,该算法速度快捷、运行稳定。     

基于平均条带划分的点的包含性测试方法

提出了一个大量点与多边形关系计算的方法.该方法首先对多边形进行简单预处理,然后采用射线法对每个点进行包含性测试.预处理将多边形的最小包围矩形划分为相同大小的竖直条带,并计算每条边在哪些条带中,该预处理过程简单快速.利用预处理信息对点进行包含性测试时,只需用当前点构造的射线和点所在的条带包含的边进行相交测试即可.每个条带...     

基于等效面积法的线宽及线宽粗糙度测量

建立一种基于刻线边缘轮廓特征求取刻线线宽和线宽粗糙度的测量方法。理想情况下,刻线线宽方向截面为矩形,面积为该矩形高度和宽度的乘积。实际测量中,沿刻线线宽方向截面为一多边形,认为该多边形面积S1和理想矩形面积S相等。利用Tsai给出的台阶高度算法计算刻线单扫描轮廓的高度以获得线宽截面高度H。刻线等效宽度We可根据上述高度H和截面面积S1求出。线宽粗糙度定义为线宽变化的3倍标准偏差,因此线宽粗糙度也能用该方法求出。     

连接不相交线段成简单多边形(链)的算法

提出一个实际问题，即如何连接平面上h条线段成一简单多边形或者简单多边形链，并证明了连接平面上线段集S成一简单多边形链的一个充分条件，S中有一条线段连接凸壳CH（S）中不相邻顶点，另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先逐层计算线段集S的凸壳，并将这些凸壳改变多边形；然后计算各多边形之间的交点，进而删去这些交点。最后合并若干个简单多边形为一个简单多边形，当S中线段数目n较大时，用分治思想可以设计分治算法，较好地求解了这个问题，利用计算机求解这个问题上有实际应用价值。     

生成三维多边形平面域的双直线算法

提出了一种生成三维多边形平面域的新算法,该算法由主投影的扫描转换与主投影方向坐标的离散计算两部分构成。算法的两个部分相互独立,因而在第一部分可采用任意一种已有的多边形扫描转换算法来实现。主投影方向坐标的离散计算可通过两个整型数组（代表双直线）快速获得。算法可保证在理论上共面的两个多边形面域的公共部分在离散后完全重叠。     

点包容性检测

介绍了一个易于实现的点包容性检测算法--倾斜射线法,其特点是射线不会与多边形的顶点或边重合,无须作特殊情况的处理,需计算的区域小,因而计算量小.判断倾斜射线与多边形的交点数,如果交点数为奇数,则点在多边形内,否则,点在多边形外.验证表明,此算法简单有效、稳定可靠,对自相交多边形及带孔多边形等情况同样适用.     

Polyarc discrete element for efficiently simulating arbitrarily shaped 2D particles

A new two‐dimensional discrete element type, termed the ‘polyarc’ element is presented in this paper. Compared to other discrete element types, the new element is capable of representing any two‐dimensional convex particle shape with arbitrary angularity and elongation using a small number of shape parameters. Contact resolution between polyarc elements, which is the most computation‐extensive task in DEM simulation only involves simple closed‐form solutions. Two undesirable contact scenarios common for polygon elements can be avoided by the polyarc element, so the contact resolution algorithm for polyarc elements is simpler than that for polygon elements. The extra flexibility in particle shape representation induces little or no additional computational cost. The key algorithmic aspects of the new element, including the particle shape representation scheme, the quick neighbor search algorithm, the contact resolution algorithm, and the contact law are presented. The recommended contact law for the polyarc model was formulated on the basis of an evaluation of various contact law schemes for polygon type discrete elements. The capability and efficiency of the new element type were demonstrated through an investigation of strength anisotropy of a virtual sand consisting of a random mix of angular and smooth elongated particles subjected to biaxial compression tests. Copyright © 2011 John Wiley & Sons, Ltd.     

基于扫描带的任意多边形窗口线裁剪算法

提出了一个基于扫描带的任意多边形窗口线裁剪算法。首先确定裁剪窗口所有顶点对于被裁剪直线段的位置关系,然后生成过顶点的扫描线,及时修改由相邻两条扫描线所构成的扫描带结构数据,增加每条扫描带中位于被裁剪直线段左侧的裁剪窗口的边界线数。最后,根据左侧边界线数的奇偶性,确定相应直线段的可见性,并最终实现任意多边形窗口的直线段裁剪过程。     

基于扫描区间表示的不规则多边形快速定位算法及应用

不规则多边形定位算法是排料算法的重要组成部分,其效率对排料算法的性能有重要影响。基于扫描区间表示的不规则多边形定位算法因能适应任意复杂多边形而被广泛采用,但它存在计算量大的不足。通过深入研究基于扫描区间表示的多边形定位算法,该文从两个方面对其方法进行改进：首先提出候选平移位置矩阵的概念,进而实现定位扫描算法;然后通过最大跨度比较法快速排除一些不可能的行,从而通过减少定位扫描算法的调用次数进一步加速。该算法已应用于自主开发服装排料软件,多个实际衣片数据的测试结果证明了该文算法的有效性和高效性。     

凸多边形星图识别算法

为解决星敏感器中较大视场快速、可靠的星图识别,提出了以凸多边形为基元、完全不依赖于星等的星图识别算法。对给定的视场,挑选其中较亮的恒星,依其坐标排序,然后采用由平面上的点生成凸多边形的算法,就能得到唯一的、以恒星为顶点的凸多边形。为验证星图识别算法的有效性,建立了导航星数据库,其储存单元为凸多边形的边和相邻边的夹角,共有3832个边数不等的凸多边形。在CPU为33MHz 的PC104上仿真结果表明:在任意视场中,生成凸多边形的时间小于5ms,基于凸多边形的星图识别成功率高于99%,并具有较强的鲁棒性。     

An efficient solid angle sampling technique using bounding volume approach

Abstract

Solid angle sampling is an important variance‐reduced technique when solving global illumination problems by Monte Carlo methods. In this paper, we present an efficient solid angle sampling technique where a paraboloidal luminaire is taken as a case study. The efficiency of our technique is due to the fact that we employ a tight bounding volume to approximate the solid angle. Our technique includes three processes. The construction process builds a bounding volume. It is a convex, frustum‐like polyhedron with a compromise between the tightness and the vertex numbers. The projection process approximates the solid angle as a convex spherical polygon on a unit hemisphere. Finally, the triangulation process triangulates the convex spherical polygon into spherical triangles for stratified sampling. We analyzed our technique in Monte Carlo direct lighting and Monte Carlo path tracing rendering algorithms. The results show that our technique provides up to 90% sampling efficiency. The significance of the proposed technique is that solid angle sampling, from being not possible for the paraboloidal luminaire, is now feasible. In addition, this technique is efficient for sampling, and it is also applicable to other types of luminaires, such as cylindrical and conic luminaires.     

An improved meshless method with almost interpolation property for isotropic heat conduction problems

In the paper an improved element free Galerkin method is presented for heat conduction problems with heat generation and spatially varying conductivity. In order to improve computational efficiency of meshless method based on Galerkin weak form, the nodal influence domain of meshless method is extended to have arbitrary polygon shape. When the dimensionless size of the nodal influence domain approaches 1, the Gauss quadrature point only contributes to those nodes in whose background cell the Gauss quadrature point is located. Thus, the bandwidth of global stiff matrix decreases obviously and the node search procedure is also avoided. Moreover, the shape functions almost possess the Kronecker delta function property, and essential boundary conditions can be implemented without any difficulties. Numerical results show that arbitrary polygon shape nodal influence domain not only has high computational accuracy, but also enhances computational efficiency of meshless method greatly.