@seacjs

Как нарисовать обрамляющую линию вокруг располагающихся рядом фигур?

У меня имеется поле из неправильных шестиугольников. Каждый из которых закрашивается одним из нескольких цветов.
Каждый из них я рисую по координатам вершин.
5b110a10dd18401fa321b08898b107cd.png
Мне необходимо нарисовать линию которая будет обводить все шестиугольники одного цвета, стоящие рядом. В результате должно получится так:
4f9ea8015fa64e879ea2e7fbff00e471.png
Подскажите алгоритм, с помощью которого можно это реализовать.

Подобное реализовано в разных стратегических играх, например в цивилизации:
3104602-6667566570-civ6p.jpg
  • Вопрос задан
  • 325 просмотров
Пригласить эксперта
Ответы на вопрос 4
ManWithBear
@ManWithBear
Swift Adept, Prague
Вот тут всё хорошо описано https://habrahabr.ru/post/144921/
Множество вершин многоугольников одного цвета составить не проблематично.

UPD. Первое пришедшее в голову решение:
Берем множество всех граней этих шестиугольников. Далее проходимся по нему и удаляем все, которые лежат между шестиугольников одного цвета. В итоге имеем множество граней, необходимых для постройки необходимой фигуры.
Можно даже абстрагироваться от шестиугольников и сделать это для любых фигур.
Ответ написан
@fireSparrow
Трудно сказать что-то конкретное, не видя, как именно реализована изнутри структура, описывающая поле.

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

Примечание: Я буду в ответе использовать термин "множество" в терминологии питона. Если у вас другой язык, воспользуйтесь аналогичной структурой из своего языка. Или используйте простой список, но перед добавлением в него элемента проверяйте, что такого элемента там нет. Иначе цикл никогда не завершится, а список будет разбухать, пока не съест всю память.

Начинаете с одной любой ячейки.

Создайте два пустых множества - назовём их 'currents' и 'visited'.
В currents поместите ту ячейку, с который вы начинаете.

Далее выполняете цикл, пока в currents есть хотя бы одна ячейка:
1. Удалите из currents первую попавшуюся ячейку (далее её я называю "текущей ячейкой").
2. Для этой текущей ячейки найдите всех её соседей.
3. Для каждого соседа:
3.1. Если он того же цвета, что и текущая, и не находится в множестве visited - добавьте его в currents
3.2. Если он другого цвета - проведите границу между этим соседом и текущей ячейкой.
4. Добавьте текущую ячейку в visited
5. Повторять, пока currents не кончится.

Граница нарисована!
Ответ написан
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Это диаграмма Вороного, если вы смогли ее реализовать на каком нибудь языке, то для вас не должно составлять труда ее раскрасить. На JS такое умеет d3js , вот код модуля.
Ответ написан
BasmanovDaniil
@BasmanovDaniil
Геймдизайнер-телепат
Медленный, но достаточно простой в реализации алгоритм.
  1. Создаёте список связанных шестиугольников одного цвета и выкидываете из него все шестиугольники без соседей другого цвета.
  2. Создаёте список вершин оставшихся многоугольников
  3. Создаёте пустую ломаную линию.
  4. Берёте один многоугольник из списка, ищете у него сторону с соседом другого цвета.
  5. Двигаетесь по часовой стрелке от этого ребра, выкидываете вершины из списка необработанных и складываете их в ломаную до тех пор, пока не наткнётесь на соседа такого же цвета.
  6. Переходите на соседа, следующее ребро по часовой стрелке от общего будет внешним. Повторяем 5-6 до тех пор, пока ломаная не замкнётся.
  7. Если в списке вершин ещё что-то осталось, ищем многоугольники с необработанными вершинами, обходим рёбра по часовой стрелке и создаём ломаные, если встречаются необработанные внешние рёбра.
  8. Если в итоге получилось несколько многоугольников, значит это многоугольник с дырками. Вершины внешнего контура будут отсортированы по часовой стрелке, а внутреннего - против часовой.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы