足迹查找算法 [英] Footprint finding algorithm

问题描述

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

我有 3 列数据:

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

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

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

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

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

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

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

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

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

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

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

数据

我应该包含一些可以在

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

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屋！