首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 109 毫秒
1.
This paper develops a computational method for numerical control (NC) of traveling wire electric discharge machining (EDM) operation from geometric representation of a desired cut profile in terms of its contours. Normalized arc length parameterization of the contour curves is used to represent the cut profile and a subdivision algorithm is developed together with kinematic analysis to generate the required motions of the machine tool axes. In generating the tool motions for cutting sections with high curvatures such as corners with small radii, a geometric path lifting method is presented that increases the machining gap and prevents gauging or wire breakage.  相似文献   

2.
Linear quadtrees from vector representations of polygons   总被引:1,自引:0,他引:1  
A new algorithm is presented which produces various forms of linear quadtrees directly from a vector representation of a polygon. This algorithm takes advantage of specific properties of linear quadtrees and associated linear keys to infer the colors of all parts of the region not cut by the polygon boundary. The method is further extended to multicolored (rather than binary) linear quadtrees which may be useful in geographic information systems applications.  相似文献   

3.
The paper discusses the development of a prototype solid modeling system based on the extended octree modeling approach and its applications in 3-D NC machining simulation and automatic verification. Along with a simple hierarchical data structure, the extended octree model uses the face boundary information (i) to represent complex objects, (ii) to improve object representational accuracy, and (iii) to accelerate the model updating procedures in a graphic simulation process. The improved representational accuracy makes it possible to carry out automatic NC program verification by generating the machined model of the part through the simulation and comparing it with the designed model of the part. The paper also addresses the issues of model conversions from CSG and B-Rep schemes to the corresponding extended octree models and the issues of carrying out Boolean operations on those extended octree models. A prototype system has been implemented and is integrated with AutoCAD AME solid modeler for object modeling and for NC simulation purpose.  相似文献   

4.
Computing geometric properties of images represented by linear quadtrees   总被引:2,自引:0,他引:2  
The region quadtree is a hierarchical data structure that finds use in applications such as image processing, computer graphics, pattern recognition, robotics, and cartography. In order to save space, a number of pointerless quadtree representations (termed linear quadtrees) have been proposed. One representation maintains the nodes in a list ordered according to a preorder traversal of the quadtree. Using such an image representation and a graph definition of a quadtree, a general algorithm to compute geometric image properties such as the perimeter, the Euler number, and the connected components of an image is developed and analyzed. The algorithm differs from the conventional approaches to images represented by quadtrees in that it does not make use of neighbor finding methods that require the location of a nearest common ancestor. Instead, it makes use of a staircase-like data structure to represent the blocks that have been already processed. The worst-case execution time of the algorithm, when used to compute the perimeter, is proportional to the number of leaf nodes in the quadtree, which is optimal. For an image of size 2n × 2n, the perimeter algorithm requires only four arrays of 2n positions each for working storage. This makes it well suited to processing linear quadtrees residing in secondary storage. Implementation experience has confirmed its superiority to existing approaches to computing geometric properties for images represented by quadtrees.  相似文献   

5.
A forest of quadtrees is a refinement of a quadtree data structure that is used to represent planar regions. A forest of quadtrees provides space savings over regular quadtrees by concentrating vital information. The paper presents some of the properties of a forest of quadtrees and studies the storage requirements for the case in which a single 2m × 2m region is equally likely to occur in any position within a 2n × 2n image. Space and time efficiency are investigated for the forest-of-quadtrees representation as compared with the quadtree representation for various cases.  相似文献   

6.
Speeding up construction of PMR quadtree-based spatial indexes   总被引:5,自引:0,他引:5  
Spatial indexes, such as those based on the quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints, especially when the queries involve spatial joins. In this paper we present a number of techniques for speeding up the construction of quadtree-based spatial indexes, specifically the PMR quadtree, which can index arbitrary spatial data. We assume a quadtree implementation using the “linear quadtree”, a disk-resident representation that stores objects contained in the leaf nodes of the quadtree in a linear index (e.g., a B-tree) ordered based on a space-filling curve. We present two complementary techniques: an improved insertion algorithm and a bulk-loading method. The bulk-loading method can be extended to handle bulk-insertions into an existing PMR quadtree. We make some analytical observations about the I/O cost and CPU cost of our PMR quadtree bulk-loading algorithm, and conduct an extensive empirical study of the techniques presented in the paper. Our techniques are found to yield significant speedup compared to traditional quadtree building methods, even when the size of a main memory buffer is very small compared to the size of the resulting quadtrees. Edited by R. Sacks-Davis. Received: July 10, 2001 / Accepted: March 25, 2002 Published online: September 25, 2002  相似文献   

7.
介绍了一种压缩四叉树形数据结构的随机化增量构造算法。首先给出了压缩四叉树的定义,然后描述了算法实现步骤,通过将单位正方形不断分割为更小的正则正方形达到压缩的目的,使用平铺区域和冲突列表,采用随机化递增的算法构建出压缩四叉树,最后分析了算法正确性和运行时间。  相似文献   

8.
The ``line quadtree' data structure hierarchically represents a region and its boundary. Based on the standard quadtree, each node in this structure stores adjacency information as well. While line quadtrees use the same amount of space as standard qaudtrees, they facilitate several region processing algorithms. In particular, we describe efficient algorithms for boundary and superimposing two maps encoded as line quadtrees.  相似文献   

9.
A computationally fast top-down recursive algorithm for connected component labelling using linear quadtrees is presented. The input data structure used is a linear quadtree representing only black leaf nodes. The boundary matching approach used ensures that at most two adjacencies of any black leaf node are considered. Neighbour searching is carried out within restricted subsets of the input quadtree. The time and space complexities of the algorithm are O(Bn) and O(B) respectively for a linear quadtree with B black leaves constructed from a binary array of size 2n × 2n. Simulations show the algorithm to be twice as fast as an existing algorithm that uses an identical input data structure. The top-down algorithm presented can also be used to efficiently generate a linear quadtree representing all nodes — ‘grey’, ‘black’ and ‘white’ — in preorder when given an input linear quadtree representing only ‘black’ leaf nodes. The boundary matching algorithm is computationally fast and has low static and dynamic storage costs, making it useful for applications where linear quadtrees are held in main memory.  相似文献   

10.
In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号