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