Как ограничить пространство поиска, используя прямоугольный буфер 2D вдоль отрезка 2D линии
У меня есть 2D линейные сегменты, извлеченные из изображения. Так что я знаю их конечную точку. Кроме того, у меня есть некоторые ссылочные сегменты 2d линии. Оба отрезка линии теперь в векторной форме. Сравнивая со ссылочными и извлеченными строками, я получаю огромное количество выделенных отрезков.
Что я хочу сделать, это найти отрезок сопряженной линии для каждой контрольной линии из моего извлечения. то есть я хочу сопоставить отрезки. Но, чтобы уменьшить область поиска Я хочу ограничить его таким образом, что путь определения буферной зоны вокруг сегмента опорной линии.
(1) Мой первый вопрос — как я могу реализовать этот буферный случай с помощью c ++, поскольку мне не хватает геометрических теорий.
Примечание: Я не хочу использовать рамку и ищет прямоугольный буфер, который ориентирует вдоль опорной линии.
(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
}
}
Чтобы проверить расстояние точки от отрезка, прочитайте это Наименьшее расстояние между точкой и отрезком
Другие решения
Других решений пока нет …