Поворот последовательных отрезков

В процессе выполнения алгоритма GRAHAM_SCAN встает следующий вопрос: куда сворачивают два последовательных отрезка p₀p₁ и p₁p₂ в точке p₁ - влево или вправо. Можно привести эквивалентную формулировку этого вопроса – определить знак угла  p₀p₁p₂. Векторное произведение позволяет ответить на этот вопрос, не вычисляя величину угла. Как видно из рис. 3, производится проверка, находится ли направленный отрезок p₀p₂ по часовой стрелке или против часовой стрелки относительно направленного отрезка p₀p₁.

Рис. 3. Использование векторного произведения для определения направления поворота последовательности отрезков

Для этого вычисляется векторное произведение (p₂ – p₀) * (p₁ – p₀). Если эта величина отрицательная, то переход от направленного отрезка p₀p₁ к направленному отрезку p₀p₂ осуществляется против часовой стрелки, и в точке p₁ образуется левый поворот. Положительное значение векторного произведения указывает на ориентацию по часовой стрелке и на правый поворот. Обе эти ситуации проиллюстрированы на рис. 3. В части а показан случай, соответствующий левому повороту, а в части б – случай, соответствующий правому повороту. Нулевое векторное произведение означает, что точки p₀, p₁ и p₂ коллинеарны.

Задание

Написать программу поиска выпуклой оболочки с привлечением графических средств Delphi. На форме разместить компонент Image размером 400*400 пикселей. С помощью датчика псевдослучайных чисел сгенерировать не менее 100 точек и отобразить их на холсте (Canvas) компонента Image. Точки изображать в виде квадратиков (Rectangle) или окружностей (Ellipse) размером в 3 пикселя. Координаты точек как по оси X, так и по оси Y должны быть в диапазоне от 10 до 390. Найти выпуклую оболочку и изобразить ее в виде многоугольника, т. е. соединить точки, принадлежащие выпуклой оболочке, отрезками прямых линий (MoveTo, LineTo, Polygon, Polyline). Начальные сведения о графических возможностях Delphi приведены в файле [Графические возможности Delphi.doc].

5