A new algorithm for clipping lines against convex polyhedron with O(N) complexity is given with modification for non-convex polyhedron. The suggested algorithm is faster for higher number of facets of the given polyhe...
详细信息
A new algorithm for clipping lines against convex polyhedron with O(N) complexity is given with modification for non-convex polyhedron. The suggested algorithm is faster for higher number of facets of the given polyhedron than the traditional Cyrus-Beck's algorithm. Some principal results of comparison of all algorithms are shown and give some ideas how the proposed algorithm could be used effectively.
An algorithm for automatic reducing of the topology of a h-genus three-dimensional polyhedron to the topology of a ball is proposed. The polyhedron is assumed to be represented by a three-dimensional cell complex. A s...
详细信息
An algorithm for automatic reducing of the topology of a h-genus three-dimensional polyhedron to the topology of a ball is proposed. The polyhedron is assumed to be represented by a three-dimensional cell complex. A special technique for separation of two-dimensional subcomplexes producing a cutting surfaces is described. This technique is based on aggregation of cells and calculation of Betti groups of the polyhedron.
A hybrid method for solving a particular physical layout problem with transportation cost minimization (investment and utilization) is presented. The available material handling consists of carts, gantries and at most...
详细信息
A hybrid method for solving a particular physical layout problem with transportation cost minimization (investment and utilization) is presented. The available material handling consists of carts, gantries and at most, one sliding bridge. These transport products or parts between cells. Cells are placed in a facility whose space may contain obstacles. Cells are linked by distance constraints. There are also constraints concerned with the utilization of the material handling systems. For solving this problem, we propose a new decomposition-based approximation method, mixing three known approaches: Among these methods, simulated annealing deals with the geometrical aspect of the problem. A genetic algorithm makes decisions about the MHS choices, the exact method (the Hitchcock method for the transportation problem) minimizes the total MHS utilization costs.
Let S be a set, f: S x S --> R+ a bivariate function, and f(x, S) the maximum value of f(x, y) over all elements y is-an-element-of S. We say that f is decomposable with respect to the maximum if f(x, S) = max{f(x,...
详细信息
Let S be a set, f: S x S --> R+ a bivariate function, and f(x, S) the maximum value of f(x, y) over all elements y is-an-element-of S. We say that f is decomposable with respect to the maximum if f(x, S) = max{f(x, S1), f(x, S2),...,f(x, S(k))} for any decomposition S = [GRAPHICS] Computing the maximum (minimum) value of a decomposable function is inherent in many problems of computational geometry and robotics. In this paper, a general technique is presented for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Our result holds for a semi-online model of dynamization: When an element is inserted, we are told how long it will stay. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.
In this paper we conside a particular 2D placement problem which consists of finding the best way to place a set of rectilinear polygons (PP P2,...,Pa) in a given rectangular area. Π/2 rotations of the polygons are a...
详细信息
In this paper we conside a particular 2D placement problem which consists of finding the best way to place a set of rectilinear polygons (PP P2,...,Pa) in a given rectangular area. Π/2 rotations of the polygons are allowed. The work area contains unusable zones. The final result is a placement where polygons do not overlap with each other nor cross the work area boundaries. This kind of problem is usually found in industry, for example sheet cutting of textile material, leather, steel and so forth. We used 3 genetic algorithm approaches to approximately solve this particular 2D placement problem. We defined a direct encoding for the first approach and a "mixed" encoding for the two others which need a specific generator to build the associated solution. Some numerical examples issued from large size problems are solved efficiently.
Simulating a crowded scene like a busy shopping street requires tight packing of virtual characters. In such cases, collisions are likely to occur, and the choice in collision detection shape will influence how charac...
详细信息
Simulating a crowded scene like a busy shopping street requires tight packing of virtual characters. In such cases, collisions are likely to occur, and the choice in collision detection shape will influence how characters are allowed to intermingle. Full collision detection is too expensive for crowds, so simplifications are needed. The most common simplification, the fixed-width, pose-independent cylinder, does not allow intermingling of characters, as it will either cause too much empty space between characters or undetected penetrations. As a possible solution to this problem, we introduce the bounding cylinder hierarchy (BCH), a bounding volume hierarchy that uses vertical cylinders as bounding shapes. Because the BCH is a generalization of the single cylinder, we expect that this representation can be easily integrated with existing crowd simulation systems. We compare our BCH with commonly used collision shapes, namely the single cylinder and oriented bounding box tree, in terms of query time, construction time, and represented volume. To get an indication of possible crowd densities, we investigate how close characters can be before collision is detected and finally propose a critical maximum depth for the BCH. Copyright (c) 2014 John Wiley & Sons, Ltd.
We propose a geometric algorithm for topic learning and inference that is built on the convex geometry of topics arising from the Latent Dirichlet Allocation (LDA) model and its nonparametric extensions. To this end w...
详细信息
ISBN:
(纸本)9781510838819
We propose a geometric algorithm for topic learning and inference that is built on the convex geometry of topics arising from the Latent Dirichlet Allocation (LDA) model and its nonparametric extensions. To this end we study the optimization of a geometric loss function, which is a surrogate to the LDA's likelihood. Our method involves a fast optimization based weighted clustering procedure augmented with geometric corrections, which overcomes the computational and statistical inefficiencies encountered by other techniques based on Gibbs sampling and variational inference, while achieving the accuracy comparable to that of a Gibbs sampler. The topic estimates produced by our method are shown to be statistically consistent under some conditions. The algorithm is evaluated with extensive experiments on simulated and real data.
In this paper, we describe a system for approximate shape matching and symmetry (rotation and re?ection) detection of geometric shapes represented as point clouds. Rather than using the leastsquares distance as a meas...
详细信息
In this paper, we describe a system for approximate shape matching and symmetry (rotation and re?ection) detection of geometric shapes represented as point clouds. Rather than using the leastsquares distance as a measure of similarity between shapes, we use the Hausdorff distance between point sets as the underlying shape metric. This allows us to exploit methods from geometric pattern matching to return symmetries and rigid transformation matches with guaranteed error bounds on the quality of our solution. The approximation is determined by intuitive user-specified input precision and distance threshold parameters. Another important feature of our method is that it leverages FFT-based techniques for string matching to compute all approximate symmetries simultaneously. Our algorithm is simple to implement and is efficient;we present a detailed experimental study.
This paper presents a novel approach that generates tool path for five-axis flank milling. Two geometric algorithms are proposed for approximating a ruled surface with a series of developable patches. First, develop a...
详细信息
ISBN:
(纸本)0769524737
This paper presents a novel approach that generates tool path for five-axis flank milling. Two geometric algorithms are proposed for approximating a ruled surface with a series of developable patches. First, develop ability is obtained in certain regions through re-parameterization of the directrices of the ruled surface. The second algorithm places the control points of a Bezier developable patch using the five DOF's for the patch design. Consecutive patches with geometric continuity are thus generated for the regions not covered in the first approximation. Due to the develop ability property, a tapered tool can move along the rulings of those patches without local tool interference. The machining deviation is determined by the surface approximation error. Thus this work transforms tool path planning in five-axis flank milling into a geometric modeling problem. It also demonstrates an effective application of developable surfaces in machining.
暂无评论