Соединение неупорядоченных отрезков

Question

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

Каким был бы чрезвычайно быстрый способ найти эти полилинии? Я должен сделать это в режиме реального времени, поэтому все, что занимает больше 10-мс, не является решением.

Я делаю это в C #, но я ищу идеи, а не источник.

Answer 1

Будет ли работать хэш конечных точек?

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

Если конечные точки имеют какую-либо неточность, то вам потребуется пространственный индекс и, вероятно, один , который использует R-дерево . Вы можете получить аналогичный эффект, просто сделав 2d хеш-сетку. Сетка хэша содержит группы соседних конечных точек. Вам нужно будет проверить соседние ячейки.