У меня есть проблема, чтобы доказать, может ли число из 4 точек образовать выпуклую оболочку, и если в корпусе находится 5-я точка, или нет. Мне удалось решить проблему выпуклой оболочки с помощью треугольников, однако я не знаю, как доказать, что 5-я точка находится внутри корпуса, созданного другими 4-мя точками.Проверьте, находится ли точка внутри 4-точечного выпуклого корпуса
Любые идеи?
Спасибо!
Предполагая, что вы спрашиваете о точках на плоскости - существует standard approach для любого многоугольника (выпуклого или нет) с любым количеством вершин.
Эта проблема не касается точек на плоскости - термин «4-точки» относится к 4-мерному пространству, где каждая точка имеет набор координат, таких как (a, b, c, d) или (0,1,2 , 54,0.4). –
@M_M Термин «треугольники» предполагает иное («упрощения» являются стандартными для более высоких измерений). –
Я думаю, ваше право, моя ошибка в чтении вопроса. Это может быть в любом количестве измерений, как это сформулировано. –
Назовите свои баллы a, b, c, d. Они образуют тетраэдр. Если тетраэдр не вырожден, то точки - это вершинные точки (крайние точки) их выпуклой оболочки.
Чтобы проверить это, проверьте, если a, b, c образуют невырожденный треугольник. Для этого вычислим нормальный вектор (назовите его n) треугольника (b-a) cross (c-a). Если он равен нулю, то треугольник вырождается, в противном случае это не так. Проверка, если d не находится в плоскости этого треугольника. Это если (d-a) точечный продукт с n равен нулю. Если это так, то тетраэдр вырождается.
Вычислить нормальный вектор для каждого из четырех треугольников тетраэдра. Каждый нормальный вектор вместе с (любой) точкой треугольника описывает полупространство; , то есть все точки на одной стороне плоскости. Пусть n - нормальный вектор, p - точка треугольника.
Точка q называется внутри полупространства, если n dot (q-p) отрицательна.
Проверьте все 4 треугольника, если четвертая точка находится внутри. Если нет, отрегулируйте знак нормального вектора.
Точка находится внутри тетраэдра, если она находится внутри всех 4 полупространств.
Если вы смогли найти выпуклую оболочку из четырех точек, то вы можете разделить четырехугольник в двух треугольниках по диагонали (если только одна из точек не была внутренней, тогда у вас есть один треугольник слева).
Таким образом, все это соответствует тесту в треугольнике.
Опять же, имея возможность построить выпуклый корпус, вы уже должны иметь удобный тест области (знак области треугольника). Пятый пункт находится внутри заданного треугольника, когда в тесте области отображается один и тот же знак для трех треугольников, образованных точкой и тремя ребрами данного треугольника.
Если вам нужно решение, которое строго минимизирует количество сравнений и арифметических операций, сообщите мне. Также прочитайте мой собственный ответ здесь: http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle –
Триангуляция ...? –
Не могли бы вы объяснить, что вы подразумеваете под «Мне удалось решить проблему выпуклого корпуса с помощью треугольников»? –
@M_M http://stackoverflow.com/a/2122620/3502949 – Stefan