Как ограничить пространство поиска, используя прямоугольный буфер 2D вдоль отрезка 2D линии

У меня есть 2D линейные сегменты, извлеченные из изображения. Так что я знаю их конечную точку. Кроме того, у меня есть некоторые ссылочные сегменты 2d линии. Оба отрезка линии теперь в векторной форме. Сравнивая со ссылочными и извлеченными строками, я получаю огромное количество выделенных отрезков.

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

(1) Мой первый вопрос — как я могу реализовать этот буферный случай с помощью c ++, поскольку мне не хватает геометрических теорий.

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

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

На самом деле, я ищу геометрический базовый метод

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

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

черная линия — опорная линия и пунктирные линии — извлеченные линии на основе изображения

введите описание изображения здесь

2

Решение

Первое предложение

Взгляни на KD-Tree а также R-Tree.

Они предназначены для разделения пространства, чтобы уменьшить некоторые вычисления. И есть много реализаций как библиотеки классов для них, так же как libkdtree. Я лично использовал KD-Tree прежде, чтобы уменьшить сравнение поиска ближайших окрестностей в 2D-пространстве, это было не просто, но это было эффективно.

Второе предложение

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

введите описание изображения здесь

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

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

Сегмент имеет две точки как начальную и конечную точки, а каждая точка имеет две составляющие, такие как X и Y.

Segment ref(r.start, r.end);

foreach(seg : extracted segments)
{
if (DistancePointSegment(seg.start, ref)<D &&
DistancePointSegment(seg.end  , ref)<D )
{
// Mark seg as a search candidate
}
}

Чтобы проверить расстояние точки от отрезка, прочитайте это Наименьшее расстояние между точкой и отрезком

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector