задачи по вычислительной геометри

[pfantom2004]

Здравствуйте програмисты и любители. Сам паскаль то знаю а вот с геометрией беда полная помогите кто чем может=((( вот. Буду весьма благодарен.
1. Параметрическое задание прямой на плоскости. Отрезок. Луч.
a. Даны три точки А,В,С, лежащие на одной прямой. Определить расположение точки С относительно отрезка АВ (между точками А и В, вне отрезка за точкой А, вне отрезка за точкой В).
b. Даны четыре точки A, B, C и D, лежащие на одной прямой. Определить пересекаются ли луч [AB) и отрезок [CD].
c. Добавить функции для:
Вычисления ориентированного угла между векторами a и b;
Вычисления ориентированной площади треугольника АВС, заданного координатами вершин;
Вычисления площади многоугольника, заданного координатами вершин в порядке обхода.
2. Основные формулы и соотношения. Написать программы для решения следующих задач, а также придумать полную систему тестов (тесты оформить в отдельных файлах, и едином документе с ответами и рисунками).

a) Треугольник задан координатами вершин. Определить координаты и радиус вписанной окружности.
b) Дано множество точек (точки заданы своими координатами). Найти треугольник с наименьшей и наибольшей площадью, вершинами которого будут исходные точки.
Формат входных данных:
Первое число – количество точек
Далее в строках по два числа – координаты точек.

3. Уравнение плоскости, прямая в пространстве
a) Даны точки А, В, С, D своими координатами, найти уравнение плоскости проходящей через точку D и параллельную плоскости АВС.
b) Даны три точки в пространстве, своими координатами, определить лежат ли они на одной прямой.
4. Взаимное расположение двух прямых, прямой и плоскости в пространстве
a. Даны точки М1, М2, М3, М4. Определить взаимное расположение прямых (М1, М2) и (М3, М4).
b. Даны точки М1, М2, М3, М4, М5. Определить взаимное расположение луча (М1, М2) и плоскости (М3, М4, М5).
5. Определить является ли данный многогранник выпуклым. Многогранник задан списком вершин и списком граней. Разработать систему тестов. Нарисовать на бумажке и записать в файл.
6. Даны три плоскости своими коэффициентами, определить их взаимное расположение. Разработать полную систему тестов. Нарисовать на бумажке и записать в файл.

[fimaxe]

Вопрос такой: для векторов идет ввод координат (точек) или в 3Д модели?

[challengerr]

p задает функцию расстояния

1a.

вне отрезка за a
p(c, a) + p(c, b) > p(a,b)
p(c, a) < p(c, b)

вне отрезка за b
p(c, a) + p(c, b) > p(a,b)
p(c, a) > p(c, b)

на отрезке (причем если равенство, то совпадение с одной из вершин отрезка)
p(c, a) + p(c, b) <= p(a,b)


1b

не пересекаются
p(c,a) + p(c, b) > p(a,b)
p(d,a) + p(d, b) > p(a,b)

пересекаются, причем[CD] поглощает [AB) а C совпадает с A
p(c,a) + p(c, b) = p(a,b)
p(c,a) = 0
p(d,a) + p(d, b) > p(a,b)
p(d, a) > p(d, b)

пересекаются в одной точке A, C совпадает с A
p(c,a) + p(c, b) = p(a,b)
p(c,a) = 0
p(d,a) + p(d, b) > p(a,b)
p(d, a) < p(d, b)


не пересекаются, C совпадает с B, D за B
p(c,a) + p(c, b) = p(a,b)
p(c,b) = 0
p(d,a) + p(d, b) > p(a,b)
p(d, a) > p(d, b)

пересекаются, причем[CD] поглощает [AB), C совпадает с B, D за A
p(c,a) + p(c, b) = p(a,b)
p(c,b) = 0
p(d,a) + p(d, b) > p(a,b)
p(d, a) < p(d, b)



D совпадает с A, C за B [CD] поглощает [AB)
p(d,a) + p(d, b) = p(a,b)
p(d,a) = 0
p(c,a) + p(c, b) > p(a,b)
p(c, a) > p(c, b)

D совпадает с A, C за A (пересечение в одной точке A)
p(d,a) + p(d, b) = p(a,b)
p(d,a) = 0
p(c,a) + p(c, b) > p(a,b)
p(c, a) < p(c, b)


D совпадает с B, C за B (не пересекаются)
p(d,a) + p(d, b) = p(a,b)
p(d,b) = 0
p(c,a) + p(c, b) > p(a,b)
p(c, a) > p(c, b)

D совпадает с B, C за A [CD] поглощает [AB)
p(d,a) + p(d, b) = p(a,b)
p(d,b) = 0
p(c,a) + p(c, b) > p(a,b)
p(c, a) < p(c, b)

1c (1)

p - длина вектора
(a,b) - скалярное произведение

cos(a,b) = (a,b) / ( p(a) * p(b) )

взятие arccos ( cos(a,b) ) дает угол между векторами a и b

1c (2)

Ориентированная площадь: http://upload.wikimedia.org/math/e/a...ab4da7d80b.png

A (xa, ya)
B (xb, yb)

S = 1/2 (xa* yb - ya*xb)
см http://school-collection.edu.ru/cata...4e142d9c/view/

1c (3)
см http://school-collection.edu.ru/cata...4e142d9c/view/

(A1A2..An) = 1/2 * ((x(1)y(2)-y1x2)+(x2y3 - y2x3)+...+(x[n-1]yn - y[n-1]xn) + (xny1 - ynx1))

xi, yi координаты точки Ai

2a
см http://fxdx.ru/page/centr-vpisannoj-...ik-okruzhnosti

***
4

Нахождение коэффициентов уравнения прямой

Пусть дано
M1 (x1, y1)
M2 (x2, y2)

A1 = y2 - y1
B1 = x1 - x2
C1 = x2 * y1 - x1 * y2

A1x+B1y+C1=0 уравнение прямой, проходящей через M1 и M2


M3 (x3, y3)
M4 (x4, y4)

A2 = y4 - y3
B2 = x3 - x4
C2 = x4 * y3 - x3 * y4

A2x+B2y+C2=0 уравнение прямой, проходящей через M3 и M4

Теорема: пусть прямая L определяется Ax+By+C = 0 Точки M1 (x1, y1) и M2 (x2, y2) принадлежат разным полуплоскостям относительно прямой L тогда и только тогда, когда ( Ax1 + By1 +C)(Ax2 +By2 +C) < 0

В 4a решается система уравнений для взаимного определения расположения. Метод Крамера или метод Гаусса и др..
A1x+B1y+C1=0
A2x+B2y+C2=0

[challengerr]

для нахождения плоскости ABC в задании 3a

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

Пусть дано
M1 (x1, y1)
M2 (x2, y2)
M3 (x3, y3)

| x-x1 y-y1 z-z1 |
| x2-x1 y2-y1 z2-z1 | =0
| x3-x1 y3-y1 z3-z1 |
http://upload.wikimedia.org/math/e/8...3dd7ddfc62.png

отсюда
A = y2*z3 - y2*z1 - y1*z3 + y1*z1 - y3*z2 + y3*z1 + y1*z2 - y1*z1
B = - ( x2*z3 - x2*z1 - x1*z3 + x1*z1 - x3*z2 + x3*z1 + x1*z2 - x1*z1 )
C = x2*y3 - x2*y1-x1*y3 + x1*y1 - x3*y2 + x3*y1 +x1*y2 - x1*y1

D = - x1 * ( y2*z3 - y2*z1 - y1*z3 + y1*z1 - y3*z2 + y3*z1 + y1*z2 - y1*z1 ) + y1 * ( x2*z3 - x2*z1 - x1*z3 + x1*z1 - x3*z2 + x3*z1 + x1*z2 - x1*z1 ) - z1 * ( x2*y3 - x2*y1-x1*y3 + x1*y1 - x3*y2 + x3*y1 +x1*y2 - x1*y1 )


Для 3b

Если точки лежат на одной прямой то в http://upload.wikimedia.org/math/e/8...3dd7ddfc62.png возникает линейная зависимость

[challengerr]

В задаче 3a : Даны точки А, В, С, E своими координатами, найти уравнение плоскости проходящей через точку E и параллельную плоскости АВС.

Нахождение коэффициентов уравнения плоскости проходящей через точку E и параллельную плоскости АВС.


Пусть заданы две плоскости
A1x + B1y + C1z + D1 = 0
A2x + B2y + C2z + D2 = 0

Плоскости параллельны, если
A1 / A2 = B1 / B2 = C1 / C2

По условию задачи
дано: Ax + By + Cz + D = 0 и точка E (e1, e2, e3)
найти: A'x + B'y + C'z + D' = 0 || Ax + By + Cz + D = 0 такую что точка E (e1, e2, e3) лежит на A'x + B'y + C'z

+ D' = 0

Это значит, что при подстановки координат точки E (e1, e2, e3) в A'x + B'y + C'z + D' = 0 оно является

верным тождеством.

Пусть A / A' = B / B' = C / C' равно некоторой константе f
тогда A = fA' B =fB' и C = fC'

отсюда
A' = A / f
B' = B / f
C' = C/ f

Подставим это в уравнение искомой плоскости A'x + B'y + C'z + D' = 0
Получаем (A / f )x + (B / f)y + (C/ f)z + D = 0
x = e1
y = e2
z = e3
Получаем (A / f ) e1 + (B / f) e2 + (C/ f) e3 + D = 0
(A / f ) e1 + (B / f) e2 + (C/ f) e3 = - D
(Ae1+Be2+Ce3) / f = - D
отсюда

f = - (Ae1+Be2+Ce3) / D

найдя f вычисляем коэффициенты искомой плоскости

Для 3b
Точки (x1, y1) (x2, y2) (x3, y3) лежат на одной прямой тогда и только тогда когда выполняется
| x1 y1 1 |
| x2 y2 1 | = 0
| x3 y3 1 |
см http://ru.wikipedia.org/wiki/%D0%9F%...BC%D0%B0%D1%8F

4a
Пусть даны две прямые
A1x + B1y + C1 = 0
A2x + B2y + C2 = 0
Прямые параллельны, если A1*B2 - A2*B1 = 0
перпендикулярны, если A1*A2 + B1 *B2 = 0
Угол между прямыми определяется формулой
tgF = (A1*B2 - A2*B1) / A1*A2 + B1 *B2

Для 5
http://hardfire.ru/convex_polygon

Для 6

Пусть заданы две плоскости
A1x + B1y + C1z + D1 = 0
A2x + B2y + C2z + D2 = 0

Плоскости параллельны, если A1 / A2 = B1 / B2 = C1 / C2
Плоскости перпендикулярны, если A1 * A2 + B1 * B2 + C1 * C2 = 0

[pfantom2004]

Всем кто писал спасибо, только я не знаю как это все в паскаль перевести=)

[challengerr]

1a

uses math;

var
a1, a2, b1, b2, c1, c2: real;
pca, pcb, pab: real;

function distance (x1: real; y1:real; x2:real;  y2: real) : real;
begin
distance := sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) );
end;

begin

pca := distance(c1, c2, a1, a2);
pcb := distance(c1, c2, b1, b2);
pab := distance(a1, a2, b1, b2);

if (pca + pcb > pab) and (pca < pcb) then
writeln('vne otrezka za a');

if (pca + pcb > pab) and (pca > pcb) then
writeln('vne otrezka za b');

if (pca + pcb <= pab) then
writeln('na otrezke');
end.

1b

uses math;

var
a1, a2, b1, b2, c1, c2, d1, d2: real;
pca, pcb, pda, pdb, pab: real;

function distance (x1: real; y1:real; x2:real; y2: real) : real;
begin
distance := sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) );
end;

begin

pca := distance(c1, c2, a1, a2);
pcb := distance(c1, c2, b1, b2);
pda := distance(d1, d2, a1, a2);
pdb := distance(d1, d2, b1, b2);
pab := distance(a1, a2, b1, b2);

if (pca + pcb > pab) and (pda + pdb > pab) then
writeln('ne peresekayutsa');

if (pca + pcb = pab)  and (pca = 0) and  (pda + pdb > pab) and (pda > pdb) then
writeln('c sovpadaet s a, ab vnutri cd');

if (pca + pcb = pab)  and (pca = 0) and  (pda + pdb > pab) and (pda < pdb) then
writeln('c sovpadaet s a, peresekayutsa v a ');

if (pca + pcb = pab)  and (pcb = 0) and  (pda + pdb > pab) and (pda < pdb) then
writeln('c sovpadaet s b, d za b');

if (pca + pcb = pab)  and (pcb = 0) and  (pda + pdb > pab) and (pda > pdb) then
writeln('c sovpadaet s b, d za a ');



if (pda + pdb = pab)  and (pda = 0) and  (pca + pcb > pab) and (pca > pcb) then
writeln('d sovpadaet s a, ab vnutri cd');

if (pda + pdb = pab)  and (pda = 0) and  (pca + pcb > pab) and (pca < pcb) then
writeln('d sovpadaet s a, peresekayutsa v a ');

if (pda + pdb = pab)  and (pdb = 0) and  (pca + pcb > pab) and (pca < pcb) then
writeln('d sovpadaet s b, d za b');

if (pda + pdb = pab)  and (pdb = 0) and  (pca + pcb > pab) and (pca > pcb) then
writeln('d sovpadaet s b, d za a ');

end.

1c

uses math;

var
a1, a2, b1, b2: real;
ab, pa, pb, csab, u :real;

function vector_length (x1: real; y1:real) : real;
begin
vector_length := sqrt( x1*x1 + y1*y1 );
end;

function distance (x1: real; y1:real; x2:real; y2: real) : real;
begin
distance := sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) );
end;

function proizvedenie (x1: real; y1:real; x2:real; y2: real) : real;
begin
proizvedenie:=sqrt( x1*x2+y1*y2);
end;

begin

ab := proizvedenie(a1, a2, b1, b2);
pa := vector_length(a1, a2);
pb := vector_length(b1, b2);
csab:= ab / (pa*pb);
u := arccos(csab);


end.

[challengerr]

3a

{3a Даны точки А, В, С, D своими координатами, найти уравнение плоскости проходящей через точку D и параллельную плоскости АВС.}

uses math;

var
ax, ay, az, bx,  by, bz, cx, cy, cz, dx, dy, dz: real;
a, b, c, d: real;
f: real;
a1, b1, c1, d1: real;

begin

{ задание координат }
ax := 1.0;
ay := 1.0;
az := 3.0;
bx := 2.0;
by := 5.0;
bz := 4.0;
cx := 5.0;
cy := 3.0;
cz := 5.0;
dx := 6.0;
dy := 7.0;
dz := 8.0;

{   нахождение коэффициентов плоскости  АВС
| x-x1 y-y1 z-z1 |
| x2-x1 y2-y1 z2-z1 | =0
| x3-x1 y3-y1 z3-z1 |
http://upload.wikimedia.org/math/e/8/6/e868d9b9463195874ddb5e3dd7ddfc62.png
}


a := (by-ay)*(cz-az) - (cy-ay)*(bz-az);
b := - ( (bx-ax)*(cz-az) - (cx-ax)*(bz-az) );
c := (bx-ax)*(cy-ay) - (cx-ax)*(by-ay);
d := - ax * a  + ay * (-b)  - az * c;

writeln('check:', a, ' x + ', b, ' y + ', c, ' z +', d, ' = 0');
writeln('check 1: ', a * ax + b * ay + c * az + d);
writeln('check 2: ', a * bx + b * by + c * bz + d);
writeln('check 3: ', a * cx + b * cy + c * cz + d);

{ нахождение коэффициентов уравнениz плоскости проходящей через точку D и параллельную плоскости АВС}

{ http://www.pm298.ru/reshenie/yrtt.php  }

a1 := a;
b1 := b;
c1 := c;
d1 := a * (-dx) + b * (-dy) + c *(-dz);

writeln('check:', a1, ' x + ', b1, ' y + ', c1, ' z +', d1, ' = 0');
writeln('check 1: ', a1 * dx + b1 * dy + c1 * dz + d1);

end.

[challengerr]

3b Даны три точки в пространстве, своими координатами, определить лежат ли они на одной прямой..

uses math;

var
ax, ay, az, bx,  by, bz, cx, cy, cz: real;
a, b, c, d: real;
a1, a2, a3, a4, a5, a6: real;
b1, b2, b3 : real;
begin  

{ задание координат }
ax := 1.0;
ay := 1.0;
az := 3.0;
bx := 2.0;
by := 2.0;
bz := 2.0;
cx := 3.0;
cy := 3.0;
cz := 1.0;



{
http://www.kakprosto.ru/kak-108319-kak-opredelit-lezhat-li-tochki-na-odnoy-pryamoy
}


a1 := cx - ax; 
a2 := bx - ax; 
a3 := cy - ay; 
a4 := by - ay; 
a5 := cz - az; 
a6 := bz - az;

if a2 <>0 then
begin
b1 := a1 / a2;
end
else
begin
b1 := 0;
end;



if a4 <>0 then
begin
b2 := a3 / a4;
end
else
begin
b2 := 0;
end;


if a6 <>0 then
begin
b3 := a5 / a6;
end
else
begin
b3 := 0;
end;

writeln(b1);
writeln(b2);
writeln(b3);

if (b1 = b2) and (b2 = b3) then
writeln('na odnoy pryamoy');

if (b1 = b2) and (b3 = 0) then
writeln('na odnoy pryamoy');

if (b1 = b3) and (b2 = 0) then
writeln('na odnoy pryamoy');

if (b2 = b3) and (b1 = 0) then
writeln('na odnoy pryamoy');

end.