how can I represent road shape in weighed graph for route planning
I've decided to build a route-planner for a game similar to Google Maps to expand my knowledge of graphs and to serve as portfolio project.
I've done my research and got to the conclusion that I need to represent the roads as nodes in a weighted graph but my understanding is that only intersections are represented.
My question is how would I also represent the shape of the road?
My reasoning on how to solve this product would be that the graph node would have the link-cost and then as data would hold an object (JSON) with the information pertaining to the road shape until the next node/intersection.
That poses some problems because what if I want to plan a route to the middle of a road. Take the figure below, I want to go from C to what is essentially between D and E but on the road above.
Figure:
Note that all of the roads are two ways so you can assume that the edges are directed and weighed.
I've tried to look into how OSM does this but the data size alone throws me off.
Any resources would be very appreciated :)
My recommendation , if you want a JSON based format, is to look into GeoJSON. This is a well established format that can represent both spatial/shape features, and non spatial features such as street names, addresses, etc. There is extensive documentation online , so I won't quote specific links. Also the GIS Stack Exchange is a good resource for this type of problem.