2

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

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

Проделываем операцию N-ое количество раз, пока не найдем прямую, сумма весов точек по обе стороны от которой будет максимальна.

Почему мне не нравится данный метод? Не факт, что он будет верно работать, а так же я вынужден производить эти действия N раз, и чем больше - тем точнее, и поэтому это слишком накладно. Что можно сделать, чтобы найти вектор с меньшими затратами?

0

2 ответа 2

0

"Всё давно придумано." Геннадий Хазанов

Главные оси и главные моменты инерции.

Найдите центр тяжести набора точек. Потом - моменты инерции относительно осей параллельных осям координат и проходящих через центр тяжести, а также центральный момент инерции относительно центра тяжести. Ориентация главных осей:

tan(2a) = 2 Iyx / (Iy - Ix)

http://www.soprotmat.ru/geom2.htm

http://mysopromat.ru/uchebnye_kursy/sopromat/geometricheskie_harakteristiki/glavnye_osi_glavnye_momenty_inertsii/

Update

Если распределение точек внутри "наклонного прямоугольника" неравномерное, для нахождения центра тяжести и моментов инерции надо использовать не набор точек, а огибающий выпуклый многоугольник - convex hull (https://en.wikipedia.org/wiki/Convex_hull).

2
  • Не совсем понимаю, что значит "ориентация главных осей". Угол я нашел, и если мнимый прямоугольник отклонен на < PI / 4, то все вроде нормально, но если отклонять больше, то угол не растет, а начинает уменьшаться. Как будто это минимальный угол между осью координат и одной из главных осей. Это так и есть?
    – selya
    28 ноя 2017 в 22:22
  • да. В конце концов у Вас будет два перпендикулярных направления, возьмите то, относительно которого момент инерции меньше - это и будет продольная ось "прямоугольника".
    – user176262
    28 ноя 2017 в 22:35
-1

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

Я бы сделал примерно следующее. Буду описывать без формул, их уже сами выбирайте для достижения результата.

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

ЗЫ Если слишком сложно, могу картиночки нарисовать, но очень не хочется. Читайте алгоритм и рисуйте картиночки сами, на бумаге станет яснее.

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

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

ЗЫЫЫ Формулы, которые вам понадобятся, вполне простые из начальных курсов геометрии.

ЗЫЫЫЫ Данное решение основано на интуиции и его верность мне сейчас доказывать не хочется.

8
  • "четырехугольников ... средняя величина углов которого будет как можно ближе к 90 градусов" - priceless
    – user176262
    28 ноя 2017 в 14:16
  • @Igor, да, вы правы, что то здесь не так :D Ща поправлю )
    – iRumba
    28 ноя 2017 в 17:19
  • Интересуюсь, от чего зависит средняя величина углов в четырехугольнике.
    – user176262
    28 ноя 2017 в 17:20
  • @Igor, да все, все, я понял свою ошибку. Уже исправил )
    – iRumba
    28 ноя 2017 в 17:21
  • @igor, сложно было сформулировать без четкого определения прямоугольника нечто вроде "фигура похожая на прямоугольник". Общий смысл проверки такой: "из всех четырехугольников выбрать тот, который больше всего похож на прямоугольник". А в остальном как считаете, способ рабочий?
    – iRumba
    28 ноя 2017 в 17:28

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.