Как проверить, лежит ли точка внутри заданных N точек выпуклого многоугольника?

Алгоритм:

1/i>. Отсортируйте данные точки вместе с точкой запроса в порядке возрастания их значений по абсциссе. Если значения абсцисс любых двух точек одинаковы, отсортируйте их по значению ординаты.

2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.

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

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

5. Проверьте, существует ли точка запроса в векторе, то она находится вне выпуклой оболочки. Поэтому верните «Нет».

6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.

Сложность: O(N * log(N))

Авторский канал инженера, который публикует свои практические Linux заметки. Ключевые слова и темы канала: Open Source, Dotfiles, Debian, Software, Linux, Scripts, Notes, Terminal, Shell, Gnu, Tools, Games, Fun, Free Software Movement.

Подписывайтесь и узнавайте много полезного!

Круговой сдвиг вправо

Круговой сдвиг (или циклический сдвиг) — это операция, которая смещает элементы массива или строки влево или вправо, перенося крайние элементы на противоположный конец.

При круговом сдвиге вправо каждый элемент перемещается на одну позицию вправо, а последний элемент переходит в первую позицию.