Структура данных для кусочно-круговой траектории на плоскости

Question

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

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

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

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

У кого-нибудь есть какие-либо идеи / советы высокого уровня, которыми можно поделиться?

Answer 1

Для наиболее эффективного прохождения траектории, если я прав, вам нужно

• конечные криволинейные абсциссы каждой дуги (накопительные),

• радиусы,

• начальные углы,

• координаты центров,

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

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

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

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

---

Для удобного вычисления, зная s и индекс дуги, рассмотримвекторы от центра к центрам соседних дуг.Поверните их так, чтобы первый стал горизонтальным.Компоненты другого даст вам угол амплитуды.Доля (s - Si-1) / (Si - Si-1) амплитуды дает вам азимут точки, к которой вы применяете встречное вращение.

Answer 2

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

Поскольку вам нужна непрерывность (тот же самый x, y, тот же самый подшипник, возможно, та же самая кривизна) между двумя конечными точками, тогда node с этими свойствами необходим. Обратите внимание, что эти свойства являются общими для дуг и прямых (специальная дуга, обозначенная радиусом = 0). Таким образом, вы можете рассматривать node так же, как item.

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

Контейнер зависит от того, как вы запрашиваете информацию.
Если траектория может быть каким-то образом представлена ​​в сетке, то лучше использовать квад-дерево.
Полагаю, вы должны найти предмет из x,y или accumulated length ввода. Вам придется перебирать контейнер, чтобы найти элемент, ближайший к входным данным. Сортированные данные могут помочь.

Мой выбор - простой вектор с последовательными элементами, который сортируется по накопленной длине траектории.

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