Пересечение nD генеральной линии с выпуклой оболочкой в ​​Python

Question

Я создал выпуклую оболочку, используя scipy.spatial.ConvexHull. Мне нужно вычислить точку пересечения между выпуклой оболочкой и общей линией, начиная с внутренней точки и заканчивая во внешней точке, поэтому пересечение должно быть гарантировано. Размер проблемы может варьироваться от 2 до 3.

проблема похожа на старая проблема . Я хотел бы иметь обобщенный

Answer 1

Для неоптимального (линейного времени), но простого решения, рассмотрите плоскость, содержащую линию, и пересекайте каждый край трехмерного корпуса с этой плоскостью. Затем поверните плоскость и точки на xy, и вы уменьшите задачу до 2D.

Создайте 2D выпуклую оболочку и пересекайте все ребра с линией. (Если вы сохраняете связи между точками прокалывания, которые принадлежат одним и тем же граням, вам даже не нужно перестраивать 2D-корпус.)