Создание программы для определения вершин пирамиды с выпуклым основанием по данным точкам (стр. 2 из 3)

Теорема доказана.

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

Плоскость, многоугольники

Плоскость

Теорема

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

Доказательство

Пусть AB – данная прямая и С – не лежащая на ней точка. Проведем через точки A и С прямую. Прямые AB и AC различны, так как точка С не лежит на прямой AB. Проведем через прямые AB и AC плоскость α. Она проходит через прямую AB и точку С.

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

Допустим, существует другая, плоскость α.`, проходящая через прямую AB и точку С. По аксиоме о том, что если две различные плоскости имеют общую точку, то они пересекаются по прямой, проходящей через эту точку, плоскости α и α` пересекаются по прямой. Эта прямая должна содержать точки A, B, C. Но они не лежат на одной прямой. Что противоречит предположению. Теорема доказана.

Выпуклый многоугольник

Ломаная называется замкнутой, если ее концы соединены отрезком.

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

Многоугольник с n вершинами, называется n-угольником.

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

B1B2B3B4B5 – невыпуклый многоугольник.

Выпуклые многоугольники. Свойство

Теорема.

Сумма углов выпуклого n-угольника равна 180°*(n-2).

Доказательство.

Нужно заметить, n ≥ 3.

Для n = 3 многоугольник превращается в треугольник и теорема справедлива.

Для n > 3 проведем n-3 диагонали: A2An, A3An, …, An-1An. Получим n-2 треугольника: Δ A1A2An, Δ A2A3An, …, An-2An-1An. Сумма углов всех треугольников равна сумме углов многоугольника. Так как сумма углов треугольнике равна 180 ° и число треугольников равно n – 2, то сумма всех углов многоугольника равна 180° * (n - 2). Теорема доказана.

ОПИСАНИЕ ОБЩЕГО АЛГОРИТМА

Пункт1.Пользователь вводит N точек.

Пункт2.Программа проверяет, лежат ли все данные точки в одной плоскости, если лежат-то решения нет, вершины пирамиды не будут найдены, а на дисплей выведется сообщение «точки лежат в одной плоскости».(переход к пункту 6)

Пункт3. Если все данные точки не лежат в одной плоскости, то программа берет N-1 точек (исключаемую точку принимая за возможную вершину пирамиды) и выполняет построение уравнения плоскости по 3-м точкам ,

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

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

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

Пункт6.вывод ответа

Описание структур данных

Для хранения точек был использован динамическая структура данных- односвязанный список. Элемент списка представляет собой запись с 2 полями:

-полем данных

-полем указателя на следующий элемент

В свою очередь поле данных представляет собой запись Coordinates с 3-я полями:x,y,z

Так же для работы со списком использовались дескрипторы ,которые представляли собой записи с 3-я полями

-start(указатель на начальный(фиктивный ) элемент)

-ptr(указатель на текущий элемент)

-Number(число элементов в записи)

Type

Coordinates=record {коориднаты}

x,y,z:real;

end;

P_Points=^point; {Описаниетипа Points}

point=record

data:Coordinates;

Next:P_Points;

end;

P_Descriptor=record {Дескриптор для работы со списком точек}

Start,Ptr:P_Points;

Number:Word;

end;

P_Vectors=^Vector; {Описаниетипа Vector}

Vector=record

data:Coordinates;

Next:P_Vectors;

end;

V_Descriptor=record {Дескриптор для работы со списком векторов}

V_Start,V_Ptr:P_Vectors;

V_Number:Word;

end;

Описаниемодуля

Спецификация подпрограмм для работы со списком

1.СпецификацияпроцедурыInitListOfPoint;

1) Procedure InitListOfPoint(var P:P_Descriptor);;

2) Назначение: инициализирует фикивный элемент списка;

3) Входные параметры: P

4) Выходные параметры: P.

2.Спецификация процедуры PutPoint;

1) Procedure PutPoint(var P:P_Descriptor);

2) Назначение: создает элемент Buf и помещает его в список;

3) Входные параметры: P;

4) Выходные параметры: P;

3.Спецификация процедуры WritePoints;

1Procedure WritePoints(var P:P_Descriptor);

2) Назначение: выводит весь список точек Pна дисплей;

3) Входные параметры: P;

4) Выходные параметры: P.

4.Спецификация процедуры ReadPoint;

1) Procedure ReadPoint(var P:P_Descriptor;var a:Coordinates);

2) Назначение: cчитывает из списка P координаты точки в переменную а;

3) Входные параметры: P;

4) Выходные параметры: P,a.

5.СпецификацияпроцедурыClearMem;

1) Procedure ClearMem(var P:P_Descriptor;var V:V_Descriptor);

2) Назначение: освобождает выделенную память под списки PuV;

3) Входные параметры: P,V;

4) Выходные параметры: P,V.

Спецификация подпрограмм для работы с векторами

1.СпецификацияпроцедурыCreateVector;

1) procedure CreateVector (a,b:Coordinates;var c:Coordinates);;

2) Назначение: создает вектор с вычитая соответствующие координаты точки b из точки a;

3)Входные параметры: a,b,c

4)Выходные параметры: c.

2.СпецификацияпроцедурыMultOnNumber;

1) Procedure MultOnNumber (Number:real; a:Coordinates;var c:Coordinates)

2)Назначение: умножает вектор aна число real и полученное значение заносится в c вектор ;

3)Входные параметры: Number,a,c;

4)Выходные параметры: ,c;

3.Спецификация процедуры lengthOfVector;

1 Function lengthOfVector(a:Coordinates):real;

2Назначение: возвращает длину вектора а ;

3Входные параметры: а;

4Выходные параметры: -.

4.СпецификацияпроцедурыScalar;

1) Function Scalar(a,b:Coordinates):real;

2Назначение: возвращает результат скалярного перемножение векторов а и b;

3Входные параметры: a,b;

4Выходные параметры: -.

5.Спецификацияпроцедурыangle;

1) Function angle(a,b:coordinates):real

2Назначение: возвращает значение косинуса угла(в радианах)

между векторами а и b

3Входные параметры: a,b;

4Выходные параметры: -.

6.Спецификация процедуры VECTMult;

1 Procedure VECTMult(a,b:Coordinates;var c:Coordinates);

2Назначение: производит векторное перемножение вектора а и b и заносит результат в вектор с ;

3Входные параметры: а,b,c ;

4Выходные параметры: c.

7.Спецификация процедуры collinearity;

1) Function collinearity(a,b:Coordinates):boolean;

2Назначение: возвращает collinearity:=истина , если векторы а и bколлинеарные, иначе- collinearity:=ложь ;

3Входные параметры: a,b;

4Выходные параметры: -.

5 возврат : collinearity

9.Спецификация процедуры MixeMult;

1) Function MixeMult(a,b,c:Coordinates):real

2Назначение: возвращает MixeMult:= значение смешанного произведения векторов а и b

3Входные параметры: a,b;

4Выходные параметры: -.

5Возврат : MixeMult

10.Спецификация процедуры coplanarity;

1) Function coplanarity(a,b,c:Coordinates):boolean

2Назначение: возвращает coplanarity :=истина ,если векторы а,b и c компланарны,иначе- coplanarity :=ложь .

3Входные параметры: a,b,c;

4Выходные параметры: -.

Спецификация подпрограмм для определения вершин пирамиды

1.Спецификацияпроцедурыploskost

1) Procedure ploskost(a,b,c:coordinates;var ax,bx,cx,dx:real);;

2) Назначение: Строит по 3-м точкам уравнение плоскости вида Ax+By+Cz+D=0 и заносит в ax,bx,cx,dx соответствующие коэффициенты

3) Входные параметры:a,b,c,ax,bx,cx,dx;

4) Выходные параметры: ax,bx,cx,dx.

2.Спецификация функции proverka_na_ploskost;

1) function proverka_na_ploskost(var P:P_descriptor;var mno:mnoj; n:byte):boolean;;

2) Назначение: проверяет условие принадлежности nточек(указатели которых хранятся в множестве mno) к плоскости ,построенной с помощью процедуры ploskost,возращает значение истины в случае удачной проверки, иначе-ложь;

3) Входные параметры: P,mno,n;

4) Выходные параметры: P,mno.

5) Возврат : f

3.СпецификацияфункцииVypuklost;

1) Function Vypuklost(var P:P_descriptor;mno:mnoj;n:byte):boolean;;

2) Назначение: Проверяет многоугольник на выпуклость, путем перебора nточек из множества mno,формированием их в векторы и последующим векторным перемножением . Возвращает значение истины, если при все N точках знак векторного умножения сохраняется, иначе -ложь;

3) Входные параметры: P,mno,n;

4) Выходные параметры: P.

5) Возврат : Q

4.СпецификацияфункцииFinDaPyramid;

1) Procedure FinDaPyramid(var P:P_descriptor;mno:mnoj);

2) Назначение: определяет вершины пирамиды с выпуклым основанием и выводит на дисплей, если же нет решений -выводит соотсветсвующее сообщение ;

3) Входные параметры: P,mno,n;

4) Выходные параметры: P,mno.

Блок-схема

Тестовые Данные

-Введем 5 точек

Точка 1(2,-1,-1)

Точка 2(1, 2, 3)

Точка 3(4, 1 1)

Точка 4(0, 1, 2)

Точка 5(7, 1, 1)

-Построим по 3-м точкам уравнение плоскости

Уравнение каждой плоскости имеет вид: Ax + By + Cz + D = 0. Так что наша задача по заданным координатам 3-ех точек плоскости найти коэффициенты A, B, C и D. Эти коэффициенты находятся по формулам:

где x, y, z - координаты наших точек, а 1-2-3 это номера точек A-B-C.