Песочница

Триангуляция многоугольников

• Чулан *

Задача: разбить произвольный многоугольник на треугольники.

Что нужно.

• Клас, что-то наподобие списка, где можно двигаться вперед-назад и конец соединен с началом. То есть замкнутый круг, элементами которого будут объекты описаны пунктом ниже.
• Клас для представления точки. В нем, как полагается, должны быть координаты х и у . Так же еще одно поле в котором записано значение угла соответствующего этой точке в многоугольнике
• Функция, на вход которой идут два векторы, а на выход - угол между ними
• Функция, на вход которой идет точка и треугольник, на выход - признак, лежит ли точка внутри треугольника.

• Создаем пустой список для хранения временных треугольников.
  Если точка слева от «рабочий» (p(i)->left) имеет угол меньше чем 180 градусов и треугольник (p(i), p(i)->left, p(i)->left->left) не содержит внутри себя других точек многоугольника - заносим этот треугольник в наш временный список.
  Если точка справа от «рабочий» (p(i)->right) имеет угол меньше чем 180 градусов и треугольник (p(i), p(i)->right, p(i)->right->
  Если «рабочая» точка (p(i)) имеет угол меньше чем 180 градусов и треугольник (p(i)->left, p(i),p(i)->right) не содержит внутри себя других точек многоугольника - заносим этот треугольник в наш временный список.
• Если временный список не содержит треугольников - выбираем вместо «рабочий», точку слева от нее и возвращаемся к первому пункту.
  Если содержит - выбираем треугольник с минимальной разницей между минимальным и максимальным углом (нужно пересчитать значение углов), заносим его в список result, удаляем из points среднюю точку из треугольника который выбрали а соседним точкам от нее (в points) пересчитываем значения углов, первую точку выбираем в качестве «рабочей» (p(i)).Если в points осталось только две точки - прекращаем работу, список треугольников содержится в res, иначе возвращаемся к первому пункту.

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

П.С. Я не встречал такой алгоритм на просторах инета, хотя и уверен, что что-то подобное уже есть.

Теги: триангуляция

Начнём с самого простого случая - n = 3. В треугольнике эта точка известна, существует и единственна для любого треугольника. Интересно исследовать, перенесутся ли какие-то из её свойств на четырёхугольник и т.д. Разбор случая n = 4 можно начать с квадрата и постепенно ослаблять условия (параллелограмм, трапеция, произвольный четырёхугольник).

Восстановление многоугольника

Тема возникла из двух задач:

1. Восстановить треугольник по серединам сторон (простая).

2. Восстановить пятиугольник по серединам сторон (посложнее).

При решении возникают два случая:

1) Число сторон нечётно. Тогда решение существует и единственно для любого расположения исходных точек. Если исходные точки образуют многоугольник, то решение невырождено.

2) Число сторон чётно. Тогда либо решение не существует, либо их бесконечно много (в зависимости от расположения исходных точек).

При решении можно использовать и теорему Вариньона, и метод координат, и программу «Живая геометрия».

Обобщение. Отметили точки, делящие стороны в отношении 1: a .

Равноугольные шестиугольники и равносторонние шестиугольники

Исследование удобно проводить в программе «Живая геометрия» (построить в ней требуемую фигуру уже является интересной «подзадачей»). Окажется, что у равностороннего шестиугольника никаких интересных свойств нет, т.е. требование равенства всех сторон слишком слабое. Можно спросить, а что надо задать ещё, чтобы какие-то свойства появились. Найти свойства равноугольного шестиугольника помогает следующая конструкция: продлим стороны до пересечения через одну, получим два правильных треугольника.

А) Противоположные стороны параллельны.

Б) Биссектрисы углов параллельны сторонам.

В) Сумма двух смежных сторон равна сумме двух противоположных смежных сторон.

Г) Три средние линии пересекаются в одной точке. (А что у четырёхугольников? А верно ли обратное утверждение? Не делятся ли средние линии пополам? В каких случаях делятся?)

Д) Середины больших диагоналей являются вершинами равностороннего треугольника, а его стороны параллельны сторонам шестиугольника.

Е) Точки пересечения малых диагоналей находятся на средних линиях.

Полуправильные шестиугольники

Можно искать свойства полуправильных шестиугольников, аналогичные свойствам параллелограмма. У параллелограмма диагонали делят друг друга пополам. У вписанного параллелограмма углы равны и диагонали равны. У описанного параллелограмма стороны равны и диагонали взаимно перпендикулярны. Какие из этих свойств есть у полуправильных шестиугольников? (Про диагонали надо ещё понять, какие именно брать и пересекаются ли они в одной точке.)

Замечательные точки

По двум данным замечательным точкам O и H по теореме Эйлера восстанавливается третья – точка пересечения медиан G. Если в произвольном месте выбрать вершину треугольника A, то нетрудно произвести построения, дающие вершины B и С (если вершины существуют). Теперь можно провести эксперимент в программе «Живая геометрия» – найти множество точек A, при которых точки B и С существуют. В силу равноправия вершин то же множество точек будет ответом и для вершин В и С.

Обобщение. 1. Изучите углы треугольника ABC в зависимости от положения вершины A. 2. Решите аналогичную задачу для данных центра вписанной окружности и точки пересечения медиан; для других пар замечательных точек.

3. Рассмотрите аналогичную задачу в пространстве (тетраэдры вместо треугольников).

4. Вообще, можно придумать много аналогичных задач, выбирая различные замечательные точки.

Сложение фигур

Полезно начать с простых фигур: две точки, точка и отрезок, два отрезка.

Обобщение. Суммой Минковского фигур F и G назовём множество точек K, определяемых равенством , где , , O – данная точка. Исследуйте свойства этой операции. Что можно сказать о площади суммы двух фигур?

1. Н.Васильев. «Сложение фигур». Квант. 1976. N 4. Сс. 22-29. Содержит ряд задач – фактически план исследования, и приложения полученных методов к сложным задачам.

2. Г.Ю. Панина. «Алгебра многогранников». Математическое просвещение. 2006. N 10. С. 109-131. Продолжение этого сюжета в современной науке.

КОМБИНАТОРИКА

Разрезы

Это одна из классических задач, на которых учат доказывать методом математической индукции. Но мы следуем принципу Пойа: «сначала угадай, потом докажи». Поскольку задача хорошо подходит для математического эксперимента, то подумать над ней полезно и школьнику, не владеющему методом математической индукции. Наименьшее число частей угадывается легко, с наибольшим бывает непросто сформулировать условия разрезания (так называемые прямые общего положения ) и доказательства их оптимальности. Помочь может следующее замечание: вопросы «Сколько частей добавляет данная прямая» и «На сколько частей данную прямую делят предыдущие» - равносильны. См. также с. …

Обобщения.

1. Все ли промежуточные значения встречаются? Нет: например, 3 прямые могут делить плоскость только на 4, 6 и 7 частей (а на 5 не могут). Какие именно значения встречаются при произвольном n , наука знает не полностью, см. В.И. Арнольд «На сколько частей делят плоскость n прямых?» / Математическое просвещение. Третья серия. Выпуск 12. 2008. С. 95-104.

2. На сколько частей делят пространство n плоскостей общего положения? , сс. 65-73, 76.

3. На сколько частей делят плоскость n попарно пересекающихся окружностей общего положения?

Раскраски

Задача имеет длинное «счётное» решение и короткое идейное. Чтобы изобрести второе, надо придумать такой способ раскрашивания, при котором разные последовательности действий приводят к разным раскраскам, а затем посчитать количество последовательностей . Например, можно зафиксировать порядок граней, а менять порядок цветов: в первый цвет закрасить любую грань, во второй – противоположную ей (5 вариантов), в третий – любую из боковых, в четвёртый – следующую за ней по часовой стрелке (3 варианта), в пятый – следующую (2 варианта), в шестой – последнюю (1 вариант). (Идея взята из работы семиклассницы.) Придумать такой способ можно, формулируя алгоритм, как понять, одинаковые или разные раскраски у двух данных кубиков.

С младшими детьми можно изготовить модели всех таких кубиков.

Обобщение.

1. Та же задача для других правильных многогранников. Может быть, стоит начать с правильного тетраэдра.

2. Можно раскрашивать не грани, а рёбра или вершины.

Разбиения многоугольников

Введение Предварительные определения и факты Основные результаты Литература

Введение

Хорошо известно, что разбиения многоугольника на треугольники и многогранника на тетраэдры служат основой при построении теории площади и объема (см. ). Кроме того, специального вида разбиения (триангуляции) являются удобным инструментом в доказательстве существования неподвижных и почти неподвижных точек у непрерывных отображений полиэдров (см. ). Поэтому возможность такого рода разбиений требует строгого доказательства. Существует несколько различных вариантов решения этой проблемы. Один из них (см. ), использующий математическую индукцию, основан на поиске разбивающей диагонали в многоугольнике. Согласно другому известному способу доказательства необходимо провести все прямые, содержащие стороны многоугольника, и рассмотреть всевозможные пересечения полученных полуплоскостей. Останется разбить на треугольники только те пересечения, которые содержаться в данном многоугольнике.

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

Предварительные определения и факты

Фигура F называется выпуклой , если для каждой пары точек A ,B Î F следует, что отрезок [AB ] содержится в F.

Упражнение 1. Доказать, что пересечение выпуклых множеств является выпуклым множеством.

Расстояние между точками A и B будем обозначать через |AB |. Тогда для любого положительного e будем называть e-окрестностью произвольной точки A плоскости a следующее множество: O e(A ) = {X Î a: |AX | < e}.

Точка A называется внутренней точкой фигуры F, если существует хотя бы одна e-окрестность точки A , которая содержится в этом множестве. Множество всех внутренних точек фигуры F обозначается через Int F. Точка A называется граничной точкой фигуры F, если для любой ее e-окрестности выполняется одновременно O e(A )ÇF ¹ Æ и O e(A )Ç(a\F) ¹ Æ. Множество всех граничных точек фигуры F обозначается через Bound F. Если каждая точка множества V является его внутренней точкой (т. е. V = Int V ), то V называется открытым множеством. Множество F , содержащее все свои граничные точки (т. е. Bound F Í F ), называется замкнутым множеством.

Упражнение 2. Доказать, что дополнение до открытого множества является замкнутым множеством и наоборот.

Множество называется связным , если его нельзя представить в виде объединения двух своих непустых открытых подмножеств. Связное открытое множество на плоскости называется областью . Следующее утверждение позволяет ввести определение многоугольника: простая замкнутая ломаная1 разбивает плоскость на две области, в точности одна их которых является ограниченным множеством2 (доказательство можно найти в ). Многоугольником будем называть объединение простой замкнутой ломаной с ее внутренней областью. Сложность последнего определения вынуждает рассматривать другой класс, состоящий из всех многоугольных фигур. При этом многоугольной фигурой называется конечное объединение треугольников.

Упражнение 3. Доказать замкнутость и ограниченность3 всякого многоугольника и любой многоугольной фигуры.

Следующее понятие сыграет главную роль в доказательстве основной теоремы. Множество F называется компактным, если из любого семейства открытых множеств V = {Gi : i Î I }, объединение которых содержит F , можно выделить конечное число членов {Gi 1,Gi 2,...,Gin }, объединение которых также будет содержать множество F . Такое семейство {Gi : i Î I } мы будем называть открытым покрытием множества F , а подходящую часть этого семейства, т. е. множество {Gi 1,Gi 2,...,Gin }, конечным подпокрытием V множества F . Очевидно, что любое конечное множество является компактным. Следующие два упражнения позволяют описать все компактные подмножества плоскости (доказательства этих утверждений можно найти в ).

Упражнение 4. Доказать, что прямоугольник является компактным множеством.

Упражнение 5. Доказать, что замкнутое подмножество компактного множества компактно.

Следствием последних трех упражнений является компактность любого многоугольника и любой многоугольной фигуры, поскольку каждое из этих множеств замкнуто и содержится в некотором прямоугольнике. Более того, всякое ограниченное замкнутое подмножество плоскости компактно. Заметим, что обратное к последнему утверждению также справедливо, и это дает критерий компактности плоских множеств.

Основные результаты

Объединение отрезков4 x = È{[AiBi ]:i Î I } будем называть цепью (а сами отрезки - звеньями этой цепи), если различные ее звенья могут пересекаться только по своим вершинам, и каждая вершина любого звена является вершиной другого и только одного звена. Заметим, что цепь может состоять из бесконечного числа звеньев, а также может распадаться на несколько непересекающихся своих связных подцепей. Для любой точки A цепи x через x (A ) обозначим объединение звеньев цепи x , содержащих точку A (x (A ) состоит из одного или из двух звеньев). Напомним, что расстоянием от точки A до некоторого множества F называют число d (A ,F) = inf{|AX |:X Î F}.

Определение. Цепь x назовем k -цепью, если для любой точки A цепи x выполнено: d (A ,x \x (A )) > 0.

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

Упражнение 6. Привести пример k-цепи, не являющейся простой замкнутой ломаной. Привести пример цепи, не являющейся k-цепью.

Определение. Фигуру M назовем k -множеством, если

1) M является компактным множеством;

2) Bound M - k -цепь;

3) для каждой e-окрестности любой точки A Î Bound M выполняется
O e(A )Ç Int M ¹ Æ.

Легко заметить, что любой многоугольник и каждая многоугольная фигура являются k -множествами.

Лемма. Любое k-множество M можно представить в виде объединения конечного числа треугольников.

Доказательство. Сразу заметим, что это утверждение очевидно, если M является выпуклым многоугольником (достаточно соединить произвольную внутреннюю точку M с его вершинами). Кроме того, легко разбивается на треугольники многоугольник M = ,

DIV_ADBLOCK550">

Первый случай. Для произвольной точки A Î Int M выберем O e(A ) так, что O e(A ) Í M . Определим через T (A ) некоторый правильный треугольник с центром в A , целиком лежащий в O e(A ).

DIV_ADBLOCK551">

1) M i состоит из треугольников,

2) Di Î M i ,

3) M Í ÈM i , различные треугольники из M i не имеют общих внутренних точек.

На рисунке показано, как с помощью шести треугольников можно дополнить Di до подходящей системы M i . Договоримся называть треугольник Di корнем системы M i . Теперь будем рассматривать все такие непустые пересечения F = F1Ç...ÇFn (Fi Î M i ), что среди {F1,F2,... Fn } есть хотя бы один корень (такие пересечения назовем корневыми). Важно заметить, что если два корневых пересечения F = F1Ç...ÇFn и F = F 1Ç...ÇFn различны, то они не имеют общих внутренних точек (из свойства 4 системы M i ). Кроме того, каждое такое множество F содержится в M (см. свойство 2) и является выпуклым многоугольником (здесь используется 1 и упражнение 1). В результате получим разбиение K = {K 1,..., Kl } множества M , состоящее из выпуклых многоугольников. Соединив теперь некоторую внутреннюю точку многоугольника Ki со всеми вершинами элементов K , попавшими на границу Ki , получим некоторую триангуляцию многоугольника Ki . Нетрудно заметить, что объединение таких триангуляций даст триангуляцию всего множества M . Теорема доказана.

Из теоремы можно вывести несколько следствий.

Следствие 1. Любую многоугольную фигуру и каждый многоугольник можно триангулировать.

Следствие 2. Класс k-множеств совпадает с классом многоугольных фигур.

1 Ломаная x = Èl = 1l = n [AlAl +1] называется замкнутой , если A 1 = An +1, и простой , если ее несмежные звенья не пересекаются.

2 Это множество называется внутренней областью ломаной

3 Множество называется ограниченным , если оно содержится в некотором круге.

4 Все отрезки считаются нетривиальными, т. е. Ai ¹ Bi для всех i Î I .

Конспект урока по математике в 4 классе II четверть

Тема: «Разбиение многоугольника на треугольники» (1 урок)

Организационный момент: (2 мин.)

Прозвенел уже звонок.

Начинается урок.

Куда мы с вами попадём –

Узнаете вы скоро.

В известном мультике найдём

Помощников весёлых.

Ребята, кто пришёл к нам в гости? (Серый волк и лиса). А почему именно эти герои? (Потому что скоро Новый год). В Новый год бывают разные приключения. И вот однажды одни мальчик и девочка написали письмо Деду Морозу и попросили Снеговика Почтовика доставить это письмо Деду Морозу. Но как вы уже знаете, снеговику по пути встретились лиса и волк, которые хотели отобрать письмо. Как вы думаете, что произошло со Снеговиком? (Когда Снеговик убегал от них, он рассыпался на части). Ребята, Снеговик просит вас помочь ему в его беде. Волк и лиса отдадут вам части Снеговика только тогда, когда вы выполните их задания.

(На доске фрагменты Снеговика)

Итак, ребята, за правильно выполненное задание волк будет отдавать вам фрагменты снеговика.

Актуализация знаний. Повторение пройденного материала. (2 -3 мин.)

Слайд 1

Ребята, посмотрите на слайд, какую геометрическую фигуру вы видите? (Многоугольник)

- Как называются отрезки красного цвета? (Сторона многоугольника)

Как называются отрезки зелёного цвета? (Диагональ)

Чем сторона многоугольника отличается от его диагонали?

(Сторона соединяет две соседние вершины, а диагональ соединяет две вершины, не принадлежащие одной его стороне)

Постановка цели и задач урока. (2 мин.)

Что делает диагональ с многоугольником? (Делит многоугольник на другие геометрические фигуры)

В нашем случае, на какие геометрические фигуры разбит многоугольник? (На треугольники)

Ребята, чему мы будем с вами сегодня учиться?

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

Первичное усвоение новых знаний . Работа с учебником .

( У учеников карточки с многоугольниками )

- Откройте учебник на стр. 108. Прочитайте задание №376

Слайд 2

В данном шестиугольнике проведи все возможные диагонали из одной его вершины. (Дети работают самостоятельно)

(Слайд 1). Один ученик разбивает шестиугольник на треугольник на слайде.

Сколько треугольников получилось? (4 треугольника).

Давайте построим шестиугольники и проведём в них всевозможные диагонали только из других вершин. (Дети выполняют построение шестиугольников и выполняют задание – у детей карточки с вершинами шестиугольников ).

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

Ребята, волк просит вас сделать вывод о проделанной вами работы.

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

Учитель даёт ребятам первый фрагмент туловища Снеговика, дети прикладывают его к голове Снеговика.

Слайд 3

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

Ребята, может быть у кого-нибудь из вас есть другие варианты?

Возможные варианты:

В каком случае прямоугольник разбит диагоналями, а в каких отрезками?

(1 вариант – диагоналями) – получают следующий фрагмент, прикрепляют к туловищу.

Слайд

Следующее задание волка.

Слайд 4

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

Ребята, кто знает, как это можно сделать?

Дети объясняют, как можно выполнить это задание.

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

Дети выполняют чертёж в тетради, затем учитель проецирует чертёж на слайде. Дети сверяют свой чертёж с чертежом на слайде.

За выполненное задание дети получают следующий фрагмент снеговика.

Работа в тетради

Слайд 5

Ребята, давайте вспомним, какие треугольники вы знаете? (Остроугольный, тупоугольный и прямоугольный).

Выберите из данных треугольников остроугольный. (Шаблоны на столах у ребят)



Начертите остроугольный треугольник и разбейте его на 3 треугольника. Один ученик выполняет задание на доске (шаблоны остр. треугольников на слайде)

Проверка чертежей. Дети сравнивают свои чертежи с чертежами на доске. (Получают фрагмент снеговика)

Выполнение задания №381. Работа с учебником

(Заготовки прямоугольников)

Ребята, прочитайте задание в учебнике № 381, что нужно сделать? Возьмите прямоугольник и при помощи линейки и карандаша разбейте его на 2 прямоугольных треугольников.

Ребята, что общего у получившихся треугольников?

У каждого есть прямой угол.

Как называется линия в прямоугольнике, которую вы провели?

Диагональ.

Согните прямоугольник по диагонали. Какой вывод вы можете сделать?

Диагональ делит прямоугольник на 2 равных прямоугольных треугольников.

(Получают фрагмент Снеговика)

Выполнение задания № 382. (Карточка с различными многоугольниками)

Учитель просит самостоятельно прочитать задание.

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

На доске проверяют решение. (Работа в парах)

Ребята, найдите площадь квадрата.

Дети выполняют решение на карточке. Проверяют вместе ответ. (Один ученик выполняет решение на доске)

Дети получают последний фрагмент снеговика.

Игра «Верёвочка»

Итог урока

Молодцы ребята, у вас получилось собрать снеговика. И теперь он сможет передать письмо деду Морозу.

Ребята, что вам понравилось на уроке? (ответ детей) А какие трудности у вас возникли? (ответ детей)

Помогли ли задания волка вам научиться чертить многоугольники и разбивать их на треугольники? Если у вас всё получилось, то поднимите зелёный смайлик. Если у вас возникали затруднения, то жёлтый смайлик. (ответ детей)

Что бы вы хотели пожелать волку в новом году?

(Пожелания ребят)

Учитель задаёт домашнее задание (Т стр. 88 №157 – 158). Слайд 6

Вместе разбирают выполнение домашнего задания

№2

№2

№2

№2

№2