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

Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач [1]. При программировании решений к задачам на геометрию требуется своя специфика. Хорошей литературы на эту тему не так уж много, но все-таки несколько источников указать можно [2], [3], [4].

Основные геометрические понятия

Системы координат и векторы

Положение любой точки $P$ в пространстве (в частности, на плоскости) может быть определено при помощи той или иной системы координат. Числа, определяющие положение точки, называются координатами этой точки. Наиболее употребительные координатные системы - декартовы прямоугольные. Кроме прямоугольных систем координат существуют косоугольные системы. Прямоугольные и косоугольные координатные системы объединяются под названием декартовых систем координат.

Иногда на плоскости применяют полярные системы координат, а в пространстве - цилиндрические или сферические системы координат.

Рис. 1

Для задания декартовой прямоугольной системы координат нужно выбрать несколько взаимно перпендикулярных прямых, называемых осями. Точка пересечения осей O называется началом координат. На каждой оси нужно задать положительное направление и выбрать единицу масштаба. Координаты точки P считаются положительными или отрицательными в зависимости от того, на какую полуось попадает проекция точки P.

Когда говорят про двухмерную систему координат, горизонтальную ось называют осью абсцисс (осью Ox), вертикальную ось - осью ординат (осью Оy). Положительные направления выбирают на оси Ox - вправо, на оси Oy - вверх. Координаты x и y называются соответственно абсциссой и ординатой точки. Запись P(a,b) означает, что точка P на плоскости имеет абсциссу a и ординату b  (рис.1).

Декартовыми прямоугольными координатами точки P в трехмерном пространстве называются взятые с определенным знаком расстояния (выраженные в единицах масштаба) этой точки до трех взаимно перпендикулярных координатных плоскостей. В зависимости от взаимного расположения положительных направлений координатных осей возможны левая и правая координатные системы.

Рис. 2

Отрезок, концы  которого упорядочены (рис.2), называется направленным (упорядоченность означает, что один конец отрезка считается начальной точкой, а другой – конечной).

Направленный отрезок называется вектором.

Длина вектора называется его модулем:
| a | – обозначение модуля вектора a.

Проекции вектора a с начальной точкой (X1, y1) и конечной точкой (X2,  2) на оси координат называются координатами вектора: a ={X2 – X1, Y2 – y1} или a(X, Y). Модуль вектора через его координаты:

Два вектора считаются равными, если они имеют одинаковую длину и направление (равенство соответствующих координат), следовательно, алгебраическое представление вектора — это упорядоченный набор чисел (его координаты). Сложение и вычитание векторов a(X1,Y1) и b(X2, Y2), умножение вектора на число t определяются по следующим правилам:

a ± b = (pan>1 ± X2 ± Y2

ta = (</i>1, tY1)

Вектора, отличающиеся множителем, называются коллинеарными.

4.1.2. Скалярное и векторное произведение

Скалярное произведение двух векторов – это число, равное произведению модулей этих векторов на косинус угла между ними (a, b) = |a|·|b| cosφ.

Следствие. Если два вектора перпендикулярны, то их скалярное произведение равно нулю.

Угол между векторами – это наименьший угол между направленными отрезками, приведенными к одной начальной точке (рис. 3).

Рис. 3

1.   Если угол φ - острый, то (a, b)>0.

2.   Если угол φ - тупой, то (a, b)<0.

3.   Если   вектор a перпендикулярен вектору b, то (a, b)=0.

4.   (a, a) = |a|2.

Скалярное произведение двух векторов a(X1, Y1) и b(X2, Y2) через их координаты выражается следующим образом: (a, b) = X1 · X2 + Y1 · Y2

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

Следствие. Вектор b(Y, -X) будет перпендикулярен вектору a(X,  Y).

 

В трехмерном пространстве для векторов a(X1, Y1,  Z1) и 2, Y2, Z2) соответственно формула скалярня выражается: (a, b) = X1·X2 + Y1·Y2  + Z1·Z2 ,  а для угла -

 

Рис. 4

Векторное произведение двух векторов – это вектор, обозначаемый [a × b], который определяется следующими условиями:

  1. длина вектора |[a × btrong>a|·|>|·sinφ; где & между векторами (т.е. равна S параллелограмма, построенного на сторонах a и b);
  2. [a × b] вектор перпендикулярен каi>a, так и вектору ng>;
  3. [a × b] направлен как ось oz к осям >ox и oy,ктора a, b и [a × < >b] образуют правую тройку (по правилу “буравчика”, если вектор a поворачивать до вектора b по i>

 

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

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

[a × b] = (Y1· Z2 - Y2 > Z1)g>i + (Z1· > X2 - Z2 · > X1) Symbol'>×span>(X1183;Y2 - X >·/i>1)×k иyle="float:left;margin:10px 10px 0 0;">

где /strong>, j, k <ые вектора осей OX >OY, OZ соответственно; det(…) – означает определитель матрицы, составленной из орт осей и координат исходных векторов.

 Если плоскость исходных векторов взять за плоскость XY, то в формулах координаты Z1 и Z2 равны нулюxt-indent:20pt'>Следует обратить внимание на многознведенных геометрических понятий, которые можно использовать в различных задачах. Например, для понятия векторное произведение:

4.1.3. Уравнения прямой и окружности на плоскости

a)      Через заданную на плоскости точку с координатами (X0,y0) можно провести прямую, перпендикулярную вектору $n$(a,b). Для любой точки на этой прямой с координатами (X,Y) направляющий вектор a = {X – X y – y0} перпендикулярен  вектору нормали $n$, т.е. скалярное произведение ($n$, a<i>= 0 или A(X – X0) + B(<sp;– y0) = 0. Раскрывая скобки, легко получить  классическое уравнение прямой Ax + By + C = 0, где константа C > = -A X0 -B y0.

b)      Уравнрпендикулярной данной Ax + By + bsp;= 0, имеет вn>Bx - Ay + C1 = 0.

c)      Уравнение прямой, проходящей через две рардинатами (X1,&ub>1) и (X2, < >y2), выражается следующей формулой:

Эта формула выражает коллинеарность векторов {X – X1, Y – y1} и {X2 – X1, y2 – y1} >X, Y) на прямой.

От этого уравнения тоже лнению классического вида Ax + By + C = 0, где A = Y1 – y2, B = x2 – x1, C =X Y2– X2 /p>

d)font:7.0pt ""'>     Уравнение прямой в парамается системой уравнений

x =1+ t (x2– x1)yle='margin-left:35.4pt;'>y  =  y1 + t (y2– y1).

Эта же система может задавать и отрезок при t ∈ [0, 1], и луч при < >t ∈ [0, e)le='font:7.0pt ""'>      окружности с центром в точке с координатами  (X,  y1) и радиусом >r имеет вид: (Xn>– x1 + (Y –  Y1)2 = r2.

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

x =  x1+ r cosφ

<nbsp; =  y1  >+ r sinφ>φ ∈ [0, 2π].

4.2. Отношения между геометрическими объектами

4.2.1. Расстояние и площадь

a)      Расстояние d между двумя точками с координатами (X1, Y1) <>X2, yi>) вычисляется по формуле <="float:left;margin:20px 10px 0 0;">

v>

      Расстояние d от точки P1(X1, Y1) до прямой Ax + By + C = 0 вычисляется следующим образом.

Предположим, что выбрана точка P0(X0, y0), лежащая на прямой (рисунок 5), тогда проекция отрезка P1P0 на вектор n(a, b). Используя формулы скалярного произведения и свойство Ax0  + By0 + C = 0, получим: ,

 

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

c)bsp;     Вычисление расстояния dX1, Y1) до луча или отрезка отличается от вышеописанного, так как основание перпендикуляра, опущенного из точки на продолженную прямую, может не лежать на луче/отрезке. В этом случае кратчайшим расстоянием будет дистанция от точки до начальной точки луча или одной из начальных точек отрезка.

d)      Площадь треугольника со сторонами a, b, c по формуле Герона , где p – полупериметр треугольника.

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

 SD = |[a × b]| / 2 = |(x1· Y2 - x2·Y1)| / 2.

Площадь произвольного многоугольника

f)       Площадь произвольного многоугольника вычисляется как сумма ориентированных площадей треугольников, у которых одна вершина – начало координат, а две другие – пары вершин многоугольника (последовсторон).

, где Si<> – площадь i<ника, $n$ – количество вершин многоугольника. Площади треугольников в следующим формулам:

Si = (Xi · yi+1 – Xi+1· yi)/2, i = 1, 2, …, $n$-1;

SN = (xN · Y1 – x1· yN)/2.

Параллельность, перпендикулярность, пересечение

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

Определение того, пересекаюте, заданные уравнениями
<sub>x + B1y + C1 = 0 и A2 + B 2y> = 0, сводится к следующему:

сляется определитель второго порядка Δ = A1 B2 – A B1;
  • проверяется, равен ли он нулю;
  • делается вывод о параллельности прямых
  • если не равен, то ресекаются;
  • координаты точки пересечения прямых находятся по следующим формулам Крамера:
    x = -Δx/Δ и у = -Δу/Δ, где Δx = c1 B2 – C2 B1, Δу  = A1 C2 – A2 c1;
  • если A2 = B1 и B2 = - A1, то прямые перпендикулярны.

    • Рис. 6

    Взаимное расположение двух отрезков можно проверить с помощью четырех векторных произведений (рис. 6).

    V1 = (x3  -  x1)(y4 – y1) – (x4 – x1)(y3 – y1)

    V2 = (x3  -  x2)(y4 – y2) – (x4 – x2)(y3 – y2)

    V3 = (x1  -  x3)(y2 – y3) – (x2 – x3)(y1 – y3)

    V4 = (x1  -  x4)(y2 – y4) – (x2 – x4)(y1 – y4)

    Отрезки пересекаются, если одновременно выполняются два условия: V1V2<0 (векторные произведения V1 и V2 разных знаков), V3V4<0 (векторные произведения V3V4 разных знаков). Если V1V2>0 или Vspan >V4>0, то отрезки не пересекаются.

    Дополнительные проверки используются, если точка пересечения лежит на одном из отрезков.

    снаружи

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

    Для выпуклого N-угольника существует несколько способов определения принадлежности точки многоугоle='margin: 0cm -.25pt 0cm 36.0pt;text-indent: -18.0pt'>1)sp;     Вычислить сумму площадей треугольников, образованных смежными сторонами многоугольника и заданной точкой, используя формь с площадью многоугольника, вычисленной по векторному произведени1. Если площади равны (или отличаются не более чем на заданную малую величину), то точка внутри многоугольника.

    2)      Пров и данная точка лежат в одной полуплоскости от каждой стороны N-угольника, то точка внутренняя. В уравнение прямой через каждые две соседние вершины xi,yi и Xi+1,yi+1, подставляем координаты данной точки X,Y и по очереди координаты всех остальных вершин. Другими словами, необходимо, чтобы полученные значения функции F(xi,yi,Xi+1,yi+1,X,y) = (Xi+1-Xi)(y-Yi)-(X-Xi)(yi+1-Yi) при разных xi, yi, Xi+1, yi+1 (i = 1, …, N-1)  были однога внутри многоугольника.

    3)      Составить N векторнын вектор — сторона многоугольника, а второй вектор — из точки до одной из вершин на стороне) и проверить, все ли они одного знака (если одного, то точка внутри).

    Для про N-угольника все эти способы работают не всегда. Необходимо щие способы:

    4) nbsp; Проверить, чему равна сумма углов вокруг исследуемой точки, тоов, под которыми видна каждая сторона многоугольника из искомой точки. Причем уо знаком, соответствующим последовательному обходу сторон многоугольника. Знак угла определяется векторным произведеторов от заданной точки до вершин многоугольника, определяющих сторону. еляется по формуле арккосинуса для найденного из скалярного произведения косину внутренняя, то сумма углов по модулю — 2p (больше либо меньше π).

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

    4.3. Построение выпуклой оболочки

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

    Идея алгоритма Джарвиса построения выпуклой оболочки (его называют еще алгоритмом «заворачивания подарка») заключается в следующем:

    1.      Ищется точка с минимальной координатой по оси OX. От нее задается первоначальное вертикальное направление.

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

    3.     Найденная точка принимается за исходную, новый построенный вектор задает исходное направление и из оставшихся N-2 точек ищется следующая точка.

    4.      Процесс продолжается до первоначальной выбранной точки.

     

    Идея алгоритма Грэхема построения выпуклой оболочки  заключается в следующем:

    1.      Найти левую верхнюю точку. Запомнить ее.

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

    3.      По очереди перебирая все отсортированные точки, исключать те, которые будут содержаться внутри выпуклой оболочки. Оставшиеся при таком отборе точки и  составят выпуклую оболочку.

    4.4. Задачи с использованием геометрических понятий

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

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

    4.4.1. Примеры решений

    Задача 1. Мэрия решила выделить деньги на постройку кольцевой автодороги вокруг города. Координаты всех домов в городе заданы парой целых чисел на плоскости.

    Уровень 1. Описать алгоритм построения дороги минимальной длины в виде отрезков, соединяющих точки-дома, вдоль которых должна пройти дорога при условии, что внутри дороги окажутся все остальные дома города.

     

    Можно использовать алгоритм Джарвиса построения выпуклой оболочки:

    1.      Найти точку с минимальной координатой по оси OX. Запомнить ее.

    2.     Построить вектор, задающий первоначальное вертикальное направление (за начало вектора можно взять найденную точку).

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

    4.     Найденную точку принять за исходную, новый построенный вектор принять за исходное направление и из оставшихся N-2 точек искать следующую точку по принципу, изложенному в предыдущем пункте.

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

    Уровень 2. Написать программу, которая выводит в файл координаты домов, вдоль которых должна пройти кольцевая автодорога.

    Формат ввода:

    Количество домов N (3<N<50000)

    Координаты 1-го дома X1 Y1 (2 числа через пробел)

    …

    Координаты N-го дома XN YN (2 числа через пробел)

    Формат вывода:

    Координаты 1-го дома X1 Y1 (2 числа через пробел)

    …

    Координаты K-го дома XK YK (2 числа через пробел)

    Пример:

    Входные данные:                      Выходные данные:             

    5                                                  1 1

    1 1                                               2 3

    2 3                                               4 4

    3 2                                               4 1

    4 4

    4 1

    style='text-decoration:none'> 

    Программа 1.1 (на языке QBasic):

    OPEN “INPUT.TXT” FOR INPUT AS #1

    TXT” FOR OUTPUT AS #2

    INPUT #1, n

    DIM x(1 TO n), y(1 TO n)                      ' координаты n точек

    FOR i = 1 TO n<style='margin: 0cm 1.0cm 0cm 20.7pt;text-indent:20pt'>INPUT #1, x(i), y(i)

    right:1.0cm;text-indent: 19.85pt'>NEXT

    ' n1- номер наx1,y1- координаты найденной точки

    x1 = x(i1 = 1: n1 = 1

    PRINT #2, x1, y1

    FOR i = 2 TO n

    m;text-indent: 19.85pt'>NEXT

    X0 = X1: y0 = Y1 – 1                                ' взяли  вспомогательную точку (x0, y0)

    k = 0

    DO

    mcos =        ‘ число, необходимое для поиска максимального cos,

    ‘ т.е. минимального угла

    X10 = X1 - X0: Y10 = Y1 - Y0                        ' строим вектор а

    a = SQR(X10 ^ 2 + Y10 ^ 2)            ' находим |a|

    FOR i = 1 TO n

    IF i <> i1 THEN

    xi1 = x(i) - x1: yi1 = y(i) - y1                ' вектор b

    1 ^ 2 + yi1 ^ 2)                   ' |b|

    cosa = (X10 * xi1 + Y10an>1) / (a * b)        ' cos угла из скалярного

    ‘ произведения

    IF cosa > mcos THEN mcos = cosa: nomi = i

    END IF

    NEXT i

    k = k + 1

    IF nomi = n1 THEN END

    x0 = x1: y0 = y1                           ' за вектор а берем b

    x1 = x(nomi): y1 = y(nomi)

    PRINT #2, x1, y1

    0cm 1.0cm 0cm 20.7pt;text-indent:20pt'>i1 = nomi

    LOOP UNTIL k > n – 1

    6.0pt;text-indent:20pt'> 

    Уровень 3. Смоделировать ора решение задачи,  изобразив каждый из домов в виде точки или одиуса. Изобразить построение кольцевой автодороги минимальной длины в виде замкнутой ломаной. Возможно использование для задания экранных координат точек датчика случайных чисел. Исследовать пря выпуклой оболочки при малом и большом количестве точек. Сравнить  процесс построения двумя разными алгоритмами (Джарвма).

    Программа 1.3 (на языке pan>):

    SCREEN                         ‘программа с графическим оформлением

    INPUT "Количество точек - ", n

    .0cm;text-indent: 19.85pt'>RANDOMIZE TIMER

    DIM x(1 TO n), y(1 TO n)                                

    FOR i = 1 TO n

    >y(i) = INT(RND * 300 + 20)

    CIRCLE (x(i), y(i)), 3

    NEXT

    IF n = 1 THEN END

    x1 = x(1): y1 = y(1): i1 = 1: n1 = 1

    FOR i = 2 TO n

    IF x(i) < x1 THEN x1 = x(i): y1 = y(i): i1 = i: n1 = i

    NEXT

    x0 = x1: y0 = y1 – 1                               

    k = 0

    DO

    mcos = -2              

    x10 = x1 - x0: y10 = y1 - y0                       

    a = SQR(x10 ^ 2 + y10 ^ 2)           

    FOR i = 1 TO n

    IF i <> i1 THEN

    >b = SQR(xi1 ^ 2 + yi1 ^ 2)      

    cosa = (x10 * xi1 + y10 * yi1) / (a * b)       

    IF cosa > mcos THEN mcos = cosa: nomi = i

    END IF

    LINE (x1, y1)-(x(nomi), y(nomi))

    k = k + 1

    IF nomi = n1 THEN END

    x0 = x1: y0 = y1                                          tyle='margin: 0cm 1.0cm 0cm 20.7pt;text-indent:20pt'>x1 = x(nomi): y1 = y(nomi)rgin: 0cm 1.0cm 0cm 20.7pt;text-indent:20pt'>i1 = nomi

    UNTIL k > n – 1

     

    pt'>Задача 2. «Штраф за левые повороты». Новый градоначальник городас целью пополнения бюджета и экономии горючего провести кампанию борьбы с “левым” уклоном. Дретил водителям выполнять левые повороты, установив за каждый поворот налево штраф в 1 млн. рублей (прейскурант тяжелого прошлого Глупову достались улицы, которые могут пересекаться под любыми углами. Градоначальник приказал установить компьютерную систему слежки за автомобилями, которая фиксирует координаты каждого автомобиля в начале движеижения и во время поворота.

    Уровень 1. Описаисления штрафа водителю автомобиля, если задана последовательность координат движмобиля.

    Поворот считается левым, если направление текущего отрезка траект>a2 относительно направления предыдущего отрезка a1 меняется по нав левую сторону (поворот против часовой стрелки). А это означает, что векторное проиов [a1 × a2] авилу «буравчика»).

    1.    Из координат первых трех точек в заданной последовательности определить два вектора ng> и a2.

          Составить их векторное произведение.

    3.      Если  [a1 × a2] > 0, то увеличить счетчик для подсчета левых поворотов на 1.

    4.      Переопределить данные, взяв за  вектор a1 вектор a2.

    5.      Определить вектор a2, взяв координаты следующей точки в последовательности.

    6.      Повторить процесс с пункта 2.

    7.      После перебора всех точек значение счетчика будет содержать ответ задачи.

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

    Формат ввода:

    Координаты начала движения X0 Y0 (2 числа через пробел)

    Координаты первого поворота X1 Y1 (2 числа через пробел)

    …

    Координаты N-го поворота XN YN (2 числа через пробел)

    Координаты конца движения X N+1 YN+1 (2 числа через пробел)

    Формат вывода:

    Величина штрафа

    Пример:

    Входные данные:                 Выходные данные:             

    -2 -1                                        2 млн. руб.

    2 0

    -2 2

    2 2

    2 3

    Рис. 7

    Программа 2.1 (на языке QBasic):

     

    OPEN “INPUT.TXT” FOR INPUT AS #1

    OPEN “OUTPUT.TXT” FOR OUTPUT AS #2

    DIM x(1 TO 1000), y(1 TO 1000)

    n = 0

    DO WHILE NOT (EOF(1))

    n = n+1

    INPUT #1, x(i), y(i)

    LOOP

    a1 = x(1): b1 = y(1)

    a2 = x(2): b2 = y(2)

    a3 = x(i): b3 = y(i)

    IF (a2 - a1) * (b3 - b2) - (b2 - b1) * (a3 - a2) > 0 THEN s = s + 1

    a1 = a2: b1 = b2

    a2 = a3: b2 = b3

    NEXT i

    PRINT #2, s; " млн. руб."

     

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

    На рисунке 7 показан пример иллюстрации к вышеуказанным входным данным - получается 2 левых поворота.

    Примечаниеформлении к задаче графического сопровождения не забывать, что экранная систвляется неправильной (левой), поэтому проверка векторноения на знак должна измениться, то есть значение должно быть < 0.

    n style='text-decoration:none'> 

    <ма 2.2 (на языке QBasic):

    > 9

    INPUT "N=", n

    1 TO n), y(1 TO n)

    FOR i = 1 TO n<  PRINT i; ": x,y "; : INPUT "", x(i), y(i)<NEXT i

    minx = x(1): miny = y(1): maxx = x(1/span>

    nminx = 1: nminy = 1: y = 1

    FOR i = 1 TO n

       IF x(EN

          minx = x(i): nminx = i

       ELSE

         IF maxx < = x(i): nmaxx = i

       END IF

    lt; miny THEN

          miny = y(i): nminy = ipan>   ELSE IF maxy < y(i) THEN maxy = y(i): nmaxy = i

    NEXT i

    VIEW (200, 100)-(620, 330), 3, 7

    dx = (maxx - minx) / 10

    dy = (maxy - miny) / 10

    WINDOW (minx - dx, miny - dy)-(maxx + dx, maxy + dy)

       CIRCLE (x(1), y(1)), (dx + dy) / 20, 0

       PAINT (x(1), y(1)), 4, 0

    FOR i = 2 TO n

       CIRCLE (x(i), y(i)), (dx + dy) / 30, 0

       PAINT (x(i), y(i)), 0, 0

    NEXT

    s = 0

     a1 = x(1): b1 = y(1)

     a2 = x(2): b2 = y(2)

    LINE (a1, b1)-(a2, b2)

    FOR i = 3 TO n

    a3 = x(i): b3 = y(i)

    LINE (a3, b3)-(a2, b2)

     IF (a2 - a1) * (b3 - b2) - (b2 - b1) * (a3 - a2) > 0 THEN s = s + 1

      a1 = a2: b1 = b2

      a2 = a3: b2 = b3

     NEXT i

     LOCATE 23

     PRINT "Штраф: "; s; " млн."

     

    Задача 3. Произвольный N-угольник задан декартовыми координатами своих вершин на плоскости и на этой же плоскости дана произвольная точка.

    Уровень 1. Описать алгоритм, который определи точка внутрь многоугольника.

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

    2.      Из формулы скалярного произведения определить косинус угла, образованного векторами.

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

    4.      Повторить процесс со 2-го пункта для каждой пары вершин других сторон многоугольника.

    5.      Полученную величину суммарного угла сравнить с нулем и 2π.

    6.      Если угол равен нулю, то точка находится снаружи, а если – 2π, то внутри.

    Уровень 2. Написать программу, которая определяет, попадает ли точка внутрь N- угольника.

    Формат ввода:

    Количество вершин многоугольника (число N)

    Координаты первой вершины X1 Y1 (2 числа через пробел)

    …

    Координаты N-й вершины XN YN (2 числа через пробел)

    Координаты точки Xa Ya (2 числа через пробел)

    Формат вывода:

    Слово «IN» (если точка внутри) или слово «OUT» (если точка снаружи)

    Пример:

    Рис. 8

    Входные данные:                      Выходные данные:

    5                                                  OUT

    -2 0

    0 2

    0 0

    2 0

    0 -3

    1 1

     

    Программа 3.1 (на языке QBasic):

    DECLARE FUNCTION acos! (X!)

    PRINT "          CОДЕРЖИТСЯ ЛИ ТОЧКА ВНУТРИ N-УГОЛЬНИКА"

    INPUT "N=", n

    DIM x(1 TO n), y(1 TO n)

    PRINT "Введите координаты вершин многоугольника"

    PRINT i; ": x,y "; : INPUT "", x(i), y(i)

    NEXT i

    '>INPUT "Введите координаты точки ", ax, ay

    s = 0                                                                 ' Суммарный угол

    FOR i = 1 TO n - 1

    a1 = x(i) - ax: b1 = y(i) - ay

    a2 = x(i + 1) - ax: b2 = y(i + 1) - ay

    u1 = a1 * b2 - b1 * a2                                                  'Векторное произведение

    u2 = SQR(a1 ^ 2 + b1 ^ 2 + b2 ^ 2)   'Произведение модулей

    u3 = a1 * a2 + b1 * b2                                  'Скалярное произведение'text-indent:1.0cm'>IF u2 <> 0 THEN ugol

    IF u1= s + ugol ELSE s = s - ugol

    a1 = x(n) - aay                              'Последняя сторона мног

    a2 = x(1) - ax: b2 = y(1) - ay

    u1 = a1 * b2 - b1 * ap style='text-indent:20pt'>u2 = SQR(a1 ^ 2 + b1 ^ 2) * SQR(a2 ^ 2n>

    u3 = a1 * a2 + b1 * b2

    IF u2 <> 0 THEN ugol = acos(u3 / u2)

    IF u1 > 0 THEN s = s + ugol ELSE s = s - ugol

    IF ABS(s) > 3.14 THEN PRINT "IN" ELSE PRINT "OUT"

    FUNCTION acos (x)

    ' Функция арккосинуса

    pi = 3.1415926#

    IF ABS(x) >= .9999 THEN acos = 0 ELSE acos = pi / 2 - ATN(x / SQR(1! - x * x))

    END FUNCTION

     

    Программа 3.2 (на языке Pascal):

    Type mas=array[1..100] of real;

    Var

      i,n:Byte;

      xp,yp:Real;

      Angle,a,b,s:Real;

      x,y: mas;

    Function Len(x1,y1,x2,y2:Real):Real;

    Begin

      Len:=Sqrt(Sqr(x2-x1)+Sqr(y2-y1));

    End;

    Function Vector(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2:Real):Real;

    Begin

      Vector:=(Ax2-Ax1)*(By2-By1)-(Bx2-Bx1)*(Ay2-Ay1);

    End;

    Function Scalar(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2:Real):Real;

    Begin

      Scalar:=(Ax2-Ax1)*(Bx2-Bx1)+(Ay2-Ay1)*(By2-By1);

    End;

    Function ArcCos(x:Real):Real;

    Begin

      If Abs(x)>=0.9999 Then ArcCos:=0 Else ArcCos:=Pi/2-ArcTan(x/Sqrt(1-Sqr(x)));

    End;

    Begin

      Writeln('Введите N ');

      Readln(n);

        For i:=1 To n Do

        Begin

          Write('Введите x, y c #',i, ' ');

          Readln(x[>

        End;

    pt'>  Write('Введите xp, yp ');

      Readln(xp, yp);

      Angle:=0;

        x[n+1]:=x[1]; y[n+1]:=y[1];

        For i:=1 To n Do

        Begin

          a:=Len(x[ i ],y[ i ],xp,yp);

          b:=Len(x[i+1],y[i+1],xp,yp);

          If (a<>0) And (b<>0) Then

          Begin

            s:=Scalar(xp,yp,x[i],y[i],xp,yp,x[i+1],y[i+1]);

            If Vector(xp,yp,x[i],y[i],xp,yp,x[i+1],y[i+1])>0 Then

              Angle:=Angle-ArcCos(s/(a*b))

            Else

              Angle:=Angle+ArcCos(s/(a*b));

          End;

        End;

      If Abs(Angle)>Pi Then Writeln('IN') Else Writeln('OUT');

      Readln;

    End.

    На рисунке 8 показан пример иллюстрации к вышеуказанным входным данным – в данном случае точка находится снаружи. Если, например, задать и
    (-1; -1), то программа должна определить, что эта точка находится внутри.

    4.4.2. Задачи для самостоятельного решения.

    Задача 4. (Областная олимпиада, 1995).

    top:6.0pt;text-indent:20pt'>Уровень 2. Написать программу, которая определяет выпуклый многоугольник с вершинами, принадлежащими множеству точек с координатами (xi , yi i = 1, 2, ..., n. Данный многоугольник содержит все точки указанного множества.

    Указание. Эта задача аналогична задаче 1. Отличием является лишь то, что из множества вершин построенного выпуклого многоугольника необходимо исключить «лишние» точки, то есть те, которые лежат на сторонах многоугольника.

    Формат ввода:

    Количество точек (число N)

    Координаты первой точки X1 Y1 (2 числа через пробел)

    …

    Координаты N-й точки XN YN (2 числа через пробел)

    Формат вывода:

    Координаты первой вершины многоугольника X1 Y1 (2 числа через пробел)

    …

    Координаты K-й вершины многоугольника XK YK (2 числа через пробел)

    Задача 5. «Бассейн». (Районная олимпиада,  2000). Емкость для декоративного бассейна по предложению архитектора было решено выполнить в виде произвольной N-угольной призмы. Для того чтобы определить количество машин с грузоподъемностью G для вывоза земли, необходимо вычислить объем строящегося бассейна.

    Уровень 2. Напишите программу, вычисляющую объем бассейна, если известна его высота H, а многоугольник в основании призмы задается Х, Y координатами своих вершин.

    Формат ввода:

    Высота бассейна H и грузоподъемность машины G (два числа через пробел)

    Координаты первой вершины X1 Y1 (2 числа через пробел)

    …

    Координаты N-й вершины XN YN (2 числа через пробел)

    Формат вывода:

    Вещественное число с 3 знаками после запятой (объем бассейна)

    Целое число (количество машин)

    Задача 6. (Областная олимпиада, 1997). Четыре населенных пункD задаются декартовыми координатами на плоскости. Известно, что между пунктами прокладывают автотрассу.

    Уровень 2. Определить, возникает ли необходимость в установлении светофора на перекреветствующую программу.

    Указание: Задача на определение пересечения двух прямых или дву

    Формат вводаle='text-indent:20pt'>Координаты X1 Y1 пункта А (2 числа через пробел)

    Координаты X2 Y2 пункта b (2 числа через пробел)

    Координаты X3 Y3 пункта C (2 числа через пробел)

    Координаты X4 Y4 пункта D (2 числа через пробел)

    Формат вывода:

    Слово «YES», если возникает необходимость в светофоре, слово «NO», если нет.

    Задача 7. (Районная олимпиада, 1997). На декартовой плоскости задано N точек и M отрезков (отрезки между собой не пересекаются, параллельны оси ординат, и ни одна из множества N точек не лежит на отрезках).

    Уровень 2. Соединить точки ломаной, не пересекающей отрезки во внутренних точках. Очески одно из возможных решений. Числа N, M, а также координаты точек и координаты концов отрезков вводятся с клавиатуры.

     Формат ввода:

    N и M (2 числа через пробел)

    Координаты X1 Y1 первой точки (2 числа через пробел)

    …

    Координаты XN YN N-й точки (2 числа через пробел)

    Координаты XN+1 YN+1 начала первого отрезка (2 числа через пробел)

    Координаты XN+2 YN+2 конца первого отрезка (2 числа через пробел)

    …

    Координаты XN+2M-1 YN+2M-1 начала M-го отрезка (2 числа через пробел)

    Координаты>XN+2M YN+2ub> конца M-го отрезка (2 числа через пробел)

    Формат вывода:

    Рисунок на экране монитора

    Уровень 3. Исследовать все возможные решения данной задачи. Определить длину кратчайшей ломаной.

    Задача 8. (Областная олимпиада, 2001).

    Уровень 2. Определить центр окружности минимального радиуса, содержащей все заданные точки на плоскости.

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

    Формат ввода:

    Nточек)

    Координаты X1 Y1 точки (2 числа через пробел)

    …

    Формат вывода:

    X Y R (координаты центра и радиус окружности через пробел)

     

     

    Используемая литература

    1. Препарата Ф. , Шеймос М. Вычислительная геометрия. Введение. - М.: Мир. – 1989.
    2. С.М. Окулов. Геометрические алгоритмы. / Статья в газете  «Информатика» (Приложение к 1 сентября), №№ 15, 16, 17, 2000.
    3. Есипов А.С., Паньгина Н.Н., Громада М.И. Информатика. Сборник задач и решений для общеобразовательных учебных заведений. – Санкт-Петербург: Наука и Техника, 2001.
    4. Е.В. Андреева, Ю.Е. Егоров. Вычислительная геометрия на плоскости. / Статья в газете  «Информатика» (Приложение к 1 сентября), №№ 39, 40, 43, 44, 2002.