Computing non-visibility of convex polygonal facets on the surface of a polyhedral CAD model

Visibility has found wide applications in manufacturing operations planning and computer vision and graphics. The motivation of this paper is to accurately calculate visibility for objects whose surface is represented by polygonal facets. In this paper, the authors focus on determining non-visibility cones, which are the complementary sets of visibility. This is accomplished by determining sliding planes that comprise the boundaries of a non-visibility cone. The approach presented in this paper directly evaluates the boundaries of the non-visibility cone of an arbitrary convex planar polygon due to the visibility blocked by obstacle polygons. The method is capable of calculating visibility for convex polygons with any number of sides, not limited to triangular facetted models. Implementation is demonstrated in this paper for three to six sided polygonal models.     

A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a ladder) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in timeO(K logn) =O(n ² logn) wheren is the number of obstacle corners and whereK is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of Leven and Sharir [5], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion-planning algorithms for other more complex robot systems.Work on this paper has been supported in part by a grant from the Joint Ramot-Israeli Ministry of Industry Foundation.     

A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a “ladder”) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in timeO(K logn) =O(n ² logn) wheren is the number of obstacle corners and whereK is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of Leven and Sharir [5], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion-planning algorithms for other more complex robot systems.     

Visiting convex regions in a polygonal map

This paper is concerned with a variant of the multi-goal path planning in which goals are represented as convex polygons. The problem is to find a closed shortest path in a polygonal map such that all goals are visited. The proposed solution is based on a self-organizing map (SOM) algorithm for the traveling salesman problem. Neurons’ weights are considered as nodes inside the polygonal domain and connected nodes represent a path that evolves according to the proposed adaptation rules. In addition, a reference algorithm based on the solution of the traveling salesman problem and the consecutive touring polygons problem is provided to find high quality solutions of the created set of problems. The problems are designed to represent various inspection and patrolling tasks and can form a kind of benchmark set for multi-goal path planning algorithms. The performance of the algorithms is examined in this problem set, which includes an instance of the watchman route problem with restricted visibility range. The proposed SOM based algorithms provide a unified approach to solve various visibility based routing problems in polygonal maps while they provide a competitive quality of solutions to the reference algorithm with significantly lower computational requirements.     

A linear algorithm for eliminating hidden-lines from a polygonal cylinder

A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A common trait among algorithms for hidden-line elimination is a worst case complexity ofO(n ²). It is the interent here to introduce an algorithm that exhibits a linear worst case complexity. The use of a restricted class of input, has been employed to achieve asymptotic improvement in complexity as well as simplifying the problem enough to permit theoretic analysis of the algorithm. The class of input is still general enough to conform to the requirements of a number of applications.     

A hidden line algorithm for a model generated by assembling solid convex polyhedra

A simple algorithm is presented for removing the hidden lines from an object which consists of a collection of solid blocks. The elementary blocks are general convex polyhedra with any number of faces. The representation of the object as a whole requires that the lines of separation between contiguous blocks are also removed.The procedures developed are described in detail and illustrated by flowcharts.     

A high quality interpolation method for colocated polyhedral/polygonal control volume methods

A high quality and efficient interpolation method for polyhedral/polygonal control volume simulation data is presented. The proposed method utilizes a non-ambiguous and efficient mesh decomposition technique. A pseudo-Laplacian is used to solve an optimization problem to approximate the variation between discrete data points in a linear fashion. The interpolation method guarantees continuous interpolation data throughout the control volume mesh topology and faithfully reproduces the input control volume data. The interpolation connectivity is structured to mimic the interpolation methods utilized by the control volume discretization. The method only requires the geometry of the input data to perform interpolations. This allows key interpolation data to be calculated once and stored for efficient interpolations. The benefits of the proposed algorithm are highlighted by an interpolation test case which demonstrates the benefits of the current method compared to a popular interpolation method currently used in industry. Since the proposed method is designed to augment an existing mesh data structure it can be used to update existing control volume software.     

Gradient algorithms for polygonal approximation of convex contours

The subjects of this paper are descent algorithms to optimally approximate a strictly convex contour with a polygon. This classic geometric problem is relevant in interpolation theory and data compression, and has potential applications in robotic sensor networks. We design gradient descent laws for intuitive performance metrics such as the area of the inner, outer, and “outer minus inner” approximating polygons. The algorithms position the polygon vertices based on simple feedback ideas and on limited nearest-neighbor interaction.     

基于抽象凸下界估计的群体全局优化算法

针对确定性全局优化算法极高的计算复杂度以及随机性全局优化算法可靠性较低的问题,在群体进化算法框架下,结合抽象凸理论,提出一种基于抽象凸下界估计的群体全局优化算法。首先,对整个初始群体构建抽象凸下界估计松弛模型;然后,利用不断收紧的下界估计信息安全排除部分无效区域,并指导种群更新,同时借助支撑面的下降方向作局部增强;最后,根据进化信息更新支撑面。数值实验结果表明了所提出算法的有效性。     

A novel differential evolution algorithm using local abstract convex underestimate strategy for global optimization

Two main challenges in differential evolution (DE) are reducing the number of function evaluations required to obtain optimal solutions and balancing the exploration and exploitation. In this paper, a local abstract convex underestimate strategy based on abstract convexity theory is proposed to address these two problems. First, the supporting hyperplanes are constructed for the neighboring individuals of the trial individual. Consequently, the underestimate value of the trial individual can be obtained by the supporting hyperplanes of its neighboring individuals. Through the guidance of the underestimate value in the select operation, the number of function evaluations can be reduced obviously. Second, some invalid regions of the domain where the global optimum cannot be found are safely excluded according to the underestimate information to improve reliability and exploration efficiency. Finally, the descent directions of supporting hyperplanes are employed for local enhancement to enhance exploitation capability. Accordingly, a novel DE algorithm using local abstract convex underestimate strategy (DELU) is proposed. Numerical experiments on 23 bound-constrained benchmark functions show that the proposed DELU is significantly better than, or at least comparable to several state-of-the art DE variants, non-DE algorithms, and surrogate-assisted evolutionary algorithms.     

A counterexample to a diameter algorithm for convex polygons

Recently, Snyder and Tang [1] proposed an algorithm for finding the diameter of a convex polygon. In this note a family of convex polygons is described for which their algorithm fails. It is also pointed out that the diameter of an arbitrary simple n-vertex polygon can be computed in O(n) time.     

An algorithm for polygonal approximation of a digital object

A fast and simple heuristic algorithm for polygonal approximation is presented. The algorithm is based on a mark and sweep technique. Results of computer implementation with various images are reported.     

A least distance algorithm for a smooth strictly convex norm

An algorithm for approximating a non negative solution of inconsistent systems of linear equations is presented. We define a best approximate solution of a system Ax = b x≥0 to be the vector x≥0 which minimizes the norm of the residual r(x) = b ? Ax, for a smooth and strictly convex norm. The algorithm is shown to be feasible and globally convergent. The special case of the ? ^p norm is included. In particular, the method converges for 1 < p < 2. A generalization of this algorithm is also given. Numerical results are included.     

A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces

This paper presents a new and simple scheme to describe the convex hull in R^d,which only uses three kinds of the faces of the convex hull.i.e.,the d-1-faces,d-2-faces and 0-faces.Thus,we develop and efficient new algorithm for constructing the convex hull of a finite set of points incrementally.This algorithm employs much less storage and time than that of the previously-existing approaches.The analysis of the runniing time as well as the storage for the new algorithm is also theoretically made.The algorithm is optimal in the worst case for even d.     

A finitely convergent algorithm for convex inequalities

In engineering design problems, it is often necessary to find a solution to a system of nonlinear inequalities in which the functions involved are not necessarily differentiable. In this paper, assuming convexity of the functions, an algorithm is presented for solving such systems of inequalities in a finite number of iterations.     

An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles

This paper concerns the development of a piecewise linear Voronoi roadmap for translating a convex polyhedron in a three-dimensional (3-D) polyhedral world. In general the Voronoi roadmap is incomplete for motion planning, i.e., it can have several disjoint components in one connected component of free space. An analysis of the roadmap shows that incompleteness is caused by the occurrence of the following simple geometric structure: a polygon in the Voronoi surface containing one or more polygons inside it. We formally bring out the details of this geometric structure and give an efficient augmentation of the roadmap that makes it complete. We show that the roadmap has size e = O(n²Q²l²), where n is the total number of faces on the obstacles, Q is the total number of obstacles and l is the number of faces on the moving object. We also present an algorithm to construct the roadmap in O((n + Ql)e + Q²log Q) time.     

A hybrid algorithm for finding a global minimum

One of the most important problems in non-linear programming is to find out the global minimum of a given objective function. In this paper, a new hybrid algorithm which combines the random optimization method of Matyas (1965) and one of the well-known ordinary descent algorithms having an effective convergence property (for example, the Fletcher-Reeves conjugate gradient method, the Davidon-Fletcher-Powell quasi Newton method, etc.) is proposed in order to find out a global minimum in as small a number of steps as possible. Several computational experiments on multimodal objective functions are carried out in order to test the efficiency of the proposed hybrid algorithm. The results obtained imply that the proposed hybrid algorithm is useful for finding out a global minimum in a small number of steps. A theorem that predicts convergence to a global minimum is also given.     

DE/EDA: A new evolutionary algorithm for global optimization

Differential evolution (DE) was very successful in solving the global continuous optimization problem. It mainly uses the distance and direction information from the current population to guide its further search. Estimation of distribution algorithm (EDA) samples new solutions from a probability model which characterizes the distribution of promising solutions. This paper proposes a combination of DE and EDA (DE/EDA) for the global continuous optimization problem. DE/EDA combines global information extracted by EDA with differential information obtained by DE to create promising solutions. DE/EDA has been compared with the best version of the DE algorithm and an EDA on several commonly utilized test problems. Experimental results demonstrate that DE/EDA outperforms the DE algorithm and the EDA. The effect of the parameters of DE/EDA to its performance is investigated experimentally.     

A new real-coded stochastic Bayesian optimization algorithm for continuous global optimization

Estimation of distribution algorithms are considered to be a new class of evolutionary algorithms which are applied as an alternative to genetic algorithms. Such algorithms sample the new generation from a probabilistic model of promising solutions. The search space of the optimization problem is improved by such probabilistic models. In the Bayesian optimization algorithm (BOA), the set of promising solutions forms a Bayesian network and the new solutions are sampled from the built Bayesian network. This paper proposes a novel real-coded stochastic BOA for continuous global optimization by utilizing a stochastic Bayesian network. In the proposed algorithm, the new Bayesian network takes advantage of using a stochastic structure (that there is a probability distribution function for each edge in the network) and the new generation is sampled from the stochastic structure. In order to generate a new solution, some new structure, and therefore a new Bayesian network is sampled from the current stochastic structure and the new solution will be produced from the sampled Bayesian network. Due to the stochastic structure used in the sampling phase, each sample can be generated based on a different structure. Therefore the different dependency structures can be preserved. Before the new generation is generated, the stochastic network’s probability distributions are updated according to the fitness evaluation of the current generation. The proposed method is able to take advantage of using different dependency structures through the sampling phase just by using one stochastic structure. The experimental results reported in this paper show that the proposed algorithm increases the quality of the solutions on the general optimization benchmark problems.