Порядок из хаоса или эллипс из произвольного многоугольника

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

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

Алгоритм приводит к эллипсу (фигуре, аппроксимирующей эллипс), только когда у исходного многоугольника больше четырех вершин. В ином случае мы получим серию подобных многоугольников: при трех вершинах — серию треугольников, при четырех — четырехугольников.

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

Последовательность простых многоугольников, не содержащих самопересечений, стороны которых поделены в отношении ?, называется последовательностью срединных многоугольников (midpoint polygons). Если на каждом шаге алгоритма делить стороны многоугольника в иной пропорции, мы получим последовательность производных многоугольников (derived polygons).

Известно, что производные многоугольники в конце концов приводят к многоугольнику, у которого противоположные стороны параллельны и имеют одинаковую длину. Эллипс — частный случай такого многоугольника. Однако более общее утверждение доказывает, что мы получим эллипс при любой пропорции деления сторон! При этом диаметры эллипса будут немного осциллировать, то есть колебаться относительно направления в 45 градусов.

> Доказательство приведено в статье К. Вандебогерта "Random polygon to ellipse: a generalization", свободно доступной для скачивания (https://arxiv.org/abs/1606.08888).

Также есть по крайней мере два строгих доказательства того, что при использовании алгоритма ? мы построим аппроксимацию эллипса.

> Одно основано на применении свертки, дельта-функции и разложения в ряд Фурье.

https://almostcomplexstructure.wordpress.com/2020/04/16/from-polygon-to-ellipse-a-proof/

> Другое использует матричные вычисления, сингулярное разложение и анализ собственных значений матриц.

Elmachtoub & Loan (2010) From random polygon to ellipse: an eigenanalysis.

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

Визуализация Ясона Девиса (Jason Davies) показывает преобразования 10- и 100-угольников в эллипс. В случае 100-угольника для получения эллипса придется подождать несколько минут.

https://www.jasondavies.com/random-polygon-ellipse/

Источник: arxiv.org

Комментарии: