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