Решение олимпиадных задач по информатике – городская олимпиада

Решение олимпиадных задач по информатике – городская олимпиада

http://pas1.ru/pascaltask

1.

Решение

1) Сначала ищем длинну отрезка от начала координат к точке (x,y).
Вот формула D=((Xo-X)^2 + (Yo-y)^2)^0.5;
(Можно и так D=((X-Xо)^2 + (Y-Yо)^2)^0.5 результат будет тот же)
Где (Xo,Yo) координати начала координат.
(X,Y) координати точки.
2) Дальше проверяем если r<=D<=R то тогда точка принадлежит кольцу, в противном случае не принадлежит!

 

 

Решение 2

https://ru.vingrad.com/Prinadlezhit-li-tochka-(xy)-krugovomu-koltsu-id50b9e0506ccc198014025120

Вот есть точка начала координат - (x0, y0). Может она у Вас будет (0, 0), но для общности не буду так делать. Надо выяснить расстояние от точки (x, y) до (x0, y0). Получаем:
d = Sqrt(Sqr(x - x0) + Sqr(y - y0));
Sqrt - это корень квадратный, а Sqr - это возведение в квадрат. Соответственно все что осталось - проверить, чтобы (d >= r) and (d <= R).

 

 

Program tochka;

uses crt;

var x0,y0,x,y,d,R,r:real;

BEGIN

clrscr;

Writeln('Попадет ли точка в кольцо');

Wriite('Введите координаты точки: ');

Read(x,y);

x0:=0;

y0:=0;

R:={Здесь задать внешний радиус};

r:={Здесь задать внутренний радиус};

d = Sqrt(Sqr(x - x0) + Sqr(y - y0));

if (d>=r) and (d<=R) then

begin

Write('Заданная точка попадает в кольцо');

end

else

begin

Write('Заданная точка не попадает в кольцо');

end;

writeln;

Write('Нажмите любую клавишу');

END.

 

Решение 3

http://pas1.ru/circle-radius

Описание переменных:

• x, y, r - координаты точки и радиус круга;

• r_xy - длина гипотенузы (расстояния от начала координат до точки).

Алгоритм решения задачи:

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

Длина гипотенузы находится по теореме Пифагора.

Программа на языке Паскаль:

Var

x, y, r: real;

r_xy: real;

 

Begin

write('x = '); readln(x);

write('y = '); readln(y);

write('R = '); readln(r);

 

r_xy:= sqrt(x*x + y*y);

 

if r_xy <= r then

writeln('The point belongs to the circle.')

Else

writeln('The point does not belong to the circle.');

end.

Пример работы программы:

x = -1

y = 3

R = 1

The point does not belong to the circle

Решение 3.

http://taskcode.ru/if/circle-point

Пояснение к задаче и алгоритм решения

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

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

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

Таким образом задача сводится по-сути к двум действия:

• Нахождение длины отрезка между точкой и началом координат по теореме Пифагора (квадрат длины гипотенузы равен сумме квадратов длин катетов).

• Сравнению полученного значения с радиусом круга.

Исходный код на языке программирования Pascal

var x,y,r,h: real;
begin
write('координаты точки: ');
readln(x,y);
write('радиус круга: ');
readln(r);
h:= sqrt(x*x + y*y);
if h > r then writeln('Точка не принадлежит кругу')
else writeln('Точка принадлежит кругу');
end.

Пример(ы) выполнения программы на языке Pascal

координаты точки: -1 -2
радиус круга: 5
Точка принадлежит кругу

Исходный код на языке программирования C

#include <stdio.h>
#include <math.h>
main() {
float x,y,r,h;
printf("Координаты точки: ");
scanf("%f%f", &x,&y);
printf("Радиус круга: ");
scanf("%f", &r);
h = sqrt(x*x + y*y);
printf("Гипотенуза равна %.2f. ", h);
if (h > r) printf("Точка не принадлежит кругу. \n ");
else printf("Точка принадлежит кругу. \n ");
}

Пример(ы) выполнения программы на языке C

Координаты точки: 4 5
Радиус круга: 10
Гипотенуза равна 6.40. Точка принадлежит кругу.

Особенности решения на языке программирования C

Для gcc компилировать с ключом -lm.

Пример(ы) выполнения программы на языке Python

x=10
y=-3
r=5
Расстояние до точки от начала координат равно 10.44
точка находится за пределами круга

Пример(ы) выполнения программы на языке КуМир

Координаты точки: 1.6 -2.1
Радиус круга: 4
Принадлежит

Примечание 1.

Содержание

• 1HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Метод трассировки луча

• 1.1HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Учёт числа пересечений

• 1.2HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Учёт числа оборотов

• 2HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Метод суммирования углов

• 3HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Алгоритмы c предобработкой

• 3.1HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Выпуклые и звёздные многоугольники

• 3.2HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Произвольный многоугольник

• 4HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Примечания

• 5HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Литература

• 6HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Ссылки

Метод трассировки луча

Учёт числа пересечений

Методы работают по-разному для многоугольников с самопересекающейся границей. Слева: even-odd rule. Справа: nonzero winding rule.

Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithm или even-odd rule.

В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[1] Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.

Алгоритм работает за время O(N) для N -угольника.

Учёт числа оборотов

Кривая делает два оборота вокруг данной точки.

Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки P. В алгебраической топологии это число называется 0%9F%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D0%BA%D1%80%D0%B8%D0%B2%D0%BE%D0%B9"индексом точки относительно кривой.0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[2] Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из P в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[3] Сумма полученных величин и есть 0%9F%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D0%BA%D1%80%D0%B8%D0%B2%D0%BE%D0%B9"индекс точки относительно кривой. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.

Такой алгоритм известен под названием nonzero winding rule. 0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[3]

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

Метод суммирования углов

Можно определить, что точка P находится внутри многоугольника c вершинами V ₀, V ₁,..., V_n = V ₀, вычислив сумму:

,

где — угол (в радианах и со знаком) между лучами PV_{i - 1} и PV_i, т.е.:

 

Можно доказать, что эта сумма есть не что иное, как winding number точки P относительно границы многоугольника, с точностью до константного множителя. Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней), и был даже назван «худшим в мире алгоритмом» для данной задачи.0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[1]

К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[4] Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки P. Алгоритм Вейлера и некоторые улучшения к нему описываются в 0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[5].

Алгоритмы c предобработкой

Произвольный многоугольник

Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки в планарном подразбиении. Для N -угольника эта задача может быть решена за время O(log² N) с использованием O(N) памяти и O(N log N) времени на предобработку.0^%97%D0^%B0^%D0^%B4^%D0^%B0^%D1^%87%D0^%B0^_%D0^%BE_%D0^%BF%D1^%80%D0^%B8^%D0^%BD%D0^%B0^%D0^%B4^%D0^%BB%D0^%B5^%D0^%B6^%D0^%BD%D0^%BE%D1^%81%D1^%82%D0^%B8^_%D1^%82%D0^%BE%D1^%87%D0^%BA%D0^%B8^_%D0^%BC%D0^%BD%D0^%BE%D0^%B3^%D0^%BE%D1^%83%D0^%B3^%D0^%BE%D0^%BB%D1^%8^C%D0^%BD%D0^%B8^%D0^%BA%D1^%83"[7]

Примечание 3.

https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"%HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"%B8%D0%BA%D1%83

Содержание

• 1HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Описание

• 2HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"ОHYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"чень быстрый алгоритм

• 3HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Perl

• 4HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Delphi (Object Pascal)

• 5HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"JavaScript

• 6HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Python 3

• 7HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин

Описание

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

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

• указатель на массив пар целочисленных координат вершин многоугольника, а именно, на массив структур вида

struct Point {

int x;

int y;

};

 

• число вершин многоугольника;

• целочисленное значение координаты X заданной точки;

• целочисленное значение координаты Y заданной точки.

Функция возвращает 1, если точка принадлежит многоугольнику, иначе — 0.

Функция имеет следующий вид.

int IsPointInsidePolygon (Point *p, int Number, int x, int y)

{

int i1, i2, n, N, S, S1, S2, S3, flag;

N = Number;

for (n=0; n<N; n++)

{

flag = 0;

i1 = n < N-1? n + 1: 0;

while (flag == 0)

{

i2 = i1 + 1;

if (i2 >= N)

i2 = 0;

if (i2 == (n < N-1? n + 1: 0))

break;

S = abs (p[i1].x * (p[i2].y - p[n ].y) +

p[i2].x * (p[n ].y - p[i1].y) +

p[n].x * (p[i1].y - p[i2].y));

S1 = abs (p[i1].x * (p[i2].y - y) +

p[i2].x * (y - p[i1].y) +

x * (p[i1].y - p[i2].y));

S2 = abs (p[n ].x * (p[i2].y - y) +

p[i2].x * (y - p[n ].y) +

x * (p[n ].y - p[i2].y));

S3 = abs (p[i1].x * (p[n ].y - y) +

p[n ].x * (y - p[i1].y) +

x * (p[i1].y - p[n ].y));

if (S == S1 + S2 + S3)

{

flag = 1;

break;

}

i1 = i1 + 1;

if (i1 >= N)

i1 = 0;

}

if (flag == 0)

break;

}

return flag;

}

Очень быстрый алгоритм

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

int pnpoly(int npol, float * xp, float * yp, float x, float y)

{

int c = 0;

for (int i = 0, j = npol - 1; i < npol; j = i++)

{

if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&

(x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))

c =!c;

}

return c;

}

Замечание: Так как умножение быстрее деления, условие можно записать так:

int pnpoly(int npol, float * xp, float * yp, float x, float y)

{

int c = 0;

for (int i = 0, j = npol - 1; i < npol; j = i++)

{

if ((

(yp[i]<yp[j]) && (yp[i]<=y) && (y<=yp[j]) &&

((yp[j] - yp[i]) * (x - xp[i]) > (xp[j] - xp[i]) * (y - yp[i]))

) || (

(yp[i]>yp[j]) && (yp[j]<=y) && (y<=yp[i]) &&

((yp[j] - yp[i]) * (x - xp[i]) < (xp[j] - xp[i]) * (y - yp[i]))

))

c =!c;

}

return c;

}

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

Perl

my $x = -40; my $y = -60; # Проверяемая точка

my @xp = (-73,-33,7,-33); # Массив X-координат полигона

my @yp = (-85,-126,-85,-45); # Массив Y-координат полигона

&InPoly(\@xp,\@yp,$x,$y);

sub InPoly()

{

my($xp, $yp, $x, $y) = @_;

my $npol = @{$xp};

my $j = $npol - 1;

my $c = 0;

for(my $i = 0; $i < $npol;$i++) {

if ((((@{$yp}[$i]<=$y) && ($y<@{$yp}[$j])) || ((@{$yp}[$j]<=$y) && ($y<@{$yp}[$i]))) &&

($x > (@{$xp}[$j] - @{$xp}[$i]) * ($y - @{$yp}[$i]) / (@{$yp}[$j] - @{$yp}[$i]) + @{$xp}[$i]))

{

$c =!$c

}

$j = $i;

}

return $c;

}

 

Delphi (Object Pascal)

type

tPolygon = array of tPoint; //tPoint - это запись, с полями двумя полями, x и y

...

function IsMouseInPoly(x,y: integer; myP: tPolygon): boolean; //x и y - это координаты мыши

var //myP - массив с вершинами полигона

i,j,npol: integer;

inPoly: boolean;

begin

npol:=length(myP)-1;

j:=npol;

inPoly:=false;

for i:=0 to npol do

begin

if ((((myP[i].y<y) and (y<myP[j].y)) or ((myP[j].y<=y) and (y<myP[i].y))) and

(x>(myP[j].x-myP[i].x)*(y-myP[i].y) / (myP[j].y-myP[i].y)+myP[i].x))

then inPoly:=not inPoly;

j:=i;

end;

result:=inPoly;

end;

 

JavaScript

var x = -40;

var y = -60;

var xp = new Array(-73,-33,7,-33); // Массив X-координат полигона

var yp = new Array(-85,-126,-85,-45); // Массив Y-координат полигона

function inPoly(x,y){

npol = xp.length;

j = npol - 1;

var c = 0;

for (i = 0; i < npol;i++){

if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&

(x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) {

c =!c

}

j = i;

}

return c;

}

inPoly(x,y);

Python 3

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

def inPolygon(x, y, xp, yp):

c=0

for i in range(len(xp)):

if (((yp[i]<=y and y<yp[i-1]) or (yp[i-1]<=y and y<yp[i])) and \

(x > (xp[i-1] - xp[i]) * (y - yp[i]) / (yp[i-1] - yp[i]) + xp[i])): c = 1 - c

return c

 

print(inPolygon(100, 0, (-100, 100, 100, -100), (100, 100, -100, -100)))

 

Растровая графика.

Векторная графика.

Введение

Данное электронное пособие содержит группу задач по теме «Кодирование графической информации». Сборник задач разбит на типы задач исходя из указанной темы. Каждый тип задач рассматривается с учетом дифференцированного подхода, т. е. рассматриваются задачи минимального уровня (оценка «3»), общего уровня (оценка «4»), продвинутого уровня (оценка «5»). Приведенные задачи взяты из различных учебников (список прилагается). Подробно рассмотрены решения всех задач, даны методические рекомендации для каждого типа задач, приведен краткий теоретический материал. Для удобства пользования пособие содержит ссылки на закладки.

Растровая графика.

Типы задач:

• Нахождение объема видеопамяти.

• Определение разрешающей способности экрана и установка графического режима.

• Кодировка цвета и изображения.

• Нахождение объема видеопамяти

Методические рекомендации:

В задачах такого типа используются понятия:

• объем видеопамяти,

• графический режим,

• глубина цвета,

• разрешающая способность экрана,

• палитра.

Во всех подобных задачах требуется найти ту или иную величину.

Видеопамять -это специальная оперативная память, в которой формируется графическое изображение. Иными словами для получения на экране монитора картинки её надо где-то хранить. Для этого и существует видеопамять. Чаще всего ее величина от 512 Кб до 4 Мб для самых лучших ПК при реализации 16,7 млн. цветов.

Объем видеопамяти рассчитывается по формуле: V=I*X*Y, где I – глубина цвета отдельной точки, X, Y – размеры экрана по горизонтали и по вертикали (произведение х на у – разрешающая способность экрана).

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

В графическом режиме экран разделяется на отдельные светящиеся точки, количество которых зависит от типа дисплея, например 640 по горизонтали и 480 по вертикали. Светящиеся точки на экране обычно называют пикселями, их цвет и яркость может меняться. Именно в графическом режиме появляются на экране компьютера все сложные графические изображения, создаваемыми специальными программами, которые управляют параметрами каждого пикселя экрана. Графические режимы характеризуются такими показателями как:

- разрешающая способность (количество точек, с помощью которых на экране воспроизводится изображение) - типичные в настоящее время уровни разрешения 800*600 точек или 1024*768 точек. Однако для мониторов с большой диагональю может использоваться разрешение 1152*864 точки.

- глубина цвета (количество бит, используемых для кодирования цвета точки), например, 8, 16, 24, 32 бита. Каждый цвет можно рассматривать как возможное состояние точки, Тогда количество цветов, отображаемых на экране монитора может быть вычислено по формуле K=2^I , где K – количество цветов, I – глубина цвета или битовая глубина.

Кроме перечисленных выше знаний учащийся должен иметь представление о палитре:

- палитра (количество цветов, которые используются для воспроизведения изображения), например 4 цвета, 16 цветов, 256 цветов, 256 оттенков серого цвета, 2¹⁶ цветов в режиме называемом High color или 2²⁴, 2³² цветов в режиме True color.

Учащийся должен знать также связи между единицами измерения информации, уметь переводить из мелких единиц в более крупные, Кбайты и Мбайты, пользоваться обычным калькулятором и Wise Calculator.

Уровень «3»

1. Определить требуемый объем видеопамяти для различных графических режимов экрана монитора, если известна глубина цвета на одну точку.(2.76 [3])

Режим экрана	Глубина цвета (бит на точку)
640 на 480
800 на 600
1024 на 768
1280 на 1024

Решение:

• Всего точек на экране (разрешающая способность): 640 * 480 = 307200
2. Необходимый объем видеопамяти V= 4 бит * 307200 = 1228800 бит = 153600 байт = 150 Кбайт.
3. Аналогично рассчитывается необходимый объем видеопамяти для других графических режимов. При расчетах учащийся пользуется калькулятором для экономии времени.

Ответ:

Режим экрана	Глубина цвета (бит на точку)
640 на 480	150 Кб	300 Кб	600 Кб	900 Кб	1,2 Мб
800 на 600	234 Кб	469 Кб	938 Кб	1,4 Мб	1,8 Мб
1024 на 768	384 Кб	768 Кб	1,5 Мб	2,25 Мб	3 Мб
1280 на 1024	640 Кб	1,25 Мб	2,5 Мб	3,75 Мб	5 Мб

2. Черно-белое (без градаций серого) растровое графическое изображение имеет размер 10 ´10 точек. Какой объем памяти займет это изображение?(2.68 [3])

Решение:

• Количество точек -100

• Так как всего 2 цвета черный и белый. то глубина цвета равна 1 (2¹ =2)

• Объем видеопамяти равен 100*1=100 бит

Аналогично решается задаа 2.69[3]

3. Для хранения растрового изображения размером 128 x 128 пикселей отвели 4 КБ памяти. Каково максимально возможное число цветов в палитре изображения. (ЕГЭ_2005, демо, уровень А). (См. также задачу 2.73 [3])

Решение:

• Определим количество точек изображения. 128*128=16384 точек или пикселей.

• Объем памяти на изображение 4 Кб выразим в битах, так как V=I*X*Y вычисляется в битах. 4 Кб=4*1024=4 096 байт = 4096*8 бит =32768 бит

• Найдем глубину цвета I =V/(X*Y)=32768:16384=2

• N=2^I , где N – число цветов в палитре. N=4

Ответ: 4

4. Сколько бит видеопамяти занимает информация об одном пикселе на ч/б экране (без полутонов)?([6],C. 143, пример 1)

Решение:

Если изображение Ч/Б без полутонов, то используется всего два цвета –черный и белый, т.е. К=2, 2ⁱ =2, I= 1 бит на пиксель.

Ответ: 1 пиксель

5. Какой объем видеопамяти необходим для хранения четырех страниц изображения, если битовая глубина равна 24, а разрешающая способность дисплея- 800 х 600 пикселей? ([6], №63)

Решение:

• Найдем объем видеопамяти для одной страницы: 800*600*24=11520000 бит =1440000 байт =1406,25 Кб ≈1, 37 Мб

• 1,37*4 =5,48 Мб ≈5.5 Мб для хранения 4 страниц.

Ответ: 5.5 Мб

Уровень «4»

6.Определить объем видеопамяти компьютера, который необходим для реализации графического режима монитора High Color с разрешающей способностью 1024 х 768 точек и палитрой цветов из 65536 цветов. (2.48 [3])

Методические рекомендации:

Если ученик помнит, что режим High Color – это 16 бит на точку, то объем памяти можно найти, определив число точек на экране и умножив на глубину цвета, т.е. 16. Иначе ученик может рассуждать так:

Решение:

1. По формуле K=2^I , где K – количество цветов, I – глубина цвета определим глубину цвета. 2^I =65536

Глубина цвета составляет: I = log₂65 536 = 16 бит (вычисляем с помощью программы Wise Calculator)

2..Количество точек изображения равно: 1024´768 = 786 432

3. Требуемый объем видеопамяти равен: 16 бит ´ 786 432 = 12 582 912 бит = 1572864 байт = 1536 Кб =1,5 Мб (»1,2 Мбайта. Ответ дан в практикуме Угринович). Приучаем учеников, переводя в другие единицы, делить на 1024, а не на 1000.

Ответ: 1,5 Мб

7. В процессе преобразования растрового графического изображения количество цветов уменьшилось с 65536 до 16. Во сколько раз уменьшится объем занимаемой им памяти? (2.70, [3])

Решение:

Чтобы закодировать 65536 различных цветов для каждой точки, необходимо 16 бит. Чтобы закодировать 16 цветов, необходимо всего 4 бита. Следовательно, объем занимаемой памяти уменьшился в 16:4=4 раза.

Ответ: в 4 раза

8. Достаточно ли видеопамяти объемом 256 Кбайт для работы монитора в режиме 640 ´ 480 и палитрой из 16 цветов? (2.77 [3])

Решение:

• Узнаем объем видеопамяти, которая потребуется для работы монитора в режиме 640х480 и палитрой в 16 цветов. V=I*X*Y=640*480*4 (2⁴ =16, глубина цвета равна 4),

V= 1228800 бит = 153600 байт =150 Кб.

• 150 < 256, значит памяти достаточно.

Ответ: достаточно

9. Укажите минимальный объем памяти (в килобайтах), достаточный для хранения любого растрового изображения размером 256 х 256 пикселей, если известно, что в изображении используется палитра из 2¹⁶ цветов. Саму палитру хранить не нужно.

• 128

• 512

• 1024

• 2048

(ЕГЭ_2005, уровень А)

Решение:

Найдем минимальный объем памяти, необходимый для хранения одного пикселя. В изображении используется палитра из 2¹⁶ цветов, следовательно, одному пикселю может быть сопоставлен любой из 2¹⁶ возможных номеров цвета в палитре. Поэтому, минимальный объем памяти, для одного пикселя будет равен log₂ 2¹⁶ =16 битам. Минимальный объем памяти, достаточный для хранения всего изображения будет равен 16*256*256 =2⁴ * 2⁸ * 2⁸ =2²⁰ бит=2²⁰ : 2³ =2¹⁷ байт = 2¹⁷ : 2¹⁰ =2⁷ Кбайт =128 Кбайт, что соответствует пункту под номером 1.

Ответ: 1

10. Используются графические режимы с глубинами цвета 8, 16. 24, 32 бита. Вычислить объем видеопамяти, необходимые для р