algorithm - 足迹查找算法

Question

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

我有 3 列的数据:

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

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

我想创建一个边界多边形，通过添加的条件最大化包含的值。

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

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

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

这似乎是在拾取一些不需要的单元格。我确定那里有形状算法，但我不知道要查找什么来寻求帮助。

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

现在代码在 R 中运行，但如果我能得到正确的算法，我可能会转向其他东西。

为了回应不明确的投票，我在没有背景或尝试解决方案的情况下试图解决的问题是:

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

编辑:

数据

我应该包含一些可以找到的数据here .

该文件是一个 csv。 4 列(X、Y、Z [未使用]、值)，长度约为 25k，大小为 800kb。

Answer 1

图形方法

我会以图形方式处理这个问题。我的直觉告诉我，内部点完全位于最小半径为 r 的铸圆内。来自附近的所有足迹点。这意味着如果您从半径为 r 的每个脚印点转换圆那么所有相邻圆中至少一半内的所有点都在多边形内。为了不那么模糊，如果你深入多边形，那么你会得到 Pi*r^2任何像素处的此类重叠圆圈。如果你处于边缘，你得到了一半。这很容易计算。

首先我需要数据集。因为你只提供了 jpg 文件，所以我没有 vales只是情节。所以我像处理二值图像一样处理这个问题。首先，我需要为图像重新着色以消除 jpg 颜色失真。之后这是我的输入:

我选择黑色背景以便轻松地在图像上应用加法数学，而且我更喜欢它而不是白色，并让足迹保持红色(最大饱和度)。现在的算法:

1. 创建临时图像

   它应该是相同的大小并且清除为黑色 (color=0) .像处理重叠圆圈的整数计数器一样处理它的像素。

2. 投圈子

   对于 source image 中的每个红色 像素添加 +1到具有最小半径的圆内的每个像素 r围绕相同的像素，但在 temp image 中.结果是这样的(蓝色是我的 pixelformat 的低位):

   

   作为r我用了r=24因为那是您示例中左下角的圆半径 +/- 像素。

3. 仅选择内部像素

   所以重新着色临时图像。所有带 color < 0.5*pi*r^2 的像素重新着色为黑色，其余颜色为红色。结果是这样的:

   

4. 仅选择多边形圆周点

   只需将黑色像素附近的所有红色像素重新着色为某种中性色蓝色，并将其余颜色重新着色为黑色。结果:

   

   现在只需将结果多边形化。要与输入图像进行比较，您可以将它们组合在一起(我 OR 它们在一起):

   

[注释]

您可以使用最小半径或区域阈值属性来实现不同的行为。但我认为这与您的问题非常接近。

这里有一些 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));

为您带来更好的匹配。它越小，多边形越能与足迹外部重叠。结果: