Триангуляция круга

[netang]

Здраствуйте!
Передо мной встала такая задача. Имею число $n$ -- количество точек, лежащих на окружности и равноудаленных друг от друга.
Получаю их следующим образом:

$h = \frac{360^{\circ}}{n}, \quad \overline{p}_i = (R\sin(hi); R\cos(hi)), \quad i = \overline{1,n},$
где R -- радиус окружности.

Есть критерий качества треугольников
$\displaystyle q = \frac{4S\sqrt{3}}{a^2+b^2+c^2}, \quad q > 0.6 - good!$
Где a, b, c -- длинны сторон треугольника, S -- площадь треугольника.
Необходимо построить (написать алгоритм) "хорошую" триангуляцию, чтобы она удовлетворяла критерию качества, приведенному выше и алгоритм построяния, к которой, имел небольшую сложность.
Хотелось бы получить более менее математически обоснованный алгоритм.
Самые первые мысли, которые приходят мне в голову -- добавить дополнительные окружности в исходную окружность, имеющие тот же центр, что и исходная окружность и размещать точки на них. При этом $R - R_1 \approx \frac{2\pi R}{n},$
где $2\pi R$ -- длина исходной окружности, $R_1$ -- радиус соседней к исходной окружности.

[slavav]

Ваш критерий качества треугольников имеет геометрический смысл. Какой?

[netang]

slavav в сообщении #1129472 писал(а):

Ваш критерий качества треугольников имеет геометрический смысл. Какой?

Треугольник, который, по подобию, стремиться к равностороннему треугольнику будет иметь "хорошее" качество. То есть $q$ будет стремиться к единице. Углы не должны быть слишком острыми и тупыми.

[slavav]

Согласен. Пусть две вершины треугольника заданы. Опишите геометрическое место третьей вершины для получения хорошего треугольника.

[netang]

Для начала подсчитаем высоту для наших треугольников.
$a = 2R\sin{\frac{\pi}{n}}$
$h =\frac{ a\sqrt{3}}{2},$
где a -- расстояние между двумя соседними вершинами нашего правильного многоугольника вписанного в окружность, h -- высота нашего треугольника.
$r = R\cos{\frac{\pi}{n}} $ -- растояние от центра окружности до центра отрезка, образуемого двумя соседнми вершинами.
$e = R - r$ расстояние от отрезка, образуемого двумя соседнми вершинами до окружности
$l = R - h - e$ -- расстояние, на котором должны находится точки от центра окружности чтобы критерий качества давал хорошие результаты.
Имея вектор (0; $l$) умножаем его на матрицу поворота и устанавливаем точки в нужных нам местах.

Но это только для "первого уровня", а что с другими? Возможно, если продолжать применять такую последовательность действий для остальных "уровней" мы можем получить "нехорошие" треугольники.
На radical не получилось залить. Вот что получилось. [https://yadi.sk/i/Osb2e-s2sKJBL]
P.S. Как плохо расписал, торопился. Нарисую рисунки к посту, исправлюсь.

[slavav]

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

-- 07.06.2016, 15:53 --

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

[netang]

slavav в сообщении #1129734 писал(а):

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

Можно использовать меньшее число вершин на следующем уровне, чем на предыдущем при движении от окружности к её центру. Сейчас подумаю, куда точки лучше всего потавить.

slavav в сообщении #1129734 писал(а):

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

На растоянии $h$ от окружности?

[slavav]

Нет, не h. Эта область хорошего $q$ - два круга. Их центры и радиусы зависят только расстояния между парой точек. Новую окружность для триангуляции надо провести примерно через центры этих кругов (круги строятся для пар точек на исходной окружности). Тогда на новой окружности вы сможете разместить примерно в два раза меньше точек. И так далее. Но чтобы навести на эти мысли "математику" надо всё-таки точно описать области хорошего $q$.

[ewert]

Если $n$ достаточно велико, то ширина одной полоски, выложенной почти равносторонними треугольниками, составит примерно $\frac{5R}{n}$. По мере достроения полосок их ширина не должна существенно изменяться, и в конце (вблизи центра) должно остаться где-то от трёх до восьми отрезков (так, чтобы оставшиеся вершины можно было более-менее безнаказанно соединить с центром). Это означает, что в каждой следующей полоске надо схлопывать примерно пять треугольничков, примерно равномерно расположенных на соответствующей окружности.

[slavav]

У вас будет $O(n^2)$ новых точек. Это много. Надо стараться схлопывать определённую долю точек, чтобы получить $O(n)$.

[ewert]

slavav в сообщении #1130282 писал(а):

У вас будет $O(n^2)$ новых точек. Это много.

У всех так будет, т.к. к-то точек на границе по порядку величины пропорционально периметру, а точек вообще -- пропорционально площади.

[slavav]

Прямоугольный треугольник подходит под критерий "хорошести". Вообразите горизонтальную полосу высотой 1. На верхней стороне полосы стоят с координатами вида $(i, 1), i \in \mathbb{Z}$. На нижней $(2i, 0), i \in \mathbb{Z}$. Триангулируйте полосу прямоугольными треугольниками. Тоже можно проделать на окружности, запас "хорошести" ещё есть. Верх полосы соответствует наружной окружности, низ - внутренней. На внутренней окружности будет примерно в два раза меньше точек. И так далее с линейным общим результатом.

[ewert]

slavav в сообщении #1130289 писал(а):

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

И выйдет очень красиво, но практически совершенно бесполезно. Поскольку триангуляция если бывает нужна, то вовсе не из спортивного или эстетического интересу, а для сугубо практических целей. Обычно -- для решения каких-либо краевых задач разностными методами. В которых "шаги" (размеры треугольников) должны быть много меньше размера всей области. У Вас же эти размеры получатся одного порядка.

Т.е. Вы получите очень простую и элегантную, но абсолютно неработоспособную схему.

[slavav]

Я решаю поставленную TC. Вы решаете задачу более строгую - c глобальными ограничениями на площадь треугольников.

[netang]

Извините, что сразу не сообщил, мне триангуляция нужна для применения метода граничных элементов.
Нашел способ распределения точек на "подуровнях". Простой, но работает. Берем в центре одну точку, на внешней окружности $N$ точек. Определяем сколько точек лежит на подуровнях -- пропорцией. Далее я применяю готову функцию delaunay(x, y) из пакета matlab, хотя можно самому вершины склеивать.
https://yadi.sk/i/Jr4jcVQAsQNar
https://yadi.sk/i/GemiE1fQsQNay