足迹查找算法

Question

我试图想出一种算法来优化多边形(或多个多边形)的形状，以最大化该形状中包含的值。

我有3列的数据：

• X: x轴上的位置
• Y: y轴上的位置
• 值:块的值，它可以有正值和负值。

这些数据来自一个规则的网格，因此每个x值和y值之间的间距是一致的。

我想要创建一个边界多边形，最大限度地使用所添加的条件所包含的值。

• 需要在多边形的所有点上保持最小半径。这意味着我们要么会失去一些正值块，要么会获得一些负值块。

我使用的当前算法执行以下操作

1. 查找最大块值作为起点(或定义的用户)。
2. 查找最小半径内的所有块，并通过检查整体值是否为正来确定其是否为可行点。
3. 从进一步的值计算中移除最小搜索半径中的所有块，并将其标记为最终形状的一部分。
4. 移动到下一个点，由一个螺旋围绕着原来的点。(中心始终是网格点，因此由deltaX或deltaY移动)

这似乎是在收集一些不需要的细胞。我肯定有一些形状算法，但我不知道该查找什么来寻找帮助。

下面是一张有希望帮助概述问题的图片。阳性细胞以红色显示(阴性细胞未显示)。黑色轮廓显示我当前例程正在返回的形状。我认为左路应该被引进更多。最小半径是100米，左下角的黑圈大约是这个。

​

​

现在，代码在R中运行，但如果算法正确，我可能会转到其他地方。

针对不明确的投票，我试图在没有背景或试图解决的情况下解决的问题是：

“在一系列点周围创建一个包围多边形(或多边形)，以使包含的值最大化，同时保持多边形的最小曲率半径”。

编辑：

数据

我应该包括一些数据，可以找到这里。

文件是csv。4列(X，Y，Z不使用，值)，长度为25k，大小为800 is。

Answer 1

如果解集必须是给定半径的磁盘的联合，我会尝试一种贪婪的方法。(我怀疑，如果你想要一个精确的解决方案，这个问题可能是难以解决的--指数运行时间。)

对于所有像素(你的“块”)，计算它周围磁盘中值的总和，并取一个和值最高的值。标记此像素并通过推导其值来调整其磁盘中所有像素的和，因为标记的像素已被“消耗”。然后扫描与其接触的所有像素的一个边缘或一个角，并用最高和标记像素。

继续这一过程，直到所有金额为负数为止。那么总数就不能再增加了。

为了有效地实现，您需要保留边框像素的列表，即标记像素的邻接的未标记像素。在选择了具有最大和的边框像素并标记它之后，从列表中删除它，并重新计算磁盘中未标记像素的和；还添加了触摸它的未标记像素。

在图片上，像素标记为蓝色，边框像素标记为绿色。突出显示的像素为

• 被标记的那个，
• 需要重新计算和的值。

​

​

计算时间将与图像面积乘以磁盘面积(用于和的初始计算)，加上形状面积乘以磁盘面积(和的更新)，再加上形状的连续周长的总长度(寻找最大和)成正比。由于后一项可能是昂贵的-根据形状面积的乘积的周长-，建议使用堆数据结构，这将把长度之和减少到它们的对数之和。

Answer 2

图形化方法

我会以图形的方式来处理这个问题。我的直觉告诉我，内部点完全在最小半径的圆圈内，最小半径r来自附近所有的足迹点。这意味着，如果你用半径r从每个脚印点投射圆，那么所有相邻圆中至少一半的点都在你的多边形内。为了不那么模糊，如果你是在多边形内部，那么在任何像素上你都会得到这样的重叠圆。如果你很紧张，你会得到一半。这很容易计算。

首先我需要数据集。因为您只提供了jpg文件，所以我没有vales。所以我把这个问题当作二值图像来处理。首先，我需要重新着色图像，以消除jpg颜色失真。在那之后，这是我的意见：

​

​

我选择黑色背景，以便于应用加性的数学图像，而且我更喜欢它比白色和留下足迹红色(最大饱和)。现在算法：

1. 创建临时图像 它应该是相同的大小，并被允许为黑色(color=0)。处理其像素，就像重叠圆圈的整数计数器。
2. 铸造圆 对于每个，source image中的红色像素，将+1添加到圆圈内的每个像素，在相同像素周围的最小半径r，但在temp image中。结果如下(蓝色是我的pixelformat的较低位数)：

在r中，我使用了r=24，因为这是示例+/-像素中左下角的圆圈半径。

1. 只选择内部像素 所以重新着色温度图像。所有像素与color < 0.5*pi*r^2重新颜色黑色，其余的红色。其结果如下：

​

1. 只选择多边形圆周点 只需重新着色所有的，红色，像素附近的黑色像素到一些中性颜色，，蓝色，，其余的黑色。结果：

现在就把结果说出来。要与输入图像进行比较，可以将两者结合起来(I OR将它们组合在一起)：

​

Notes

您可以使用最小半径或“区域”属性来实现不同的行为。但我觉得这和你的问题很接近。

这里有一些C++源代码，用于此：

//picture pic0,pic1;
    // pic0 - source
    // pic1 - output/temp
int x,y,xx,yy;
const int r=24;                 // min radius
const int s=float(1.570796*float(r*r));     // half of min radius area
const DWORD c_foot=0x00FF0000;  // red
const DWORD c_poly=0x000000FF;  // blue
// resize and clear temp image
pic1=pic0;
pic1.clear(0);
// add min radius circle to temp around any footprint pixel found in input image
for (y=r;y<pic1.ys-r;y++)
 for (x=r;x<pic1.xs-r;x++)
  if (pic0.p[y][x].dd==c_foot)
   for (yy=-r;yy<=r;yy++)
    for (xx=-r;xx<=r;xx++)
     if ((xx*xx)+(yy*yy)<=r*r)
      pic1.p[y+yy][x+xx].dd++;
pic1.save("out0.png");
// select only pixels which are inside footprint with min radius (half of area circles are around)
for (y=0;y<pic1.ys;y++)
 for (x=0;x<pic1.xs;x++)
  if (pic1.p[y][x].dd>=s) pic1.p[y][x].dd=c_foot;
   else                   pic1.p[y][x].dd=0;
pic1.save("out1.png");
// slect only outside pixels
pic1.growfill(c_foot,0,c_poly);
for (y=0;y<pic1.ys;y++)
 for (x=0;x<pic1.xs;x++)
  if (pic1.p[y][x].dd==c_foot) pic1.p[y][x].dd=0;
pic1.save("out2.png");
pic1|=pic0; // combine in and out images to compare
pic1.save("out3.png");

我使用自己的picture类来处理图像，因此有些成员如下：

• 图像的xs,ys大小(像素)
• p[y][x].dd是(x,y)位置的像素，为32位整数类型。
• clear(color) -清除整个图像
• resize(xs,ys) -将图像调整为新的分辨率

Edit1我在源代码中发现了一个小错误

我注意到一些边缘太锋利了，所以我检查了代码，并且在填充时忘记了添加圆圈条件，所以它填充了方格。我修复了上面的源代码。我真的只是增加了行if ((xx*xx)+(yy*yy)<=r*r)。结果略有改变，所以我也用新的结果更新了图像。

我玩的是内面积系数比，这个是：

const int s=float(0.75*1.570796*float(r*r));

为你带来更好的匹配。越小，多边形就越能重叠外部足迹。结果：

​

​