做方案收集图片的网站,红木家具网站模板,营销网站建设定制,网站后台不能编辑目录
一、说明
二、帝国边界划分问题
三、voronoi的正规定义
3.1 最简单的voronoi情况
3.2 在距离空间的数学描述
3.3 不同距离空间所得 Voronoi 单元不同
四、代码和库
4.1 算法库
4.2 参数说明
4.3 调用方法
五、后记 一、说明 Voronoi 单元也称为泰森多边形。 …目录
一、说明
二、帝国边界划分问题
三、voronoi的正规定义
3.1 最简单的voronoi情况
3.2 在距离空间的数学描述
3.3 不同距离空间所得 Voronoi 单元不同
四、代码和库
4.1 算法库
4.2 参数说明
4.3 调用方法
五、后记 一、说明 Voronoi 单元也称为泰森多边形。 Voronoi 图在许多领域都有实际和理论应用主要是在科学和技术领域但也在视觉艺术领域使用。Voronoi 图以数学家 Georgy Voronoy 的名字命名也称为 Voronoi 镶嵌、Voronoi 分解、Voronoi 分区或 Dirichlet 镶嵌以 Peter Gustav Lejeune Dirichlet 命名。 在数学中Voronoi 图是将对平面集合划分为多个区域的算法。在最简单的情况下这些对象只是平面上的有限多个点称为种子、站点或生成器。对于每个种子都有一个对应的优先划分区域。这种区域称为 Voronoi 单元由平面上离该种子比其他任何点更近的所有点组成。一组点的 Voronoi 图与该组的 Delaunay 三角剖分是对偶的。 注意点、区域、边界线成为这个算法的关键要素。 二、帝国边界划分问题 我们用一个童话故事构成思想实验。 话说哈里发国王年事已高厌倦朝政因而计划将他的王国分为四份分别由四个王子管理。于是召来宰相易普拉辛说到“我亲爱的宰相我打算将王国分成四个部落分别交给王子们统辖如今有四个城池分别是查兰是哥达玛宿吐作为它们的都城可是如何划分疆土我毫无主张是真主启发我召你商议此事。”宰相思索片刻说到“赞美安拉我倒是有一个谋划请借地图叙述”国王当即请出地图如下 且看宰相如何划分国土。首先确定查兰的边疆如下 1从查兰引出两个线段分别连接是哥达玛因为宿土与查兰不接壤所以不必引进宿土。 2分别作出两条线段的垂直中分线。 做出两条中分线L1L2。中分线上的特征是L1线上点到查兰的距离一定等于该点到是哥距离L2上的任意点到查兰距离一定等于它到达玛的距离。因此站在平分线上看两国首都谁也没“侵犯”谁。故绿线和红线都是“公平线”就此查兰的土地被公平线L1和L2包络已经画出。 3接着划分达玛从达玛引出线段连接宿土和是哥作公平线S1和S2这样达玛土地在公平线L2S1S1包围下也能画出如图粉色区域。 显然图中新增出粉色区域中任意一点到达玛距离比到其它三城距离更近保证达玛没有“侵犯”其它邻国。至此达玛的边界因L2S1S2包络而确定。 注意 虽然有公平线L1横穿达玛但此线是【查兰是哥】的公平线与达玛无关。 4最后从宿土到是哥引出线段并做出中分线T 如图 至此宿土的边疆也因T-S2-L1包络出是哥的领土至此国土划分完成。 哈里发看了宰相的划分依然不悦对宰相说到“依照爱卿的划分国土面积不等如何说服四位王子服从分配”宰相说到“安啦是唯一的主不妨把命运交给安拉让他们抓阄分配”国王听后大喜曰“然”。 提示有个三线交于一点的问题如L1-L2-S2三线交于一点T-S1-S2三线相交。这需要证明。 三条线共交于一点的说明在相邻三城边界划分中每三个中分线是共点的如下证明 先假定篮圈内三线不相交从角的垂线定律说明红蓝角红黑角黑绿角180度因此三线必然共点。 或者说三个点组成三角形其外接圆圆心引出三条到边的垂线这三条垂线正好等分三边。 三、voronoi的正规定义
3.1 最简单的voronoi情况 在最简单的情况下如第一张图片所示我们在欧几里得平面中得到一组有限的点 {p1, ..., pn}。在这种情况下每个站点 pk 只是一个点其对应的 Voronoi 单元 Rk 由欧几里得平面中的每个点组成这些点到 pk 的距离小于或等于它到任何其他 pk 的距离。每个这样的单元都是从半空间的交集获得的因此它是一个凸多面体。 [6] Voronoi 图的线段是平面上与最近的两个站点等距的所有点。 Voronoi 顶点节点是与三个或更多站点等距的点。 3.2 在距离空间的数学描述 下文中生成点站点 设X是一个距离函数的度量空间K是一组索引 是空间中非空子集站点的元组索引集合。 Voronoi 单元或 Voronoi 区域与网站相关 是所有点的集合距离 不大于它们到其他站点的距离其中 是任何不同于。换句话说如果 表示点与集合之间的距离 和子集然后有 Voronoi 图只是单元格的元组。原则上一些站点可以相交甚至重合下面描述了代表商店的站点的应用程序但通常假定它们是不相交的。此外定义中允许有无限多个站点此设置在数字几何和晶体学中有应用但同样在许多情况下只考虑有限多个站点。 在空间是有限维欧几里德空间的特殊情况下每个站点都是一个点有有限多个点并且所有点都不同那么 Voronoi 单元是凸多边形它们可以用组合方式表示它们的顶点、边、二维面等。有时导出的组合结构被称为 Voronoi 图。然而一般而言Voronoi 单元可能不是凸的甚至可能不是连接的。在通常的欧几里德空间中我们可以用通常的术语重写形式定义。每个 Voronoi 多边形 与生成点相关联。假定 是欧氏空间中所有点的集合。且 是生成其 Voronoi 区域的的点 生成2个, 和3个 生成3个等等。然后Voronoi 多边形中的所有位置都比欧几里得平面中的 Voronoi 图中的任何其他生成点更接近该多边形的生成点”。
3.3 不同距离空间所得 Voronoi 单元不同 如图下面是基于欧氏空间和曼哈顿空间的划分 以上就是欧氏空间和曼哈顿空间的划分细节。 四、代码和库
4.1 算法库
以下给出算法库Voronoi是通过python写的代码
from PIL import Image, ImageColor, ImageDraw
from random import randint, choice, random, seed as randomseed
from typing import *
from math import hypot, sqrt
from queue import Queue
from dataclasses import dataclass
from enum import Enumimport os
import sysclass ColorAlgorithm(Enum):random 1no_adjacent_same 2least_possible 3class RegionAlgorithm:def randomized(width: int, height: int, regions: int, mask_function) - List[Tuple[int, int]]:Return regions that are entirely random.points []while len(points) ! regions:p (randint(0, width - 1), randint(0, height - 1))if p in points:continueif not mask_function(p):continuepoints.append(p)return pointsdef uniform(width: int, height: int, regions: int, mask_function) - List[Tuple[int, int]]:Return regions that attempt to be somewhat uniform.k 10points []while len(points) ! regions:best_p Noned_max 0i 0while i k * len(points) 1:p (randint(0, width - 1), randint(0, height - 1))if p in points:continueif not mask_function(p):continueif len(points) 0:best_p pbreakd_min float(inf)for x, y in points:d hypot(p[0]-x, p[1]-y)if d d_min:d_min dif d_min d_max:d_max d_minbest_p pi 1points.append(best_p)return pointsclass DistanceAlgorithm:def euclidean(x, y, xn, yn):Calculate the image regions (up to a distance) using euclidean distance.return hypot(xn-x, yn-y)def manhattan(x, y, xn, yn):Calculate the image regions using manhattan distance.return abs(xn-x) abs(yn-y)def euclidean45degrees(x, y, xn, yn):Calculate the image regions using euclidean, but allow only lines in 45 degree increments.return sqrt(2 * min(abs(xn-x), abs(yn-y)) ** 2) abs(abs(xn-x) - abs(yn-y))def chebyshev(x, y, xn, yn):Calculate the image regions using chebyshev distance.return min(abs(xn-x), abs(yn-y)) abs(abs(xn-x) - abs(yn-y))def set_each_point(seed: int, width: int, height: int,region_centers: List[Tuple[int, int]], image: List[List[int]],d_limit: int, f: List[Callable[[int, int, int, int], float]], mask_function):Calculate the image regions (up to a distance) using the provided metric.randomseed(seed)region_distance_functions [f if not isinstance(f, list) else choice(f) for _ in range(len(region_centers))]for x in range(width):for y in range(height):if not mask_function((x, y)):continued_min float(inf)for i, region in enumerate(region_centers):xn, yn regiond region_distance_functions[i](x, y, xn, yn)if d d_min:d_min dif d d_limit:image[x][y] id(region)class Utilities:def error(message, qTrue):print(f\u001b[38;5;1mERROR:\u001b[0m {message}, flushTrue)if q:sys.exit(1)def warning(message):print(f\u001b[38;5;208mWARNING:\u001b[0m {message}, flushTrue)def info(message):print(f\u001b[38;5;11mINFO:\u001b[0m {message}, flushTrue)def success(message):print(f\u001b[38;5;2mSUCCESS:\u001b[0m {message}, flushTrue)def hex_to_tuple(color: str):color color.strip(#)return (int(color[0:2], 16), int(color[2:4], 16), int(color[4:6], 16))def get_different_adjacent_colors(width, height, image, colors, color_algorithm):from pulp import LpProblem, LpVariable, LpMinimize, lpSum, PULP_CBC_CMDedges set()mapping {}n 0for x in range(width):for y in range(height):for xd, yd in ((0, 1), (1, 0), (-1, 0), (0, -1)):xn, yn x xd, y ydif not 0 xn width or not 0 yn height:continuei1, i2 image[x][y], image[xn][yn]if i1 is None or i2 is None:continueif i1 i2:if i1 not in mapping:n 1mapping[n] i1mapping[i1] nif i2 not in mapping:n 1mapping[n] i2mapping[i2] nedges.add((mapping[i1], mapping[i2]))edges list(edges)model LpProblem(senseLpMinimize)chromatic_number LpVariable(namechromatic number, catInteger)variables [[LpVariable(namefx_{i}_{j}, catBinary) \for i in range(n)] for j in range(n)]for i in range(n):model lpSum(variables[i]) 1for u, v in edges:for color in range(n):model variables[u - 1][color] variables[v - 1][color] 1for i in range(n):for j in range(n):model chromatic_number (j 1) * variables[i][j]if color_algorithm ColorAlgorithm.least_possible:model chromatic_numberelse:model chromatic_number len(colors)status model.solve(PULP_CBC_CMD(msgFalse))if chromatic_number.value() len(colors):Utilities.error(Not enough colors to color without adjacent areas having the same one!)return {mapping[variable 1]: colors[color]for variable in range(n)for color in range(n)if variables[variable][color].value() 1}def add_border(background, border_size, read_image, write_image, width, height, mask_function):r border_size // 2for x in range(width):for y in range(height):if not mask_function((x, y)):continuefor dx, dy in ((0, 1), (1, 0)):xn, yn x dx, y dyif not 0 xn width or not 0 yn height:continueif not mask_function((xn, yn)):continueif read_image[x][y] ! read_image[xn][yn]:draw ImageDraw.Draw(write_image)draw.ellipse((x-r, y-r, xr, yr), fill(*background,0))def generate(path: str,regions: int,colors: List[Union[Tuple[int], str]],width: int 1920,height: int 1080,region_algorithm RegionAlgorithm.uniform,distance_algorithm DistanceAlgorithm.euclidean,color_algorithm ColorAlgorithm.random,seed: Optional[int] None,border_size: int 0,mask: Optional[str] None,mask_color #000000,animate False,background #FFFFFF,
):# possibly seed the random algorithmif seed is None:seed random()# possibly convert string colors to tuplesi 0while i len(colors):if type(colors[i]) str:colors[i] Utilities.hex_to_tuple(colors[i])i 1if type(mask_color) str:mask_color Utilities.hex_to_tuple(mask_color)elif type(mask_color) list:mask_color tuple(mask_color)if type(background) str:background Utilities.hex_to_tuple(background)elif type(background) list:background tuple(background)randomseed(seed)mask_function lambda p: Trueif mask is not None:try:mask_img Image.open(mask)Utilities.info(Mask provided.)w, h mask_img.sizemask_function lambda p: mask_img.getpixel(p) mask_colorif w ! width:Utilities.warning(Specified width doesnt match mask width, using mask width.)width wif h ! height:Utilities.warning(Specified height doesnt match mask height, using mask width.)height hexcept Exception as e:Utilities.error(fError loading mask from {mask}.)if type(regions) list:Utilities.info(Region centers provided, skipping generation.)# flip vertically!region_centers [(int(center[0] * width), int(height - center[1] * height)) for center in regions]else:Utilities.info(Calculating region centers.)region_centers region_algorithm(width, height, regions, mask_function)image [[None] * height for _ in range(width)]Utilities.info(Calculating region areas.)DistanceAlgorithm.set_each_point(seed, width, height, region_centers, image, float(inf), distance_algorithm, mask_function)# either assign colors randomly, or calculate the chromatic number and assign them thenif color_algorithm ColorAlgorithm.random:Utilities.info(Assigning region colors.)region_colors {id(region): choice(colors) for region in region_centers}else:Utilities.info(Assigning region colors such that no two adjacent regions have the same color.)region_colors Utilities.get_different_adjacent_colors(width, height, image, colors, color_algorithm)# if were masking, some regions wont be assignedregion_colors[None] background# the original, full image (without borders)pil_image Image.new(RGB, (width, height))for x in range(width):for y in range(height):pil_image.putpixel((x, y), region_colors[image[x][y]])if border_size ! 0:Utilities.add_border(background, border_size, image, pil_image, width, height, mask_function)if animate:if not os.path.exists(path):os.makedirs(path)d 1while True:animation_image [[None] * height for _ in range(width)]DistanceAlgorithm.set_each_point(seed, width, height, region_centers, animation_image, d, distance_algorithm, mask_function)animation_pil_image Image.new(RGB, (width, height))for x in range(width):for y in range(height):animation_pil_image.putpixel((x, y), background if animation_image[x][y] is None else region_colors[image[x][y]])if border_size ! 0:Utilities.add_border(background, border_size, animation_image, animation_pil_image, width, height)animation_path os.path.join(path, f{d}.png)animation_pil_image.save(animation_path, PNG)Utilities.success(fAnimation image saved to {animation_path})d 1if image animation_image:Utilities.success(fDone!)breakelse:pil_image.save(path, resolution300)Utilities.success(fImage saved to {path}!)
4.2 参数说明
generate function arguments
path: the path (including an extension) to save the resulting file toregions: the number of distinct regions in the diagramcolors: a list of tuples denoting the RGB of the color, or strings denoting the color in hexwidth: the width of the image; defaults to 1920height: the height of the image; defaults to 1080region_algorithm: the algorithm that determines the centers of the regions: RegionAlgorithm.uniform attempts to make the centers equidistant to one another; defaultRegionAlgorithm.randomized makes the center positions entirely randomdistance_algorithm: the algorithm that determines the way the distance is measured; if a list of the algorithms is provided, a random one is picked for each point DistanceAlgorithm.euclidean: standard euclidean distance (hypotenuse); defaultDistanceAlgorithm.manhattan: Manhattan (taxicab) distance (4 directions)DistanceAlgorithm.chebyshev: Chebyshev distance (8 directions)DistanceAlgorithm.euclidean45degrees: euclidean distance, but lines can only point in 45 degree incrementscolor_algorithm: the algorithm that determines the colors of the regions DistanceAlgorithm.random: pick the colors randomlyDistanceAlgorithm.no_adjacent_same: pick the colors such that no two adjacent regions have the same colorDistanceAlgorithm.least_possible: same as no_adjacent_same, but attempt to do so in the least number of colorsseed: the seed for the random number generator; no seed by defaultborder_size: the thickness of the border (in pixels); defaults to 0 (no border)mask: a path to an image mask so only specific areas are usedmask_color: the color of the mask to fill, ignoring everything else; defaults to #000000animate: creates images in the folder path of the regions filling in; defaults to Falsebackground: background of the animation/masking/borders; defaults to #FFFFFF
4.3 调用模块的方法
from voronoi import *generate(path 1.png,width 3840,height 2160,regions 70,colors [(0, 0, 0), (15, 15, 15), (23, 23, 23), (30, 30, 30)],color_algorithm ColorAlgorithm.no_adjacent_same,
)
结果图 五、后记 值得注意的是本文专注于说明Voronoi图是个啥有两个问题需要进一步阐述1特殊情况分析。2算法和原理没有说明。鉴于时间和精力有限本文先就此告一段落后续文章我们继续讨论更多的相关内容。
