Unity C#, закольцевать линию по неупорядоченным координатам из массива.

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

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

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

Метод рабочий, но есть проблема, иногда некоторые диагональные ячейки пропускаются,
и соответственно линия проходит мимо них. Алгоритм рабочий, но 1% ячеек просирает.

Ну а теперь вопрос, как мне в такой области массива, бесформенной, но закольцованной,
получить последовательные координаты ячеек на границе этой области, чтобы нарисовать
закольцованный лайн?

Мой метод меня не устраивает, заниматься всякими диаграммами вороного, и триангуляцией
никакого желания, это долго и бессмысленно. Как это сделать проще и быстрее?
У меня есть мысль написать волновой алгоритм типа А*, который будет искать не
самый короткий путь, а самый длинный, он пойдёт по кольцу, но может вы что посоветуете.

Что хочу:

Что имею в сыром виде:

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

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

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

даже добавить нечего, опередили))
у тя нет исходников Northgard? можно было бы посмотреть. Это же прям основа любой из игр по типу Civilization
Мой комментарий можно не читать, я тут поглазеть какой выберешь за основу)

Есть библиотека поиска пути там используется поиск в ширину BFS, я так понял это и есть волновой алгоритм. Она с открытым исходным кодом и там есть уже готовые функции.
https://arongranberg.com/astar/docs/graphutilities.html
Можно посмотреть как там сделано или просто использовать её.

>TERMOGAD

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

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

0) Если точки в 3D проецируем на плоскость
1) Берем среднюю точку от всех координат X и Z получая некоторую базовую точку, назовем BasePoint (геометрический центр)
2) Сортируем массив точек по дистанции
3) Сортируем ранее отсортированный массив по дистации, но в этот раз сортируем его по углу от любого выбранного вами положения оси. от 0 до 360 градусов (важно не 0-180 0 -180) а именно 360.
4) Проходим отсортированный по дистанции и кругу массив следующим образом:
Берем Первые 3 точки: Если угол между точками 0 - 1 - 2  смотрит вовнутрь к базовой, (точку 1 удалить) взять следующую точку 0  - 2 - 3 повторить операцию.
Если угол 0 - 2 -3 смотрит от базовой, сместить первую точку 2 - 3 - 4 и повторить все до конца массива по ранее заданному виду.

- Первый проход даст фигуру в виде неправильного многоугольника, описывая настоящую границу
- Второй проход даст выпуклый многоугольник.

* Если точек немного, скажем несколько тысяч, можно использовать алгоритм псевдосортировки через индексы в 1 проход

* В алгоритме точки могут быть на одной прямой, это не повлияет на работу.

Что-то типа такого для первого прохода:

Получится вот как-то так для второго прохода:

Так же можно почитать вот это: ссылка
Но там есть некоторые проблемы и не работают при всех условиях, хотя эти алгоритмы считаются самыми быстрыми. Я когда то-то то же спрашивал, никто не ответил ))

* Добавил, сорри перепутал местами пункт 1 и 2. Изменил.

FourGen

>RikiTikiTak
Я математики не знаю, по этому выводить ничего не могу к сожалению. Но знал бы математику, знал бы про алгоритмы, которые указал ниже.

Ruslan

Сложный костыль, лишние действия.

BooTheJudge

Ну я хз, как сам перебор по граням то осуществить? Да без потерь )

Salamandr

Исходников нет, примеров реализации нет. Пока к А* склоняюсь.

RikiTikiTak

Ну волновой я сам написать могу.

FourGen

У меня не многоугольники, там сгенерирвоаться вообще любая форма может.
Может быть где угодно впуклым, выпуклым, где-то вообще в линию вытянуться,
лесенкой идти, потом зигзагом, и т.д. Я про поиск по расстояниям думал, не подходит.

>не подходит
Как так? Оно же обрисует или реальную границу или  выпуклый многоугольник?
(Там вообще по барабану зигзаги не зигзаги - лесенки не лесенки, это реальная граница)

p. s

это многоугольник если он не пересекает сам себя.

FourGen

Допустим вот:

Разве у меня не возникнут проблемы?

>TERMOGAD
Возникнут однозначно.

Но изначально задача не описана полностью, а так же непонятен сам вопрос. Если вы знаете границу, зачем вам ее искать?

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

Что-то вы недоговариваете.

TERMOGAD
> Сложный костыль, лишние действия.
Хм, костыль? Ну ок, перебирайте соседей в массиве  сортируйте, рисуйте линерендером, дело ваше. Когда-то может придете и к "костылю".

>TERMOGAD
Поясните плз, как вы генерируете во этот элемент?

Это чисто физически не может быть рендомный набор точек. Он 100% должен подчиняться алгоритму генерации.

P. S.
Если же вы нарисовали кучу точек, но знаете где должна идти граница визуально, то тут не нужно ничего выдумывать, нужно просто обойти вокруг все требуемые вам элементы ландшафта.

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

FourGen
В условии написано это волновой алгоритм. То есть там это препятствия.

TERMOGAD
В библиотеки поиска пути есть функции которые контуры рисуют. Только где вы такие границы в играх видели или реальности. Другой алгоритм берите, упрощайте задачу. Попробуйте всё таки сделать как написал FourGen.