Quark, если это вы стороны треугольников обрабатываете, то лучше брать не отрезки в 3d координатах, а номера точек. Там же треугольники индексами в массиве точек заданы, верно? Сортировать 2 инта всяко легче чем точки.
mayton2019, ссылку почитайте. Там алгоритмы для нахождения представления чисел, существующего по теореме лагранжа. Но формулировка у автора вопроса кривая, да.
Надо бы понять, как это апи работает. А то, может, задача вообще не решаемая. Если апи отдает до 100 пользовтелей с данной подстрокой, допустим, с минимальными внутренними id, то может быть, что там 100 пользователей со строкой abc, перед самим пользователем abc. И вы никаким запросом этого abc не получите.
mayton2019, Жесть. Интересно, как долго оно решать будет. Там же 2^66 вариантов! Конечно, отсечения какие-то у него будут, но я боюсь это нереально долго будет. А какая-нибудь система символьной алгебры, или тупо метод гауса, дай бог 7^3 шагов сделает.
mayton2019, Если свапать только 2 ключа, то нарушится свойство дерева поиска. Поэтому обычно используют именно повороты. Тут не тоько ключи меняются местами, но и стуктура дерева.
Ну, и конечно, вопрос в скорости этого процесса. Так-то, очевидно, что всегда можно вообще все дерево разобрать на элементы и потом из них собрать новое, идеально сбалансированное дерево.
Yatagarashy, Раз ваш второй вопрос (про структуры) сюда сдублировали, отвечу тут:
Чтобы генерировать структуры, надо сначала сгенерировать ландшафт. Возможно несколько соседних чанков тоже (по размеру структуры). Потом среди них посмотреть, в каких точках структура может теоретически быть (перепад высот, биом и т.д). Потом надо какой-то другой шум взять в качестве случайной величины и с заданной вероятностью решить, в каких точках структуры генерируются. Потом остается только аккуратно их впендюрить.
В качестве случайной величины можно, например, взять какой-то шум. С резкими перепадами высот, чтобы структуры рядом не спавнились. Надо считать, что стурктура ставится там, где этот шум имеет достаточно большое значение (если все условия для возможности спавна выполняются).
Трюк генерации в следующем: научитесь генерировать какбы всю карту целиком, без разбития на чанки. Эта генерация будет в несколько проходов. Сгенерили высоту, биом, разлили воду, растительность, структуры. И вот когда вам надо разбить генерацию на чанки, чтобы сгенерировать вот этот вот чанк на этапе N, вам надо его и все соседние сгенерировать до этапа N-1. Причем эти соседние чанки могут быть за границей видимости и не требовать генерации по всем этапам. Тут надо все лениво генерировать и кешировать.
Чем больше у вас структуры, тем больше чанков надо генерировать вокруг локации.
Quark, Да, ребра придется считать самостоятельно. Но это просто.
У вас же есть список троек, опысывающих треугольники номерами точек? Вот вы привели в пример треугольник {0,1,2}. Точно должны быть треугольники {1, 0, a}, {2, 1, b}, и {0, 2, c} (порядок точек может быть любым). Эти три треугольника - прямые соседи {1,2,0} - ведь они делят с ним стороны. Вам надо найти треугольник с такой же парой точек. Можно было бы тупо пройтись по всему списку треугольников и сравнить стороны, но это медлено. Но подумайте, эта задача практически идентична такой: Дан массив с числами. Каждое число встречается ровно 2 раза. Найдите пары индексов с одинаковыми числами. Только в вашей задаче чисел по три и совпадают они парами.
Понятно, как быстро решать простую задачу. Или отсортировать массив с индексами, или использовать hash_map. Вам надо просто для каждого числа знать, где оно раньше встречалось. Если оно ее не встречалось - запомните его индекс. Если встречалось - то вот вы нашли пару индексов (текущий и запомненый ранее). Для этого можно использовать hash_map.
Вот у вас будет структура: map из пары int в int. По двум номерам точек оно будет выдавать номер треугольника с такой стороной.
Пройдитесь по списку треугольников один раз. Возьмите все 3 стороны. Если в мапе эта пара точек как ключ еще не лежит, то кладите map[{v1, v2}] = triangle_id. Если там уже что-то лежит, то вот оно является соседом текущего треугольника по стороне. Добавьте в списки смежности этих треугольников друг друга. Не забудьте только номера точек перед использованием в качестве ключа отсортировать, а то может в соседнем треугольнике они в другом порядке идут.
Quark, для построения графа и нужны всякие структуры данных. Или мап из пары интов в инт (по стороне треугольника хранить его номер), или список трекгольников для каждой точки.
Вот есть у вас треугольник {0,1,2} - запомнили, что точка 0 связана с первым треугольником. Допустим, десятый треугольник {1, 33, 0}. Он тоже попадет в список для точки 0. А дальше суть в том, что вы не храните граф, но там, где надо посмотреть всех соседей данной вершины графа (ака треугольник), вы смотрите все треугольники, пересекающиеся с текущим по углу. И когда вы будете искать соседей первого треугольника вы из списка точки 0 найдете десятый треугольник.
EvgenyApMr, Зависит от данных. Если хотите более пологую кривую, то можно добавить новых точек между ключевыми, скажем, по линейной интерполяции. Будет полином более высокой степени. Так сказать, прибейте кривую гвоздями чтобы сделать более пологой.
