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



страница1/3
Дата16.06.2015
Размер0,58 Mb.
ТипДокументы
  1   2   3

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

Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи встречаются в машинной графике, проектировании интегральных схем, технических устройств и др. Исходными данными такого рода задач могут быть множество точек на плоскости, набор отрезков, многоугольник (заданный например, списком своих вершин в порядке движения по часовой стрелки) и т.п. результатом может быть либо ответ на какой то вопрос (типа принадлежит ли точка отрезку с концевыми точками, пересекаются ли два отрезка, …), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, соединяющий заданные точки, площадь многоугольника, и т.п.) В этом разделе мы рассмотрим решение некоторых геометрических задач. В наших задачах исходными данными будет множество точек на плоскости Рi, заданных своими координатами: Pi = (Xi,Yi), где Xi,Yi принадлежат множеству действительных чисел R. (В языке Паскаль это тип real, но целесообразно применять тип extended).    Геометрические задачи в информатике встречаются довольно часто, так как компьютер является очень удобным и быстродействующим средством для их решения, поскольку ручной счёт здесь абсолютно неприменим. Так же часто задачи вычислительной геометрии встречаются на олимпиадах разного уровня, так как они требуют от участника собранности и точности даже в мелких деталях реализации. Малейшая ошибка в них приводит к тому, что автор программы вынужден тратить множество драгоценного времени на отладку программы и поиск в ней ошибки. Поэтому именно тот, кто успешно справляется с такими задачами в течение короткого времени, достоин наивысшей похвалы, каковой является победа на олимпиаде.     В задачах аналитической геометрии используются все стандартные геометрические объекты: точки, отрезки, вектора (а также их скалярное и векторное произведения), прямые, многоугольники (выпуклые и невыпуклые) и т.д.. Поэтому даже школьнику уровня 7-8 класса несложно будет разобраться в изложенном материале.    Будем рассматривать задачи вычислительной геометрии только на плоскости и только в декартовой системе координат.

            Точки и вектора. Координаты точки будем задавать парой чисел (x,y). Кроме того, нам понадобится понятие вектора, т.е. направленного отрезка. Его координаты также будем обозначать парой чисел, например (x,y). Координаты вектора будем находить следующим образом:

x=x2-x1                        (x1,y1) - координаты начала вектора;

y=y2-y1                        (x2,y2) - координаты конца вектора.

            Длина вектора в таком случае легко выражается по теореме Пифагора:

                        

            Поскольку длина вектора равна длине отрезка, образующего этот вектор, из предыдущей формулы легко выразить формулу расстояния между точками A(x1;y1) и B(x2;y2).

                        AB=

            Большинство задач вычислительной геометрии используют понятия скалярного и векторного произведений векторов.

            (скалярное произведение)          

            (векторное произведение)         ,

где: - длины векторов a, b соответственно; - угол между направлениями векторов.

            Поскольку все величины в вышеуказанных формулах скалярные, т.е. числовые, результат также будет являться скаляром.

            Скалярное и векторное произведение векторов могут быть также выражены через их координаты:

            (скалярное произведение)            

            (векторное произведение)    .

            Таким образом, зная координаты двух векторов, легко найти значения всех основных тригонометрических функций для угла между ними:



      В отличие от скалярного, векторное произведение векторов имеет две геометрические интерпретации.

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

            Во-вторых, знак векторного произведения определяет положение векторов друг относительно друга:

Если векторное произведение , то по часовой стрелке относительно

Если векторное произведение , то и лежат на одной прямой

Если векторное произведение , то против часовой стрелке относительно

Прямые и вектора.

Будем использовать два основных способа задания прямых в декартовой плоскости:

(x-x1)(y2-y1)=(y-y1)(x2-x1)     (уравнение прямой, проходящей через точки (x1,y1) и (x2;y2));

y=kx+b                             

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

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

Задана прямая y=kx+b. Найти её представление в виде (x-x1)(y2- y1)=(y-y1)(x2-x1), т.е. найти две точки (x1;y1)   и (x2;y2), проходящие через эту прямую.

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

            y1=kx1+b;   y2=kx2+b.

            Прямая проходит через найденные точки (x1;y1) и (x2;y2), следовательно её уравнение может быть записано в виде (x-x1)(y2-y1)=(y-y1)(x2-x1).

Задана прямая (x-x1)(y2-y1)=(y-y1)(x2-x1). Найти её представление в виде y=kx+b.

            Раскроем скобки в исходном уравнении:

                        x(y2 - y1) - x1(y2 - y1) = y(x2 - x1) - y1(x2 - x1);

             y(x2 - x1) = x(y2 - y1) + y1(x2 - x1) - x1(y2 - y1);

           

            Таким образом, видим, что в полученном уравнении

            В практической реализации, после подсчёта k, b можно вычислить проще. Для этого достаточно вспомнить, что прямая проходит через точку (x1;y1):   

 y=kx+b;    y1=kx1+b;      b=y1-kx1.

            Кроме того, нужно обязательно помнить, что для прямой, параллельной оси ординат, x1=x2, а значит, невозможно будет найти искомое представление для данной прямой.

Задана прямая ax + dy + c=0. Найти её представление в виде y = kx + b.

            Выполним следующие преобразования над исходным уравнением:

                                    ax + dy + c=0; отсюда    dy=-ax-c;

; ; . Получаем

      Аналогично, в этом примере не стоит забывать, что прямая может быть параллельна оси ординат.

Задана прямая (x - x1)(y2 - y1) = (y - y1)(x2 - x1). Найти её представление в виде ax + by + c = 0.

Раскроем скобки в исходном уравнении:

            x(y2 - y1) - x1(y2 - y1) = y(x2 - x1) - y1(x2 - x1);

            x(y2 - y1) + y(x1 - x2) + y1(x2 - x1) - x1(y2 - y1)=0.

Из уравнения видим, что:

            a=y2-y1;            b=x1-x2;         c=y1(x2-x1)-x1(y2-y1).

            

            Расстояние от точки до прямой ax + by + c = 0 выражается формулой



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

Далее рассмотрим несколько простейших задач, необходимых при решении более сложных. Оформим их решение в виде функций и процедур Turbo Pascal, которые по желанию можно объединить в модуль (unit), либо вставлять в исходный текст программ, решающих более сложные задачи.

Будем предполагаем, что все прямые для этих алгоритмов задаются в виде (x-x1)(y2-y1)=(y-y1)(x2-x1). Если при написании программы появляется необходимость использовать другое представление прямой, нужно просто воспользоваться методами перехода от одного представления к другому, описанными ранее.



  1. Заданы точки A(x1;y1), B(x2;y2) и прямая (x-x3)(y4-y3)=(y-y3)(x4-x3). Определить, лежат ли точки по разные стороны от заданной прямой.  По условию, прямая проходит через точки C(x3;y3) и D(x4;y4).

            Для того, чтобы определить, лежат ли точки по разные стороны от прямой, возьмём точку C и построим вектора . Если вектора и лежат по разные стороны относительно , точки будут лежать по разные стороны от прямой. В обратном случае точки будут лежать по одну сторону от прямой.

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



Sign()Sign().

Sign - это известная математическая функция, определяющаяся таким образом:

Sign(x)=

Внесём в наш модуль две первые функции:

function VectorMult(x1,y1,x2,y2:real):real;
   begin
   VectorMult:=x1*y2-x2*y1;
   end; {VectorMult}

function Sign(n:real):shortint;


   begin
   if n>0 then Sign:=1 else
      if n<0 then Sign:=-1 else
         Sign:=0;
   end;

Очевидно, что если одна из точек лежит на прямой, то для неё векторное произведение будет равно нулю. В этом случае будем считать, что она лежит по ту же сторону от прямой относительно первой точки. Но если есть необходимость использовать другой подход, нужно будет просто проверять вариант, когда векторное произведение нулевое.

function OtherSide(x1,y1,x2,y2,x3,y3,x4,y4:real):boolean;

var v0x,v0y,v1x,v1y,v2x,v2y:real; {координаты векторов}

   begin

   v0x:=x4-x3; v0y:=y4-y3;

   v1x:=x1-x3; v1y:=y1-y3;

   v2x:=x2-x3; v2y:=y2-y3;

   if (v0x*v1y-v0y*v1x)*(v0x*v2y-v0y*v2x)<0 then OtherSide:=true else OtherSide:=false;

   {Можно заменить на

                              if Sign(VectorMult(v0x,v0y,v1x,v1y))<>Sign(VectorMult(v0x,v0y,v2x,v2y))}

   end; {OtherSide}


2. Заданы точки A(x1;y1), B(x2;y2), C(x3;y3) и D(x4;y4). Определить, пересекаются ли отрезки AB и CD.

  Отрезки пересекаются тогда и только тогда, когда:

точки A и B лежат по разные стороны относительно прямой CD;

точки С и D лежат по разные стороны относительно прямой AB.

Для проверки этих условий воспользуемся уже написанной функцией OtherSide.

Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real):boolean;

begin

   if OtherSide(x1,y1,x2,y2,x3,y3,x4,y4) and



        OtherSide(x3,y3,x4,y4,x1,y1,x2,y2) then LinesCross:=true                                                                                      else LinesCross:=false

end;



  1. Заданы прямая (x-x1)(y2-y1)=(y-y1)(x2-x1) и точка (x0;y0). Определить, лежит ли точка на прямой. 

Такая задача решается очевидно. Ясно, что если точка лежит на прямой, то её координаты удовлетворяют уравнению этой прямой. Следовательно, достаточно лишь проверки следующего условия: (x0 - x1)(y2 - y1) = (y0 - y1)(x2 - x1).
function PointOnLine(x0,y0,x1,y1,x2,y2:real):boolean;

begin


   if (x0-x2)*(y1-y2)=(y0-y2)*(x1-x2) then PointOnLine:=true                                                                              else PointOnLine:=false

end;


4. Заданы точки A(x1;y1), B(x2;y2), C(x3;y3) и D(x4;y4). Определить, лежат ли отрезки AB и CD на одной прямой.

Уравнение прямой AB: (x-x1)(y2-y1)=(y-y1)(x2-x1).

 Чтобы отрезок CD лежал на этой же прямой, необходимо, чтобы обе точки C и D лежали на этой прямой, т.е. удовлетворяли её уравнению.  При реализации этого алгоритма можно воспользоваться ранее описанной функцией PointOnLine:

function SameLine(x1,y1,x2,y2,x3,y3,x4,y4:real):boolean;

begin

   if PointOnLine(x3,y3,x1,y1,x2,y2) and



        PointOnLine(x4,y4,x1,y1,x2,y2) then SameLine:=true

                                                                              else SameLine:=false

end;

5.Заданы прямые (x - x1)(y2 - y1) = (y - y1)(x2 - x1) и (x - x3)(y4 - y3)=(y - y3)(x4 - x3). Найти точку их пересечения (если таковая имеется).

 Очевидное решение состоит в том, чтобы решить систему уравнений прямых:

                                                

                                    Однако если попытаться раскрывать скобки, выражать значение одной из неизвестных переменных через другую и подставлять выражение в другое уравнение, получим достаточно сложные вычисления, которых хотелось бы избежать. Поэтому для простоты решения приведём заданные представления прямых к виду y=kx+b. Мы уже знаем, как это делать. Тогда достаточно будет решить систему:

                                                

                                                k1x+b1=k2x+b2;

                                                x(k1-k2)=b2-b1;

                                                

 y теперь можно найти из любого начального уравнения системы.

   Теперь можно подумать о том, что будет, если одна из прямых (или обе) параллельны оси y, ведь тогда мы не сможем вычислить для неё угловой коэффициент k. Поэтому перед его вычислением будем проверять параллельность прямой оси y. Пусть, например, прямая (x - x1)(y2 - y1) = (y - y1)(x2 -x1) параллельна оси y, т.е. x2 = x1 и нужно найти точку её пересечения с прямой y = k2x + b2, которая не параллельна оси y, т.е. k2 существует. Тогда абсцисса пересечения этих двух прямых, очевидно, и будет x1, ординату же можно получить из уравнения второй прямой. Аналогичным способом поступаем в случае, если вторая прямая параллельна оси y. Теперь остаётся только подумать о том, как учесть возможную параллельность заданных прямых. Ответ очевиден: прямые параллельны, если у них совпадает угловой коэффициент, т.е. k1=k2. Нужно лишь дополнительно проверить, параллельны ли обе прямые оси y и если это так - значит, они параллельны друг другу. В нашей реализации этого алгоритма в процедуру в качестве параметров задаются координаты x1, y1, x2, y2, x3, y3, x4, y4, в качестве переменных - результаты выполнения процедуры:  x,y - координаты точки пересечения (если она существует);     err - логическая переменная, которая истинна, если прямые параллельны.

procedure CrossPoint(x1,y1,x2,y2,x1,y1,x2,y2:real; var x,y:real; var err:boolean);
var k1,b1,k2,b2:real;
begin
   if (x1=x2) and (x3=x4) then err:=true else
      begin
      k1:=(y1-y2)/(x1-x2); b1:=y1-k*x1;
      k1:=(y3-y4)/(x3-x4); b1:=y3-k*x3;
      if x1=x2 then
         begin {Первая прямая - параллельна оси y, вторая - нет}

         x:=x1; y:=k2*x+b2;


         end else
      if x3=x4 then
         begin
         x:=x3; y:=k1*x+b1;
         end else

      if k1=k2 then err:=true {прямые параллельны} else

         begin
         x:=(b2-b1)/(k1-k2);
         y:=k1*x+b1;
         end;
      end;
   end; {CrossPoint}

 

Задача "Точка в многоугольнике".

            Условия. Многоугольник (необязательно выпуклый) задан координатами своих вершин (xi;yi), 1iN в порядке обхода. Определить, лежит ли точка с координатами (x0;y0) внутри или вне многоугольника.

            Входные данные содержатся в файле input.txt: в первой строке - пара чисел (x0;y0), в каждой (i+1)-й строке - координаты i-й точки (xi;yi).



            Выходные данные нужно вывести в файл output.txt: единственная строка этого файла должна содержать одно число - 1, если точка внутри многоугольника (или на его стороне), 0 - в противном случае.

Пример.




Input.txtt




Output.txt




Input.txt




Output.txt

5

3.1

1




5

3.7

0




1

1







1

1







6

3.8







6

3.8







3

3







3

3







5

3







5

3







2

2







2

2







2

4







2

4







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

            Проведём луч из точки (x;y) в любом направлении и найдём количество пересечений этого луча со сторонами многоугольника. Очевидно, что если точка внутри многоугольника, полученное количество будет нечётным. Если же точка не принадлежит многоугольнику, количество пересечений будет чётным   либо нулевым.

            На этой идее и основан наш алгоритм. Для удобства мы проводим луч через точку (x0; y0) параллельно оси абсцисс. Для определения результата используется логическая функция XOR. Ясно, что если количество истинных операндов в выражении XOR будет нечётным, в конце концов её значение будет истинно - это и будет означать, что точка лежит в многоугольнике. В противном случае результат будет ложным - точка вне многоугольника. Кроме того, в программе используется функция CrossPoint, описанная в модуле Geometry, текст которого приведен в начале этого раздела.

uses Geometry;

const maxn=100; {максимальное количество точек многоугольника}

type index=1..maxn;

           coord=real;      {координаты}

var dat,out:text;


        n,i,i1:index;
        x,y:array[index] of coord;

        x0,y0:coord; {координаты точки}

        inpoly:boolean;

function min(a,b:real):real;


   begin
   if a   end; {min}

function max(a,b:real):real;


   begin
   if a>b then max:=a else max:=b;
   end; {max}

function ExCrossPoint(i:index):boolean;

{Определяет, пересекается ли проведенный луч с i-й стороной многоугольника}
var cx,cy:real; {координаты точки пересечения}

        err:boolean;


   begin
   if i=n then i1:=1 else i1:=i+1;
   CrossPoint(x0,y0,x0+1,y0,x[i],y[i],x[i1],y[i1],cx,cy,err);
   if err then ExCrossPoint:=false else
      if (cx>=x0) and (cx>=min(x[i],x[i1])) and (cx<=max(x[i],x[i1]))
                              and (cy>=min(y[i],y[i1])) and (cy<=max(y[i],y[i1]))

                              {точка пересечения должна принадлежать стороне}

              then ExCrossPoint:=true
              else ExCrossPoint:=false;
   end; {ExistSamePoint}

begin {Main}

   Assign(dat,'input.txt'); Reset(dat);

   ReadLn(dat,x0,y0); {координаты заданной точки}

   while not eof(dat) do
      begin
      Inc(n);
      ReadLn(dat,x[n],y[n]);
      end;
   Close(dat);

   for i:=1 to n do


      begin
      if (x0=x[i]) and (y0=y[i]) then

         begin {Точка (x0;y0) совпадает с одной из вершин многоугольника}

         inpoly:=true; Break;
         end;
      inpoly:=inpoly xor ExCrossPoint(i);
      end;

   Assign(out,'output.txt'); Rewrite(out);


   if inpoly then write(out,1) else write(out,0);
   Close(out);

end.
 


  1   2   3

Похожие:

Вычислительная геометрия iconЦель проведения вступительного испытания
При поступлении в аспирантуру по направлению «Информатика и вычислительная техника» сдается вступительное испытание, включающее в...
Вычислительная геометрия iconРабочая программа дисциплины для специальности 230100 Информатика и вычислительная техника, направление
Рабочая программа составлена в соответствии с гос впо по направлению подготовки (специальности) 230100 Информатика и вычислительная...
Вычислительная геометрия icon2. Основная часть. Что такое геометрия? Геометрия
Геометрия – раздел математики, изучающий пространственные структуры, отношения и их обобщения. Геометрия всегда интересовала учёных...
Вычислительная геометрия iconУчебный план направление подготовки 230000 (552800) "Информатика и вычислительная техника "

Вычислительная геометрия iconРабота в графическом редакторе Paint Геометрия в Paint
...
Вычислительная геометрия iconКонтрольная работа выполняется в виде реферата. Темы рефератов распределяются и закрепляются на сессии
Геометрия до Евклида : геометрия Вавилона и Египта, геометрия древней Греции ( Фалес Милетский, школа Пифагора, Платон, Аристотель,…)....
Вычислительная геометрия iconФункциональный анализ и вычислительная математика
...
Вычислительная геометрия icon«Вычислительная математика» по физико-математическим наукам
...
Вычислительная геометрия iconПроект программы дисциплины
Фгос впо к структуре и результатам освоения основных образовательных программ магистратуры по «профессиональному» циклу по направлению...
Вычислительная геометрия iconБесполезная геометрия? Или: потерянная геометрия окружности и симметрий
Трудно назвать в какой-либо другой части геометрии теоремы, которые проще всего доказать используя методы и идеи теории групп, а...
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com