Проверка того, какие треугольники пересекают выпуклый корпус

Question

У меня есть набор двумерных треугольников (т. Е. В R ² ), а также двумерный выпуклый корпус (представленный в виде набора линейных ограничений), и мне нужно проверить, какой из этих треугольников пересекают выпуклый корпус. Какие существуют алгоритмы для этого?

На более позднем этапе мне также может понадобиться обобщить задачу для более высоких измерений, чем 2D (т. Е. Из набора симплексов в R ^d проверьте, какие из них пересекают выпуклую оболочку в R ^d ), так что если вы знаете алгоритм, который может обрабатывать общий случай, который также будет хорош.

Answer 1

Вы можете решить двумерную задачу в два этапа:

• построить вершины выпуклой оболочки;

• пересекают треугольники и корпуса, которые являются выпуклыми многоугольниками (https://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring17/Lectures/cg-convexintersection.pdf). Время для пересечения будет O (N) для корпуса из N вершин.

Если вам нужно сделать это для многих треугольников, существует возможность разложить корпус на две монотонные цепочки. вдоль оси, скажем X, и найдите диапазон перекрытия корпуса и каждого треугольника с помощью поиска дихотомии c. Это уменьшит время до O (Log N + K), где K - среднее число сторон корпуса в X-образном перекрытии с треугольниками.