БГПУ

Замкнутая ломаная без самопересечений


Содержание

Введение

Глава 1

§1. Понятие ломаной

§2. Прямая на плоскости

Глава 2

Введение: Перечень основных процедур и функций, используемых в программах

§1. Function Peres, Блок Схема

п.2 Function Peres, на языке Turbo Pascal

§2. Рекурсивный способ построения простой замкнутой ломаной

§3. Верхняя оценка количества способов построения ПЗЛ

§4. Построения простой замкнутой ломаной методом "Треугольника"

п.1 Идея метода

п.2 Реализация на языке Паскаль

Список литературы


Введение

Тема бакалаврской работы является "Простая замкнутая ломаная кривая" (ПЗЛ).

Актуальность : выбранной темы заключается в том, что теория ПЗЛ имеет практическое применение например: прокладывание газопровода, железнодорожных путей и т.д., но теория ПЗЛ не дает ответа как и сколькими способами это возможно сделать. В теории ПЗЛ дано лишь определение ПЗЛ и ее компонентов без выделения, каких либо свойств. А так решение проблемы выбранной темы является, частным случаем решения задачи Коммивояжера её ещё называют транспортной задачей.

Объект исследования: Планиметрия.

Предмет исследования: Простая замкнутая ломаная на плоскости.

Цели: Изучит понятие ПЗЛ, выделить его свойства и составить алгоритм построения.

Задачи:

1)         Составить рекурсивный алгоритм позволяющий построить все возможные ПЗЛ через n произвольных точек плоскости (замечание эти точки должны быть вершинами ПЗЛ, и других вершин нет). Реализовать его в среде Turbo Pascal.

2)         Дать верхнюю оценку количества способов построения ПЗЛ через n произвольных точек плоскости.

3)         Составить не рекурсивный алгоритм и реализовать его на языке Turbo Pascal, позволяющий строить ПЗЛ для большого количества произвольных точек

Гипотезы:

1.         ПЗЛ можно построить всегда, кроме случая когда все точки лежат на одной прямой.

2.         Пусть через n точек проходят S прямых имеющих не менее 4 данных точек, тогда через эти n точек можно провести не более чем


 

 различных ПЗЛ, где k i-количество точек принадлежащих i-ой прямой, i=1,2…S


Глава 1 §1. Понятие ломаной

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

Ломаная обозначается последовательным указанием ее вершин. Например, ломаная АВСDE, ломаная A1A2…An.

Ломаная называется простой, если она не имеет точек самопересечения (рис. 2).

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

Длиной ломаной называется сумма длин ее сторон.

  §2. Прямая на плоскости.

 

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

Из курса геометрии известно, что любая прямая на плоскости xOy имеет уравнение (1)[2], где - постоянные.

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

Воспользуемся уравнением (1).

Рассмотрим два случая, когда 1) и 2).

1)         Если то, уравнение(1) примет вид , т.е. прямая будет параллельна оси Оу или совпадать с ней.

Замечание: так как коэффициенты а и с заданы не однозначно, поэтому в алгоритмах, использующих уравнение прямой используется только геометрическая интерпретация этого случая, т.е. тот факт если прямая проходит через две точки у которых первые координаты равны, то эта прямая параллельна оси Оy.

2)         Если тогда уравнение(1) можно представить в виде (2), где . Так как точки илежат на прямой l, то их координаты являются корнями уравнения(2). Поэтому для нахождения коэффициентов уравнения(2) достаточно решить систему уравнений

í

относительно этих переменных k и d, получим решение,

íт.е. мы нашли уравнение прямой l.

Таким образом, если прямая не параллельна оси Оу то уравнение(1) равносильно уравнению иначе уравнение(1) равносильно уравнению .

п.2 Взаимное расположение двух прямых на плоскости.

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

Пусть две прямые l: , и g:  тогда если эти прямые параллельны, то  [2] иначе .

Если две различные прямые l и g не параллельны, то они имеют общую точку. Координаты этой точки являются решением системы уравнений.

íÞ íÞ í


Глава 2   Введение: Перечень основных процедур и функций, используемых в программах

Function S_3(T,B,C:tochka):Boolean;

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

Идея: находим уравнение прямой l, проходящей через точки В и С, и проверяем на принадлежность точки Т прямой l .

Var k1,b1:real;

Begin

If ((B.x=C.x)and(B.x=T.x)) or

((B.y=C.y)and(B.y=T.y))then S_3:=true

else

if B.x=C.x then S_3:=false

else begin

k1:=(B.y-C.y)/(B.x-C.x);

b1:=B.y-k1*B.x;

if round(T.y)=round(k1*T.x+b1) then S_3:=true

else S_3:=false;

end

End;

Function Prin(T,B,C:tochka):boolean;

Функция истина если точка Т принадлежит отрезку ВС.

Идея: Если точка Т лежит на отрезке ВС, то она лежит на прямой проходящей через точки В и С, и заключена между ними.

Begin

If S_3(T,B,C) then

if (((B.x<=T.x)and(T.x<=C.x)) or ((C.x<=T.x)and(T.x<=B.x))) and

(((B.y<=T.y)and(T.y<=C.y)) or ((C.y<=T.y)and(T.y<=B.y)))

then Prin:=true

else Prin:=false

else Prin:=false

End;

§1. Function Peres, Блок Схема

Истина если отрезки [AB] и [CD] имеют общие точки за исключением случаев:

1) если отрезки совпадают;

2) если один конец отрезка совпадает с одним из концов другого отрезка, и других общих точек нет.




п.2 Function Peres, на языке Turbo Pascal

Function Peres (A, B, C, D: tochka): boolean;

Var O: tochka;

k1, k2, b1, b2: real;

s1, s2: Boolean;

Begin

{Проверка 1-го случая}

if (A.x=C.x)and(A.y=C.y) and (B.x=D.x)and(B.y=D.y) then Peres:=False

else

if (A.x=D.x)and(A.y=D.y) and (B.x=C.x)and(B.y=C.y) then Peres:=False

else

{Проверка 2-го случая}

If (A.x=C.x)and(A.y=C.y) then if Prin(D,A,B) or Prin(B,C,D) then Peres:=true else Peres:=False

else

If (A.x=D.x) and (A.y=D.y) then if Prin(C, A, B) or Prin (B,C,D) then Peres:=true else Peres:=False

else

If (B.x=C.x)and(B.y=C.y) then if Prin(D,A,B) or Prin(A,C,D) then Peres:=true else Peres:=False

else

If (B.x=D.x)and(B.y=D.y) then if Prin(C,A,B) or Prin(A,C,D) then Peres:=true else Peres:=False

else { общей случай }

If A.x=B.x then begin if C.x=D.x then if Prin(A,C,D) or

Prin(B,C,D) or

Prin(C,A,B) or

Prin(D,A,B) then Peres:=true else Peres:=false

else begin

k2:=(C.y-D.y)/(C.x-D.x);

b2:=C.y-k2*C.x;

O.x:=A.x;

O.y:=k2*O.x+b2;

if Prin(O,C,D) and Prin(O,A,B) then Peres:=true

else Peres:=False

end end

else if C.x=D.x then begin

k1:=(A.y-B.y)/(A.x-B.x);

b1:=A.y-k1*A.x;

O.x:=C.x;

O.y:=k1*O.x+b1;

if Prin(O,C,D) and Prin(O,A,B) then Peres:=true

else Peres:=False

end

else begin

k1:=(A.y-B.y)/(A.x-B.x);

k2:=(C.y-D.y)/(C.x-D.x);

if k1=k2 then {} if Prin(A,C,D) or

Prin(B,C,D) or

Prin(C,A,B) or

Prin(D,A,B) then Peres:=true

else Peres:=false

else begin

b1:=A.y-k1*A.x;

b2:=C.y-k2*C.x;

O.x:=(b1-b2)/(k2-k1);

if k1=0 then O.y:=b1

else if k2=0 then O.y:=b2

else O.y:=(b1/k1-b2/k2)/(1/k1-1/k2);

if Prin(O,C,D) and Prin(O,A,B)

then Peres:=true

else Peres:=false

end

end

End;

§2. Рекурсивный способ построения простой замкнутой ломаной

 

Идея: Чтобы перебрать все возможные способы построения простой замкнутой прямой мы воспользовались следующим алгоритмом построения:

1.         Зафиксировали одну из n точек, т.к. не имеет значение, какая точка будет начальной т.к ломаная замкнутая;

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

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

Ø Новую точку можно соединить с последней присоединённой точкой, если отрезок, соединяющий эти точки, не пересекает ни одну из уже построенных сторон ломаной;

Ø Продолжаем построение до тех пор, пока есть незадействованные точки,

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


Информация о работе «Простая замкнутая ломаная кривая»
Раздел: Информатика, программирование
Количество знаков с пробелами: 18844
Количество таблиц: 0
Количество изображений: 4

Похожие работы

Скачать
17597
0
8

... можно показать, что формулы будут справедливы и в случае y!!<0. Параметрическое задание кривой Если кривая задана параметрически: x = j(t), y = y(t), то координаты центра кривизны можно получить из формул *, подставляя в них вместо y! и y!! их выражения через параметр: . Тогда (2) Эволюта и эвольвента Если в точке M1(x, y) данной линии кривизна отлична от нуля, то этой точке соответствует ...

Скачать
352659
353
269

... для графа на рис. 3, приняв, что дерево образовано ветвями 2, 1 и 5 Ответ: B= Решить задачу 5, используя соотношения (8) и (9).  Теория / ТОЭ / Лекция N 3. Представление синусоидальных величин с помощью векторов и комплексных чисел. Переменный ток долгое время не находил практического ...

Скачать
216281
1
0

... будет подставляться вместо отсутствующих в системе шрифтов. Выберите любой шрифт, который вам нравится. ЧАСТЬ П. РАБОТА СО СТАТИЧНОЙ ГРАФИКОЙ..   Глава 4. Форматы статичной графики Итак, с пользовательским интерфейсом Macromedia Flash мы разобрались. Как выполняются типичные для всех Windows-приложений задачи, выяснили. Теперь самое время приступить к работе над графикой. Да, мы так и ...

Скачать
468961
25
171

... М. В. Неоклассическая модель чистой монополии. М.: ИМЭМО, АН СССР, 1990. 3. Лейбенстайн X. Аллокативная эффективность в сравнении с "Х-эффективностью" // Теория фирмы. С. 477—506. 4. Маленво Э. Лекции... Гл. III. § 9. С. 80—85. 5. Робинсон Дж. Экономическая теория... Гл. 3—5. С. 88—130. 6. Стиглер Дж. Совершенная конкуренция: исторический ра­курс // Теория фирмы. С. 299—328. 7. Самуэльсон П. ...

0 комментариев


Наверх