Какова лучшая структура данных для поиска отрезков? - PullRequest
Новая
       24

Какова лучшая структура данных для поиска отрезков?

2 голосов
/ 19 декабря 2011

Мне нужна структура данных, чтобы найти все сегменты, попадающие в прямоугольник (в C #, даже если это не главная проблема).

Например, сегмент [(0,0), (10,10)] должен быть в прямоугольнике, начиная с (5,5) с размером (1,1).

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

Какая структура данных мне нужна для эффективного поиска?
Я ищу, но ничего не нашел для этого случая, даже если кажется, чтоочень стандартный!

Размер задачи: 6000 сегментов, средний 20 линейный сегмент в прямоугольнике

Сортировка дубликатов:

Ответы [ 3 ]

1 голос
/ 19 декабря 2011

Для неточечных объектов (отрезок линии не является точечным объектом) R-дерево может лучше подходить, чем kd-дерево.Если у вас небольшое количество линейных сегментов (<50), то хранить их в векторе и всегда проверять их все может быть самым быстрым способом. </p>

0 голосов
/ 19 декабря 2011

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

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

// we will intersect against three of the rect's borders (the 4th's results are redundant)
borders = {(TopLeft, TopRight), (TopRight, BottomRight), (BottomRight, BottomLeft)}
// each border forms a shape in (y, slope) space defined by two intersecting half spaces
// we query the line space using something standard like kd-trees
lines1 = Union(borders.ForEach(LineSpace.Inside(ShapeOfSegmentInIntersectSpace(?border))))
// now filter out lines that don't cross the rect when extended
// since we already know they intersect when extended, the check is pretty simple
lines2 = lines1.Where(?line.BoundingRect.Intersects(rect))
0 голосов
/ 19 декабря 2011

Я не знаю стандартного алгоритма для вашей задачи, но первая мысль, которая пришла мне в голову, это представить прямоугольники в виде 4 линий, а если у вас много отрезков - найти пересечения всех отрезков и линий (путем сортировкиотрезки линий и линий, а затем «сливаются» их координаты).
То есть это N * log (N) + M * Log (M), где N - количество отрезков линий, M - количество квадратов.

После этого вы можете найти отрезки, которые пересекают квадрат как (SquareHorizLine1Intersections UNION SquareHorizLine2Intersections) INTERSECT (SquareVerticalLine1Intersections UNION SquareVerticalLine2Intersections)

Снова установить пересечения и объединения, где K *, K имеют сложность, где K * Logэто размер набора.Или даже просто войти (K), если вы используете структуру данных "Биноминальная куча" (есть также куча Фибоначчи, которая может быть еще более эффективной).

Таким образом, этот алгоритм выглядит как сложность N * log (N).Я надеюсь, что это помогает ... Или вам нужно лучше?

...