Нахождение стабильного размещения неправильной (невыпуклой) формы

Question

Учитывая изображение 2-мерной неправильной (невыпуклой) формы, как бы я мог рассчитать все способы, которыми он мог бы устойчиво лежать на плоской поверхности? Например, если форма представляет собой идеальный квадратный прямоугольник, то у него, безусловно, будет 4 способа обеспечения стабильности. С другой стороны, окружность либо не имеет устойчивой ориентации, либо каждая точка имеет устойчивую ориентацию.

РЕДАКТИРОВАТЬ: есть эта милая маленькая игра под названием Splitter (Осторожно, захватывающая игра впереди), которая кажется близкой к тому, что я хочу. Заметил, что если вы отрежете кусок дерева, он упадет на землю и будет лежать устойчиво.

РЕДАКТИРОВАТЬ: В конце концов, подход, который я выбрал, состоит в том, чтобы вычислить центр масс (фигуры) и вычислить выпуклую оболочку (используя OpenCV), а затем перебрать каждую пару вершин. Если центр масс падает поверх линии, образованной двумя вершинами, он считается стабильным, иначе нет.

Answer 1

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

Выпуклый корпус и центр масс http://walkytalky.net/extern/hull.png

Если корпус является многоугольником, то устойчивое положение - это положение, в котором фигура опирается на одну из сторон, а КМ находится непосредственно над этой стороной (не обязательно над средней точкой стороны, просто где-то над ней). .

Если у корпуса есть изгибы (то есть, если у формы есть изгибы, которые касаются корпуса), они должны подвергаться особой обработке. Форма будет устойчивой, если она опирается на изогнутый край, если КМ находится непосредственно над самой нижней точкой кривой, а радиус кривой в этой точке превышает высоту КМ.

Примеры:

1. Прямоугольник. Корпус - это просто прямоугольник, а CM находится в центре. Форма стабильна на каждой из четырех сторон.
2. Прямоугольник с выдолбленными сторонами, но углы все еще целы. Корпус по-прежнему является исходным прямоугольником, а КМ находится там, где он был раньше. Все четыре стороны корпуса по-прежнему стабильны (то есть вы можете по-прежнему сохранять форму на любых двух углах).
3. Круг. СМ находится в центре, корпус - это круг. Не существует устойчивых позиций, так как радиус кривой всегда равен высоте CM. Дайте этому легкое прикосновение, и это будет катиться.
4. Эллипс. CM находится в центре, корпус имеет форму. Сейчас есть две стабильные позиции.
5. Полукруг. КМ находится где-то на оси симметрии, корпус - это форма. Две стабильные позиции.
6. Узкий полукруглый полумесяц. Корпус полукруг, CM находится за пределами формы (но внутри корпуса). Две стабильные позиции.

Иллюстрация примеров http://walkytalky.net/extern/stable.png

(Положение эллипса, помеченное знаком X, нестабильно, поскольку кривизна меньше расстояния до центра масс.)

Answer 2

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

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

Обратите внимание, что это фактически физическое определение вращательного равновесия, как следствие ньютоновской вращательной кинематики.

Для правильного многоугольника, если мы исключим случаи, когда он стоит на единственной вершине, это определение эквивалентно устойчивой позиции.

Итак, если у вас прямая гравитация вниз, сначала найдитесамые левые и самые правые его части, которые касаются земли.

Затем вычислите свой центр масс. Для многоугольника с известными вершинами и равномерной плотности эта проблемасводится к поиску Centroid ( соответствующий раздел ).

После этого удалите строку из вашего CoM;если пересечение CoM и земли находится между этими двумя значениями x, оно находится в равновесии.

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

Обратите внимание, что это также может быть использовано для измерения "насколько устойчив" объект - эта мера является максимальным y-расстоянием, на которое Центр масс может двигаться доон больше не находится в пределах диапазона между двумя контактными точками.

РЕДАКТИРОВАТЬ: изящная диаграмма, сделанная наспех

Диаграмма http://img52.imageshack.us/img52/9506/1276930988102131dc.png

Итак, как вы можете использовать это, чтобы найтивсе способы он может сидеть на столе?См .:

---

РЕДАКТИРОВАТЬ

Программируемый подход

Вместо дорогостоящей задачи вращения формы, попробуйте это вместо этого.

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

Найдите вершины выпуклой оболочки вашей фигуры (в основном, ваша фигура, но со всеми вогнутыми вершинами)- вершины, которые "вставлены" - исключены).

Затем выполните итерацию по каждой из пары смежных вершин на вашей выпуклой оболочке (т. е. если бы у меня были вершины A, B, C, D, I 'повторить AB, BC, CD, DA)

Выполните этот тест:

1. Нарисуйте линию A через две тестируемые вершины
2. Нарисуйте линию, перпендикулярную A , проходя через CoM C .
3. Найдите пересечение двух линий (простая алгебра)
4. Еслизначение y пересечения находится между значением y двух вершин, оно устойчиво.Если все значения y равны, сравните значения x.

Это должно сработать.

Вот пример теста, выполняемого на одной паре вершин:

Пример теста http://img17.imageshack.us/img17/918/stabled.png

Если ваша форма не представлена ​​его вершинами в структуре данных, вам следует попытаться преобразовать их.Если это что-то вроде круга или эллипса, вы можете использовать эвристику, чтобы угадать ответ (круг имеет бесконечные положения равновесия; эллипс 4, хотя только две «устойчивые» точки).Если это изогнутая, шаткая неправильная форма, вам придется предоставить свою структуру данных, чтобы я мог помочь в программном отношении, вместо того, чтобы просто предоставлять эвристику в каждом конкретном случае.

Answer 3

Я уверен, что это не самый эффективный алгоритм, но это идея.

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