I
Так, вообще говоря, автор - я. Но в 3D, увы не делал. Тем не менее, мне кажется, что реально сделать в 3D. А вот в 2D, у меня работало за 0.2 сек на 1млн.
Size: a a a
2020 March 01
I
Но, это коммерческий проект был.
I
А, ну да, для 2д эту и реализовывал. Еще в прошлом году для курсовой
Вот это круто, что то чем делюсь - помогает!
A(
Так, вообще говоря, автор - я. Но в 3D, увы не делал. Тем не менее, мне кажется, что реально сделать в 3D. А вот в 2D, у меня работало за 0.2 сек на 1млн.
ухты) круто
A(
Ну, QHull за N^4
хм, не совсем
I
За куб?
A(
почему такая асимптотика?
A(
там не больше квадрата вроде елси правильно реализовать
I
Ну, там переборное решение, как помню.
A(
там строится опуклая оболочка для точек в 4д
A(
ибо есть биекция между 4д оболочкой и 3д воронным
A(
ну а оболочка этим алгом строится за NlogN в лучшем случае вроде как
I
Ну, я в 3D не строил, но Сигал, который я использовал по скорости не устраивал. Дело, давно было. Но, в целом, ты можешь быть прав, что не 4-ая.
I
А на миллионе в 3D сколько времени уходит?
A(
сейчас починю, и чекну) а то немного сломал пока рефакторил
A(
но значительно дольше секунды конечно.
На порядка 10к-30к вершин - была 1секунда вродь
На порядка 10к-30к вершин - была 1секунда вродь
A(
Ну, я в 3D не строил, но Сигал, который я использовал по скорости не устраивал. Дело, давно было. Но, в целом, ты можешь быть прав, что не 4-ая.
а в CGALе не такой алгоритм как на хабре?
I
Нет, там Форчуна алгоритм, то есть sweep line. Он, конечно хороший, но не параллельный и не Кеш Френдли.