find most efficient pattern that is guaranteed to overlap shape

user_9991191 0
Viewed 132

I am looking for an algorithm that gives me the most efficient pattern to find a shape, no matter its rotation on a map (in case there are multiple, one of them).

Edit: Defininition of shape, pattern and overlap.

  • Shape - a joined combination of fields, in the following colored grey.
  • Pattern - a selection of fields, in the following colored yellow.
    If this selection is finite, it should be repeatable while upholding its property of overlapping with a given shape.
  • overlap - A pattern overlaps a shape if, no matter the position and rotation of the shape, the shape and the pattern will always share at least one field, in the following colored brown.

Here is an example:

shape
shape

map with pattern in yellow
map

Given the shape (1x2) and its rotations, it is guaranteed that the shape (grey) overlaps with at least (in this case exactly) one field of the pattern (yellow field). For this shape, this pattern is also the most efficient (i.e. lowest ratio of yellow fields to white ones) with a efficiency of 1/2. The pattern can mathematically be expressed as (x + y) % 2 == 0 (x and y being the index on the axis).

For 1 wide shapes, the defining expression can be generalized to (x + y) % length == 0 (0 can be replaced by any number >= 0 and < length). this will result in diagonal lines length - 1 fields apart.

yellow + brown := pattern
grey + brown := shape
map with 1x3 shape and pattern map with 1x4 shape and pattern

You can also extend this pattern to rectangles where no side has length 1, in this case the expression would be (x + y) % (ShapeSideA + ShapeSideB - 1) == 0. This doesnt result in the most efficient pattern though.

For a 2x2 Shape this would be the most efficient pattern:

map with 2x2 shape and pattern

and for a 2x3 this one:
enter image description here

Furthermore there are also those shapes that are not any kind of rectangle. My currently best approach would be to find the biggest rectangle inside and use my already inefficient methode on the rectangle to find a pattern.

Here are some more shapes with their respective most efficient pattern I could come up with:

v Shape enter image description here enter image description here enter image description here enter image description here

Thank you

language-agnostic algorithm
1 Answers

Excluding the possibility of large efficient patterns probably requires bespoke mathematical arguments, but restricting the possibilities to m-by-n patterns, you can formulate the problem as a set cover problem, where the elements to be covered are the at most 4mn placements of the shape in 4 orientations, m modulo classes for the rows, and n modulo classes for the columns, and the sets to be chosen correspond to the squares of the pattern, where each set contains the placements of the shape that intersect the square corresponding to the set. Set cover is NP-hard, but integer programming works well in practice for small instances.

user_21446690
Related