![Выше по иерархии](../../../gif/3arrow3.gif)
Математика. Пути и Графы. Комбинаторика и перебор
Сортировка
Защита и сокрытие информации. Атаки и взлом
Сжатие информации и кодирование. СRC
Графика и обработка изображений. Фракталы
Поиск в строках, массивах, последовательностях
Разбор выражений. Компиляторы и интерпретаторы
Cтруктуры данных. Хранение информации
AI, ГА, Нейронные сети
Вейвлеты
Игры, и все с ними связанное
Олимпиадные задачи
Разное
Софт: просмотр PS и PDF файлов
![](../../../gif/cancelle.gif) Написать веб-мастеру
Почитать историю сайта
|
Математика:
Вычислительная геометрия:
Построение выпуклой оболочки.
Пока рассматриваем выпуклую оболочку на плоскости. Статья для n-мерного случая имеется в архиве.
Пусть задано некоторое множество точек на плоскости.
Выпуклая оболочка - наименьший выпуклый многоугольник, содержащий данные точки.
Если на них, как на гвозди, натянуть кольцо из резины, то оно, сжавшись, превратится как раз в выпуклую оболочку. Очевидно, стороны выпуклой оболочки - отрезки от одной вершины к другой.
Алгоритм |
Время - все точки внутри |
Время - все точки на оболочке |
Среднее время |
Оптимальность/ примечания |
|
O( n ) |
O( n2 ) |
O( nh ) |
Простой принцип работы. h - количество углов оболочки. |
|
O( n ) |
O( nlogn ) |
O( nlogn ) |
в среднем быстрейший |
|
O( nlogn ) |
O( nlogn ) |
O( nlogn ) |
Время тормозится сортировкой. Сам алгоритм всегда O( n ) |
|
O( n ) |
O( n ) |
O( n ) |
Вводимые точки должны образовывать ломаную без самопересечений. Если это не так, пользуйтесь другими алгоритмами. Впрочем, этого можно добиться за O(n), например, поразрядной сортировкой сначала по x, затем по y |
Архив статей.
![](../../../gif/3arrow1.gif) Вверх по странице, к оглавлению и навигации
| |