以平行线段为模型的非精确数据凸包问题研究

doi:10.3778/j.issn.1002-8331.2010.01.047

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (1): 154-159.DOI: 10.3778/j.issn.1002-8331.2010.01.047

• 图形、图像、模式识别 • 上一篇下一篇

以平行线段为模型的非精确数据凸包问题研究

鞠汶奇^1，2，3，罗军²

1.中国科学院计算技术研究所，北京 100080
2.中国科学院深圳先进技术研究院，广东深圳 518055
3.中国科学院研究生院，北京 100049

收稿日期:2009-10-15 修回日期:2009-11-16 出版日期:2010-01-01 发布日期:2010-01-01
通讯作者: 鞠汶奇

New algorithms for convex hull of maximum area based on parallel line segment

JU Wen-qi^1，2，3，LUO Jun²

1.Institute of Computational Technologies，Chinese Academy of Sciences，Beijing 100080，China
2.Shenzhen Institute of Advanced Technology，Chinese Academy of Sciences，Shenzhen，Guangdong 518055，China
3.Graduate University of Chinese Academy of Sciences，Beijing 100049，China

Received:2009-10-15 Revised:2009-11-16 Online:2010-01-01 Published:2010-01-01
Contact: JU Wen-qi

摘要/Abstract

摘要： 现实应用中，计算机处理的数据往往是非精确的。对于非精确的输入数据，一般使用线段，圆和正方形等模型表示。对以平行线段代表非精确数据的模型研究非常重要，因为这种非精确数据模型是解决其他更复杂模型的基础[1]。loffler等[1]给出了一种算法，可以在时间O（n³）内求出以竖直平行线段表示的非精确数据的最大面积凸包。但是该算法对于任何输入数据计算量都是一样，而现实生活中的非精确数据往往不是完全没有规律的，比如来自同一设备采样的数据的误差范围是一致的。首先给出了一种新的算法，可以在O（nlog（n））时间内求出具有相同取值范围的非精确数据的最大面积凸包，同时研究了输入数据是n个非精确数据和m个退化为精确数据的非精确数据如何求最大面积凸包的问题。如果把这些已经退化的非精确数据仍然看作非精确数据，套用文献[1]的算法时间复杂度将会是O（（n+m）³）。针对这种情况给出了一种算法，算法时间复杂度为O（n³+nm）。

关键词: 非精确数据, 计算几何, 凸包

Abstract: The imprecise inputs can be assumed as segments，circles or squares.It is very important to study the model of parallel line segments for imprecise inputs because it is the fundament to solve other models.An algorithm for the largest area of the convex hull with the assumption of parallel line segments is presented in reference[1].The running time of the algorithm is O（n³）.But in many real life cases，there are some patterns for error ranges.For example，the error ranges are the same.In this paper a new algorithm is presented firstly.Using the algorithm the convex hull with the largest area in O（nlog（n）） is found out if the size of all the line segments is the same.When there are n imprecise data and m precise data，which can be regarded as degenerated imprecise data，mixed in the plane，the running time will be O（（n+m）³） if the algorithm in reference[1] is used.A new algorithm is also presented to solve the problem and the running time is O（n³+nm）.

Key words: imprecise data, computational geometry, convex hull

中图分类号:

TP301.6

鞠汶奇^1，2，3，罗军². 以平行线段为模型的非精确数据凸包问题研究[J]. 计算机工程与应用, 2010, 46(1): 154-159.

JU Wen-qi^1，2，3，LUO Jun². New algorithms for convex hull of maximum area based on parallel line segment[J]. Computer Engineering and Applications, 2010, 46(1): 154-159.

[1]	王家润，孙禹楠，尹辉，杨志龙. 军事目标关系的拟合地势及双重保凸可视建模[J]. 计算机工程与应用, 2020, 56(5): 270-278.
[2]	董本志，于尚书，景维鹏. 多先验融合的图像显著性目标检测算法[J]. 计算机工程与应用, 2019, 55(2): 179-186.
[3]	李格非1，马蔚吟2，李力3. Spark平台下的凸包问题研究[J]. 计算机工程与应用, 2018, 54(22): 67-73.
[4]	许孝盛1，靳萍2，郑稳2. 室内座椅线框图识别[J]. 计算机工程与应用, 2016, 52(23): 196-202.
[5]	杨秀娟1，董军1，李慧慧2. 欧式空间中反向最远邻查询方法的研究[J]. 计算机工程与应用, 2015, 51(4): 142-147.
[6]	傅天裕1，2，罗永龙1，2，郭良敏1，2，孙玲玲1，2. 保护私有信息的两多边形相交面积计算[J]. 计算机工程与应用, 2014, 50(9): 37-40.
[7]	吴芬1，仲红1，2，石润华1，2. 隐私保护的费马问题极值计算协议[J]. 计算机工程与应用, 2014, 50(4): 77-80.
[8]	黄珂，薛月菊，陈瑶，陈汉鸣，李鸿生. QR码图像几何校正算法的研究[J]. 计算机工程与应用, 2014, 50(20): 192-196.
[9]	汪志华，戴林送，陈素根，苏本跃. 拟Timmer曲线[J]. 计算机工程与应用, 2014, 50(10): 161-164.
[10]	才让卓玛1，张名成2. 基于结构特征的飞机目标识别方法[J]. 计算机工程与应用, 2013, 49(4): 174-177.
[11]	徐志，许宏丽. 一种基于凸包近似的快速体积计算方法[J]. 计算机工程与应用, 2013, 49(21): 177-179.
[12]	常振华1，陈伯成1，李英杰2，刘文煌1，闫学为3. SVM的几何方法—SK类思路的研究[J]. 计算机工程与应用, 2011, 47(8): 149-153.
[13]	李雪辉，魏立力. 多分类问题的凸包收缩方法[J]. 计算机工程与应用, 2011, 47(31): 135-137.
[14]	戴海鹏，唐厚君. 求凸多边形直径的改进算法[J]. 计算机工程与应用, 2011, 47(3): 44-46.
[15]	刘文静1，田铮1，2，张朝阳1. 图像点模式匹配的一种凸包序列的图谱方法[J]. 计算机工程与应用, 2011, 47(23): 197-200.

以平行线段为模型的非精确数据凸包问题研究

New algorithms for convex hull of maximum area based on parallel line segment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics