I
Задачу можно разбить на несколько этапов:
1) Найти уравнение цилиндра, а также двух полусфер, которые получаются после перемещения.
2) Проверять каждую точку, которая будет находиться в выделенной области на включение в цилиндр и, позже, в полусферы.
3) Удалить данные точки из вектора точек куба.
1) Чтоб найти уравнение цилиндра - нужно вычислить скалярное произведение вектора, который получается между стороной цилиндра и стандартных базисных декартовых векторов. Получится три угла. Далее нужно, применив преобразования эйлера, вычислить матрицы перехода от базиса цилиндра к стандартному базису, чем получить уравнение цилиндра в декартовой системе координат.
2) Имея уравнение цилиндрической поверхности, мы можем проверять каждую точку на включение в цилиндр, просто используя трассировку: проверяя луч от точки в любую сторону цилиндра и смотря, сколько раз он пересекает грани. Если четное кол-во - точка снаружи.
3) Если точка не принадлежит цилиндру - смотреть принадлежит ли она полусферам, в построении уравнения полусфер проблем нет никаких.
4) Вырезать найденные точки из вектора.
При достаточной плотности точек в кубе, решение будет занимать титаническое кол-во времени
1) Найти уравнение цилиндра, а также двух полусфер, которые получаются после перемещения.
2) Проверять каждую точку, которая будет находиться в выделенной области на включение в цилиндр и, позже, в полусферы.
3) Удалить данные точки из вектора точек куба.
1) Чтоб найти уравнение цилиндра - нужно вычислить скалярное произведение вектора, который получается между стороной цилиндра и стандартных базисных декартовых векторов. Получится три угла. Далее нужно, применив преобразования эйлера, вычислить матрицы перехода от базиса цилиндра к стандартному базису, чем получить уравнение цилиндра в декартовой системе координат.
2) Имея уравнение цилиндрической поверхности, мы можем проверять каждую точку на включение в цилиндр, просто используя трассировку: проверяя луч от точки в любую сторону цилиндра и смотря, сколько раз он пересекает грани. Если четное кол-во - точка снаружи.
3) Если точка не принадлежит цилиндру - смотреть принадлежит ли она полусферам, в построении уравнения полусфер проблем нет никаких.
4) Вырезать найденные точки из вектора.
При достаточной плотности точек в кубе, решение будет занимать титаническое кол-во времени
