足迹查找算法

Question

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

我有 3 列的数据：

X：x轴上的位置
Y：y轴上的位置
Value：方块的值，可以有正负值。

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

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

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

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

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

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

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

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

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

"Create a bounding polygon (or polygons) around a series of points to maximize the contained value, while maintaining a minimum radius of curvature along the polygon"

编辑：

数据

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

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

Answer 1

图解法

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

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

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

创建临时图像

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

对于 source image 中的每个 red 像素，将 +1 添加到圆内的每个像素，半径最小 r 围绕同一像素，但是在 temp image。结果是这样的（蓝色是我的pixelformat的低位）：

As r 我使用了 r=24 因为那是你示例中左下角的圆半径 +/- 像素。
select 仅内部像素

所以重新着色临时图像。所有具有 color < 0.5*pi*r^2 的像素重新着色为 black，其余为 red。结果是这样的：
select 仅多边形圆周点

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

现在只需将结果多边形化。要与输入图像进行比较，您可以将它们组合起来（我 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 class 来制作图片，所以一些成员是：

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));

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

Answer 2

如果解集必须是给定半径的圆盘的并集，我会尝试 greedy 方法。（我怀疑这个问题可能是棘手的 - 指数运行时间 - 如果你想要一个精确的解决方案。）

对于所有像素（您的 "blocks"），计算其周围圆盘中值的总和，并取总和最高的那个。标记这个像素并通过推导它的值来调整其磁盘中所有像素的总和，因为标记的像素已经"consumed"。然后通过边或角扫描所有与其接触的像素点，标记和最高的像素点。

继续这个过程，直到所有的和都为负数。那么总和就不能再增加了。

为了高效实施，您需要保留一个边界像素列表，即与标记像素相邻的未标记像素。在选择了总和最大的边界像素并对其进行标记后，将其从列表中删除并重新计算其圆盘内未标记像素的总和；您还添加了触摸它的未标记像素。

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

被标记的那个，
需要重新计算总和的那些。

计算时间与图像面积乘以磁盘面积（用于总和的初始计算）加上形状面积乘以磁盘面积（用于更新总和）加上形状在增长时连续周长的总长度（以找到最大的总和）。 [由于后一项可能代价高昂——按照形状面积与其周长的乘积——，建议使用 heap 数据结构，这将减少长度之和与其对数之和。]

足迹查找算法

Footprint finding algorithm

algorithm

2d

polygon

image-processing