Modify

Opened 14 years ago

Closed 14 years ago

#5109 closed enhancement (fixed)

[patch] relation analysis

Reported by: NE2 Owned by: team
Priority: normal Milestone:
Component: Core Version:
Keywords: relation_analyzer Cc: PetrDlouhy

Description

It would be useful to have a built-in relation analyzer (or a plugin that does such a thing). Essentially it would take a relation - I'll use 450456 as an example - and check that it describes a continuous route. If I were doing it manually, here's what I'd do:

find type:way child id:450456 (role:east | role: ) only problem here is that this also finds elements that may be tagged west in 450456 but east in another relation

hit C to see that yes, the ways do form a single string of nodes and thus can be combined

do the same for west

This is the basic idea, but it could be enhanced, for instance to check if the route is routable (one-ways in the right direction, and even no turn restrictions against the flow if possible), like this analyzer: http://toolserver.org/~nakor/relation.fcgi?relation=450456

Attachments (17)

forward_backward.patch (20.9 KB ) - added by PetrDlouhy 14 years ago.
forward/bacward analyzator for relation editor
forward_backward.png (141.2 KB ) - added by PetrDlouhy 14 years ago.
screenshot of patch in action
relation_sorting.osm (44.4 KB ) - added by PetrDlouhy 14 years ago.
testing data
forward_backward1.png (116.3 KB ) - added by PetrDlouhy 14 years ago.
One aditional screenshot with curcular route with forward parts
design-suggestion.png (19.8 KB ) - added by bastiK 14 years ago.
unconnected-lane.png (12.9 KB ) - added by bastiK 14 years ago.
left-right-left-right.png (13.6 KB ) - added by bastiK 14 years ago.
forward_backward.2.patch (32.6 KB ) - added by PetrDlouhy 14 years ago.
new version of the patch
relation_sorting.2.osm (53.4 KB ) - added by PetrDlouhy 14 years ago.
new file with examples
left-right.osm (4.5 KB ) - added by bastiK 14 years ago.
2 examples for possible improvement
gap.png (32.8 KB ) - added by bastiK 14 years ago.
b 95.osm (51.9 KB ) - added by bastiK 14 years ago.
this file throws NPE when opening the relation editor (patch 3 v2)
forward_backward.3.patch (131.3 KB ) - added by PetrDlouhy 14 years ago.
new version of the patch
connection-bug.osm (20.1 KB ) - added by bastiK 14 years ago.
Problems with connection and L/R
roundabout-and-oneway-loop_(tricky).osm (25.0 KB ) - added by bastiK 14 years ago.
left-right.diff (3.4 KB ) - added by PetrDlouhy 14 years ago.
few-liner which fixes left-right bug (ex1) and connection bug
relation_analysis.osm (108.7 KB ) - added by PetrDlouhy 14 years ago.
small fixes to testing file

Download all attachments as: .zip

Change History (61)

comment:1 by stoecker, 14 years ago

You can do most of these things in relation editors third column, when you sort the entries. The the linkedness state shwos either a continous line or it does not.

comment:2 by NE2, 14 years ago

No you can't - not if the highway is partially dual carriageway (with opposite roles) and partially single carriageway (with no role). There's also, I believe, no way to automatically sort; this has to be done manually, which is not simple for large relations.

comment:3 by stoecker, 14 years ago

Sure you can sort the relation list. The forward/backwards issue makes analysis a bit more complicated, but not impossible.

comment:4 by NE2, 14 years ago

Would you mind sorting relation 450456 so one can see at a glance whether the route is continuous in both directions?

comment:5 by stoecker, 14 years ago

Done. Thought there are many issues with the relation:

  • Using Rd and St instead of Road and Street
  • Using west/east instead of forward/backward

The relation now consists of one main part for east-direction and two parts for other direction. Currently we cannot display two-way links and I have no idea how to do so. Probably using another sign for the place where the roads split and another node symbol for the separate parts. Make suggestions if you have an idea.

comment:6 by stoecker, 14 years ago

Summary: Relation analysisImprove linkedness display in relation editor to show multiple connections

Probably we could a a little sidewards line to left side when a node is connected to more than the next one and a little line to the right when the node is connect to something, but not to the next/previous one.

in reply to:  5 comment:7 by NE2, 14 years ago

  • Using west/east instead of forward/backward

West/east is the way it's done for U.S. roads. I see you sorted it so you can tell that eastbound is one route, but you can't do the same for westbound. Compare it to the output of http://toolserver.org/~nakor/relation.fcgi?relation=450456&purge , where elements with no role are in both lists (because they carry eastbound and westbound CR 516).

comment:8 by bastiK, 14 years ago

Replying to stoecker:

Probably we could a a little sidewards line to left side when a node is connected to more than the next one and a little line to the right when the node is connect to something, but not to the next/previous one.

This would be an improvement, but it's not sufficient. The relations get more and more complex - see oxomoa scheme for example. Special validation tools for each type of relation and much better visualization will be required. In the meantime, there are other tools out there that try to do this, e.g.

http://betaplace.emaitie.de/webapps.relation-analyzer/index.jsp

comment:9 by NE2, 14 years ago

Summary: Improve linkedness display in relation editor to show multiple connectionsrelation analysis

The other issue is having to manually sort it. How'd you like to sort 946435?

comment:10 by stoecker, 14 years ago

Well, I'm not to sort your relations. Try yourself.

@bastiK:

Visual improvements in JOSM to ease work are our task, but we don't need to takeover the whole work of OSM related stuff. Let webservices do their work, JOSM its work. OSMInspector and others are required. Validator can't and shouldn't replace them.

by PetrDlouhy, 14 years ago

Attachment: forward_backward.patch added

forward/bacward analyzator for relation editor

comment:11 by PetrDlouhy, 14 years ago

Hello,

I made forward/backward analyzer for relation editor. It includes relation sorting and painting of the relation based on forward/backward roles.

by PetrDlouhy, 14 years ago

Attachment: forward_backward.png added

screenshot of patch in action

by PetrDlouhy, 14 years ago

Attachment: relation_sorting.osm added

testing data

comment:12 by PetrDlouhy, 14 years ago

Cc: PetrDlouhy added

by PetrDlouhy, 14 years ago

Attachment: forward_backward1.png added

One aditional screenshot with curcular route with forward parts

comment:13 by anonymous, 14 years ago

That looks pretty nice. Would it be possible to also recognize user-defined pairs (like north/south) without caring about direction?

When you say "it includes relation sorting" does that mean it will automatically sort the members for you?

comment:14 by NE2, 14 years ago

Damn it, that was me above.

comment:15 by PetrDlouhy, 14 years ago

Probably yes, but I will now focus on making this patch commitet first. I have started some aditional refactoring and bug fixing work.

Please write, how it should work more concretely.

by bastiK, 14 years ago

Attachment: design-suggestion.png added

comment:16 by bastiK, 14 years ago

I like it, too. Here is a suggestion for a slight change in visual presentation. (Upper half is current rendering and lower half is my proposal.)

Reasoning:

  • small black squares and larger red boxes represent nodes and the lines in between are the member ways.
  • when a route splits into 2 lanes, this usually happens in a "Y" shape and not in a "T" shape. The rounded corners are to represent a round island or forest.

comment:17 by PetrDlouhy, 14 years ago

bastiK: That looks better, I will try to do that.

NE2: How should north/south (east/west) notation work, if the branches get crossed without intersection (ie. using bridge)? Or the roles names are just acronyms for branch1/branch2?

by bastiK, 14 years ago

Attachment: unconnected-lane.png added

comment:18 by bastiK, 14 years ago

This revers to the first example in the second row of relation_sorting.osm.


Left is visualization from first patch, on the right is what i would expect.

by bastiK, 14 years ago

Attachment: left-right-left-right.png added

comment:19 by bastiK, 14 years ago

Here is another one:

If you have 2 lanes, it might be legitimate to mix like this:


The members are sorted 1,2,3,l1,r1,l2,r2,l3,r3,7,8,9. Left is current rendering and right what is expected.

by PetrDlouhy, 14 years ago

Attachment: forward_backward.2.patch added

new version of the patch

by PetrDlouhy, 14 years ago

Attachment: relation_sorting.2.osm added

new file with examples

comment:20 by PetrDlouhy, 14 years ago

Hello,

I made (sorry for double post of the patch) some refactoring and bug fixing, and I also implemented BastiK's suggestion (except comment:18). I focussed primarily on positive examples (see attachment:relation_sorting.2.osm). There are still several bugs, uncertainness solving, refactoring and unit testing to do.

BastiK: I like your examples, it helps a lot. Please make some more, if you have ideas (especially for negative examples).
I am not sure about comment:18 example - I am lacking something as common mechanism, when the line should be disconnected.

comment:21 by stoecker, 14 years ago

Summary: relation analysis[patch] relation analysis

by bastiK, 14 years ago

Attachment: left-right.osm added

2 examples for possible improvement

comment:22 by bastiK, 14 years ago

I added 2 examples. 1st shows a solid line in the order LRRLLL but it should be RRRLLL or LLLRRR. Second example illustrates my request from comment 19, but I'm not sure this is already addressed by the 3rd patch.

by bastiK, 14 years ago

Attachment: gap.png added

in reply to:  19 comment:23 by bastiK, 14 years ago

Here is how one could present a gap in one of the "branches". As always, current drawing left and suggestion right.


PS: I remember this was quite some fiddling to get it right even without forward and backward roles. Now there is another level of complexity. I can commit if it looks Ok for non-broken route relations. The ideal presentation for broken routes has lower priority as long as looks jumbled somehow. :)

comment:24 by PetrDlouhy, 14 years ago

Ok, I don't have more time for further development now (until end of the month, or so). It will be good to get this changes to users sooner, so please commit it, if you are satisfied with the current state.

I have done some more refactoring and bug fixing, so I am posting new patch.

I am not sure, if I was able to generate enough examples - particularly I didn't make test cases, if it doesn't visualize some incorrect cases as correct ones.

comment:25 by stoecker, 14 years ago

A note: Please add a testfile like routes.osm to "data_nodist" directory containing all recorded test-cases, so future improvements can validate against known issues.

comment:26 by PetrDlouhy, 14 years ago

I don't have time for making unit tests for that, could I left it for manual testing (for this moment)? Is it OK, if there will be also non-working cases with comment what is not working?

comment:27 by stoecker, 14 years ago

I don't mean unit tests. Simply an OSM file containing all cases probably with comments. See the other OSM files in that directory for examples.

by bastiK, 14 years ago

Attachment: b 95.osm added

this file throws NPE when opening the relation editor (patch 3 v2)

in reply to:  18 comment:28 by bastiK, 14 years ago

Replying to Petr_Dlouhy:

Ok, I don't have more time for further development now (until end of the month, or so). It will be good to get this changes to users sooner, so please commit it, if you are satisfied with the current state.

I have done some more refactoring and bug fixing, so I am posting new patch.

I am not sure, if I was able to generate enough examples - particularly I didn't make test cases, if it doesn't visualize some incorrect cases as correct ones.

It should work for most of the "real world" route relations. 2 issues are shown in the file "left-right.osm". Especially the first example from the file looks like a bug. When the NPE is resolved, I will download some relations from the database and see how it performs.

by PetrDlouhy, 14 years ago

Attachment: forward_backward.3.patch added

new version of the patch

comment:29 by PetrDlouhy, 14 years ago

I have added new version of the patch with fix for b_95 bug and testing cases added.

I hope, all other remaining issues can be considered as extra functionality (If you didn't find another clear bug). I have comments for them, but I will wait with that until the patch is commited, and separate bugs are opened for them.

comment:30 by bastiK, 14 years ago

In [3788/josm]:

see #5109 (patch by Petr Dlouhý) - take forward/backward roles for route relations into account (sorting and connectivity column in relation editor). This is still in development and has known limitations.

Opened 7 months ago

Last modified 102 minutes ago
[patch] relation analysis

comment:31 by bastiK, 14 years ago

Ok, committed your last patch. We need some "finetuning" before the next tested version. I'll add 2 more examples. First looks like a bug and second is some kind of edge case, but apparently not so uncommon.

by bastiK, 14 years ago

Attachment: connection-bug.osm added

Problems with connection and L/R

comment:32 by PetrDlouhy, 14 years ago

Hello,

thanks for committing, but the testing file seems not to be included.

I think, that this bug should be closed now, because the original requirement was (partially) covered. The remaining issues should probably be transfered to new tickets, because it is becoming chaotic here (it could point here for further description), it could get forgotten here and the issues should be tracked separately.

The connection bug is probably same as left-right (yet in testing file) and the roundabout is covered in testing file, although more testing cases could help.

in reply to:  32 ; comment:33 by bastiK, 14 years ago

Replying to Petr_Dlouhy:

Hello,

thanks for committing, but the testing file seems not to be included.

I'll add it later, when the feature is finished and more tests have been created.

I think, that this bug should be closed now, because the original requirement was (partially) covered. The remaining issues should probably be transfered to new tickets, because it is becoming chaotic here (it could point here for further description), it could get forgotten here and the issues should be tracked separately.

Ok, but I won't add all the files again.

in reply to:  33 comment:34 by PetrDlouhy, 14 years ago

Replying to bastiK:

Ok, but I won't add all the files again.

Ok, just point here, and write which files are relevant (or link the files, if Track support it).

comment:35 by bastiK, 14 years ago

I'm fine with a single thread, but feel free to open tickets for each issue.

comment:36 by PetrDlouhy, 14 years ago

I have reported the roundabout issue as ticket #5848.

by PetrDlouhy, 14 years ago

Attachment: left-right.diff added

few-liner which fixes left-right bug (ex1) and connection bug

comment:37 by PetrDlouhy, 14 years ago

I fixed left-right bug (same as connection bug).

The ex2 relation in the attachment:left-right.osm doesn't seem as correct ordering to me. The members in south pointing part are not in order. Or the bug is, that the north pointing part is not visualized correctly?

comment:38 by PetrDlouhy, 14 years ago

The broken branch problem is reported as ticket #5849 now.

in reply to:  description comment:39 by PetrDlouhy, 14 years ago

NE2: could you please report all issues, that are remaining here for you to the new bugs (you could point here, to shorten the description).

by PetrDlouhy, 14 years ago

Attachment: relation_analysis.osm added

small fixes to testing file

comment:40 by PetrDlouhy, 14 years ago

Keywords: relation_analyzer added

comment:41 by Claudius, 14 years ago

Does any developer see the possiblity for this relation branch visualisation to work without assigning the members "forward" and "backward" roles? You might take this road route relation as example which is has party branching off into dual carriageways and joining a few kilometers later. http://www.openstreetmap.org/browse/relation/1179604

The idea would be to check for nodes shared by three member ways in a relation to check for a branch through checking if two ways join again at another three-way node. Or via a more specialized way by checking for "oneway=yes" on two of the three ways departing that node. Doable?

in reply to:  41 comment:42 by PetrDlouhy, 14 years ago

Replying to Claudius Henrichs <claudius.h@…>:

Does any developer see the possiblity for this relation branch visualisation to work without assigning the members "forward" and "backward" roles? You might take this road route relation as example which is has party branching off into dual carriageways and joining a few kilometers later. http://www.openstreetmap.org/browse/relation/1179604

The idea would be to check for nodes shared by three member ways in a relation to check for a branch through checking if two ways join again at another three-way node. Or via a more specialized way by checking for "oneway=yes" on two of the three ways departing that node. Doable?

No, I don't think, that it is reasonable to do that. All applications working with branching routes needs clue, which way is passable which way. That information cannot be guessed by any observation. Not based on which way is on the left, because the two streams could be crossed, or it could be in Great Britain. Not based on oneway=yes, because it could be hiking/cycling route in opposite direction. Not based on anything else.

That is also the reason, why I don't thing, that left/right, north/west nor east/south roles could work.

See example, how it should be rendered.

Or am I missing some cases, when anything other than forward/backward is reasonable to use?

comment:43 by bastiK, 14 years ago

In [3789/josm]:

see #5109 (patch by Petr Dlouhy) - relation analysis; fix left-right and connection issue

comment:44 by PetrDlouhy, 14 years ago

Resolution: fixed
Status: newclosed

I am closing this ticket. If you see any remaining issues here, which are not covered by #5848 or #5849, feel free to open separate ticket for them.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain team.
as The resolution will be set.
The resolution will be deleted. Next status will be 'reopened'.

Add Comment


E-mail address and name can be saved in the Preferences .
 
Note: See TracTickets for help on using tickets.