Я реализовал 3 варианта алгоритма развертки для обнаружения пересечения плоского замкнутого графа. У меня есть большие данные, которые представляют график (например, 200 ребер или более. Вершины - это пары точек в 2D, ребра - это пара двух вершин, одна из которых является источником, а другая - местом назначения), которая читается из другой функции, реализованной в библиотека C ++ для других целей.
Проблема в том, что реализация 3 отлично работает с целыми числами или удваивает данные, которые не так длинны, но когда я попробовал любую из этих трех реализаций на моих данных, представляющих график, я каждый раз получал разные результаты, и даже не хорошие .
Есть ли у меня все пересечения, которые я хочу, но некоторые другие точки на графике (которые не являются пересечениями)
Имею ли я некоторые точки на графике в качестве результата, но некоторые пересечения, которые мне нужны, отсутствуют в вычисленном результате
Есть ли у меня только необходимые пересечения
Все зависит от функции сортировки, которую я видел, и, может быть, от чего-то другого, но я не могу понять это. Функция сортировки упорядочивает ребра графа следующим образом:
Учитывая два ребра как E1(Vstart,Vend), E2(Vstart,Vend):
x.E1.Vstart<x.E2.Vstart or
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart<y.E2.Vstart or
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart==y.E2.Vstart and slope(E1)<slope(E2)
Я думал, что эта функция сортировки хороша для монотичности и других случаев, но, очевидно, она работает только в некоторых случаях, когда помимо обычных пересечений она обнаруживает и некоторые другие пересечения; в некоторых случаях он работает вообще, поскольку он вычисляет не все пересечения, а лишь некоторую точку на графике.