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

[GANJE]

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

1) хватаем любую (первую) вершину и начинаем крутить;
2) для каждой итерации берём ограничивающий прямоугольник и находим его центр (элементарно - пересечение диагоналей);
3) сохраняем каждый предварительный центр относительно каждого поворота;
4) поворачиваем все центры обратно;
5) находим приближённый центр как центр тяжести предварительных центров.

Крутим раз 10-12. Даже на моём слабеньком компьютере все эти синусы-косинусы даже 1000 раз по 10000 (пробовала) вычислялись меньше чем за секунду, а кроме того, можно заранее составить таблицу, и каждый раз их вычислять вообще не придётся.

Чем плох простой центр тяжести?
Предположим, у нас есть многоугольник из 100000000 + 1 вершин. 100000000 вершин лежит близко к стороне правильного треугольника и изображает реки, леса, поля, птичек и кошечек. А 1 вершина находится на противолежащей вершине правильного треугольника. И тогда центр тяжести будет сколь угодно близок к "тяжёлой" стороне треугольника, чем больше нулей возьмём, тем ближе.

Зачем я это объясняю. Я пишу программу, которая будет работать с выкройками, а простейшее представление выкройки - многоугольник. Детали надо покрутить так, чтобы на тех отрезах произвольной формы, что есть у пользователя (он сам должен задать их), осталось как можно меньше неизрасходованной ткани. И соответственно, больше остатков можно было пустить в дело.

Что вы думаете по этому поводу? Думала использовать центр описанной вокруг выпуклого огибающего многоугольника окружности, но если многоугольник по форме будет близок к полуокружности, то центр будет рядом с краем, поэтому крутиться будет некрасиво. А надо чтобы удобно.
Да и ещё "построение минимальной выпуклой оболочки" мне показалось чем-то чудовищным, хотя если вникнуть, может не стоить и выеденного яйца.

-- 05.02.2018, 19:32 --

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

[atlakatl]

GANJE Вы сами понимаете, что излагаете? Последние 2 абзаца более-менее понял. Вы кладёте на куски ткани произвольных форм набор выкроек из кальки, так, чтобы отходов было, как можно меньше. Обычная численка, аналитики для общего случая там немного.
Но центр тяжести тут мало поможет.

[arseniiv]

Про частную задачу:

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

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

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

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

И тогда центр тяжести будет сколь угодно близок к "тяжёлой" стороне треугольника, чем больше нулей возьмём, тем ближе.

Про раскрой вообще:

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

Детали надо покрутить так, чтобы на тех отрезах произвольной формы, что есть у пользователя (он сам должен задать их), осталось как можно меньше неизрасходованной ткани.

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

[slavav]

Ищите алгоритм "минимальный описанный прямоугольник". На входе выпуклый многоугольник, на выходе минимальный по площади или периметру повёрнутый прямоугольник.
Но у нас невыпуклый многоугольник. Сделаем его выпуклым - построим выпуклую оболочку.
Для обоих подзадач есть много реализаций.

[GANJE]

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

Ищите алгоритм "минимальный описанный прямоугольник". На входе выпуклый многоугольник, на выходе минимальный по площади или периметру повёрнутый прямоугольник.
Но у нас невыпуклый многоугольник. Сделаем его выпуклым - построим выпуклую оболочку.
Для обоих подзадач есть много реализаций.

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

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

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

Была ещё идея найти точку, сумма расстояний до которой от всех вершин минимальна (для этого достаточно взять квадраты, а не сами расстояния, тогда можно избежать "тяжёлого" вычисления квадратного корня), но как?.. И потом, с тем треугольником, который я сочинила, то же самое получится. С триангуляцией было бы неплохо, спасибо, arseniiv, но центры надо вычислять как пересечение медиан, так что не знаю, опять головоломная геометрия, и минимальной оболочки всё равно не избежать.

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

А ещё у меня была соседняя задача пересечения невыпуклых многоугольников, но это уже для частичной автоматизации раскроя, усилий может уйти много, а толку будет мало. Это скорее для фирм, которые пишут такой софт.

[slavav]

Мы с вами говорим на разных языках.

Попробуйте другой подход: пусть задано направление вектором, найдите самую дальнюю точку в этом направлении (для этого служит скалярное произведение), поверните вектор на 90 градусов (это не сложно), найдите самую дальнюю точку в этом новом направлении. Повторите ещё два раза. Получится четыре точки, на которые натягивается прямоугольник одна сторона которого задана направлением. Вычислить координаты углов это прямоугольника не сложно.

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

Это простой алгоритм который строит то что вам надо с достаточной точностью.

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

[arseniiv]

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

но центры надо вычислять как пересечение медиан

Зачем-зачем, это как раз будет просто $(A+B+C)/3$. Площади тоже вычисляются легко (псевдоскалярным произведением), так что если будете пробовать находить барицентр всей штуки, самая трудность в триангуляции.

[slavav]

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

[GANJE]

Очередная гениальная идея!
Не надо никого крутить приблизительно, можно накрутить точно за 1 шаг. (Но для этого нужна оболочка.)
Последовательно просматриваем стороны выпуклого многоугольника и находим самую длинную (достаточно квадрата). Она будет лежать на стороне описанного прямоугольника, который нам нужен. Достраиваем прямоугольник, как тут советовали, и находим его середину. Всё!

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

P.S. А на матрицы у меня с детства аллергия.

[slavav]

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

[arseniiv]

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

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

О, это вообще прекрасно, запомню на будущее.

[wrest]

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

Предположим, у нас есть многоугольник из 100000000 + 1 вершин. 100000000 вершин лежит близко к стороне правильного треугольника и изображает реки, леса, поля, птичек и кошечек. А 1 вершина находится на противолежащей вершине правильного треугольника. И тогда центр тяжести будет сколь угодно близок к "тяжёлой" стороне треугольника,

Это если вершины массивные. А если вершины с нулевой массой, то центр тяжести будет в центре тяжести треугольника.

[levtsn]

Методом Монтекарла.

[slavav]

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

[GANJE]

Что я делаю не так. Сейчас скопирую комментарии.

i = [1; nCentres]
{
   поворачиваем копию многоугольника:
   j = [1; nVertex]
   {
      поворот каждой вершины вокруг временного центра на угол, равный 2 пи / количество центров
      (при любом выбранном центре вращения все центры для каждого угла ложатся в одну точку,
      что косвенно свидетельствует о правильности алгоритма)
   }
   находим его центр
   поворачиваем его обратно вокруг предварительного центра на угол, равный (2 пи / количество центров) * i
   добавляем к имеющимся
}
делим на общее число центров - находим центр тяжести всех этих приближённых центров.

Вроде всё работает довольно интересно, хотя чувствуется некоторый дискомфорт. С произвольными точками и невыпуклыми полигонами должно работать так же, потом проверю, сейчас очень устала. Вначале приближённый центр падал в прежнюю точку, пока не вспомнила, что надо каждый новый центр охватывающего прямоугольника поворачивать обратно на тот угол, на который был повёрнут многоугольник.
Картинки для сравнения (первая старая):



Разумеется, первый центр прямоугольника (сиреневый на первой картинке) лежит на зелёной капле, значит, ничего не напортачила. Количество предварительно вычисленных центров - 71. Причём когда было чётное число, количество зелёных точек драматически падало. Видимо, потому что 2пи / 2. С числом 6 это было особенно заметно.
Нет сил думать, надеюсь, вам было интересно.

Всё-таки не удержалась и попробовала случайные точки. Прикольно. К сожалению из-за ограничений пришлось ужать картинку. Количество поворотов - 21.