论二维点集或线段集凸壳生成算法改进与优化的同构化方向

On an Isomorphic Direction of Improving and Optimizing an Algorithm for Determining the Convex Hull of 2D Point Set or Line Segment Set

本文指出了迄今为止的现行二维点集或线段集(包括:多边形、封闭折线、半封闭折线、开放线段集等)凸壳生成算法的共同弱点;提出了可改进与优化凸壳算法的同构化凸壳构造基本定理。进而,基于同构化凸壳构造基本定理,阐明了有限二维点集或线段集凸壳生成算法改进与优化的同构化方向,应当是:第一,使凸壳极点(或称顶点)分布域极小化,即让包含凸壳极点的判定区域尽可能小;使极点判定对象直接化,即让所判定对象尽可能接近当前所寻极点。第二,尽力对有可改造潜力的优秀串行凸壳算法施以并行化改造和创新。

In this paper, the common weakness of the current algorithms for seeking the convex hull of a finite 2D points set or Line Segment Set （include： polygons, closure broken lines, semi-closure broken lines,opening line segments, etc. ） is pointed out up to day; the isomorphic fundamental theorem of the convex hull is raised, with which an algorithm for determining the convex hull would be improved and optimized. Further, based on the isomorphic fundamental theorem of the convex hull, an isomorphic direction of improving and optimizing an algorithm for determining the convex hull of a finite 2D points set or line segments set is clarified, which should be; 1）. a minimum distributed domain of the poles of the convex hull, i. e. , make that the domain including all poles of the convex hull is as small as possible; a immediate objects-judged for all poles of the convex hull, i. e. , make all objects-judged are as near by the current poles of the convex hull to be determined as possible. 2） try one＇s best to improve the excellent sequential algorithms, which would be reformed, for finding the convex hull into their parallel algorithms, or create other new parallel algorithms.