Уменьшение полигонов при рисовании на карте

Question

Сегодня мы рисуем полигоны в MKMapView. Мы используем следующий псевдокод для рисования полигонов.

CGContextMoveToPoint
CGContextAddLineToPoint
CGContextAddLineToPoint
CGContextAddLineToPoint
CGContextClosePath
CGContextFillPath

Результат потенциально может выглядеть следующим образом:

Мы получаем данные по одной строке за раз, цвета присваиваются ячейке на основе данных, которые мы получаем. Есть ли способ или алгоритмы сокращения полигонов, которые бы группировали все цветные полигоны вместе (при условии, что они пересекаются), чтобы получить один большой полигон? Таким образом, в этом примере все красные будут одним большим многоугольником.

Answer 1

Это задание для функций рисования прямоугольника, а не для функций рисования контура. См. CGContextFillRect(), CGContextStrokeRect() и CGContextFillRects(). Они будут намного быстрее.

Answer 2

CoreGraphics может обрабатывать вогнутые многоугольники изначально, поэтому основной частью проблемы является заливка, чтобы определить границы заполненной области.

Думая внешне, наивный алгоритм мог бы быть связан с флагами границ с каждой ячейкой.Флаг границы устанавливается, если этот край является частью внешней части многоугольника.Флаги являются общими для двух ячеек, которые встречаются на этом краю.

Выберите любую ячейку и установите все четыре флажка.Сброс флажков края на всех других ячейках.Затем напишите рекурсивный метод, который для каждой ячейки:

• по очереди проверяет, установлен ли каждый флаг ребра;
• , если установлен флаг, проверяет, имеет ли ячейка, которая разделяет это реброимеет тот же цвет;
• , если это так, инвертирует флаги краев этой ячейки и возвращается к ней.

Инверсия такая же, как сказать «подключиться к любой ячейке, которую выкак известно, рядом с ним устанавливаются любые ребра, которые находятся рядом с ячейками, которые мы еще не рассматривали, как часть границы ".

Рекурсия может получить сотни элементов в глубину, поэтому она может бытьСтоит сохранить список ячеек для рассмотрения и добавления в этот список, а не повторять, просто как вопрос реализации.Не должно иметь значения, в каком порядке вы посещаете ячейки, поэтому результат должен быть одинаковым.

Как только у вас закончится посещение ячеек, вы можете восстановить всю границу, обходя ее из любогопомеченный край.Единственная небольшая сложность будет, когда вы доберетесь до диагонального собрания ячеек, например, где желтые и зеленые ячейки соприкасаются между вашими четвертым и пятым столбцами.Вам необходимо применить логику, по которой вы перемещаетесь от текущего ребра к следующему, с которым оно разделяет и вершину, и ячейку правильного цвета.