Может ли набор трехмерных позиций быть разделен плоскостью?

У меня 3 точки в трехмерном пространстве: A, B и C. У меня также есть еще один набор трехмерных точек: P, Q, R, S, T и U. Какой будет самый простой алгоритм для определения, существует ли плоскость, которая полностью отделяет первый и второй набор? Я знаю все координаты всех точек.

4 голоса | спросил Markus Fjellheim 22 J000000Saturday17 2017, 06:01:25

3 ответа


1

Как уже упоминалось в комментариях, вы можете построить выпуклую оболочку каждого точечного множества, а затем проверить выпуклые оболочки для пересечения, используя ваш любимый алгоритм обнаружения выпуклых столкновений (например, SAT, GJK ...)

Если два корпуса пересекаются друг с другом или цепляются в точке, то нет плоскости, которая полностью разделяет два набора.

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

ответил DMGregory 6 J0000006Europe/Moscow 2018, 13:26:13
0

Вы можете найти такой самолет, используя простой линейный поддерживающий векторный компьютер . Я бы не описал это как «самый простой» алгоритм, но с помощью этого метода, безусловно, будет очень быстрое решение.

ответил mklingen 26 J000000Wednesday17 2017, 19:59:37
0

То, о чем вы говорите, относится к линейной разделимости данных (в вашем случае в 3D). Это изученная тема в Machine Learning (которая распространяется на N-мерность). Это была одна из причин, по которой SVM стали чрезвычайно популярными в тот день, поскольку он вычисляет лучший гиперплоскость (наиболее отдаленный, относящийся к двум классам категорий), обеспечивая хорошую производительность для многих проблем. Тема, известная как измерение VC , обеспечивает тщательный анализ этого понятия.

Как упоминалось в комментариях, алгоритм Convex Hull будет вычислять это в 3D для вас, так как он будет наименьшим многогранником, который инкапсулирует множество точек. Если они не пересекаются, вы можете иметь плоскость между двумя наборами точек.

ответил dev_nut 5 Mayam18 2018, 02:56:44

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132