Предложения по ускорению выбора краев

Question

Я строю графический редактор в C #, где пользователь может размещать узлы, а затем соединять их с направленным или неориентированным ребром. По завершении алгоритм поиска пути A * определяет наилучший путь между двумя узлами.

Что у меня есть: Класс узла с x, y, списком подключенных узлов и F, G и H баллами. Класс Edge с Началом, Концом и направлен ли он или нет. Класс Graph, который содержит список узлов и ребер, а также алгоритм A *

Прямо сейчас, когда пользователь хочет выбрать узел или ребро, позиция мыши записывается, и я перебираю все узлы и ребра, чтобы определить, должен ли он быть выбран. Это явно медленно. Я думал, что смогу реализовать QuadTree для своих узлов, чтобы ускорить его, однако, что я могу сделать, чтобы ускорить выбор ребер?

Answer 1

Так как пользователи «рисуют» эти графики, я бы предположил, что они включают в себя количество узлов и ребер, которые люди, вероятно, смогут генерировать (скажем, 1-5k максимум?). Просто сохраните оба в одном QuadTree (при условии, что у вас уже есть одно написанное).

Вы можете легко расширить классическое QuadTree на PMR QuadTree , которое добавляет критерии разделения на основе количества отрезков линий, проходящих через них. Я написал гибридный PR / PMR QuadTree , который поддерживал группирование как точек, так и линий, и на самом деле он работал с достаточно высокой производительностью для движущихся объектов 10–50 тыс. (Перебалансирование сегментов!).

Answer 2

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

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

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

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

Answer 3

Я думаю, у вас уже есть все ингредиенты. Вот предложение:

1. Индексируйте все ваши ребра в пространственной структуре данных (может быть QuadTree , R-Tree и т. Д.). Каждое ребро должно быть проиндексировано с помощью ограничительной рамки.
2. Запишите положение мыши.
3. Поиск наиболее конкретного прямоугольника, содержащего положение мыши.
4. Этот прямоугольник должен иметь один или несколько ребер / узлов; Итерируйте их в соответствии с нужным режимом.
5. (Сложная часть): если пользователь не указал ни одного ребра из самого определенного прямоугольника, вам нужно подняться на один уровень вверх и перебрать все ребра, включенные в этот уровень. Может быть, вы можете обойтись без этого.

Это должно быть быстрее.