足迹发现算法 [英] Footprint finding algorithm

问题描述

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

I拥有3列数据：

• X：x轴上的位置


• Y： y轴上的位置


• 值：可以具有正值和负值的块的值。

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

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

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

我正在使用的当前算法是关注

1. 查找最大块值作为起点（或用户定义）


2. 查找全部


3. 从最小值计算中删除最小搜索半径中的所有块并将其标记为最小半径范围内的块并通过检查总值为正确定它是否可行。
最终形状

4. 移动到原点周围螺旋线确定的下一个点。 （中心始终是一个网格点，因此按deltaX或deltaY移动）

这似乎正在拾取一些不需要的单元格。我确定那里有形状算法，但我不知道该怎么查找才能找到帮助。

下面是一张希望有助于概述问题的图片。阳性细胞以红色显示（阴性细胞未显示）。黑色轮廓显示我当前正在返回的形状。我相信左侧应该更多。最小半径是100米，左下方的黑色圆圈大约是这个。

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

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

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

编辑：

数据

我应该包含一些可以在

计算时间将与图像面积乘以磁盘面积（对于总和的初始计算）成正比，加上形状面积乘以磁盘面积（用于更新磁盘的面积） sums），加上形状的连续周长的总长度（找到最大的总和）。 [由于后面的术语可能很昂贵 - 按照形状区域乘以其周长的顺序 - ，建议使用堆数据结构，这将减少总和长度与它们的对数之和。]

I'm trying to come up with an algorithm to optimize the shape of a polygon (or multiple polygons) to maximize the value contained within that shape.

I have data with 3 columns:

• X: the location on the x axis
• Y: the location on the y axis
• Value: Value of the block which can have positive and negative values.

This data is from a regular grid so the spacing between each x and y value is consistent.

I want to create a bounding polygon that maximizes the contained value with the added condition.

• There needs to be a minimum radius maintained at all points of the polygon. This means that we will either lose some positive value blocks or gain some negative value blocks.

The current algorithm I'm using does the following

1. Finds the maximum block value as a starting point (or user defined)
2. Finds all blocks within the minimum radius and determines if it is a viable point by checking the overall value is positive
3. Removes all blocks in the minimum search radius from further value calculations and flags them as part of the final shape
4. Moves onto the next point determined by a spiraling around the original point. (center is always a grid point so moves by deltaX or deltaY)

This appears to be picking up some cells that aren't needed. I'm sure there are shape algorithms out there but I don't have any idea what to look up to find help.

Below is a picture that hopefully helps outline the question. Positive cells are shown in red (negative cells are not shown). The black outline shows the shape my current routine is returning. I believe the left side should be brought in more. The minimum radius is 100m the bottom left black circle is approximately this.

Right now the code is running in R but I will probably move to something else if I can get the algorithm correct.

In response to the unclear vote the problem I am trying to solve without the background or attempted solution is:

"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"

Edit:

Data

I should have included some data it can be found here.

The file is a csv. 4 columns (X,Y,Z [not used], Value), length is ~25k size is 800kb.

解决方案

If the solution set must be a union of disks of given radius, I would try a greedy approach. (I suspect that the problem might be intractable - exponential running time - if you want an exact solution.)

For all pixels (your "blocks"), compute the sum of values in the disk around it and take the one with the highest sum. Mark this pixel and adjust the sums of all the pixels that are in its disk by deducing its value, because the marked pixel has been "consumed". Then scan all pixels in contact with it by an edge or a corner, and mark the pixel with the highest sum.

Continue this process until all sums are negative. Then the sum cannot increase anymore.

For an efficient implementation, you will need to keep a list of the border pixels, i.e. the unmarked pixels that are neighbors of a marked pixel. After you have picked the border pixel with the largest sum and marked it, you remove it from the list and recompute the sums for the unmarked pixels inside its disk; you also add the unmarked pixels that touch it.

On the picture, the pixels are marked in blue and the border pixels in green. The highlighted pixels are

• the one that gets marked,
• the ones for which the sum needs to be recomputed.

The computing time will be proportional to the area of the image times the area of a disk (for the initial computation of the sums), plus the area of the shape times the area of a disk (for the updates of the sums), plus the total of the lengths of the successive perimeters of the shape while it grows (to find the largest sum). [As the latter terms might be costly - on the order of the product of the area of the shape by its perimeter length -, it is advisable to use a heap data structure, which will reduce the sum of the lengths to the sum of their logarithm.]

这篇关于足迹发现算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！