Алгоритм Oriented Bounding Box, Нужно некоторое понимание / уточнение нескольких строк существующего (рабочего) кода

Question

Я рассматриваю некоторый код MATLAB, который общедоступен в следующем месте: https://github.com/mattools/matGeom/blob/master/matGeom/geom2d/orientedBox.m

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

В строке 44: hull = bsxfun(@minus, hull, center);. По-видимому, это переводит все точки в наборе выпуклой оболочки, поэтому вычисленный центроид находится в (0,0). Есть ли какая-то конкретная причина, почему это выполняется? Мое единственное предположение состоит в том, что позднее в коде допускается прямое вращательное преобразование, поскольку вращение вокруг реального источника вызовет значительные проблемы.

В строках 71 и 74: indA2 = mod(indA, nV) + 1;, indB2 = mod(indB, nV) + 1;. Это трюк, чтобы предотвратить выход индекса доступа за пределы? Мое предположение состоит в том, чтобы запретить доступ через границы, он перевернет индекс при достижении конца.

В строке 125: y2 = - x * sit + y * cot;. Это правильное преобразование, так как код ведет себя правильно, но я не уверен, почему это на самом деле используется и отличается от других вращательных преобразований, выполненных позже, а также ранее (с вызовами rotateVector). Мое лучшее предположение, что я просто не представляю, что вращение нужно сделать в моей голове правильно.

Примечание: внешняя функция вызывает vectorAngle, rotateVector, createLine и distancePointLine все можно найти в одном и том же хранилище, в файлах, названных по имени функции (согласно стандарту MATLAB). Они относительно неинтересны и делают то, что вы ожидаете, за исключением того факта, что происходит нормализация векторных углов.

Answer 1

Я на самом деле не смотрел на код, это объяснение того, как работают вращающиеся суппорты.

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

• попробуйте каждое ребро по очереди;

• для данного ребра, рассматриваемого как горизонтальное, на юг, найдите самые дальние вершины к северу, западу и востоку;

• оценивают площадь или периметр прямоугольника, который они определяют;

• запоминают наилучшую область.

Важно отметить, что при переходе от ребра к следующему вершины N / W / E могут двигаться только вперед, и их легко найти, найдя следующее уменьшение соответствующая координата. Таким образом, общее время обработки линейно по числу ребер (поиск начальных вершин N / E / W требует 3 (N-3) сравнений, затем обновления занимают 3 (N-1) + Nn + Nw +). Ne сравнения, где Nn, Nw, Ne - количество ходов от вершины к следующей; очевидно, всего Nn + Nw + Ne = 3N) индексация ребер и вершин.

Answer 2

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

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

Строка 44 -> цель перевода в происхождение состояла в том, чтобы улучшить числовую точность. Когда многоугольник расположен далеко от начала координат, координаты могут быть большими и близко друг к другу. Многие вычисления включают произведения координат. Посредством перемещения многоугольника вокруг начала координат координаты меньше, и ожидается, что точность получаемых продуктов улучшится. Ну, если честно, я не наблюдал этот эффект напрямую, это более осторожный способ кодирования, чем исправление ...

Строка 71-74! Да. Идея состоит в том, чтобы найти индекс следующей вершины вдоль многоугольника. Если текущая вершина является последней вершиной многоугольника, то следующий индекс вершины должен быть 1. Использование масштабирования по модулю между 0 и N-1. Две строки гарантируют правильную итерацию.

Строка 125: есть несколько преобразований. Используя функцию rotateVector (), можно просто вычислить минимальное значение для данного ребра. На линии 125 поверните точки (выпуклой оболочки), чтобы выровнять их в «лучшем» направлении (то, которое минимизирует ширину). Последнее изменение координат (линии 132-> 140) связано с тем, что центр ориентированного прямоугольника отличается от центра многоугольника. Затем мы добавляем сдвиг, который корректируется поворотом.