Алгоритмы и структуры данных

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

Алгоритм:

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

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

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

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

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

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

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

www.tgoop.com/the_algorithms/4966

3.89K viewsAug 11 at 08:59

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

Алгоритм:

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

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

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

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

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

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

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

BY Алгоритмы и структуры данных