Вычислительная геометрия (стр. 4 )

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

Прежде всего, отсортируем вершины по возрастанию абсциссы. При этом для каждой вершины будем хранить соседние (в многоугольнике) с ней вершины. Определим для каждой вершины её тип:

начальная вершина — обе соседние вершины располагаются справа;

промежуточная вершина — соседние вершины располагаются и слева и справа;

конечная вершина — обе соседние вершины располагаются слева.

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

Рассмотрим первую фазу (вторая аналогична первой). Пока есть необработанные вершины, выбираем самую правую из них. Возможны три случая:

	вершина является конечной: удаляем из сканирующей линии исчезнувшие рёбра (рёбра c и b) обновляем представителя пары рёбер, ставших соседними (теперь вершина v — представитель пары рёбер ad);
	вершина является промежуточной:   обновляем ребро сканирующей линии и представителей верхней (cb') и нижней (ab') пар рёбер;
	вершина является начальной: находим пару соседних рёбер ad, между которыми располагается данная вершина, а также их представителя w; добавляем два ребра (b и c) в сканирующую линию; обновляем представителей трех пар ребер (ab, bc, cd); уничтожаем излом v, разрезая многоугольник отрезком vw (это можно реализовать, раздвоив вершины v и w на v1, v2 и w1, w2 и добавив ребра v1w1 иw2v2).

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

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

Будем говорить, что ребро a находится снаружи ребра b, если конец ребра a расположен слева от b.

Будем говорить, что ребро a нацелено на ребро b, если бесконечная прямая линия, определяемая ребром b, расположена перед a.

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

Ориентируем границы многоугольников в направлении по часовой стрелке. Выберем в качестве текущих рёбер многоугольников P и Q ребра p и q соответственно.

Правила перемещения указателей p и q:

	p и q нацелены друг на друга: перемещаем тот указатель, который соответствует тому ребру, которое находится снаружи от другого;
	p нацелено на q, а q не нацелено на p: если p не находится снаружи q, то конечная концевая точка ребра p заносится в многоугольник пересечения; перемещаем окно p;
	q нацелено на p, а p не нацелено на q: если q не находится снаружи p, то конечная концевая точка ребра q заносится в многоугольник пересечения; перемещаем окно q;
	p и q не нацелены друг на друга: если p и q пересекаются, то точка их пересечения заносится в многоугольник пересечения; перемещаем окно, которое соответствует тому ребру, которое находится снаружи от другого.

Алгоритм состоит из двух частей:

перемещаем указатели по указанным выше правилам (не формируя многоугольник пересечения) до обнаружения точки пересечения рёбер. Если такая точка нашлась, то переходим к следующей части, иначе проверяем принадлежность многоугольников друг другу и завершаем работу; перемещаем указатели по тем же правилам (формируя многоугольник пересечения) до повторного обнаружения какой-либо точки пересечения.

Время работы алгоритма составляет O(n), где n — суммарное количество рёбер в многоугольниках P и Q.

Решение задачи

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

Описание:

Решение задачи можно разбить на несколько пунктов:
1) выборка двух точек из n без повторений реализована циклами

for i:= 1 to n-1 do

for j:= i+1 to n do begin

...

end;

2) внутри этого цикла производится перебор всех точек, и выясняется лежит ли проверяемая точка внутри круга (условие (x-rx)2+(y-ry)2 > r2 означает, что расстояние от точки до центра круга меньше его радиуса). Если точка внутри круга подставляем её координаты( x и y ) в уравнение прямой

где x1,y1,x2,y2 - координаты первой и второй выбранных выше точек соответственно.
Подставляем x и y:
если,

то точка находиться выше прямой

если,
то ниже прямой.
Может оказаться так, что точки имеют одинаковую координату по x, поэтому в уравнении получиться деление на ноль. Поэтому перед подстановкой в неравенство(уравнение прямой), сравним абсциссы точек, и если они равны, все точки будут лежать либо справа либо слева от прямой.
Чтобы выяснить, где лежит каждая проверяемая точка будем сравнивать первую координату точки с первой координатой любой из двух выбранных точек(в нашем примере сравнивается с координатой первой точки).
3) После каждого сравнения увеличиваем счётчики high - для подсчёта точек выше прямой или справа и счётчик low - для подсчёта точек ниже прямой и, соответственно, слева от неё.
Каждый раз найдя решение лучше предыдущего сохраняем его в переменных res, t1, t2.

Математическая модель

Для определения координат центра окружности, проходящей через 3 точки нужно:

Провести две прямые через данные три точки

Найти координаты центров отрезков, соединяющих точки

Провести через центральные точки две прямые, перпендикулярно исходным прямым. (Прямая с уравнением (y-y0 ) = - 1/p(x-x0) проходит через точку с координатами (x0 , y0 ) перпендикулярно линии у = px.).

Далее нужно найти координаты точки пересечения перпендикуляров. Это и будет центр окружности, проходящей через три точки.

Псевдокод

Цикл по тройкам точек  Перебор окружностей

Определить радиус и центр окружности

Обнулить локальный счетчик

Цикл по точкам множества

Если точка лежит на расстоянии радиуса до центра ТО

Увеличить локальный счетчик

Все Если

Все цикл по точкам множества

Если локальный счетчик больше, То

Запомнить окружность

Все Если

Все цикл по тройкам

Работа с программой:

Задаем координаты точек произвольно. Выводим координаты точек на экран.

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

Результат работы программы:

Литература  и источники

лгоритмы: построение и анализ. — М.: МЦНМО, 2000. ычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997. , , Начала компьютерной графики. – М: Диалог-МИФИ, 1993 http://rain. ifmo. ru/cat/view. php/theory/math/geometry-2005 - Дискретная математика: алгоритмы. Вычислительная геометрия. http://pasadvice. narod. ru/prog/krug. htm - Круг и множество точек. Примеры программ на языке программирования Paskal.

Приложение

Код программы:

program Krug;

const

n = 5;        {число точек}

var

i, j,t, r,rx, ry, high, low, res: integer;                {i, j,t - счётчики}

M: array[1..n,1..2] of integer;

t1,t2: integer;        {в них запишем номера двух точек, - решение задачи}

Begin

rx:= 0;                {x-координата центра круга}

ry:= 0;                {y-координата центра круга}

r:= 8;                {радиус круга}

Randomize;                {координаты точек задаём пройзвольно}

for i:= 1 to n do begin

M[i,1]:= Random(21)-10;        {из диапазона [-10,10]}

M[i,2]:= Random(21)-10;

end;

for i:= 1 to n do begin                {вывод координат точек на экран}

Write(M[i,1]:3,' ',M[i,2]:3);

Writeln;

end;

res:= n+1;                        {инициализация просто большим числом}

for i:= 1 to n do

if sqr(M[i,1]-rx)+sqr(M[i,2]-ry) > sqr(r) then inc(j); {в j считаем точки вне круга}

if j = n then begin

Writeln('Все точки вне круга!');

Readln;

Exit;

end;

for i:= 1 to n-1 do                {выборка двух точек из n без повторений}

for j:= i+1 to n do begin        C:\Program Files (x86)\ZennoLab\RU\ZennoPoster Pro\5.27.1.0\Progs\

high:= 0;        {начальные условия: high - для подсчёта точек выше прямой или справа, если}

low:= 0;        {прямая параллельна Oy; low - для подсчёта точек ниже и, соответственно, слева}

for t:= 1 to n do begin  {перебираем все точки}

if sqr(M[t,1]-rx)+sqr(M[t,2]-ry) < sqr(r) then {которые внутри круга}

begin

if (M[i,1]=M[j,1]) and (M[t,1] > M[i,1]) then inc(high); {прямая||Oy, точки справа}

if (M[i,1]=M[j,1]) and (M[t,1] < M[i,1]) then inc(low);  {прямая||Oy, точки слева}

if (M[i,1] <> M[j,1]) then begin {прямая не||Oy, подставляем координаты в уравнение прямой}

if M[t,2] > ((M[i,2]-M[j,2])/(M[i,1]-M[j,1]))*(M[t,1]-M[i,1])+M[i,2] then inc(high);

if M[t,2] < ((M[i,2]-M[j,2])/(M[i,1]-M[j,1]))*(M[t,1]-M[i,1])+M[i,2] then inc(low);

end;

end;

end;

if res > abs(high - low) then begin        {вычисляем разницу high - low по модулю}

res:= abs(high - low); {если меньше результата, полученного ранее}

t1:= i; {эти две точки будут новым решением}

t2:= j;

end;

end;

Writeln;

Writeln(res);        {вывод разницы в количестве точек по разные стороны от прямой}

Writeln(M[t1,1]:3,' ',M[t1,2]:3); {и самих точек на экран}

Writeln(M[t2,1]:3,' ',M[t2,2]:3);

Readln;

End.