Начнём с самого простого случая - 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 .

Песочница

незнакомец 6 апреля 2012 в 15:50

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

• Чулан *

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

Что нужно.

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

Теперь сам алгоритм.
Подготовка рабочих объективов.
Результатом работы должен быть список треугольников (result), потому создаем пустой список. Рабочий двунаправленный замкнутый список (points), представляющий многоугольник.
Перед стартом просчитываем углы для всех точек многоугольника.
Выбираем любую точку многоугольника как «рабочую» (p(i)).

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

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

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