Книги-online

Геометрия.

И в библиотеке бывают рекламные паузы.

Геометрия.

Проверка принадлежит ли точка прямой.

Функция проверяет принадлежит ли точка с координатами (x,y,z) прямой заданной точками (xli,yli,zli) i=1,2.. В данном случае прямую в пространстве можно задать параметрически при помощи следующей системы:

	x=xl1+t(xl2-xl1)
	y=yl1+t(yl2-yl1)
	z=zl1+t(zl2-zl1)

И точка принадлежит прямой, если система имеет непротиворечивое решение t. Проверкой этого и занимается функция.

Если одновременно выполнены следующие три условия

	xl1=xl2
	yl1=yl2
	zl1=zl2

то прямая вырождается в точку и работа функции не имеет смысла. Наверх

Проверка принадлежит ли точка плоскости.

Функция проверяет принадлежит ли точка с координатами (x,y,z) плоскости заданной точками (xpi,ypi,zpi) i=1,2,3.. При этом три точки в пространcтве задают плоскость, если они попарно различны, и не лежат на одной прямой, для проверки последнего условия используется алгоритм из предыдущей задачи. Далее находим параметры a,b,c,d для задания плоскости уравнением:

	ax+by+cz=d, где
	a=(yp2-yp1)(zp3-zp1)-(yp3-yp1)(zp2-zp1);
	b=-(xp2-xp1)(zp3-zp1)+(xp3-xp1)(zp2-zp1);
	c=(xp2-xp1)(yp3-yp1)-(xp3-xp1)(yp2-yp1);
	d=xp1a+yp1b+zp1c

и проверяем удовлетворяет ли точка (x,y,z) полученому уравнению. Наверх

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

Функция проверяет лежат ли точки с координатами (x1,y1) и (x2,y2) по одну сторону от прямой заданной точками (xl1,yl1) и (xl2,yl2) или нет. Да же нечего написать по этому поводу все и так ясно. Наверх

Пересечение отрезков.

Процедура ищет пересечение двух отрезков заданных своими конечными точками. Первый отрезок: (x1(1),y1(1));(x2(1),y2(1)). Второй отрезок: (x1(2),y1(2));(x1(2),y1(2)). В результате может получится три варианта пересечения: точка, отрезок, пустое множество.

Прямая содержащая i-й отрезок задается при помощи уравнений:

	x=x1(i)+t(i)(x2(i)-x1(i))
	y=y1(i)+t(i)(y2(i)-y1(i))

при этом точка на прямой принадлежит отрезку, если t лежит внутри отрезка [0,1]. Следовательно, пересечением отрезков будет точка если существует решение (t(1),t(2)) системы:

	t(1)(x2(1)-x1(1))+t(2)(x1(2)-x2(2))=x1(2)-x1(1)
	t(1)(y2(1)-y1(1))+t(2)(y1(2)-y2(2))=y1(2)-y1(1)

и при этом и t(1) и t(2) лежат в отрезке [0,1]. Если хотя бы одно из t(i) не удовлетворяет этому условию, то пересечением отрезков будет пустое множество.

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

В результате работы процедуры, вид пересечения можно определить рассматривая переменную s, а именно: Если s=0, то пересечение является пустым множеством. Если s=1, то пересечение - точка и ее координаты находятся в переменных x,y. Если s=2, то пересечение отрезок и координаты его концов возращаются в переменных x11,y11;x12,y12. Наверх

Положение точки относительно многоугольника.

Функция проверяет, лежит ли точка с координатами (x,y) внутри n-угольника (точнее, n-вершинника), заданного координатами вершин (xi,yi), i=1..n.

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

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

Функция проверяет, лежит ли точка P с координатами (x,y) внутри выпуклого n-угольника, заданного координатами вершин Pi(xi,yi), i=1..n.

Принцип простой, если точка внутри выпуклого многоугольника, то sin углов Pi,P,Pi+1(с учетом порядка обхода) имеют один знак для всех i=1..n, если sin равен нулю, то точка лежит на стороне Pi,Pi+1. Наверх

Площадь многоугольника.

Если координаты вершин n-угольника равны (xi,yi), i=1..n, то площадь многоугольника может быть вычислена по формуле

где (x0,y0)=(xn,yn).

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

Триангуляция области на основе заданного набора точек.

Пусть на плоскости задан набор из n точек своими координатами (x[i],y[i]), i=1,...,n. Процедура осуществляет разбиение области на треугольники, при этом разбиение области удовлетворяет двум условиям: 1) область полностью покрыта непересекающимися треугольниками с вершинами в узловых точках; 2) любой выпуклый четырехугольник разбивается по кратчайшей диагонали.

Выполенение этих двух условий позволяет провести "хорошую" интерполяцию функцию, которая заданна значениями в узловых точках.

Алгоритм мне прислал Michael V. Pakki. Я привожу его практически без изменений, единственное усовершенствование, которое я себе позволил, это избавился от рекурсии, итак:
ШАГ 1 Находим такие две точки P1 и P2, чтобы все остальные точки лежали по одну сторону от прямой P1P2;
ШАГ 2 Вводим фиктивную точку P0, лежащую по другую сторону от прямой P1P2;
ШАГ 3 Помещаем на стек номера точек P1,P2,P0.
ШАГ 4 Снимаем со стека точки P1,P2,P3. Ищем такую точку M, разделенную от точки P3 прямой P1P2, чтобы угол P1_M_P2 был максимальный; если такой точки нет, то переход на ШАГ 6;
ШАГ 5 Сравниваем треугольник P1MP2 с найденными ранее; если совпадения не обнаружено, то запоминаем треугольник P1MP2 и помещаем на стек номера точек P1,M,P2 и P2,M,P1;
ШАГ 6 Если стек не пуст возвращаемся к ШАГУ 4;

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

На выходе получаем в переменной nt количество треугольников, сами треугольники (заданные номерами вершин в исходном массиве) содержаться в массиве tr. Наверх

Разбиение многоугольника на треугольники.

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

Пусть некоторый многоугольник задан набором координат своих вершин P0=(x0,y0);P1=(x1,y1);...;Pn=(xn,yn) при этом будем полагать, что вершины занумерованы по часовой стрелке. В случае если многоугольник выпуклый, задача нахождения разбиения тривиальна, можно взять набор диагоналей выходящих из какой-либо вершины.

В случае невыпуклого многоугольника задача существенно усложняется. Будем действовать следующим образом, на каждом шаге алгоритма будем отсекать один треугольник Pi-1,Pi,Pi+1 и исключать вершину Pi из дальнейшего рассмотрения. Чтобы определить можно ли использовать диагональ Pi-1Pi+1 для отсечения треугольника, будем вначале проверять знак sin угла Pi-1,Pi,Pi+1 учитывая при этом последовательность обхода вершин, так для многоугольника изображенного на рисунке при i=0,1,2,3,4,7 sin будет отрицателен, а при i=5,6 положителен.

Далее найдя i для которой sin отрицателен, проверем не входят ли в треугольник Pi-1,Pi,Pi+1, какие-либо точки из многоугольника (естественно кроме i-1,i,i+1), если нет значит отсечем этот треугольник, иначе ищем следующую вершину с отрицательным sin и проверяем ее. Проверку принадлежности точки треугольнику можно осуществить одним из алгоритмов рассмотренных на этой странице переписав его для частного случае треугольника.

Алгоритм можно оптимизировать по скорости введя, например массив, содержащий знаки sin, и перевычисляя на каждом шаге только i - й знак. Возможны и другие усовершенствования.

Теперь немного о блок-схеме реализующей алгоритм. Номер последней вершины передается в переменной n (всего будет соответственно n+1 вершина), координаты в массивах x и y, полученое разбиение помещается в массив tr, tr[1..3][i] содержит номера вершин исходного многоугольника, составляющие i-ый треугольник. Внутри блок-схемы дополнительно используются массив t для хранения вершин промежуточных многоугольников. Наверх