Two simple and efficient algorithms for Jordan sorting and polygon cutting and clipping |
| |
| Affiliation: | 1. School of Natural and Environmental Sciences, Newcastle University, Newcastle-upon-Tyne, United Kingdom;2. Earth to Ocean Research Group, Department of Biological Sciences, Simon Fraser University, Burnaby, British Columbia V5A 1S6, Canada;3. Ecology Action Centre, Halifax, Nova Scotia, BSK 4L3, Canada;4. Alaska Fisheries Science Center, NOAA, Seattle, United States;1. School of Atmospheric Sciences, Sun Yat-sen University, Key Laboratory of Tropical Atmosphere-Ocean System, Ministry of Education, and Southern Marine Science and Engineering Guangdong Laboratory (Zhuhai), Zhuhai, China;2. Jiangsu Key Laboratory of Environmental Engineering, Jiangsu Academy of Environmental Sciences, Nanjing, China;3. Department of Civil and Environmental Engineering, Hong Kong Polytechnic University, Hong Kong, China;4. School of Geography and Marine Science, Nanjing University, Nanjing, China |
| |
| Abstract: | This paper deals with the Jordan sorting problem: Given n intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, sort these points into the order in which they occur along the x-axis. The worst-case time complexity of this problem is θ(n). Unfortunately, the known O(n) time algorithms are too complicated, which causes that they are difficult to implement and slow for the inputs of sizes that are of practical interest. In this paper, two algorithms for Jordan sorting are presented. The first algorithm is extremely simple. Although its worst-case time complexity is O(nlogn), it is shown that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. Furthermore, an improved O(nlog logn) worst-case time algorithm is presented. For the input sequences of size from 4 to 105, the algorithms are compared with Quicksort, with the algorithm based on splay trees and with the O(n) time algorithm proposed by Fung et al. The results show that our algorithms are faster. The relevant implementation details are given. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
