An algorithm for line clipping against a polygon based on shearing transformation

Line clipping against a polygon is widely used in computer graphics such as the hidden line problem. A newline‐clipping algorithm against a general polygon is presented in this paper. The basic idea of this algorithm is tochange the line to be clipped into a horizontal line by shearing transformation. Then each edge of the polygonalwindow is transformed by a shearing transformation with the same parameters as those used to the line. Eachedge of the polygon is processed against a horizontal line, which makes the clipping process simpler. The result inthis paper shows that less calculation is needed for the new algorithm with a higher speed compared to existingalgorithms.     

An efficient algorithm for line and polygon clipping

We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.     

任意多边形窗口的圆裁剪算法

针对任意多边形窗口内圆的裁剪问题,本文提出一种更加全面、有效的裁剪算法.该方法提出借助x-扫描线算法来判断圆和多边形窗口的位置关系,排除圆完全在窗口内或者窗口外的情况;针对多边形窗口和圆相交的情况,按照逆时针方向依次求出多边形各边与圆的交点;最终,通过判断两点间的关系,决定两点之间画线还是画弧,完成圆的裁剪.实验结果表明,该方法能够有效全面的完成多边形窗口的圆裁剪.     

基于VC的任意不自相交多边型新裁剪算法

计算机图形学的基础经典裁剪算法的改进是添加一些附加的判断条件以提高效率或只是适用于某种特殊条件环境的应用。对常用的线段裁剪算法和多边形之间的裁剪算法进行简单的原理描述与比较,提出一个新的任意不自相交多边形之间的裁剪算法,该算法以基本线段单元为控制对象,在线段求交中使用梁友栋-barskey算法,然后从裁剪之后的线段单元组中寻找多边形的线段单元组合。分带环多边形之间的裁剪和不带环多边形之间的裁剪来详细描述算法的实施步骤和算法流程;最后用C++语言实现该裁剪算法,结合工程应用解决了多边形裁剪实例,通过测试证明该算法对不自相交多边形之间的裁剪是很有效的,同时使用该算法解决了多边形与折线之间的裁剪问题,改善工程应用。     

On an algorithm for combined system optimisation and parameter estimation

The paper is concerned with the determination of optimum steady-state operation of industrial plant where the optimisation is performed using a mathematical model with parameters whose values are estimated by comparing model and real plant measurements. The two associated problems of system optimisation and model parameter estimation are discussed and an algorithm is examined whose purpose is to accomplish the correct steady-state optimum operating condition on the real plant in spite of inaccuracies in the structure of the mathematical model. The aim of the paper is to investigate the performance of the algorithm which is accomplished through a theoretical analysis of its application to a linear process, where the optimisation is performed using a quadratic performance index and a mathematical model of incorrect structure. Particular emphasis is given to the stability and convergence properties of the algorithm and to the effect of real process measurement errors. Simulation results are also presented illustrating the effectiveness of the technique when applied to nonlinear optimisation problems including a study concerned with determining optimum controller set points to maximise the net rate of return from a chemical reactor plant.     

Seeker optimisation (human group optimisation) algorithm with chaos

Seeker optimisation algorithm (SOA), also referred to as human group metaheuristic optimisation algorithms form a very hot area of research, is an emerging population-based and gradient-free optimisation tool. It is inspired by searching behaviour of human beings in finding an optimal solution. The principal shortcoming of SOA is that it is easily trapped in local optima and consequently fails to achieve near-global solutions in complex optimisation problems. In an attempt to relieve this problem, in this article, chaos-based strategies are embedded into SOA. Five various chaotic-based SOA strategies with four different chaotic map functions are examined and the best strategy is chosen as the suitable chaotic scheme for SOA. The results of applying the proposed chaotic SOA to miscellaneous benchmark functions confirm that it provides accurate solutions. It surpasses basic SOA, genetic algorithm, gravitational search algorithm variant, cuckoo search optimisation algorithm, firefly swarm optimisation and harmony search the proposed chaos-based SOA is expected successfully solve complex engineering optimisation problems.     

Extension of the Nicholls-Lee-Nichols algorithm to three dimensions

A new algorithm for clipping a line segment against a pyramid in E ³ is presented. This algorithm avoids computation of intersection points that are not end points of the output line segment. It also solves all cases more effectively. The performance of this algorithm is shown to be consistently better than that of existing algorithms, including the Cohen–Sutherland, Liang–Barsky, and Cyrus–Beck algorithms.     

Discrete bacteria foraging optimization algorithm for graph based problems – a transition from continuous to discrete

Bacteria Foraging Optimisation Algorithm is a collective behaviour-based meta-heuristics searching depending on the social influence of the bacteria co-agents in the search space of the problem. The algorithm faces tremendous hindrance in terms of its application for discrete problems and graph-based problems due to biased mathematical modelling and dynamic structure of the algorithm. This had been the key factor to revive and introduce the discrete form called Discrete Bacteria Foraging Optimisation (DBFO) Algorithm for discrete problems which exceeds the number of continuous domain problems represented by mathematical and numerical equations in real life. In this work, we have mainly simulated a graph-based road multi-objective optimisation problem and have discussed the prospect of its utilisation in other similar optimisation problems and graph-based problems. The various solution representations that can be handled by this DBFO has also been discussed. The implications and dynamics of the various parameters used in the DBFO are illustrated from the point view of the problems and has been a combination of both exploration and exploitation. The result of DBFO has been compared with Ant Colony Optimisation and Intelligent Water Drops Algorithms. Important features of DBFO are that the bacteria agents do not depend on the local heuristic information but estimates new exploration schemes depending upon the previous experience and covered path analysis. This makes the algorithm better in combination generation for graph-based problems and combination generation for NP hard problems.     

Bresenham's Line Generation Algorithm with Built-in Clipping

One of the most important operations in many graphical systems is the generation of a line segment. This process consists of two stages: clipping and drawing. These two stages are separated in current graphical applications. In this paper a new approach to line generation is proposed, which unifies these stages. The proposed algorithm is based on Bresenham's line generation algorithm to include necessary line clipping. The line clipping stage is an operation-reduced, integer arithmetic only algorithm. The notion of correctness of line clipping is introduced and correctness of the proposed algorithm is shown. Complete C-notation of the algorithm is included.     

一般多边形窗口的线裁剪

已有的线裁剪算法都是针对矩形窗口或凸多边形窗口的。对于一般的多边形窗口(包括凹多边形)的线裁剪,目前尚无有效的算法。开发这种算法是很必要的,因为它在计算机图形学中有很广泛的应用,如物体的消隐处理等。因此,提出一个对于一般多边形窗口的线裁剪算法,并给出了最优实现。     

Optimal allocation of FACTS devices for static security enhancement in power systems via imperialistic competitive algorithm (ICA)

The problem of optimal allocation of flexible AC transmission systems (FACTS) devices is deemed as a formidable optimisation problem. Metaheuristics are the common approaches for solving FACTS allocation problems. Imperialistic competitive algorithm (ICA) is a well-established optimisation algorithm which has been successfully employed for solving complex optimisation problems in different fields. It is inspired by imperialistic competition and socio-political evolution of human beings and offers appropriate exploration and exploitation capabilities during the search for global optima. This paper employs ICA for solving FACTS allocation problem in a way that low values of overloads and voltage deviations are resulted both during line outage contingencies and demand growth. Thyristor-controlled phase shifting transformers (TCPST’s) and thyristor-controlled series compensators (TCSC’s) have been used as FACTS devices. The results of employing ICA for FACTS allocation problem indicate that ICA Offers better results than artificial bee colony (ABC), gravitational search algorithm (GSA), evolutionary programming (EP), bat swarm optimisation (BSO), nonlinear programming (NLP), pattern search (PS), asexual reproduction optimisation (ARO) and backtracking search algorithm (BSA).     

Classes of submodular constraints expressible by graph cuts

Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n ⁶) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. Furthermore, we describe how our results translate to certain optimisation problems arising in computer vision.     

一种基于几何变换的高效的线裁剪新算法

线裁剪是计算机图形学的重要基础问题之一。在对现有的两种优秀算法作了分析之后提出一种利用简单几何变换，将裁剪问题简化为对两种基本情况的处理，并先后对被裁剪线段的首末端点作变换处理的新算法，有效地克服了上述两种方法中存在的调用函数多，基本情况处理复杂等弱点，理论分析和实例测试均表明，该算法优于当代国际最快的几种裁剪方法。     

采用区域编码的椭圆对直线裁剪算法

裁剪算法的核心问题是速度问题,而求裁剪窗口和裁剪对象的交点是影响裁剪速度的主要因素。特别是椭圆对线段的裁剪,由于椭圆的方程是二次的,求椭圆与线段的交点 需要求解一元二次方程,涉及开方运算,非常浪费机器时间。为提高裁剪速度,设计出5位的区域编码,利用此技术能够迅速而准确地判断出椭圆和线段的位置关系。对于完全可见 或显然完全不可见的线段立即做出保留或弃掉的决定,避免求交运算;对于能够明确断定与椭圆相交的线段,采用中点分割算法求椭圆和线段的近似交点,避免求解一元二次方程 和开方运算;对于其他情形的线段通过求解一元二次方程来完成裁剪。基于前述思想设计出的椭圆对线段裁剪算法与现有的同类算法相比,算法实现简单,裁剪速度具有较大提高 。     

Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.     

An optimisation strategy for industrial metal forming processes

Product improvement and cost reduction have always been important goals in the metal forming industry. The rise of finite element (FEM) simulations for processes has contributed to these goals in a major way. More recently, coupling FEM simulations to mathematical optimisation techniques has shown the potential to make a further giant contribution to product improvement and cost reduction. Much research on the optimisation of metal forming processes has been published during the last couple of years. Although the results are impressive, the optimisation techniques are generally only applicable to specific optimisation problems for specific products and specific metal forming processes. As a consequence, applying optimisation techniques to other metal forming problems requires a lot of optimisation expertise, which forms a barrier for more general industrial application of these techniques. In this paper, we overcome this barrier by proposing a generally applicable optimisation strategy that makes use of FEM simulations of metal forming processes. It consists of a structured methodology for modelling optimisation problems related to metal forming. Subsequently, screening is applied to reduce the size of the optimisation problem by selecting only the most important design variables. Finally, the reduced optimisation problem is solved by an efficient optimisation algorithm. The strategy is generally applicable in a sense that it is not constrained to a certain type of metal forming problem, product or process. Also, any FEM code may be included in the strategy. Furthermore, the structured approach for modelling and solving optimisation problems should enable non-optimisation specialists to apply optimisation techniques to improve their products and processes. The optimisation strategy has been successfully applied to a hydroforming process, which demonstrates the potential of the optimisation of metal forming processes in general and more specific the proposed optimisation strategy.     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段，使得每个片段都能局部地形成一个凸多边形，称为凸片段，并建立一个二叉树来管理这些凸片段．在裁剪计算时，先根据二叉树快速地找到与被裁剪线段相交的凸片段，再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度，使其在O（logN）～O（N）之间自适应地变化，且大部分情况下时间复杂度小于O（N）．     

Berth allocation planning in Seville inland port by simulation and optimisation

We study the problems associated with allocating berths for containerships in the port of Seville. It is the only inland port in Spain and it is located on the Guadalquivir River. This paper addresses the berth allocation planning problems using simulation and optimisation with Arena software. We propose a mathematical model and develop a heuristic procedure based on genetic algorithm to solve non-linear problems. Allocation planning aims to minimise the total service time for each ship and considers a first-come-first-served allocation strategy. We conduct a large amount of computational experiments which show that the proposed model improves the current berth management strategy.     

0/1背包问题竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来到达优化目的的新型寻优算法。在考虑0/1背包问题特点的基础上给出了用竞争决策算法求解0/1背包问题的算法,经过大量数据测试和验证,获得了较好的结果。