Заполнение многоугольника с максимальным числом квадратов сетки

Question

У меня 2-го многоугольника.

Я положил его на квадратной сетке и маркировки квадраты, которые полностью внутри формы.

Мне нужно найти место размещения, максимизирует количество отмеченных квадратов. Ориентация многоугольника фиксирована, ее можно перевести только.

Как я могу это сделать?

Answer 1

Решим задачу в случае, если мы можем двигаться только наш полигон P вправо и ширина ячейки равна ж.

Прежде всего, заметим, что это достаточно, чтобы исследовать изменения для расстояния д _P в [0; w), потому что если мы переместим P в w направо, мы получим такую ​​же ситуацию, как если бы мы не двигали ее вообще.

Пусть S _P быть количество клеток в настоящее время в P. Предположим, мы немного переместили P. Что может случиться? Ну, некоторые из вершин сетки может теперь быть из P (давайте назовем это множество O), а также некоторые новые вершины могут быть теперь P (комплект I). Как определить, потеряли ли мы или приобрели какие-либо ячейки?Если клетка была в P и имел угол, который находится в O, то мы должны уменьшить S _P. Если же, наоборот, клетка имеет углы в I и другие углы уже в P, то мы должны увеличить S _P.

Давайте теперь сортируем эти события (получение и потерю вершин) путем увеличения его расстояний от начального положения P. Таким образом, мы описали порядок наших «маленьких шагов» в алгоритме.

Теперь мы можем написать некоторый псевдокод:

def signedDistance(vertex, edge): 
    p = [ closest point of edge to vertex ] 
    return vertex.x - p.x 

Events = { (vertex, edge) : 0 <= signedDistance(vertex, edge) < w } 
sort(Events, [ by increasing signedDistance ]) 
EventsEquiv = { E' : E' is subset of Events and 
        for any a, b from E' 
        signedDistance(a.vertex, a.edge) = signedDistance(b.vertex, b.edge) } 
S = [ cells in P initially ] 
maxS = S 
for E' in EventsEquiv: 
    for e in E': 
     if e is loss: S -= 1 
     else if e is acquirement: S += 1 
    if S > maxS: 
     maxS = S 

метод близок к sweep line.

UPD: Для обобщения этого нам нужно заметить, что для любого оптимального положения P существует другой оптимальное положение, что P имеет вершину сетки на ребре. Таким образом, решение, чтобы исправить некоторые сетки вершины G и двигаться P «вокруг» так P всегда G на шаг края за шагом, где шаги производятся в связи с событиями, происходящими, которые были описаны выше , Выполняется алгоритм O (P |/w).

Answer 2

Многоугольник большой, размер квадратов сетки маленький (например, 10x10 пикселей)?

Тогда есть один простой брутфорс решение:

1. Начните с одной сетки, подсчет квадратов.

2.1-2.10 Переместить сетку 1px вправо, подсчитать и обновить лучший результат, если не указано.

3. Переместить сетку 1px вверх, подсчитать и обновить лучший результат, если нет.

4. повторить ака идти до 2.1 до всех возможных решений проверяемых ...

Это легко проверить, если квадрат находится в пределах полигона или нет. Вы могли бы реализовать алгоритм, который идет по краям ...