У среднестатистического гражданина сочетание слов «геометрия» и «компьютер» вызывает, как правило, ассоциацию с компьютерной графикой. Действительно, графика — наиболее наглядное применение геометрических принципов в компьютере. Однако помимо графики геометрический аппарат имеет огромное количество не менее важных сфер применения. На современном компьютере ставятся задачи, решение которых требует не просто нескольких формул, а достаточно сложных алгоритмов. С некоторыми из них вы познакомитесь в этой статье.
Для начала договоримся, как геометрические объекты будут представляться в памяти компьютера. Итак, точка — это пара чисел (координат X и Y). Отрезок — это пара точек, а многоугольник — это N точек; подразумевается, что они последовательно соединены отрезками, причем последняя точка также соединена с первой.
Нахождение наименьшего расстояния между точками
Такая задача может возникнуть, например, в системе контроля над транспортом: полезно знать, насколько близко транспортные средства находятся друг к другу. Кроме того, она часто встречается в задачах планировки и прокладывания маршрута. Для ее решения существуют несколько алгоритмов. Самый простой и очевидный — это перебрать расстояния между всеми возможными парами точек и выбрать из них наименьшее. Реализация не представляет особых сложностей:
Type Point = record {Представление точки в памяти} x,y : real; end; Var Points : array[1..1000] of Point; {Массив точек} i,j : integer; N : integer; {Количество точек} D : real; {Наименьшее расстояние} Begin {Ввод количества точек N и их координат} … if n>1 then D:=100000000 {Полагаем наименьшее растояние достаточно большим числом} else D:=0; for i:=1 to N-1 do for j:=i+1 to N do {Перибераем все пары точек} if sqrt(sqr(Points[i].x-Points[j].x)+sqr(Points[i].y-Points[j].y))0) do {Поиск первого кандидата на пренадлежность выпуклой оболочке} i:=i+1; for j:=i+1 to N do {Выбор такой точки, чтобы угол между сторонами был наименьшый} if (x0*(Points[j].y-shell[H].y)-y0*(Points[j].x-shell[H].x)>0) and ((Points[j].x-shell[H].x)*(Points[i].y-shell[H].y)-(Points[j].y-shell[H].y)*(Points[i].x-shell[H].x)>0) then i:=j; x0:=Points[i].x-shell[H].x; y0:=Points[i].y-shell[H].y; until (i>N) or used[i]; {Повторяем до тех пор, пока не наткнемся на уже отмеченную точку (замкнем круг)} {Дальнейшая обработка результата} … End.
Время работы программы есть O(NH), где H — количество вершин выпуклой оболочки. Очевидно, что это не больше O(N2), на практике же алгоритм редко когда работает дольше O(Nlog2N).
Цель статьи полагалась в том, чтобы ознакомить вас с некоторыми достижениями computer science в области геометрии. Комбинация геометрии с алгоритмами сортировки и выбора позволяет находить эффективные решения для большинства задач. Причем, методы решений актуальны и в пространственных задачах. Доказать корректность всех приведенных выше алгоритмов несложно; желающие могут заняться этим самостоятельно.
P.S. Все программы проверены на работоспособность — надо только вставить код ввода и вывода вместо троеточий :-).