У меня есть несколько многоугольников. Каждый можно охарактеризовать двумя массивами, в одном точки в другом линии межд точками. Каждая из точек знает какой линии она принадлежит и каждая линии знает какие две точки она соединяет.Проблема вот в что иногда считываются неправильно созданные массивы и программма считывает данные как на пикче. Массивы уже никак не поправить если че. Другими словами, выделенные красным цветом два многоугольника программа считывает как один.Вопрос, как определить связность фигуры, тобишь является ли фигура образованная линиями одним многоугольником или несколькими?
Как тут отвечать если программы мы не видим? Ну хз, попробуй пройтись по вершинам - зациклишься вот и многоугольник
>>212340147Создает массивы одна программа считывает другая. Ту что считывает я могу поправить а ту что создает нет.
То, что у тебя фигуры лежат в двух массивах это конечно лютое извращение, ну да ладноЕсли у тебя массив изначально неправильно создался, и ты его никак не можешь исправить, то имхо, тут уже ничего особо не поделаешь. По крайней мере каким-нибудь простеньким универсальным алгоритмом
>>212340631Вот смотри, на первом пике я выделил все многоугольники. Программа их видит в количестве четырех штук, каждый пронумерован по номеру массива.Вторая пикча я "разделил" дефективный многоугольник на два отдельных. Поправил его я вручную, а нужен алгоритм который сам будет проверять что как и где.>>212340720Квадрат внутри квадрата (номер 3 на пиках) по такому методу это "отдельная" фигуры. Тобишь он мне создает копию уже существующего из нихуя.
>>212341464Но они даже не касаются ничем. Так что ковыряй код, твоя читалка лажает.Или у тебя на них уже общий массив? Может тогда отсекать все точки, которые не дружат? Чтобы остался замкнутый контур.
>>212341915В исправленом виде 8.>>212341990Читалка все нормально читает. Она находит массив, считывает его и следующий за ним для точек/линий. Так дефективный многоугольник она считывает за один проход.>Может тогда отсекать все точки, которые не дружатНе понял, что значит не дружат?
>>212342300Ну вот у тебя есть точка, она касается только 2х других в многоугольнике. Все остальные с ней не дружат, они где-то там. Если выбрать точки по такому проходу, то у тебя будет контур замкнутый. Всё что не в нём - отдельно нахуй и из них опять пробуешь запилить кирпич.
>>212342300>Читалка все нормально читает. Охуеть, читалка нормальная, массивы править нельзя, больше в процессе ничего не участвует. Чего ты от двачеров хочешь? Думаешь проблема в фазе луны?>Не понял, что значит не дружат?Нет пути
>>212342300Раз 8, значит считаем, что фигуры с дырками. Тогда можешь найти все вершинные циклы и проверять их на вложенность друг в друга (с помощью линейной алгебры), можешь просто проверять влеженость 1 вершины из цикла в некий другой цикл.
>>212342567А, пробовал уже так. Выходит что квадрат номер три из этих>>212341464пикч (который внутри прямоугольника) считывается как отдельный многоугольник. Дублируется он короче.>>212342647Я сохраненный массив в джсоне вручную править буду? Их там дохуя.
>>212341464>Программа их видит в количестве четырех штукОбъяснение уровня "комплюктер ни работает"Задача не выглядит сложной, но не похоже что у тебя есть достаточное понимание проблемы для её решения.
>>212343099Объяснил максимально доступно без проволочек, чтобы понятно было. Нужно было дизассемблированный код скинуть?
>>212343476Если точки с линиями принадлежат двум разным массивам они дублируются в каждом.Например линия между двумя разными многоугольниками.
>>212343351Алгоритм этотhttps://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B8_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8Но чёт сомневаюсь, что ты осилишь. Наверное потому, что ты спросил в /b, а не в /pr.
>>212343973> в каждом.У тебя проблема в том, что 2 прямоугольника в одном массиве живут из-за говнокода, а не в дублях. Работай с одним массивом для проверки контура и разделения его на два, если он порвался нахуй. Вряд ли у тебя будут сложные фигуры деленные 1 точкой на части.
>>212344068Запустил я алгоритм с вот таким вот единственным многоугольником от помеченой вершины (с той у которой вершины[0]) с проходом по всему массиву вершин, используя ссылкку вершины на линии которым она принадлежит для проверки связности, пока массив полностью не пройдется.Он отработал и вернул мне два многоугольника. Он внутренние вершины с линиями посчитал отдельно. Дойти к ним через линии внешнего контура он не смог.Че делать теперь?
>>212344205Я хочу сразу покрыть все возможные варианты чтобы потом не возвращаться к этому гавну еще раз.
>>212345711А что тебе в итоге надо получить?Вершины до которых алгоритм смог дойти это первая компонента связности. Если надо получить все компоненты - то среди оставшихся вершин выбираешь случайную и повторяешь процесс пока вершин не останется.
>>212346192Нужно получить область которую эти вершины с линиями ограничивают, ту в которой текстурка есть короче.
>>212346441Делаешь проходки, а потом смотришь, есть ли фигура, точки которой все влезают внутрь другой, тогда их взад дружишь.
>>212339489 (OP)Что пишешь то ОП, игру или генератор уровней для неё? Скинь тогда хотя бы псевдокод своего генератора.
>>212346752Ну так выкладывай сразу какие ещё граничные ситуации возможны. Общая угловая точка у многоугольников? Общая сторона? Пересечение многоугольников? Самопересечение у одного многоугольника?Какое максимальное количество точек и линий?
>>212347560Общая вершина для неограниченого количества многоугольноков, линия может принадлежать только двум максимум многоугольникам, самопересечений нету, максимальное количество вершин и линий (отдельно) для многоугольника 65536
>>212339489 (OP)>>является ли фигура образованная линиями одним многоугольником или несколькими?Есть теорема что если набор не нулевых векторов имеет нулевую сумму, то этот набор образует многоугольник.
>>212348485Не, малех иначе: если набор векторов, отложенных из одной точки, имеет нулевую сумму, то сумма векторов образует замкнутую ломанную.
>>212348092Неприятные ограничения. Особенно про общую точку и сторону. Изучи https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83 и https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D0%BE%D0%B1%D0%BE%D0%BB%D0%BE%D1%87%D0%BA%D0%B0 чтобы лучше понять подходы.Вряд ли стоит самому всё писать. Полазь по гитхабу, поищи подходящие либы для работы с полигонами, типа https://github.com/bast/polygonsИ посмотри на реальные данные. Может они проще чем ты описал.
>>212350498Точки линии и внутренне число массива с оригинальной датой, тобишь номер пары (вершины линии) в джонсе.
>>212351552Кажется есть решение:1) Наш массив - это граф.2)Многоугольником будет "кратчайший цикл" (не уверен насчет названия)Тогда, если п.2 верный, нас устроит следующий алгоритм: Возьмем произвольную точку, перейдем из нее в другую, за каждый переход будем +1 к счетчику, если появляется развилка, счетчик дублируем, если мы вернулись в изначальную точку и наш счетчик меньше всех остальных - мы нашли многоугольник. Вырезаем все с ним связанное и повторяем.Наверное можно получить прибавку к скорости если отмечать уже пройденные отрезки.Проверь, м.б. сработает но не спеши радоваться, графы - не самая сильная моя сторона
>>212352261Проблема с такой вот конфигурацией будет.Левый многоугольник он обойдет раз, вернет один многоугольник, обойдет по не пройденным вернет второй.А если он по правому пойдет, он вернет те же два многоугольница. Но по факту он там один, так как "внутренний" квадрат там пуст.
>>212353058Ну тогда уже у задачи нет решения, или ты что-то не договариваешь: Если дан набор точек (как на пике), то откуда мне, как человеку, узнать что там 1 фигура, а не 2? Если это нигде не оговорено, то это невозможно. Разве что нам дано количество фигур...
>>212353977>Разве что нам дано количество фигурЗначит я не пояснил правильно. Каждая фигура пронумерована.
>>212354153Есть несколько многоугольников.Каждый многоугольник состоит из точек и линий между ними. Данные о них хранятся в двух разных массивах, один для точек другой для линий.Многоугольники пронумерованы в том же порядке в каком они сохранены в джонс файле.Некоторые из многоугольника имеют багованные массивы в которых кодируются несколько многоугольников вместо одного. Нужно определить такие массивы и разделить их на отдельные многоугольники.
>>212354399>>Многоугольник — геометрическая фигура, обычно определяемая как часть плоскости, ограниченная замкнутой ломаной, звенья которой не пересекаются.Переделывай, под это опрнделение твой "выколотый прямоугольник" не подходит.
>>212354399Алсо, >>Данные о них хранятся в двух разных массивахНепонятно: для каждого многоугольника своя пара массивов?Т.е. на вход мы получаем:n - кол-во многоугольников.2n массивов с данными.Так?
>>212354399Если багованные массивы хранят данные об отдельных фигурах не вперемешку, а по-очереди, то это надо использовать. Иначе всё непросто.
>>212355117Ну тогда почему не подходит вышеуказанный алгоритм? Всё так же: прошлись по вершинам, если получили >1 многоугольника - смотрим попадают ли все вершины одного в область другого, если да - это дырка, ее не трогаем, если хоть одна нет - разделяем.
>>212355698Однако задача не будет иметь решения в таком случае:Есть у нас многоугольник с дыркой, и одним лишним многоугольником в своей области. У нас нет возможности определить кто из двух "дырок" будет тру дыркой
>>212355880Тогда только вариант с обходом вершин. Вершина №1, дальше обход по линиям до тех пор, пока не будет достигнута вершина №1 (многоугольники все замкнутые, так?).Оставшиеся вершины скидываются в отдельный массив, после чего операция повторяется до тех пор, пока не останется непройдённых вершин.
>>212339489 (OP)А что мешает хранить только выпуклые многоугольники, а дырки обрабатывать разностью? Ну типа точка входит в большой и не входит во вложенный == всё заебись.
>>212357623А, почитал тред и понял, что кодеров, как у инцелов, проблема в дырках, лол. Для решения вопроса ты берёшь полученные на предыдущем этапе многоугольники, и смотришь их вложенность друг в друга. Если один вложен в другой, то это дырка.
>>212358205Там может быть как дырка так и другая фигура, в этом то и проблема а не конкретно в дырках.
>>212358692Предполагаю, что это не существующий вариант. В Build-подобных редакторах (а это явно что-то из такой области) всё равно текстура как-то привязывается к многоугольнику, и массивы должны сохраняться по большей части по отдельности.Хотя, если писал долбоёб (а среди индюков это частое явление), то всё возможно, лол. Тогда можно проверять, какие текстуры привязаны именно к этой области. Если есть текстура - то многоугольник, если нет текстуры то дырка.Текстур-то явно меньше, чем фигур.
>>212360946>Текстур-то явно меньше, чем фигур.Это я хуйню сморозил. Имел ввиду, что проверок на текстуры нужно меньше, чем на вершины.
>>212360946>>212362014Полная инфа по фигуре состоит из охулиона пунктов, мне же нужна только сама фигур чтобы я мог построить ноды для ботов.Тобишь, одна фигура - одна нода.А тут несколько фигур под одну ноду попадают и все ноды ложатся как сосач когда макака яйца чешет.
>>212339489 (OP)Ну хз, если у тебя два квадрата обрабатываются как один, ниши добавь - и из за уникальности шейпа и координат не будет совпадения. Мимо ебался с TrenchBroom по той же причинеhttps://www.youtube.com/watch?v=shcAvnYp9ow
>>212363094Не могу, фигурки уже в файле и я их поменять не имею права (работа аффтара, лицензия, все дела).
