Архив метки: вычислительная геометрия

Сканирование Грэхема — нахождение выпуклой оболочки множества точек

Еще один алгоритм по нахождению выпуклой оболочки множества точек. Теперь уже не такой тормозной (не O=n^3, а O=n log n ) — Сканирование Грэхема. Вначале сортируем все точки по X. На случай, если вдруг будет несколько точек с одним X, … Читать далее

Рубрика: Без рубрики | Метки: , | Оставить комментарий

Нахождение выпуклой оболочки для множества точек. Медленный вариант.

Давно хотел начать разбирать алгоритмы вычислительной геометрии и вот начал. Это, самый первый алгоритм из книги «Вычислительная геометрия. Алгоритмы и приложения».  В книге он называется SlowConvexHull. Работает он неидеально — из-за того, что в нем нет разницы в том, где … Читать далее

Рубрика: Без рубрики | Метки: , | Оставить комментарий