search

moovida / dart_jts

An effort to port some of the Java Topology Suite to dart
Other
26 stars 19 forks source link

Convert Line segments to Graph #13

Closed mohammedX6 closed 2 years ago

mohammedX6 commented 2 years ago

How I can convert a list of Line segments to a Graph?

moovida commented 2 years ago

Hi @mohammedX6 , jts does not have such functionality. When I had to use graphs, I made use of the geotools module: https://docs.geotools.org/maintenance/userguide/extension/graph/index.html That would be worth a port I think.

mohammedX6 commented 2 years ago

@moovida it could be changeling, but I will give it a try.

moovida commented 2 years ago

Yes, I agree with you, there is sure some work behind, since that one also allows for weighting edges and do shortest paths. It really depends on what you need to do. Maybe to navigate it conceptually something like https://pub.dev/packages/graphs might be enough?

mohammedX6 commented 2 years ago

@moovida My intention was to find the shortest path between two points, so I ported this implementation of the A* algorithm from C# earlier, but it gave me wrong results maybe I missed something I don't know ..., I thought JTS could have something to do with Graphs and shortest paths...

moovida commented 2 years ago

@mohammedX6 , a pity the A* didn't work out. That was a really cool one.

No, JTS doesn't implement that. Everything on top of that is in the geotools library. And Dijkstra is implemented in that graph module of geotools. Geotools uses jts under the hood, so when it comes to coordinates and geometries, it is compatible. That is the main reason I proposed it. And since it has testcases, if for some reason the port doesn't work, you are able to debug both languages and see where the problem lies. But yes, it sure is a bit of work.

PS: it also has Astar: https://github.com/geotools/geotools/blob/main/modules/extension/graph/src/main/java/org/geotools/graph/path/AStarShortestPathFinder.java

mohammedX6 commented 2 years ago

Thanks @moovida