tgoop.com/the_algorithms/4676
Last Update:
Как проверить, лежит ли точка внутри заданных N точек выпуклого многоугольника?
Алгоритм:
1. Отсортируйте данные точки вместе с точкой запроса в порядке возрастания их значений по абсциссе. Если значения абсцисс любых двух точек одинаковы, отсортируйте их по значению ординаты.
2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.
3. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении по часовой стрелке. Сохраните их в векторе.
4. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении против часовой стрелки. Сохраните эти точки в векторе.
5. Проверьте, существует ли точка запроса в векторе, то она находится вне выпуклой оболочки. Поэтому верните «Нет».
6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.
Сложность: O(N * log(N))
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4676