首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >平行四边形内的随机点

平行四边形内的随机点
EN

Stack Overflow用户
提问于 2008-10-27 17:40:37
回答 8查看 27.7K关注 0票数 47

我有一个由2D中的4个点定义的4边凸多边形,我希望能够在其中生成随机点。

如果它确实简化了问题,我可以将多边形限制为平行四边形,但更一般的答案是首选的。

生成随机点直到一个人进入多边形是行不通的,因为它所花费的时间真的是不可预测的。

EN

回答 8

Stack Overflow用户

发布于 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的公式,除了预处理和将点折叠回三角形的最后一步,因此它可以处理平行四边形以外的其他形状)。

票数 18
EN

Stack Overflow用户

发布于 2008-10-27 17:46:16

您的多边形是两个三角形,所以为什么不随机选择其中之一,然后在三角形中找到一个随机点。

可能不是最好的解决方案,但它可以工作。

票数 4
EN

Stack Overflow用户

发布于 2008-10-27 17:44:41

一种稍微不那么"naïve“的方法是使用polygon fill algorithm,然后从填充线中随机选择点。

C代码示例

代码语言:javascript
复制
//  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.
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/240778

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档