设为首页收藏本站

EPS数据狗论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 1588|回复: 0

[数据可视化] 在不规则多边形内均匀撒点的算法

[复制链接]

18

主题

126

金钱

210

积分

入门用户

发表于 2019-8-13 13:14:18 | 显示全部楼层 |阅读模式

给定一个不规则的多边形(可能是凹多边形,可能是凸多边形),在其中要显示拓扑网络数据,要求节点不重合、不超出边界。


该问题出现的场景:
在地图上撒点
在未知画布上生成初始的拓扑布局

解决方案:
方法一 随机撒点
取凸多边形的外接矩形,在矩形中随机撒点,如果落在凸多边形外,再次随机撒点,直至落在凸多边形内。
这个方法比较暴力,可以通过计算期望来控制撒点次数,撒点次数应该符合泊松分布。

方法二 把不规则多边形切割成若干三角形
可以看作方法一的改进。切成多个三角形之后,问题转化为了如何在多个三角形内撒点。
参考:https://beta.observablehq.com/@scarysize/finding-random-points-in-a-polygon
切割库:https://github.com/mapbox/earcut
1.png
三角形是凸多边形,如何在三角形内均匀撒点可参考:http://mathworld.wolfram.com/TrianglePointPicking.html

算法步骤:
1.随机选取任意一三角形
2.在三角形内撒点
3.重复12,直到点撒完

这里有个问题*:每个三角形被选取的概率相同,但三角形面积不同。这就可能出现小面积三角形中的点和大面积三角形中的点个数差不多,从而造成总体上看起来点集中在小面积三角形中的情况。
所以要保证三角形被选取的概率跟它的面积成正比。

方法三 用力导向迭代
可以看作是 方法二 的改进。给随机撒好的点设置相同的电荷力,使其不停迭代到稳定状态,即形成下图状态,达到尽量“均匀”。
参考:https://bl.ocks.org/mbostock/1b64ec067fcfc51e7471d944f51f1611
2.png

方法四 用四叉树生成点
和前三种方法无关。用四叉树将二维空间切割成相等大小的正方形,然后用正方形图心撒点。
参考:https://www.phase2technology.com/blog/using-d3-quadtrees-power-interactive-map-bonnier-corporation
3.png
4.png

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /1 下一条

客服中心
关闭
在线时间:
周一~周五
8:30-17:30
QQ群:
653541906
联系电话:
010-85786021-8017
在线咨询
客服中心

意见反馈|网站地图|手机版|小黑屋|EPS数据狗论坛 ( 京ICP备09019565号-3 )   

Powered by BFIT! X3.4

© 2008-2028 BFIT Inc.

快速回复 返回顶部 返回列表