Я работал над вопросом, в котором мы должны найти выпуклую оболочку заданных N точек и проверить, присутствует ли другая точка P в многоугольнике или нет. Поэтому я реализовал алгоритм упаковки подарков Марш Джарвиса. Таким образом, он вернул результат с правильно выровненными точками многоугольника, если ни одна из конечных точек выпуклой оболочки не коллинеарна. Но в случае коллинеарности Эти коллинеарные точки не совпадают. Итак, если у такого многоугольника нет выровненных конечных точек, как мы можем проверить, находится ли точка P внутри или снаружи? В основном все алгоритмы, которые я знаю или о которых думаю, работают на стороне fr, и мы должны точно знать, какая точка идет первой, а какая - второй. Есть ли какой-либо подход для этого особого случая ???
пример: если точки многоугольника равны {0,0}, {1,1}, {4,4}, {2,2}, {3 , 3}, {2,0}, а точка - {2,1}. Он должен принять его как многоугольник {0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {2,0} и должен вернуть {2,1} находится в многоугольнике.