[OSM-dev] Suggestion about design of OSM data structure (take out segments)

Fri Jul 27 15:07:32 BST 2007

To whom still want to keep segment, please consider my long post below. I combine all your arguments and answer one by one:

  <<<
  but we often have a residential road with residential branches, so they're all the same type.
  >>>

  Again, you are assuming residential road and its residential branches are 2 ways road. 
  When you model a road, you can not assume the road is 2 ways road. each branch of the road has its own direction arrow and the direction arrow is very important factor. direction arrow is used in routing and finding shortestway apps.

  Let say today you used segments to model a residential road with its branches. One month later, one branch of the residential road change from 2 ways to 1 way road. How you modify your segment model without break that branch to another way? If you do not use segment, you break all the branches of the residential road to serveral ways at the beginning, you can easy modify the direction arrow for each way, isn't it?

  Furthermore, if you allow using of segments to model ways, user can model Y-shaped ways, T-shaped ways, H-shaped ways, K-shaped ways and no routing application can calculate shortest way with Y-shaped ways, T-shaped ways, H-shaped ways, K-shaped ways... 

  Compare to Google map and Yahoo map, osm can only render the map in the web browser while Google map and Yahoo map can let user key in start point and end point then they calculate the route and show in the web browser. If you try to apply A* algorithm (finding shortest algorithm) to do the same for osm, you will know how difficult to do that with current osm data structure (nodes/segments/ways). 

  <<<
  About areas with holes:
Without segments, I still can use simple way to model area with hole. 
For example: I have 11 nodes. Node: 1, 2, 3, 4, 10, 11 form the outer
ring clockwise and nodes: 5, 6, 7, 8, 9 form inner ring anticlockwise.
Two rings joined at node 4 and 5.

That's a bad way to do it. Imagine you have an area drawn with contours 
(for example, lakes sometimes have a darker blue contour and a light
blue fill) - the contour would run straight through your lake from 4 to 5!
>>>

  If we want we can break polygon with hole into 2 simple polygon without hole. for example: a polygon with hole "O" shaped can break into 2 polygons: 1 polygon "(" shaped + 1 polygon ")" shaped.

  If you model an area as a complex polygon it will be difficult for render program to fill complex polygon. Break that area into serveral simple polygons and render program can render them faster by using simple filling polygon algorithmn.

  We have to avoid complex polygons in our map data. It is to help render program run faster.

  So I think simple way (1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 10, 11) is good enough to model polygon with hole. And it is also simple enough for render program to fill the polygon.

  Simple polygon:
  http://en.wikipedia.org/wiki/Simple_polygon

  <<<
  So, to model the above area with hole, I can use simple way like
this (1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 10, 11)

Looks way too hack-ish to me. And, you are wasting a little bit of
space duplicating info about nodes 4 and 5.
>>>

  Duplicating only 2 integers to store 2 nodes 4 and 5 for a polygon with hole is not a big deal. It is still far better than you use segments because each segment require 1 integer for its own id! so 12,000,000 segments required a lot of space in planet.osm file.

  <<<
I'll be doing a quick proposal, based on having read a couple of times
the 
(hideous) OGC specs:

node = (lat, lon)
string = (nodeid[0], nodeid[1], nodeid[2], ... )
poly = (stringid[0], stringid[1], ...)

So:
Nodes are still nodes,
A string is the same as a "simple way" right now,
A poly is either a polystring (a "complex way" with branches, or the 
dubbed "superway") or a polygon (the first string being the outer hull,
any 
others being the inner hulls)

Checking for areas (closed rings) would be fairly easy: the first node
id is 
the same as the last one. And the polygon model should be fairly good.

Simple editors (e.g. potlach) should not worry about polys, to keeps
things 
even simpler, and complex ones should ("want to create an area? learn
to use 
JOSM"), as well as cleaning-up tools.

Should this solve everyone's problems?
>>>

  No, your solution does not solve the space issue problem. The planet.osm file still wastes a lot of space for string's id. The data structure still has 3 components (nodes, strings, ways) which is difficult for converting, clipping, routing, and finding shorttest way.

  <<<
  If I were starting the project from scratch, I would do segments a bit differently, but I don't think there is enough to be gained at this stage from making such a change. Also, segments are useful for tagging address information onto (like that in tiger). 
  >>>

  Please do not to tag address to segment. You can tag address to node. The xml format of the node will be:
  <node id = "1234" lat="..." lon="..."/>
  <way id = "123'/> <-- point to the road id that this node's addres is belong to
  <tag k="HouseNumber", v="430"/>
  <tag k="PostalCode", v="123456"/>
  <tag k="Phone", v="23453-4567"/>
  </node>

  If you want to retrieve address range for a particular road you can run this sql statement:
  select nodeid,housenumber,postalcode,phone
  from nodes
  where wayid = "xyz"

  If you join with ways table you can get street name as well.

  Or if you don't want to put way id in nodes, you can tag address as below:
  <node id = "1234" lat="..." lon="..."/>
  <tag k="HouseNumber", v="430"/>
  <tag k="StreetName", v="Street ABC"/>
  <tag k="PostalCode", v="123456"/>
  <tag k="Phone", v="23453-4567"/>
  </node>

  For your information, Tiger data is incompleted. It does not have oneway indicator for each road. So please do not keep segments just for tag Tiger data. 

  Conclusion:
  Current data structure (nodes,segments,ways) may be good for modeling polygons and 2-way roads but it is not good for modeling 1-way roads, not good for importing/exporting/converting (waste space), not good for clipping, not good for routing and finding shortest way...

  New data structure (nodes,ways) is good for model 2-way roads and 1-way roads. It can model simple polygon with hole as well. It is good for importing/exporting/converting (save space), good for clipping, routing and finding shortest way... as well.

  If we are going to convert to new data structure --> It will be a big change but it is better we do it now when planet.osm file is only 5GB. If we delay and the planet.osm file grow up to 100GB then no other program can use osm data except osm itself.

  <<<
  1. Branched and disconnected ways can be found and, mostly, remedied 
  even today. Same with tagged segments and unwayed segments. So 
  instead of breaking them up and then putting them on a Wiki page, we 
  could do that today and at least reduce their number. (OTOH people 
  might not be inclined do something about it until we thoroughly break 
  it.)
  >>>

  I have no idea on this issue.

  <<<
  2. Areas with holes. Don't have a good idea for them yet. Anyone else?
  >>>

  Areas with holes --> you can break it to simply polygons.

  <<<
  3. Dropping way and segment history is acceptable to me, but maye we 
  should keep these things on file somewhere in case we need to do 
  check something.
  >>>

  The new xml format for way will be like this:
  <way id = '1234" timestamp = "..."/>
  <node id = "123"/>
  <node id = "456"/>
  <node id = "789"/>
  <tag =.../>
  <tag =.../>
  <tag =.../>
  <tag =.../>
  So you still can keep way's history because the way id of existing way does not change

  <<<
  4. We would install all this on a testing platform first, to allow 
  JOSM etc. to catch up... wouldn't we?
  >>>

  Yes, please test it on setup testing platform.

  Thanks for reading a long post.

  Regards,

---------------------------------
Need a vacation? Get great deals to amazing places on Yahoo! Travel. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20070727/58df3e82/attachment.html>