Nob*_*ody 5 algorithm mesh approximation
给定(可能是开放的)具有密度纹理和多个点的网格,我需要根据网格上的密度分布这些点.
到目前为止,我已经制定了几个解决方案,其中一些有效,有些则没有.我尝试的算法之一是通过弹簧连接点并模拟分布直到平衡(或直到解决方案适合用户需求).源重新排列多边形表面 不幸的是,对于更高数量的点(> 2k),这有点慢,所以我需要一个可行的解决方案来获得更高的数字.
我已经有了一些想法,但我想听听是否有一些标准的解决方案.我试过谷歌,但我使用的关键字(分布密度离散)只显示处理与我的其他问题的页面.如果你指出正确的搜索词,我会很高兴的.
通常,在具有任意密度函数的任意空间中,您可以通过拒绝采样得到合理的近似值.
D.p.r从范围中选择一个随机数[0,D).p大于r,则接受p作为您的一个点.我不确定这适用于您的案件有多容易.在网格上生成随机,均匀分布的点本身就像一个棘手的问题.我能想到的唯一解决方案是计算网格中每个三角形的面积,随机选择一个与其面积成比例的三角形,并在三角形内选择一个随机点.我相信你可以在O(logN)的N个三角形上做这个选择.
但是考虑到你可能会抛弃大部分这些点,这可能会比你当前的方法更糟糕,因为网格足够大并且密度函数非常令人不快(即最大值远大于平均值).
像任何类型的随机抽样一样,在它开始类似于底层分布之前需要花费很多点; 一小部分点可能看起来或多或少随机.但是你可以通过某种准随机的点放置方法解决这个问题(即使使用大型集合,也可能会产生更好的结果).
我想到的一件事是上述方法与@ BlackBear算法的混合.您可以计算每个三角形的面积和平均密度,并使用它来确定每个三角形必须包含的点数.然后,要将点实际放置在三角形内,请使用拒绝采样方法.