我有一个由2D中的4个点定义的4边凸多边形,我希望能够在其中生成随机点。
如果它确实简化了问题,我可以将多边形限制为平行四边形,但更一般的答案是首选的。
生成随机点直到一个人进入多边形是行不通的,因为它所花费的时间真的是不可预测的。
发布于 2008-10-27 18:09:42
假设你想要一个均匀的分布:从你的多边形形成两个三角形。根据面积比例选择要生成点的三角形。
调用三角形A,B,C的角点,边向量AB,BC,AC,生成0,1中的两个随机数u和v,设p=u* AB +v* AC。
如果A+p在三角形内,则返回A+p
如果A+p在三角形之外,则返回A+ AB + AC -p
(这基本上是PierreBdR的公式,除了预处理和将点折叠回三角形的最后一步,因此它可以处理平行四边形以外的其他形状)。
发布于 2008-10-27 17:46:16
您的多边形是两个三角形,所以为什么不随机选择其中之一,然后在三角形中找到一个随机点。
可能不是最好的解决方案,但它可以工作。
发布于 2008-10-27 17:44:41
一种稍微不那么"naïve“的方法是使用polygon fill algorithm,然后从填充线中随机选择点。
C代码示例
// public-domain code by Darel Rex Finley, 2007
int nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;
// Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {
// Build a list of nodes.
nodes=0; j=polyCorners-1;
for (i=0; i<polyCorners; i++) {
if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
|| polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
*(polyX[j]-polyX[i])); }
j=i; }
// Sort the nodes, via a simple “Bubble” sort.
i=0;
while (i<nodes-1) {
if (nodeX[i]>nodeX[i+1]) {
swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
else {
i++; }}
// Fill the pixels between node pairs.
// Code modified by SoloBold 27 Oct 2008
// The flagPixel method below will flag a pixel as a possible choice.
for (i=0; i<nodes; i+=2) {
if (nodeX[i ]>=IMAGE_RIGHT) break;
if (nodeX[i+1]> IMAGE_LEFT ) {
if (nodeX[i ]< IMAGE_LEFT ) nodeX[i ]=IMAGE_LEFT ;
if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
for (j=nodeX[i]; j<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}
// TODO pick a flagged pixel randomly and fill it, then remove it from the list.
// Repeat until no flagged pixels remain.
https://stackoverflow.com/questions/240778
复制相似问题