一种基于空间染色细胞搜索一融合生成Voronoi图的统一框架

打开文本图片集

中图分类号：TP391；P91 文献标识码：A

文章编号：1006-8228（2025）10-11-07

AUnified Framework for Generating Voronoi Diagrams Based on Search-and-Merge of Spatial Chromatic Cells

Zhuge Yan1，Liu Jing'，ZhuWeining²

（1.ZhejiangTechnical InstituteofEconomics，Hangzhou，Zhejiang31o9，China;2.ZhejiangUniversity）

Abstract：AsatypeofspatialteselltionmodelVoronoidiagam（V）iswidelyusedinmanynaturalandsocialfeldssuchas computersciene，geogaphcoomicsologyandphsicsanditisalsonimportantspatialstructuralobjectforcoutatioal geometryresearch.Whengenerationspacestypesofspatialentities，distancemetricsandrelationshipsbetweeentitiesandVoronoi spacesdiffr，Voronoidiagrams（VDs）exhibitvarioustypes，suchastheordinaryVD，VDinspheres，VDforlinearentities， weightedVD，orderedhigher-orderVD，andtheseVDsalsohavetheirownmultipleconstructionalgorithms.Inthispaper，we proposeanewSearch-and-Merge （&M）Voronoiconstructionalgorithmwhichisbasedonaspatialchromaticmodel.The advantageoftheS&MalgorithmisthatitcanquicklyconstructdiverseVDsunderauniformframeworkandviasearching databases，withoutdesigningaspecificalgorithmforeachVD.Thedatabase-basedS&MVoronoialgorithmcanbeparticularly apliedinthecaseswhereavarietyofVoronoidiagramsarerequestedfrequentlyforcomputationandanalysis，suchasthe location-basedspatialanalysis.Inadion，theproposedS&Mmethodcangeneratesomenewspatialteselltionswhichare different from the VDs in terms of features.

Keywords：Voronoi Diagram； Spatial Chromatic Model; Spatial Tesselation; Computational Geometry

0引言

Voronoi图（Voronoidiagram，以下简称VD或V图）是一种空间镶嵌或剖分模型-21，早期法国数学家Descartes、德国数学家Dirichlet及乌克兰数学家Voronoi（V图因此得名）均对该模型开展过理论构建与应用研究。（剩余9451字）