0

我正在寻找一种算法，该算法将从图像中生成凹多边形（具有 N 个点，其中 N > 3 - 用户输入此值）。

我对算法的想法：

 // Every pixel in image is checked and a minimal orientated bounding box  is generated  (transparent pixels are ignored)
 boundingBox = createImageBoundingBox(image);
 curpoints = 4, A = 0, B = 1, tmppoints = curpoints;
 while(curpoints < maxNumberOfPoints)
 { 
    add a new point between point A and point B (A and B are points from the boundingBox)
    reposition points so that it will contain the minimal surface
    A++; B++;
    curpoints++;

    if(A == tmppoints) 
    { A = 0; B = 1; tmppoints=curpoints; }
 }

我面临的问题是我不知道如何最佳地重新定位点。这可以通过任何其他方式完成（更好/更快的方式）。将不胜感激任何想法。

谢谢

编辑：

图像必须至少为 10x10。我需要 N 点参数，以便用户可以调节要使用的点数（用于优化）。另一种方法是使用一个因子 (0-1)，它告诉您希望多边形具有多少细节（多少点）（0 是 4 个点，> 0 5 个或更多点）。但不确定如何实施。

4

3 回答 3

2

您可以使用 delaunay 三角剖分并获得平均边长。然后尝试删除比平均值更长的边缘。这个概念来自阿尔法形状。

于 2013-09-23T13:24:49.260 回答
1

凹形船体可以用阿尔法形状建造。CGAL 链接。

于 2012-04-28T02:57:39.533 回答
1

1.) 在方形图像的中间选择一个点。

2.) 从中心随机抖动这个点N次，生成N个新点。

3.) 根据与中心点的最大角度对这些点进行排序

4.）使用边界框中的四个点和按升序角度排序的中点来创建凹多边形的有序点列表。

我不确定我是否理解您上面的“最小表面”步骤，但我相信这个算法可以用于截取图像以生成凹多边形。我认为这比你上面的要快，但我不确定，因为我不完全理解那一步。

这将始终生成与原始图像具有相同边界的凹多边形。如果您不想要这个，您可以添加一个步骤 0.)，它会抖动您的边界框，然后根据此更改您的中点抖动。我认为，这两个想法都会产生一个带有 n 大小点块的边界四边形。

  • 这需要 n > 4 （如果您希望这需要 n > 3，则将两个边界框点合并为一个，就像您说的那样。）
于 2012-04-27T19:28:15.943 回答