ГС
Даны N фигур на плоскости,операции добавления,удаления,изменения фигуры. обойти по контуру передвигаясь только через вершины по часовой стрелке,онлайн. Подскажите алгоритм.
Size: a a a
2020 May 07
ГС
Ищу эйлеров путь максимальной длины для вывода контура, как оптимизировать что бы не искать если что то удалили\добавили\изменили
/¯
Ищу эйлеров путь максимальной длины для вывода контура, как оптимизировать что бы не искать если что то удалили\добавили\изменили
У всех эйлеровых путей длина максимальна
/¯
Бери любой
/¯
Но не ясно зачем тебе в этой задаче эйлеров путь
ГС
А,да, он тут не нужен
/¯
Тебе по сути надо уметь поддерживать выпуклую оболочку
A(
Даны N фигур на плоскости,операции добавления,удаления,изменения фигуры. обойти по контуру передвигаясь только через вершины по часовой стрелке,онлайн. Подскажите алгоритм.
что значит обойти по контуру? что нужно найти?
Фигуры - полигоны? Выпуклые?
Фигуры - полигоны? Выпуклые?
/¯
А, и да. Дай определение контура в этой задаче. Какие ограничения на фигуры?
ГС
Фигуры любые, в том числе с отверстиями внутри
ГС
При добавлении важно сохранять порядок обхода а не только точки которые входят в оболочку
/¯
Выпуклая оболочка сцены состоит из сегментов соединяющих фигуры и частей выпуклых оболочек фигур, чередуясь. Проход по частям оболочек можешь хранить как индексы вершин начала и конца оболочек фигур. Отдельно поддерживай оболочки фигур (и перрестраивай их при изменении фигуры)
A(
Фигуры любые, в том числе с отверстиями внутри
Как они заданы?
A(
При добавлении важно сохранять порядок обхода а не только точки которые входят в оболочку
все еще, что нужно найти в задаче
n
При добавлении важно сохранять порядок обхода а не только точки которые входят в оболочку
https://en.wikipedia.org/wiki/Vatti_clipping_algorithm я бы в эту сторону смотрел
ГС
Еще есть ограничение: если у фигур менее чем 2-х общих вершин - не соединяем их
/¯
Еще есть ограничение: если у фигур менее чем 2-х общих вершин - не соединяем их
Так что нужно найти. Не выпуклую оболочку сцены? Какое вообще условие задачи?
A(
я один все еще ничего не понял?
/¯
я один все еще ничего не понял?
Я тоже понял, что не понял
ГС
да, нужно искать выпуклую оболочку для множества точек