Выпуклые множества.

Проверка является ли многоугольник выпуклым.

Функция проверяет является ли многоугольник заданный координатами вершин (xi,yi), i=1..n выпуклым или нет. При проверке используется определение выпуклого многоугольника, а именно: многоугольник является выпуклым, если любые две его вершины лежат по одну сторону от прямой продолжения любой из его стороны.

Функция использует описанную ранее функцию для определения лежат ли две точки по одну сторону от прямой. Так же надо заметить, что внутри функции используются элементы X[0],Y[0] для "замыкания" многоугольника, т.е. X[0]=X[n] и Y[0]=Y[n]. Наверх

Проверка является ли многоугольник выпуклым(используя векторные произведения).

Функция проверяет является ли многоугольник заданный координатами вершин (xi,yi), i=1..n выпуклым или нет. В отличии от предыдущего алгоритма, проверка осуществляется следующим образом: для каждой пары смежных сторон вычисляется векторное произведение. В случае, если для всех пар векторные произведения равны нулю, многоугольник вырожденный (отрезок), если все произведения одного знака - многоугольник выпуклый (при этом если все произведения положительные, то вершины обходятся против часовой стрелки, если все произведения отрицательны, то против часовой), если имеются произведения разных знаков, то многоугольник не является выпуклым.

Внутри функции используются элементы X[0],Y[0] для "замыкания" многоугольника, т.е. X[0]=X[n] и Y[0]=Y[n]. В результате получаем логическую переменную Result, которая истина, если многоугольник выпуклый, и ложь, если многоугольник не выпуклый или вырожденный. Наверх

Построение выпуклой оболочки множества точек на плоскости.(мой метод)

Процедура строит выпуклую оболочку множества точек на плоскости, т.е. из множества точек, заданных координатами (xi,yi) выбираются те которые образуют выпуклый многоугольник, содержащий все множество точек.

Алгоритм придумывал я сам, поэтому если найдете ошибки пишите. Метод можно обобщить для построения выпуклой оболочки множества точек в пространстве практически любой размерности.

На вход процедуры подаются массивы координат точек входящих в множество, на выходе получаем преобразованный массив координат (из них удаляются дублирующиеся точки) и массив Conv содержащий номера точек, которые являются вершинами искомого выпуклого многоугольника (естественно порядок следования точек важен!)

При работе процедуры вначале из набора удаляются дублирующиеся точки. На следующем шаге строится матрица A элементы которой ai j принимают значения 0 или 1, при этом ai j=1, если все точки исходного множества кроме точек с номерами i,j лежат по одну сторону от прямой, проходящей через точки с номерами i,j и ai j=0 в противном случае. Не трудно показать, что: Во-первых матрица A симметрична, и во-вторых любая строка (столбец) матрицы A содержит 0 либо 2 элемента отличных от нуля. Построив матрицу A переходим к непосредственному заполнению массива Conv, проследить этот процесс несложно рассмотрев блок-схему.

Процедура использует в своей работе алгоритм проверки лежат ли две точки по одну сторону от заданной прямой, который рассматривался ранее. Наверх

Построение выпуклой оболочки множества точек на плоскости.(метод Грехема)

Письма с описанием этого алгоритма прислали мне сразу два человека Marsel и Нурий Т. Карачурин за что им большое спасибо.

Работа алгоритма начинается с выбора центра масс множества, т.е. точки с координатами:

	xs=(x1+ . . .+xn)/n
	ys=(y1+ . . .+yn)/n

а также точки заведомо принадлежащей оболочки, например точки с наименьшей координатой x (пусть ее номер l). Далее, каждой точке ставим в соответствие угол отмеренный от прямой проходящей через точки (xs,ys) и (xl,yl), и сортируем точки по величине этого угла.

Проходим все точки в порядке сортировки. Определяем лежит ли i+1 точка и центр масс по одну сторону от прямой проходящей через i и i+2 точки, если да то i+1 точка не содержится в наборе образующем выпуклую оболочку, и ее надо исключить из рассмотрения. Действуем так до тех пор пока не рассмотрим все последовательные тройки.

Несколько замечаний к алгоритму.

Алгоритм быстрее чем предыдущий метод получения выпуклой оболочки, но при этом не всегда корректно работает при малом колличестве исходных точек.

Я использую в процедуре сортировку методом пузырька, но можно использовать и любую другую, что может ускорить работу алгоритма.

Также в алгоритме используется функция проверки лежат ли две точки по одну сторону от прямой., так что желательно скачать и ее тоже для рассмотрения алгоритма.

Как обычно для более подробного рассмотрения алгоритма отсылаю Вас к блок-схеме. Наверх

Поиск пересечения двух выпуклых многоугольников.

Нетрудно показать, что результатом пересечения двух выпуклых многоугольников, является так же выпуклый многоугольник. При этом его вершинами будут вершины исходных многоугольников и возможно две дополнительных точки. Процедура, как следует из названия, ищет такой многоугольник.

Координаты вершин исходных многоугольников задаются в массивах ax,ay для первого и bx,by для второго результат помещается в массивы cx,cy при этом дополнительно на выходе получаем количество вершин результирующего многоугольника (переменная n), а так же номера "новых" вершин не входящих ни в один из исходных многоугольников (переменные k1,k2).

Вначале ищутся вершины первого многоугольника лежащие внутри второго многоугольника и наоборот вершины второго многоугольника лежащие внутри первого многоугольника. Надо заметить, что в силу выпуклости исходных фигур и в первом и во втором случаи вершины будут идти подряд поэтому достаточно найти номера первой и последней вершины обладающих указанными свойствами. Затем основываясь на результатах поиска заполняется массив вершин искомого многоугольника, на этом же этапе определяется существование дополнительных вершин и их номера. За подробностями отсылаю Вас к блок-схеме.

Процедура использует функции: проверки принадлежит ли точка многоугольнику и поиска пересечения отрезков. Наверх