o
у меня нету траблов со стабильностью, хоть и сижу не на вендорской оболочке
Size: a a a
2021 June 24
YS
Бтв пишу с айфона 5s из... 2013 года кажется
o
ммм, ютуб с рекламой
o
RG
жирненько полилось, давайте во флуд
eb
У меня в десктопе 16, и я даже не представляю как их загрузить без рендера или компиляции в 24 потока (там конечно можно и больше сожрать)..
eb
Ой, кстати да..
ЕЕ
Все привет, есть набор отрезков, как мне их совместить в закнутые линии за O(n)?
Есть std::vector<std::array<glm::vec3, 2>> lineSegments.
lineSegments = {P1P2, A2A3, P2P3, ...}
То есть отрезки хранятся не в отсортированном виде.
Как мне его преобразовать в std::vector<std::vector<glm::vec3>> polygons за О(n)?
Есть std::vector<std::array<glm::vec3, 2>> lineSegments.
lineSegments = {P1P2, A2A3, P2P3, ...}
То есть отрезки хранятся не в отсортированном виде.
Как мне его преобразовать в std::vector<std::vector<glm::vec3>> polygons за О(n)?
AP
Строишь граф, потом запускаешь обход в глубину))
VD
Звучит не очень O(N). Я правда не уверен можно ли вообще за линию в его случае
S
radix
AP
Если хешами заносить, то на каждую точку по две вершины пишем суммарно за O(N), N - число вершин
Потом обход, на каждом шаге будет выбор из двух вершин, из одной уже пришли, соответственно обход займет O(N)
Потом обход, на каждом шаге будет выбор из двух вершин, из одной уже пришли, соответственно обход займет O(N)
AP
Задачу решить проще, но в одно предложение вот за O(N) решение
AP
Там будет несколько компонентов связности правда, нужно будет из непосещенных вершин повторно запускать dfs
Но в итоге мы все равно обойдем каждую вершину только по одному разу
Но в итоге мы все равно обойдем каждую вершину только по одному разу
ЕЕ
Можно подробнее, что значит заносить хешами?)
AO
хэш функция суммы вершин будет с ошибками так как 2+3==3+2 например, нужна другая функция
AP
Мы же хотим список смежности для обхода графа. Тогда чтобы быстро подцеплять к вершинам ребра, нужно (x, y, z) -> int преобразовать
AP
Я не говорил ничего про то, какой будет хеш
AO
а в какой структуре можно будет по хэшу порядок найти? просто получается на каждое место точки будет две вершины?
AP
Список смежности просто