number all houses on branch roads first

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

number all houses on branch roads first

積丹尼 Dan Jacobson
I want to go down the (all unnamed) roads in my future mountain
community assigning house numbers every 50 meters.

   50-100   170-200
    /         /
1  / 107 147 /  213
+-+---+---+-+----+--240--main-road--
2 48   \   168
        \
      120-140

I stay on my main road, but whenever encountering a fork, first go down it.
"Depth first pre-order ordered labeled rooted binary tree traversal but with central path"?
http://math.stackexchange.com/questions/1856814/binary-tree-traversal-with-fixed-final-node

OK for PostGIS, given a few linestrings, I suppose I first (somehow)
connect them to form a network, then ride my virtual car down it. And
whenever my odometer reaches another 50m, make a mark on the centerline.
(Assume a strict binary tree (mountain roads with no 4-way junctions))
At each road junction I first choose a side road, and if already on a
side road, first choose the left road, before choosing the right road.
When backtracking turn off my odometer, until finally back on to my main
road.

Holy smokes, sounds tough. Can I do this with PostGIS or should I go
back to GRASS or what?

(I am thinking instead of using ST_OffsetCurve (previous project, thanks
Sandro) to put odd on the left even on the right, down the centerline
I'll just put odd numbers at 25, 75m, padded "1 ", and even at 50, 100m
reverse padded " 2".) These points and their labels are what I want for output.
_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|

Re: number all houses on branch roads first

Stephen Woodbridge
Sounds like you want a "graph" based on the road network topology like
what is used in pgRouting. Then given the graph do a depth first
traversal of the topology, labeling the edges as you go.

If you build the graph topology (not the postgis topology), the you can
probably write a recursive query to do the traversal and labeling. I
think I would probably write a pgsql function(s) to traverse the graph
and label the edges.

Unfortunately, pgRouting does not have depth first search function built
into it, hence the need to code one in pgsql.

-Steve

On 7/12/2016 5:16 PM, Dan Jacobson wrote:

> I want to go down the (all unnamed) roads in my future mountain
> community assigning house numbers every 50 meters.
>
>    50-100   170-200
>     /         /
> 1  / 107 147 /  213
> +-+---+---+-+----+--240--main-road--
> 2 48   \   168
>         \
>       120-140
>
> I stay on my main road, but whenever encountering a fork, first go down it.
> "Depth first pre-order ordered labeled rooted binary tree traversal but with central path"?
> http://math.stackexchange.com/questions/1856814/binary-tree-traversal-with-fixed-final-node
>
> OK for PostGIS, given a few linestrings, I suppose I first (somehow)
> connect them to form a network, then ride my virtual car down it. And
> whenever my odometer reaches another 50m, make a mark on the centerline.
> (Assume a strict binary tree (mountain roads with no 4-way junctions))
> At each road junction I first choose a side road, and if already on a
> side road, first choose the left road, before choosing the right road.
> When backtracking turn off my odometer, until finally back on to my main
> road.
>
> Holy smokes, sounds tough. Can I do this with PostGIS or should I go
> back to GRASS or what?
>
> (I am thinking instead of using ST_OffsetCurve (previous project, thanks
> Sandro) to put odd on the left even on the right, down the centerline
> I'll just put odd numbers at 25, 75m, padded "1 ", and even at 50, 100m
> reverse padded " 2".) These points and their labels are what I want for output.
> _______________________________________________
> postgis-users mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/postgis-users
>


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|

Re: number all houses on branch roads first

Stephen Woodbridge
Opened an enhancement request to pgrouting:
https://github.com/pgRouting/pgrouting/issues/625

On 7/12/2016 9:56 PM, Stephen Woodbridge wrote:

> Sounds like you want a "graph" based on the road network topology like
> what is used in pgRouting. Then given the graph do a depth first
> traversal of the topology, labeling the edges as you go.
>
> If you build the graph topology (not the postgis topology), the you can
> probably write a recursive query to do the traversal and labeling. I
> think I would probably write a pgsql function(s) to traverse the graph
> and label the edges.
>
> Unfortunately, pgRouting does not have depth first search function built
> into it, hence the need to code one in pgsql.
>
> -Steve
>
> On 7/12/2016 5:16 PM, Dan Jacobson wrote:
>> I want to go down the (all unnamed) roads in my future mountain
>> community assigning house numbers every 50 meters.
>>
>>    50-100   170-200
>>     /         /
>> 1  / 107 147 /  213
>> +-+---+---+-+----+--240--main-road--
>> 2 48   \   168
>>         \
>>       120-140
>>
>> I stay on my main road, but whenever encountering a fork, first go
>> down it.
>> "Depth first pre-order ordered labeled rooted binary tree traversal
>> but with central path"?
>> http://math.stackexchange.com/questions/1856814/binary-tree-traversal-with-fixed-final-node
>>
>>
>> OK for PostGIS, given a few linestrings, I suppose I first (somehow)
>> connect them to form a network, then ride my virtual car down it. And
>> whenever my odometer reaches another 50m, make a mark on the centerline.
>> (Assume a strict binary tree (mountain roads with no 4-way junctions))
>> At each road junction I first choose a side road, and if already on a
>> side road, first choose the left road, before choosing the right road.
>> When backtracking turn off my odometer, until finally back on to my main
>> road.
>>
>> Holy smokes, sounds tough. Can I do this with PostGIS or should I go
>> back to GRASS or what?
>>
>> (I am thinking instead of using ST_OffsetCurve (previous project, thanks
>> Sandro) to put odd on the left even on the right, down the centerline
>> I'll just put odd numbers at 25, 75m, padded "1 ", and even at 50, 100m
>> reverse padded " 2".) These points and their labels are what I want
>> for output.
>> _______________________________________________
>> postgis-users mailing list
>> [hidden email]
>> http://lists.osgeo.org/mailman/listinfo/postgis-users
>>
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> _______________________________________________
> postgis-users mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/postgis-users


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|

Re: number all houses on branch roads first

Rémi Cura
Would be much easier to send your graph to python networkx
If you have plpython, this is immediate (line 368)

I found it painful  to work on graph in pgsql (or pgrouting, besides the excellent already written functions),

much easier with dedicated tools.


If you really really want to use pgsql,
you can use pure SQL with a  recursive CTE,
I find it hard to test and debug though

Cheers,
Rémi-C

2016-07-13 4:17 GMT+02:00 Stephen Woodbridge <[hidden email]>:
Opened an enhancement request to pgrouting:
https://github.com/pgRouting/pgrouting/issues/625


On 7/12/2016 9:56 PM, Stephen Woodbridge wrote:
Sounds like you want a "graph" based on the road network topology like
what is used in pgRouting. Then given the graph do a depth first
traversal of the topology, labeling the edges as you go.

If you build the graph topology (not the postgis topology), the you can
probably write a recursive query to do the traversal and labeling. I
think I would probably write a pgsql function(s) to traverse the graph
and label the edges.

Unfortunately, pgRouting does not have depth first search function built
into it, hence the need to code one in pgsql.

-Steve

On 7/12/2016 5:16 PM, Dan Jacobson wrote:
I want to go down the (all unnamed) roads in my future mountain
community assigning house numbers every 50 meters.

   50-100   170-200
    /         /
1  / 107 147 /  213
+-+---+---+-+----+--240--main-road--
2 48   \   168
        \
      120-140

I stay on my main road, but whenever encountering a fork, first go
down it.
"Depth first pre-order ordered labeled rooted binary tree traversal
but with central path"?
http://math.stackexchange.com/questions/1856814/binary-tree-traversal-with-fixed-final-node


OK for PostGIS, given a few linestrings, I suppose I first (somehow)
connect them to form a network, then ride my virtual car down it. And
whenever my odometer reaches another 50m, make a mark on the centerline.
(Assume a strict binary tree (mountain roads with no 4-way junctions))
At each road junction I first choose a side road, and if already on a
side road, first choose the left road, before choosing the right road.
When backtracking turn off my odometer, until finally back on to my main
road.

Holy smokes, sounds tough. Can I do this with PostGIS or should I go
back to GRASS or what?

(I am thinking instead of using ST_OffsetCurve (previous project, thanks
Sandro) to put odd on the left even on the right, down the centerline
I'll just put odd numbers at 25, 75m, padded "1 ", and even at 50, 100m
reverse padded " 2".) These points and their labels are what I want
for output.
_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users


_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|

Re: number all houses on branch roads first

積丹尼 Dan Jacobson
In reply to this post by 積丹尼 Dan Jacobson
Thanks fellows. In fact I am convinced that I have stumbled upon
a new traversal of binary trees,
http://jidanni.org/geo/house_numbering/taizhong/dongshi/zaokeng.html
useful for numbering irregular communities, campgrounds, cemeteries...
_______________________________________________
postgis-users mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-users