Разбить игровое поле на ячейки проивзольной формы.
 

Доброго всем времени суток.
Сабж в названии темы. Как грамотно реализовать разбивку поля на ячейки произвольно размера и формы. Сие часто можно увидеть в пошаговых стратегиях, к примеру в таких играх как Hears of Iron, Victoria и т.д. Вот еще очень интересный пример. В голову почему-то не лезут никакие толковые мысли. В идеале нужен исходник(хорошо бы на С/C++, но и на любом другом языке тоже подойдет), буду благодарен также за любую теорию или ссылки по теме.

Ответ: Разбить игровое поле на ячейки проивзольной формы.
 

Должно быть, вы ищете что-то в этом роде.
В англ. версии статьи можно увидеть объяснение измененной версии, которая по виду довольно близко подходит к ячейкам первой упомянутой игры.

Ответ: Разбить игровое поле на ячейки проивзольной формы.
 

Вы третий кто мне это посоветовал) Это не подходит. Возьмем следующее расположение ячеек:

Красные точки это "центры" или "образующие" ячеек. Синяя точка лежит в черной ячейке, но она более близка к центру белой ячейки, и при расчетах будет относится к белой.

Ответ: Разбить игровое поле на ячейки проивзольной формы.
 

хранить границу (в виде ломанной) и проверять принадлежность точки, тут для не выпуклых многоугольников сложнее, поэтому советую разбивать на выпуклые и запоминать ввиде списка
ну для выпуклых вот алгоритм http://e-maxx.ru/algo/pt_in_polygon
правда тут надо еще оптимизировать тем что проверять достаточно ли близко к центру и тогда только проверять
ну либо делать туже диаграмму воронова, но только некоторые области будут связаны и в логике будут одной ячейкой