# Footprint finding algorithm

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 of the block on the x axis
• Y: the location of the block on the y axis
• Value: Value of the block (can have positive or 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 vertices of the polygon (it can't "turn too sharply").

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. Find the maximum block value as a starting point (or user defined)
2. Find all blocks within the minimum radius and determine if it is a viable point by checking the overall value is positive
3. Remove all blocks in the minimum search radius from further value calculations and flag them as part of the final shape
4. Move onto the next point determined by a spiralling around the original point.

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

Background: I'm an engineer with minimal formal knowledge in programming or computer science. I like using code to help increase efficiencies in the office.

Below is a picture that hopefully helps illustrate the situation. Positive cells are shown in red (negative cells are not shown). The black outline shows the shape my current algorithm is returning. I believe the left side should be brought in more.

Effectively my algorithm is covering the areas with circles since each value check is done on a circular radius and all the blocks are flagged at the same time. Spiraling is done on the grid cells so it always moves by 1 deltaX or 1 deltaY. I saw someone mention Minkowski dimension or ball packing but I'm not familiar with those. My problem seems different: ball packing looks like you want complete coverage of the desired surface whereas I want to select or omit cells based on the total value inside the circle.

• This question is based on you doubting your current method. Do you have concrete evidence that the solution is suboptimal or even bad? "I believe the left side should be brought in more" is not a strong reason, since looks can be deceiving. (You should at least color the points by value.)
– Raphael
Apr 16 '16 at 12:17
• "There needs to be a minimum radius maintained at all points of the polygon." -- That means no polygon can be smaller than a sphere with that minimum radius? Otherwise I don't understand the condition.
– Raphael
Apr 16 '16 at 12:18
• I agree coloured blocks would have been useful. As for the current method it is clearly picking up blocks <0 which it doesn't need to making it sub-optimal. As for minimum radius the solution basically needs to be a union of circles with min radius r. Apr 16 '16 at 20:14
• I don't understand what the boundary is. In one point you say you want a polygon, where the vertices have to be on grid points (integer x and y coordinates). In other place you say you are covering it with circles. Those can't both be right. The picture doesn't look like a circle; it looks like a polygon (though the resolution is poor enough that it's hard to tell for sure). Is the "radius" language misleading? Perhaps you mean that at any vertex of the polygon, the angle between the adjacent two line segments can't be too small (you have some minimum allowable angle)?
– D.W.
Apr 16 '16 at 21:13