质心容量限制Power图一体化生成算法

doi:10.16182/j.issn1004731x.joss.201807008

系统仿真学报 ›› 2018, Vol. 30 ›› Issue (7): 2489-2496.doi: 10.16182/j.issn1004731x.joss.201807008

质心容量限制Power图一体化生成算法

郑利平, 路畅, 蔡瑞文, 桂志强

合肥工业大学计算机与信息学院,安徽合肥 230009

收稿日期:2017-08-08 出版日期:2018-07-10 发布日期:2019-01-08
作者简介:郑利平(1978-), 男, 湖北, 博士, 教授, 研究方向为可视化、群体和疏散仿真; 路畅(1991-), 男, 安徽, 硕士生, 研究方向为计算机图形学与信息可视化。
基金资助:
国家重点研发计划(2016YFC0800100),安徽省科技强警项目(1704d0802177)

Integrated Generating Algorithm of Centroidal Capacity Constrained Power Diagram

Zheng Liping, Lu Chang, Cai Ruiwen, Gui Zhiqiang

School of Computer and Information, Hefei University of Technology, Hefei 230009, China

Received:2017-08-08 Online:2018-07-10 Published:2019-01-08

摘要/Abstract

摘要： Power图是带权重的Voronoi图,对Power图施加容量限制与质心限制,即可得到基于质心的容量限制Power图(Centroidal Capacity Constrained Power Diagram,CCCPD)。为解决现有CCCPD生成算法交替优化权重和站点位置带来的相互干扰、收敛减慢问题,提出对所有变量进行一体化优化的生成算法,采用多目标优化策略,直接优化质心限制和容量限制形成的混合能量。结果表明：所提算法的生成性能比传统方法提高40%。

关键词: Power图, 容量限制, 质心, 快速生成

Abstract: Power diagram is the weighted Voronoi diagram. Centroidal capacity constrained power diagram (CCCPD) can be obtained by imposing capacity constraint and centroid constraint to the ordinary power diagram. To increase the convergence speed of existing CCCPD algorithms which optimize the weight and location of site interlacedly, an improved algorithm is proposed which optimizes all variables integratedly. Research results exhibit that the performance of the proposed algorithm is 40% higher than the traditional method.

Key words: power diagram, capacity constrained, centroidal, fast computing

中图分类号:

TP391.1

郑利平, 路畅, 蔡瑞文, 桂志强. 质心容量限制Power图一体化生成算法[J]. 系统仿真学报, 2018, 30(7): 2489-2496.

Zheng Liping, Lu Chang, Cai Ruiwen, Gui Zhiqiang. Integrated Generating Algorithm of Centroidal Capacity Constrained Power Diagram[J]. Journal of System Simulation, 2018, 30(7): 2489-2496.

参考文献

[1] Balzer M, Schlömer T, Deussen O.Capacity- Constrained Point Distributions:A Variant of Lloyd's Method[J]. ACM Transactions on Graphics (S0730-0301), 2009, 28(3): 86.
[2] De Goes F, Breeden K, Ostromoukhov V, et al.Blue noise through optimal transport[J]. ACM Transactions on Graphics (S0730-0301), 2012, 31(6): 567-571.
[3] 郑利平, 程亚军, 周乘龙, 等. 异构群体队形光滑变换控制方法[J]. 计算机辅助设计与图形学学报, 2015, 27(10): 1963-1970.
Zheng Li-Ping, Cheng Ya-Jun, Zhou Cheng-Long, et al.Research on Smooth Formation Control of Heterogeneous Crowds[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(10): 1963-1970.
[4] Mridul Aanjaneya, Ming Gao, Haixiang Liu, et al.Power diagrams and sparse paged grids for high resolution adaptive liquids[J]. ACM Transactions on Graphics(S0730-0301), 2017, 36(4): 140.
[5] 郑利平, 江婷, 周乘龙, 等. 基于Power图求解容量限制P-中值问题[J]. 计算机应用, 2015, 35(6): 1623-1627.
Zheng Li-Ping, Jiang Ting, Zhou Cheng-Long, et al.Solving approach of capacity constrained P-median problem based on Power diagram[J]. Journal of Computer Applications, 2015, 35(6): 1623-1627.
[6] 郑利平, 刘玉飞, 江婷, 等. 稠密需求下城市应急中心布局方法[J]. 计算机辅助设计与图形学学报, 2014, 26(6): 948-955.
Zheng Li-Ping, Liu Yu-fei, Jiang Ting, et al.A Layout Approach of City Emergency Centers with Dense Demand[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(6): 948-955.
[7] Borgwardt S.On Soft Power Diagrams[J]. Journal of Mathematical Modelling and Algorithms in Operations Research (S2214-2487), 2015, 14(2): 173-196.
[8] G Barlow.Hexagonal territories[J]. Animal Behav (S0003-3472), 1974(22): 876-878.
[9] 郑利平, 程亚军, 路畅, 等. 质心Power图下覆盖路径规划算法[J]. 系统仿真学报, 2017, 29(5): 1120-1124.
Zheng Liping, Cheng Yajun, Lu Chang, et al.Coverage Path Planning Algorithm Based on Centroidal Power Diagram[J]. Journal of System Simulation, 2017, 29(5): 1120-1124.
[10] Aurenhammer F.Voronoi diagram-A survey of a fundamental geometry data structure[J]. ACM Computing Surveys(S0360-0300), 1991, 23(3): 345-405.
[11] Aurenhammer F.Power diagrams: properties, algorithms and applications[J]. SIAM Journal on Computing (S0097-5397), 1987, 16(1): 78-96.
[12] H Imai, M Iri, K Murota.Voronoi diagram in the Laguerre geometry and its application[J]. SIAM Journal on Computing(S0097-5397), 1985, 14(1): 93-105.
[13] Balzer Michael, Daniel Heck.Capacity-constrained Voronoi diagrams in finite spaces[C]//Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering, Voronoi’s Impact on Modern Science, 2008, 4(2): 44-56.
[14] Balzer M.Capacity-constrained Voronoi diagrams in continuous spaces[C]. ISVD, 2009: 79-88.
[15] 江婷. 容量限制Power 图的快速生成及其应用[D]. 合肥: 合肥工业大学, 2015.
Jiang Ting.A Rapid Generating Method of Capacity Constrained Power Diagram and Its Applications [D]. Hefei: Hefei University of Technology, 2015.
[16] Xin S Q, Vy B, Chen Z, et al.Centroidal power diagrams with capacity constraints: computation, applications, and extension[J]. ACM Transactions on Graphics (S0730-0301), 2016, 35(6): 1-12.

质心容量限制Power图一体化生成算法

Integrated Generating Algorithm of Centroidal Capacity Constrained Power Diagram

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	费月, 桂志强, 姚裕友, 徐本柱, 郑利平. 面状LED发光体灯珠分布和组合连接优化算法[J]. 系统仿真学报, 2020, 32(12): 2317-2323.
[2]	李琦, 崔建江, 薛定宇, 耿宏雨. 一种手背静脉感兴趣区域提取算法[J]. 系统仿真学报, 2019, 31(10): 2174-2180.
[3]	孙水发, 李准, 夏坤, 施云飞, 杨继全, 董方敏. 变尺度点云配准算法[J]. 系统仿真学报, 2018, 30(7): 2465-2474.
[4]	王继东, 范丽鹏, 庞明勇. 密度场控制的四面体网格自适应生成算法[J]. 系统仿真学报, 2018, 30(1): 45-52.
[5]	郑利平, 程亚军, 路畅, 廖婷. 质心Power图下覆盖路径规划算法[J]. 系统仿真学报, 2017, 29(5): 1120-1124.