Node / line segment database statistics separation

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Node / line segment database statistics separation

ANDY ROBINSON-2
There is a growing trend that the difference between the number of nodes on
the database and the number of line segments is increasing. Currently it
stands at around 2% of nodes (dropped a little last night with Nick's
Freemap additions).

On the basis that I would have thought there would be proportionally more
nodes than line segments as there are two nodes required for a line segment
and thus you gain a node at the end of each line run, plus there are plenty
of loose nodes lying around on the map. Therefore you would expect the
number of nodes to increase more, proportionally with time, than line
segments and not the other way around.

I have also noted when editing that you can make a line segment from a node
and this seems to stick. Does it mean we have a large number of zero length
line segments on the database?

Andy

Andy Robinson



_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Tom Carden
Andy Robinson wrote:

> There is a growing trend that the difference between the number of nodes on
> the database and the number of line segments is increasing. Currently it
> stands at around 2% of nodes (dropped a little last night with Nick's
> Freemap additions).
>
> On the basis that I would have thought there would be proportionally more
> nodes than line segments as there are two nodes required for a line segment
> and thus you gain a node at the end of each line run, plus there are plenty
> of loose nodes lying around on the map. Therefore you would expect the
> number of nodes to increase more, proportionally with time, than line
> segments and not the other way around.
>  

Not really.  We don't have line runs - we have a mesh of streets.  Your
assumption would only be right for motorways.  It might be worth getting
a plot of the distribution of node degrees (how many times each node
appears in a line).  I'm pretty sure that for lots of nodes it will be
greater than one, and I think orphan nodes will be insignificant.

> I have also noted when editing that you can make a line segment from a node
> and this seems to stick. Does it mean we have a large number of zero length
> line segments on the database?
>  

Do you mean it's possible to create a line with the same start and end
node?  Yeah, we should catch that, but if nobody has done it on purpose
then it'll be easy to delete them all at once from the database.

Best,

Tom.



_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

RE: Node / line segment database statistics separation

ANDY ROBINSON-2
>-----Original Message-----
>From: Tom Carden [mailto:[hidden email]]
>Sent: 15 November 2005 10:52
>To: Andy Robinson
>Cc: [hidden email]
>Subject: Re: [Openstreetmap-dev] Node / line segment database statistics
>separation
>
>Andy Robinson wrote:
>> There is a growing trend that the difference between the number of nodes
>on
>> the database and the number of line segments is increasing. Currently it
>> stands at around 2% of nodes (dropped a little last night with Nick's
>> Freemap additions).
>>
>> On the basis that I would have thought there would be proportionally more
>> nodes than line segments as there are two nodes required for a line
>segment
>> and thus you gain a node at the end of each line run, plus there are
>plenty
>> of loose nodes lying around on the map. Therefore you would expect the
>> number of nodes to increase more, proportionally with time, than line
>> segments and not the other way around.
>>
>
>Not really.  We don't have line runs - we have a mesh of streets.  Your
>assumption would only be right for motorways.  It might be worth getting
>a plot of the distribution of node degrees (how many times each node
>appears in a line).  I'm pretty sure that for lots of nodes it will be
>greater than one, and I think orphan nodes will be insignificant.
>

I see your logic here. Its just that I know we have a lot of loose nodes out
there so was surprised by the difference. But if zero length segments is the
reason then that could be the cause.


>> I have also noted when editing that you can make a line segment from a
>node
>> and this seems to stick. Does it mean we have a large number of zero
>length
>> line segments on the database?
>>
>
>Do you mean it's possible to create a line with the same start and end
>node?  Yeah, we should catch that, but if nobody has done it on purpose
>then it'll be easy to delete them all at once from the database.
>

Yes, you can by accident and sometimes you don't realise that you have done
it. The node retains white in the editor when you refresh but I believe many
are invisible because they lie under proper segments. Should be easy to
check the database anyway.

>Best,
>
>Tom.
>
>


Andy


_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Tom Carden
Andy Robinson wrote:
>
> I see your logic here. Its just that I know we have a lot of loose nodes out
> there so was surprised by the difference. But if zero length segments is the
> reason then that could be the cause.
>  

Think about a basic grid (draw dots on paper).

In a 2x2 grid street pattern, there are 4 nodes and 4 lines, right?  But
in a 3x3 there are 9 and 12, and in a 4x4 there are 16 and 24, and so
on.  For n x n, there are n^2 nodes and (2n^2 - 2n) lines.  I think.  
Anyway, they diverge :)  This effect is lessened by orphan nodes and by
long roads and other sections of the map that aren't pure grids, but
then it's increased by things like 5 way junctions.  So you shouldn't be
surprised to see more lines than nodes, you should be expecting it :)

Best,

Tom.







_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

RE: Node / line segment database statistics separation

ANDY ROBINSON-2
>
>In a 2x2 grid street pattern, there are 4 nodes and 4 lines, right?  But
>in a 3x3 there are 9 and 12, and in a 4x4 there are 16 and 24, and so
>on.  For n x n, there are n^2 nodes and (2n^2 - 2n) lines.  I think.
>Anyway, they diverge :)  This effect is lessened by orphan nodes and by
>long roads and other sections of the map that aren't pure grids, but
>then it's increased by things like 5 way junctions.  So you shouldn't be
>surprised to see more lines than nodes, you should be expecting it :)
>

Thanks for the math lesson Tom ;)

I was looking at it from my editing standpoint rather than the logic of a
grid. Principally because most of my editing results in significantly more
nodes that have only 2 line segments attached than those with 3 or more.

>Best,
>
>Tom.
>

Andy


_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Tom Carden
Andy Robinson wrote:
> Thanks for the math lesson Tom ;)
>  

Maths. Please! ;)

> I was looking at it from my editing standpoint rather than the logic of a
> grid. Principally because most of my editing results in significantly more
> nodes that have only 2 line segments attached than those with 3 or more.
>  

Fair enough.  I think the towns out-weigh the long roads though, and
even if you don't have grid iron streets, then every t-junction,
crossroads, roundabout etc contributes more lines than roads.

That's the way I see it on screen grabs like this one anyway....
http://www.openstreetmap.org/news/images/birmingham-detail2-nov-2005.jpg
(your work I believe?)

I'll see if they're easy stats to pull out of the database anyway, then
we can keep track.

Tom.



_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

RE: Node / line segment database statistics separation

ANDY ROBINSON-2
>
>Fair enough.  I think the towns out-weigh the long roads though, and
>even if you don't have grid iron streets, then every t-junction,
>crossroads, roundabout etc contributes more lines than roads.
>
>That's the way I see it on screen grabs like this one anyway....
>http://www.openstreetmap.org/news/images/birmingham-detail2-nov-2005.jpg
>(your work I believe?)

Nice screen shot!

It may not be as one sided as you think though, although I admit the
grid-iron does figure more strongly in the older town centres. Look at all
those little cul-de-sacs in the newer residential areas. They are
effectively linear rather than grid and because of all the modern curved
roads there are loads of nodes. From all the cycling I have done up and down
this area I can say that there have been a lot more cul-de-sacs than grids.

These little quiet cul-de-sacs should also carry an OSM warning about
getting funny looks when slowly riding a bike down the middle of the road in
a florescent cycling jacket. "You can't get out of here mate/love/dear"
seems to be the general response :)

>
>I'll see if they're easy stats to pull out of the database anyway, then
>we can keep track.
>
>Tom.
>
>


Andy


_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Tom Carden
Andy Robinson wrote:
> Nice screen shot!
>  

Hope to make this easier soon (might add a ticket on trac for "save this
map" links from view-map), but if you want specific areas you can
quickly hack around with the URL of the image in view-map so long as you
get the proportion of width and height right.  1280x914 seems a nice
compromise.

Here's London...
http://tile.openstreetmap.org/cgi-bin/steve/mapserv?map=/usr/lib/cgi-bin/steve/wms.map&service=WMS&WMTVER=1.0.0&REQUEST=map&STYLES=&TRANSPARENT=TRUE&LAYERS=landsat,streets&width=1280&height=914&bbox=-0.546135581013279,51.3492791203629,0.251208161013279,51.7036148796371

North/south divide?  Not much!

> It may not be as one sided as you think though, although I admit the
> grid-iron does figure more strongly in the older town centres. Look at all
> those little cul-de-sacs in the newer residential areas. They are
> effectively linear rather than grid and because of all the modern curved
> roads there are loads of nodes. From all the cycling I have done up and down
> this area I can say that there have been a lot more cul-de-sacs than grids.
>
>  

You're right about the character of most streets, and of course the more
detail you add then the less the number of nodes and lines will
diverge.  That's why we're accounting for a 2% divergence rather than
the pure-grid divergence which would tend to 100%...

> These little quiet cul-de-sacs should also carry an OSM warning about
> getting funny looks when slowly riding a bike down the middle of the road in
> a florescent cycling jacket. "You can't get out of here mate/love/dear"
> seems to be the general response :)
>
>  

This is just asking for a video to be made... Day in the life of a
mapping activist :)

Tom.




_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Steve Coast
Is this a gopod time to mention that the stats include deleted nodes and
segments, not just the currently live ones? The logic being that any
dead ones can be brought back. I can change this.

I've added tickets for checking loopback segments and doing a nod degree
graph.

* @ 15/11/05 12:46:15 PM [hidden email] wrote:

> Andy Robinson wrote:
> >Nice screen shot!
> >  
>
> Hope to make this easier soon (might add a ticket on trac for "save this
> map" links from view-map), but if you want specific areas you can
> quickly hack around with the URL of the image in view-map so long as you
> get the proportion of width and height right.  1280x914 seems a nice
> compromise.
>
> Here's London...
> http://tile.openstreetmap.org/cgi-bin/steve/mapserv?map=/usr/lib/cgi-bin/steve/wms.map&service=WMS&WMTVER=1.0.0&REQUEST=map&STYLES=&TRANSPARENT=TRUE&LAYERS=landsat,streets&width=1280&height=914&bbox=-0.546135581013279,51.3492791203629,0.251208161013279,51.7036148796371
>
> North/south divide?  Not much!
>
> >It may not be as one sided as you think though, although I admit the
> >grid-iron does figure more strongly in the older town centres. Look at all
> >those little cul-de-sacs in the newer residential areas. They are
> >effectively linear rather than grid and because of all the modern curved
> >roads there are loads of nodes. From all the cycling I have done up and
> >down
> >this area I can say that there have been a lot more cul-de-sacs than
> >grids.
> >  
>
> You're right about the character of most streets, and of course the more
> detail you add then the less the number of nodes and lines will
> diverge.  That's why we're accounting for a 2% divergence rather than
> the pure-grid divergence which would tend to 100%...
>
> >These little quiet cul-de-sacs should also carry an OSM warning about
> >getting funny looks when slowly riding a bike down the middle of the road
> >in
> >a florescent cycling jacket. "You can't get out of here mate/love/dear"
> >seems to be the general response :)
> >
> >  
>
> This is just asking for a video to be made... Day in the life of a
> mapping activist :)
>
> Tom.
>
>
>
>
> _______________________________________________
> Openstreetmap-dev mailing list
> [hidden email]
> http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev

have fun,

SteveC [hidden email] http://www.asklater.com/steve/

_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Tom Carden
SteveC wrote:
> Is this a gopod time to mention that the stats include deleted nodes and
> segments, not just the currently live ones? The logic being that any
> dead ones can be brought back. I can change this.
>  

Might be good to graph separately?

> I've added tickets for checking loopback segments and doing a nod degree
> graph.
>  

Yay trac.

Tom.



_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

RE: Node / line segment database statistics separation

ANDY ROBINSON-2
In reply to this post by Steve Coast
>
>Is this a gopod time to mention that the stats include deleted nodes and
>segments, not just the currently live ones? The logic being that any
>dead ones can be brought back. I can change this.

I think we should only show on the stats table and graphs the number of live
nodes and lines actually available to the "user". I'm sure it would be
useful to know how many nodes and points can be put back into the map if
required but that's not, I suspect, a lot of interest to end users. I've
deleted a pile of segments simply to allow a new node to be inserted and
two/three new lines drawn to connect it all up again. Not sure I would ever
want to reverse that.

When you GET map data, it only returns live nodes/segments right?



Andy Robinson



_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Lars Aronsson
In reply to this post by Tom Carden
Tom Carden wrote:

> In a 2x2 grid street pattern, there are 4 nodes and 4 lines,
> right?  But in a 3x3 there are 9 and 12, and in a 4x4 there are
> 16 and 24, and so on.  For n x n, there are n^2 nodes and (2n^2
> - 2n) lines.

A very common pattern is that each road segment between street
corners (or countryside crossroads) has a slight bend, which
requires one or more intermediate nodes.  Considering the long
runs of country roads and motorways, I think the vast majority of
nodes are such that only connect line segments into long roads.  
Thus the number of nodes should be very close to the number of
line segments.


--
  Lars Aronsson ([hidden email])
  Aronsson Datateknik - http://aronsson.se

_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Node / line segment database statistics separation

Tom Carden
Lars Aronsson wrote:

> Tom Carden wrote:
>  
>> In a 2x2 grid street pattern, there are 4 nodes and 4 lines,
>> right?  But in a 3x3 there are 9 and 12, and in a 4x4 there are
>> 16 and 24, and so on.  For n x n, there are n^2 nodes and (2n^2
>> - 2n) lines.
>>    
>
> A very common pattern is that each road segment between street
> corners (or countryside crossroads) has a slight bend, which
> requires one or more intermediate nodes.  Considering the long
> runs of country roads and motorways, I think the vast majority of
> nodes are such that only connect line segments into long roads.  
>  

Yeah, Andy had that case covered I think.

> Thus the number of nodes should be very close to the number of
> line segments.

Within, say, 2%?  I agree.  The above was an example of an extreme case,
a few examples of which would account for the diverging trend that was
confusing Andy at the start of this thread.

Best,

T.




_______________________________________________
Openstreetmap-dev mailing list
[hidden email]
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev