Найдите вращение, в котором фигура имеет наименьшую возможную ширину по оси X

Question

Я играю с проблемой формы, и я ищу более умное решение, чем то, что я смог придумать.

Вот проблема:

У меня естьнабор точек, которые образуют замкнутую форму на декартовой сетке, скажем, A (-1,0), B (1,0) и C (0,4), которая образует острый треугольник.

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

При учете формы выше этого расстояния будетрасстояние между A и B. В то время как для более интересных фигур между точками могут быть более короткие расстояния, я полагаю, что нет способа повернуть форму выше, так что западная и восточная большинство точек меньше, чем расстояние между A и B.

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

Есть идеи?

Answer 1

Выполните анализ основного компонента и выровняйте основной компонент по оси y.Это оптимизирует «среднее» квадратное расстояние от каждой точки до оси y (то есть ширину по оси x).Возможно, это также является оптимальным или близким к оптимальному по вашим критериям.

См .: http://en.wikipedia.org/wiki/Principal_component_analysis

Альтернативное решение (Оптимальное решение):

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

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

Сложность: O(nlogn) для выпуклой части корпуса и O(m^2) для второй части, где m - количество точек на выпуклой оболочке.

Answer 2

Вращающиеся суппорты - хороший инструмент для решения этой проблемы.

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

Answer 3

Пусть {N} будет набором точек, определяющих наименьший выпуклый многоугольник, содержащий вашу форму, отсортированный по порядку по часовой стрелке. Для каждого края (N - 1, N): определите расстояние от этого края до самой дальней точки. Возьмите самое короткое из этих расстояний и поверните свою форму так, чтобы соответствующий край был перпендикулярен оси X.

Answer 4

Я не слишком уверен в вашем понимании математики, поэтому, пожалуйста, примите мои извинения, если это идет над вашей головой, или если это действительно слишком просто объясняется, но решение, которое мне сразу же пришло в голову, - это использовать анализ Фурье на дискретной выборке ширины многоугольника под фиксированными углами.

Ваш подход к вращению на небольшую величину и тест можно считать дискретной выборкой непрерывной функции.

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

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

Мы знаем, что, поскольку вы вращаетесь через радианы с 2ПИ, функция ширины будет периодической с 2ПИ, и поэтому вы могли бы идеально реконструировать функцию, учитывая, что выбрано достаточное количество углов, применяя анализ Фурье.

Вопрос в том, сколько сэмплов нужно для идеальной реконструкции функции?

Я думаю, это определяется наименьшим расстоянием между граничными точками.

ceil(perimiterLength/smallestDistanceBetweenPoints);

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

Выборка точек в восточном и западном направлениях в n точках с равномерно распределенными углами через радианы 2PI и построение графика их разности в виде функции угла в n-точечной ширине.

Возьмите преобразование Фурье этого графика, чтобы получить наборы вещественных коэффициентов ряда Фурье, необходимые для определения функции расстояния

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

Итак, я полагаю, что для вас в качестве примера треугольника вы определите, что вам нужно ceil (3 + root (3)) = 5 семплов. Рассчитайте расстояние в 0 2pi / 5 4pi / 5 6pi / 6 и 8pi / 5, возьмите преобразование Фурье этого результата и восстановите сигнал, создав формулу, подобную

a0 + a1 sin (t) + a2 sin (2t)

И тогда вы должны определить минимум этой функции (для которой есть много опций)