Какие есть алгоритмы для выполнения булевыех операций с поверхностями?

Question

[Антон П.]

У меня есть массивы, которые из себя представляют набор точек с координатами, образующие области.
Мне нужно выполнять булевые операциям на ними.

Посоветуйте, что мне нужно изучить для этого.
Какие алгоритмы применяются для этого?
Какие математические аппараты используются?

Answer 1

[Николай Чуприк]

Посмотрите алгоритмы CSG (Construtive Solid Geometry). Они конечно касаются объёмных тел, но в целом, если разберётесь с приёмами, можно, я думаю, легко перенести на поверхности. А если ваши области лежат на двухмерной поверхности (я это не понял из вашего вопроса), то CSG в одну секунду легко упрощается до 2D.

В своё время мне помогла разобраться с алгоритмами CSG библиотека three_csg.js. Я работал со three.js, и эта библиотека по сути расширяет её, позволяя добавить булевы операции. Она совсем небольшая, несложно разобраться в её работе целиком.

Наверняка и на других языках есть куча реализаций CSG, просто я написал о том, с чем сам имел дело.

Если у вас чисто 2D, то такую библиотеку можно и самому за полдня легко написать. Даже интересно. Тут и знаний особых не надо, кроме как умения решать систему уравнений:
y = k1 * x + b1
y = k2 * x + b2

Comments

[Антон П.]

Да, по началу мне нужен 2D, потом 3D.
Задача именно академическая, не для бизнеса.

Мне хочется разобраться с этим и реализовать самостоятельно.

Я правильно понимаю, что вы предлагаете с помощью систем найти все точки пересечения между областями?
Это мне тогда нужно циклом проверить все отрезки в областях на факт пересечения, и сложность данного алгоритма O(n^2).
А есть советы по написанию чего-то боле быстрого?