Нахождение центра произвольного многоугольника

[Vince Diesel]

Если что, центр масс многоугольника умеет считать математика, команда RegionCentroid. Например,

A = Polygon[{{-1, 0}, {0, -5}, {1, 0}, {0, -3}}];
M = RegionCentroid[A]
Graphics[{{LightBlue, A}, {Black, Point @@ A}, {Green, PointSize[Medium], Point[M]}}] 

Можно пользоваться этим кодом здесь.

[GANJE]

Получилось довольно интересно (поворот на 20 градусов, больше было лень):

С полукольцами эллипсов тоже выглядит круто и вертится аккуратно:




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

[GANJE]

Тут вот ещё в соседних темах много красивых слов писали о триангуляции, а можно ли произвольный несамопересекающийся многоугольник триангулировать только с использованием его вершин?

P.S. С мятыми эллипсами интересные узоры получаются:

[slavav]

Да, можно.

[GANJE]

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

Да, можно.

А есть какой-нибудь понятный лирикам способ сделать это за время $O(2 \cdot N)$?
И если уж получится так просто триангулировать полигон, где можно посмотреть формулы пересечения двух треугольников? Получается, они заданы тремя векторами $(x_{1,1}, y_{1,1})$, $(x_{1,2}, y_{1,2})$, $(x_{1,3}, y_{1,3})$ и $(x_{2,1}, y_{2,1})$, $(x_{2,2}, y_{2,2})$, $(x_{2,3}, y_{2,3})$. Тогда задача проверки на пересечение двух многоугольников будет порядка $O(N^2)$.
Математическое форматирование класс!

[slavav]

О триангуляции многоугольника:
Поставить задачу можно за час. Сложность будет $O(N^2)$.
За день можно объяснить как сделать триангуляцию за $O(N\log N)$.
Несколько дней уйдёт на разбор алгоритма за $O(N)$.

Так как после триангулирования вы собираетесь пересекать многоугольники за квадратичное время, то вам подойдёт первый вариант.

Но за квадрат можно проверить пересечение двух многоугольников без триангуляции. Технически такая проверка реализуется проще чем триангуляция.

-- 07.02.2018, 23:11 --

Проверка пересечения многоугольников - стандартный алгоритм. Есть много реализаций. Рекомендую искать готовое решение.

[wrest]

GANJE в сообщении #1290943 писал(а):

можно ли произвольный несамопересекающийся многоугольник триангулировать только с использованием его вершин

Если неизвестно как соединены вершины -- то нет. Возьмите например регулярную сетку 6x6 вершин: их можно соединить в разные многоугольники, без самопересечений, например в форму буквы "Ш" - с перекладиной снизу, сверху "m" или сбоку "Е" и "З", посередине "Ж". Или в виде буквы "S", и т.п.

[GANJE]

wrest в сообщении #1290977 писал(а):

Если неизвестно как соединены вершины -- то нет. Возьмите например регулярную сетку 6x6 вершин: их можно соединить в разные многоугольники, без самопересечений, например в форму буквы "Ш" - с перекладиной снизу, сверху "m" или сбоку "Е" и "З", посередине "Ж". Или в виде буквы "S", и т.п.

Можно нарисовать?

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

Проверка пересечения многоугольников - стандартный алгоритм. Есть много реализаций. Рекомендую искать готовое решение.

Что-то есть и на этом форуме. Спасибо! Вот вам:


-- 08.02.2018, 00:28 --

С формой буквы Ш у меня получилось:

[wrest]

GANJE в сообщении #1290978 писал(а):

Можно нарисовать?

Одинаковый набор вершин, разные многоугольники, самопересечений нет:


-- 07.02.2018, 23:56 --

GANJE в сообщении #1290978 писал(а):

С формой буквы Ш у меня получилось:

У вас там 12 вершин, а не 36.

[GANJE]

wrest в сообщении #1290992 писал(а):

Одинаковый набор вершин, разные многоугольники

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

[wrest]

GANJE в сообщении #1290996 писал(а):

Даже мне видно, что элементарно разбивается:

Вы же спрашивали, можно ли если известны только вершины плюс известно что самопересечений нет. Я вам ответил, что если стороны неизвестны, то нельзя. А если стороны известны - то конечно можно.

Ну вот есть у вас 36 точек, а как они соединены - в букву Ш или букву S неизвестно. Как будете триангулировать?

[GANJE]

Я вовсе такого не писала! Как это может быть многоугольник неизвестен быть, есть есть все точки по порядку - с первой по последнюю?!

[wrest]

GANJE в сообщении #1291099 писал(а):

Я вовсе такого не писала!

Ок, значит я не так понял.

[GANJE]

А как бы оценить расстояние до отрезка? Я хочу добавлять вершины к многоугольнику, для этого можно разбивать одно из рёбер - ближайшее к курсору мыши. С вершинами просто, достаточно найти самый маленький квадрат расстояния. А с отрезками так не получится. Сперва думала, что достаточно будет выбрать для каждого из рёбер минимальное расстояние до краёв и середины, но с длинными такая оценка не подходит. Кажется, не обойтись без нормалей и проверки, попадает ли точка пересечения нормали с прямой в отрезок. Потому что если у нас длинное ребро, а курсор находится близко к середине первой половины, а рядом с ним, но дальше длинного ребра будет короткое, то такая оценка даст меньшее расстояние до малого ребра, чем до края и середины длинного отрезка.

[wrest]

GANJE
Пусть $x$ - длина ребра, $y$ и $z$ -- расстояния от точки до концов ребра.
Тогда если $x^2+y^2-z^2>0$ и $x^2+z^2-y^2>0$ то перпендикуляр попадает внутрь ребра. Если одно из них равно нулю, то перпендикуляр попадает в один из концов ребра, если разные знаки, то расстояние равно $y$ или $z$ (в зависимости от того что получится отрицательным). Ну а если оба отрицательные...