Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center princlple

The nesting problem involves arranging pieces on a plate to maximize use of material. A new scheme for 2D irregular-shaped nesting problem is proposed. The new scheme is based on the NFP （No Fit Polygon） algorithm and a new placement principle for pieces. The novel placement principle is to place a piece to the position with lowest gravity center based on NFP. In addition, genetic algorithm （GA） is adopted to find an efficient nesting sequence. The proposed scheme can deal with pieces with arbitrary rotation and containing region with holes, and achieves competitive results in experiment on benchmark datasets.     

A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram

INTRODUCTION To compute the minimum distance between two convex polygons or polyhedrons is often a main step of many applications, such as collision detection (Choi et al., 2006; Li et al., 2003), path planning. In order to reduce the time complexity of the algorithm as much as possible, the convex property must be applied fully. Edelsbrunner (1985) proposed an algorithm for computing the minimum distance between two dis- joint convex polygons. The algorithm takes O(logm logn) time, and …     

Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle

INTRODUCTION 2D irregular-shaped nesting problem is the problem of finding an efficient arrangement for pieces in a containing region without overlapping (Fig.1), and is aimed at maximizing use of material. Nesting problem is of great interest to garment, paper, ship building, and sheet metal industries since small improvement of layout can lead to large savings in material. Many effective solutions have been pro- posed for the case when pieces and containing region are both rectangular. …     

板材自动排料初探

应用计算机图形学、几何学、优化方法等方面的知识,提出了一种适合在微机上实现的解决钢板排料问题的方法.     

Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting

This paper presents a new algorithm for line clipping against a polygonal window by exploiting the local relationship between each line segment and the polygon. Firstly, a minimal enclosing box (MEB) of the polygon is adopted to reject the invisible line segments located outside the MEB. Secondly, a 45° rotated box is used to encode the endpoint of the line segment, and then reject a portion of the invisible segments crossing polygon corners. Finally, instead of encoding the endpoints of all line segments with respect to the polygonal window, each vertex of the polygon is encoded, taking the line segment to be clipped as reference. For efficient encoding of the polygon vertices, a new concept, termed with slope adaptive virtual box, is introduced regarding each line segment. Such a box can not only conveniently reject all totally invisible lines lying outside the MEB conveniently, but also precisely identify the edges of the polygon with which the line segment potentially intersects. With the summation of the vertex codes, it can be verified whether the line segment is separated from or potentially intersects the polygon window. Based on the product of the codes of adjacent vertices, singular cases of intersection can be solved accurately. Experimental results demonstrate the efficiency and stability of the new algorithm.     

Maya多边形角色建模技术初探

动漫产业发展迅速,其中三维动画占据了重要的地位。制作动画,建模是基础,为了让动漫形象和个性更加立体丰满,对角色模型的塑造就有了很高的要求。Maya Polygon建模,更适合有机物模型的创建。系统阐述多边形角色建模的原则和实用性技术,旨在使模型创建更加专业化。     

基于ArcGIS的VBA多边形空洞去除方法研究

拓扑关系是GIS进行空间推理、查询和分析的基础。多边形之间的拓扑关系应用是较为广泛的GIS应用之一。目前多边形的拓扑关系一般都针对简单无洞多边形而言,而目前对多边形空洞的去除没有一个很好的办法,本文利用ArcGIS的VBA,开发算法去除多边形空洞。经试验表明,该方法简单、效果理想。     

多边形的面积矢量及应用

给出平面上多边形的面积矢量的定义及公式,并应用它求出多边形的面积公式.