Песочница

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

• Чулан *

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

Что нужно.

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

• Создаем пустой список для хранения временных треугольников.
  Если точка слева от «рабочий» (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. Можно раскрашивать не грани, а рёбра или вершины.

Конспект урока по математике в 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