2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 12:14 
Если что, центр масс многоугольника умеет считать математика, команда 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]}}]

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 14:15 
Аватара пользователя
Получилось довольно интересно (поворот на 20 градусов, больше было лень):
Изображение
С полукольцами эллипсов тоже выглядит круто и вертится аккуратно:
Изображение

Изображение

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 20:39 
Аватара пользователя
Тут вот ещё в соседних темах много красивых слов писали о триангуляции, а можно ли произвольный несамопересекающийся многоугольник триангулировать только с использованием его вершин?

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

Изображение

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 20:55 
Да, можно.

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 22:51 
Аватара пользователя
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)$.
Математическое форматирование класс! :appl:

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

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

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

-- 07.02.2018, 23:11 --

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 23:15 
GANJE в сообщении #1290943 писал(а):
можно ли произвольный несамопересекающийся многоугольник триангулировать только с использованием его вершин

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 23:21 
Аватара пользователя
wrest в сообщении #1290977 писал(а):
Если неизвестно как соединены вершины -- то нет. Возьмите например регулярную сетку 6x6 вершин: их можно соединить в разные многоугольники, без самопересечений, например в форму буквы "Ш" - с перекладиной снизу, сверху "m" или сбоку "Е" и "З", посередине "Ж". Или в виде буквы "S", и т.п.
Можно нарисовать?

slavav в сообщении #1290975 писал(а):
Проверка пересечения многоугольников - стандартный алгоритм. Есть много реализаций. Рекомендую искать готовое решение.
Что-то есть и на этом форуме. Спасибо! Вот вам:
Изображение

-- 08.02.2018, 00:28 --

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 23:50 
GANJE в сообщении #1290978 писал(а):
Можно нарисовать?

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

-- 07.02.2018, 23:56 --

GANJE в сообщении #1290978 писал(а):
С формой буквы Ш у меня получилось:

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение07.02.2018, 23:59 
Аватара пользователя
wrest в сообщении #1290992 писал(а):
Одинаковый набор вершин, разные многоугольники

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение08.02.2018, 00:05 
GANJE в сообщении #1290996 писал(а):
Даже мне видно, что элементарно разбивается:

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

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

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение08.02.2018, 13:12 
Аватара пользователя
Я вовсе такого не писала! Как это может быть многоугольник неизвестен быть, есть есть все точки по порядку - с первой по последнюю?!

 
 
 
 Re: Нахождение центра произвольного многоугольника
Сообщение08.02.2018, 13:17 
GANJE в сообщении #1291099 писал(а):
Я вовсе такого не писала!

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

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

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

 
 
 [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group