search

aerostitch / testnavit

0 stars 0 forks source link

Multipolygon relations not handled correctly #65

Open aerostitch opened 13 years ago

aerostitch commented 13 years ago

Issue migrated from trac ticket # 754

component: tools | priority: major | keywords: multi, poly, water, coast

2011-01-27 23:49:22: jrahe created the issue

settlement (landuse=residential type=multipolygon) will not be displayed (colored) on the map.[[BR]]

example 1: http://www.openstreetmap.org/browse/relation/1304643[[BR]]

example 2: http://www.openstreetmap.org/browse/relation/1347636

Maybe similar problem like multipolygons for natural=water (http://trac.navit-project.org/ticket/689)

settlement (landuse=residential) are ok.[[BR]]

example 3: http://www.openstreetmap.org/browse/way/87861851[[BR]]

example 4: http://www.openstreetmap.org/browse/way/24961414

Greetings Jörg

aerostitch commented 13 years ago

2011-01-27 23:51:45: jrahe commented

I forgot: navit 0.2.0 3708 WinCE map from Planet::Extractor 26.01.2011

aerostitch commented 13 years ago

2011-01-28 04:04:10: jrahe commented

FYI Same or similar issue with maps from OSM in mapfactor Navigator 10 free http://forum.openstreetmap.org/viewtopic.php?id=9839&p=4

Greetings Jörg

aerostitch commented 13 years ago

2011-02-03 04:34:53: jrahe commented

FYI issue in mapfactor Navigator 10 free seemed to be solved:

Berichtigt, danke. ...neuere Dateien ... sollten zur Verfügung nächste Woche sein.
danke
Martin

s.a. http://forum.mapfactor.com/discussion/12/de-problem-darstellung-landuseresidential-mit-typemultipolygon/#Item_4 [[BR]]

(I wasn´t able yet to test it, because the next update will be next week)

Greetings Jörg

aerostitch commented 13 years ago

2011-02-25 04:07:01: jrahe changed priority from major to minor

aerostitch commented 13 years ago

2011-02-25 04:07:01: jrahe commented

Issue still exists in 0.2.0 4004 WinCE map from Planet::Extractor 25.02.2011

FYI: same issue in mapfactor Navigator is solved.

aerostitch commented 13 years ago

2011-02-25 04:31:47: korrosa commented

Hi jrahe - many thanks for keeping the ticket updated (and also for putting your custom menu on the wiki! Menu_configurations#QVGASquare.28240x240.29_Configuration1.28German.29 for those interested!)

As far as I know, Navit doesn't have full support for relations just yet (though they are recognised by maptool http://navit.svn.sourceforge.net/viewvc/navit/trunk/navit/navit/maptool/osm.c?view=markup) hence multipolygons are not yet supported. This is to the best of my knowledge, and by way of ensuring that you're aware that we're aware of the issue!

(If anyone knows different, please update this ticket!)

aerostitch commented 13 years ago

2011-02-28 12:52:55: jrahe commented

Hello korrosa, thanks for responding.

...its good to know that you know ;-)

Greetings Jörg

aerostitch commented 13 years ago

2011-08-31 06:01:52: @mvglasow commented

689 describes the same issue with lakes. I'm also seeing it happen with highways which are areas (tags on relation: type=multipolygon; highway=pedestrian; name=Place Scheurer-Kestner).

Links:

Tested on Android (CyanogenMod 7 on GeeksPhone One), 4696, map data downloaded today from planet extractor.

This is most likely a design question: where would relation data be applied to geometries? In maptool? In the map driver? In navit core? (Does any of the latter two have any capabilities that could be used for handilng relations?)

If the binfile format allows for complex geometries, such as polygons with holes, then it should be possible to break down multipolygon relations in maptool. Multiple role=outer members can be converted into multiple polygons (each with the same tags) if not directly supported by the binfile format.

I'm closing #689 as a duplicate of this ticket and extending the scope of this one to generic handling of multipolygons.

aerostitch commented 13 years ago

2011-08-31 06:01:52: @mvglasow

aerostitch commented 13 years ago

2011-08-31 06:03:18: @mvglasow changed title from Problem with multipolygon for landuse=residential to Multipolygon relations not handled correctly

aerostitch commented 13 years ago

2011-08-31 13:19:05: tryagain commented

AFAIK Multipolygones are handled in maptool. They should be working for country borders now. Not sure if cp15 done extending that to anything else.

aerostitch commented 13 years ago

2011-09-20 09:07:21: zoff99 commented

Priority: minor? i think you are underestimating that problem. already many rivers, lakes and some roads are disappearing in navit, because in OSM they have been converted to relations. --> (see danube in vienna, donau durch wien)

i fear that in a few months other features will become useless, when roads are missing. dont you thing so? this trend is progressing very fast

at least a workaround like user:mvglasow suggested should be applied ASAP!!

Multiple role=outer members can be converted into multiple polygons
(each with the same tags) if not directly supported by the binfile format.
aerostitch commented 13 years ago

2011-09-20 09:07:58: zoff99 changed priority from minor to major

aerostitch commented 13 years ago

2011-09-20 09:07:58: zoff99 changed component from core to tools

aerostitch commented 12 years ago

2011-10-13 01:32:12: wakefred@gmail.com commented

this problem still exists (svn 4838).

the multipolygons won't be visible in navit - its really annoying, because a lot of the lakes, rivers, forests, residentials, buildings, parkings (and much more) are taggt as multipolygons, and so many things are invisible in Navit.

its really a big problem.

have a look at these 2 pictures (both times the same area - one is a screenshot from osm.org; the other is a screenshot from navit):

http://trac.navit-project.org/attachment/ticket/689/osm_with_lakes.png

http://trac.navit-project.org/attachment/ticket/689/navit_without_lakes.png

aerostitch commented 12 years ago

2011-10-13 01:32:12: wakefred@gmail.com

aerostitch commented 12 years ago

2011-12-11 07:57:38: tegzed commented

Hello,

I created a patch for maptool to handle multipolygons (see attached water_relation.diff). Currently it is in early pre-experimental :) state and handles only natural="water" multipolygons. Running this version of maptool I experienced other problems (which appeared for me before the modification also). I think it is related to self intersecting coastlines, but I'm not sure. Maybe the algorithm that breaks coastlines into tiles needs some improvement. Please test the patch and let me know how it works for you.

David Tegze

aerostitch commented 12 years ago

2011-12-26 14:02:50: tegzed commented

Latest update to the patch solves some issues of the previous version. Now it filters out self-intersecting multipolygons, and only outer polygons are used. I tested the patch with osm data of Hungary and Austria and the non-self-intersecting multipolygons I tested were OK. If I get positive feedbacks I will commit it after some cleanup.

aerostitch commented 12 years ago

2011-12-27 07:54:42: tegzed commented

I have updated the patch again. When applied, maptool skips self-intersecting water areas not only for multipolygons but for ordinary polygons, too. This avoids flooding effects I experienced by the osm data of certain countries (Germany and Romania and maybe some others also).

aerostitch commented 12 years ago

2012-01-03 10:42:51: tegzed uploaded file water_relation.diff (10.2 KiB)

fixed waterway="riverbank" tag support

aerostitch commented 12 years ago

2012-01-04 00:50:40: wakefred@gmail.com commented

@tegzed... looks great and works fine for my maps. thanks for this patch. I hope, there will be a patch available for the other MP-areas soon. And I hope also, it will be integrate in the original source code.

aerostitch commented 12 years ago

2012-01-04 02:16:11: korrosa commented

tegzed: Ignore what I previously told you on IRC - the patch works fine for me too!

aerostitch commented 12 years ago

2012-01-05 08:01:18: tegzed commented

Hi korrosa, hi wakefred,

Thanks for your feedback, I'll implement the handling of other MP areas when I can find the time for that. Hopefully in a couple of days. Next version will map osm tags to navit item types using the same mechanism that is used for non-MP items today.

aerostitch commented 12 years ago

2012-01-08 08:48:50: tegzed commented

Hello,

I updated the patch again(see area_relation.diff), now all area typed items are generated based on the relation tags that would be generated for a normal way with the same tags. This version also emits warnings about self intersecting polygons during way and relation processing, so the user have some info about the skipped items (self-intersecting polygons introduce nasty flooding effect in navit). Unfortunately currently navit's map drivers cannot handle polygons with holes, so inner members are not processed. After some testing the patch seems to generate most of the items that were missing before.

aerostitch commented 12 years ago

2012-01-09 00:05:10: wakefred@gmail.com commented

@tegzed... now, with this new patch (area_relation.diff), the multipolygon-lakes are not visible in navit.

aerostitch commented 12 years ago

2012-01-09 02:58:08: tegzed commented

Hi wakefred,

Can you pls link a non-visible lake? Maybe it is self-intersecting (you will see a line something like this for the problemmatic relation in the maptool output: ''OSM Warning:http://www.openstreetmap.org/browse/relation/1691138 Self intersecting relation area '') or no rule matches the tags of the lake.

aerostitch commented 12 years ago

2012-01-09 03:05:38: wakefred@gmail.com commented

p.e. http://www.openstreetmap.org/browse/relation/1537206 with the patch water_relation.diff this lake is visible in navit, but not with the area_relation.diff

aerostitch commented 12 years ago

2012-01-09 08:47:03: tegzed commented

Thanks for the link, the problem was related to handling the rule matching after mapping osm tags to navit type. When we had more that one matches, only one item is generated from the first match. Now we generate an item for each match. Please let me know your results with the updated patch.

aerostitch commented 12 years ago

2012-01-09 10:40:21: wakefred@gmail.com commented

@tegzed... thanks a lot... now, it work's perfect for me.

aerostitch commented 12 years ago

2012-01-13 12:58:51: tegzed uploaded file area_relation.diff (17.1 KiB)

added support for disjunct outer polygons

aerostitch commented 12 years ago

2012-01-13 13:04:13: tegzed commented

Hello,

I updated the patch again, this version supports disjunct outer polygons. If you can test it, please give me some feedback about the results.

aerostitch commented 12 years ago

2012-01-13 14:42:40: wakefred@gmail.com commented

@tegzed... works like a charm...

aerostitch commented 12 years ago

2012-01-15 06:17:39: wakefred@gmail.com uploaded file navit.png (50.4 KiB)

navit.png

aerostitch commented 12 years ago

2012-01-15 06:17:47: wakefred@gmail.com uploaded file osm.png (124.5 KiB)

osm.png

aerostitch commented 12 years ago

2012-01-15 06:18:08: wakefred@gmail.com commented

@tegzed... now, it would be great, if the islets will be also rendered. p.e. the ways 125314597 and 125319223 in the relation 1282756. link: http://www.openstreetmap.org/?lat=46.69811&lon=7.1009&zoom=17&layers=M see also the screenshots: in navit, the islet isn't visible ( http://trac.navit-project.org/attachment/ticket/754/navit.png ). in mapnik is the islet visible ( http://trac.navit-project.org/attachment/ticket/754/osm.png ).

aerostitch commented 12 years ago

2012-01-15 06:18:08: wakefred@gmail.com

aerostitch commented 12 years ago

2012-01-15 06:18:08: wakefred@gmail.com

aerostitch commented 12 years ago

2012-01-17 04:20:05: tegzed commented

Hello wakefred,

Unfortunately supporting polygons with holes is not so easy, since current map file formats cannot represent these polygons and map drivers and graphics drivers in navit do not support polygons of this type. After the representation problem is solved in the map file formats, we need a good tessellation routine to cut these polygons into several polygons without holes, but this is also not very easy. I think the solution should be discussed with Cp15. The most correct solution would be to redesign the mentioned parts which would be a huge work...

aerostitch commented 12 years ago

2012-01-17 04:29:47: wakefred@gmail.com uploaded file multipolygon.png (113.9 KiB)

multipolygon.png

aerostitch commented 12 years ago

2012-01-17 04:33:39: wakefred@gmail.com commented

@tegzed... I'm not sure, if I understand it correctly... But, if you have a look at the attached screenshot "multipolygon.png" ( http://trac.navit-project.org/attachment/ticket/754/multipolygon.png ), you can see, for other multipolygons, it works... p.e. at this MP id=1713904, the islets are visible, which are tagged as natural=scrub.

aerostitch commented 12 years ago

2012-01-17 04:33:39: wakefred@gmail.com

aerostitch commented 12 years ago

2012-01-17 10:54:55: tegzed commented

I think in your last example not only the but the elements of the islands are tagged so that separate items are generated for them. These items are rendered above the item that is generated from the relation. Maybe in the case above where inslets are not rendered, the tags are not tagged,so only the relation is rendered - without hole. The problem is that the existing item structure in navit cannot be extended to contain info about inner polygons in a way it remains compatible with the existing code.

aerostitch commented 12 years ago

2012-01-18 23:00:17: wakefred@gmail.com commented

all right. thanks for the answer. but i have another islet: per excample the way with the id=125314599. this islet have the tag natural=wood directly on the way. but in navit its not rendered. here is a direct link to the islet: http://www.openstreetmap.org/?lat=46.68156&lon=7.0957&zoom=17&layers=M you see, its the same scheme like http://trac.navit-project.org/attachment/ticket/754/multipolygon.png where the islets will be rendered (at these islets here its just missing the tag place=islet and they are tagged as natural=scrub instead of natural=wood)

aerostitch commented 12 years ago

2012-01-19 00:31:23: tegzed commented

Maybe in this case the water is rendered after the island and you will not see the island. As I remember render order is specified by the order of itemgra entries in navit.xml. Anyway I thought about the problem and maybe there is a solution. Maybe the info about inner polygons can be stored as an attribute of the map item and the polygon rendering routine should be modified to render polygons with such an attribute using a special method that can handle polygons with holes. In this way we can avoid modifying the map format and the related large amount of code in maptool and binfile/textfile map driver. I will try to implement this and attach a patch when I have some time for that.

aerostitch commented 12 years ago

2012-01-19 00:39:47: wakefred@gmail.com commented

that would be great, if you can implement this. thanks a lot for your effort.

aerostitch commented 12 years ago

2012-02-01 12:56:15: tegzed commented

Hello again,

I attached an initial version of relation area handling with hole support. I introduced a new attribute type to hold the info about the inner members of the relations. Both maptool and navit is updated. This modification stores inner polygon info into an attribute of the generated map items. Navit uses this info to triangulate these items so that the holes are preserved. The triangulation algorithm is borrowed from here: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html and modified to fit navit. The source code for the triangulator is from ftp://ftp.cs.unc.edu/pub/users/manocha/CODE/Triangulation/triangulation.tar.gz . Maybe I will change the design to do the triangulation in maptool and store the info about the triangles in an attribute if it turns out that the trianagulation takes too much cpu cycles runtime. However this will result in bigger map files. The code is not yet complete, it needs a lot of clean up and arrangement and there may be cases where the triangulator will not work, but I experienced that it works well for most non-intersecting polygons. Intersecting polygons are filtered out since the triangulator cannot handle them. If you try this please let me know your experiences.

aerostitch commented 12 years ago

2012-02-12 05:50:12: tegzed commented

Hi,

In the latest diff I moved triangulation of polygons with holes to maptool to improve runtime performance of navit. Please test it and let me know your results.

Dandor

aerostitch commented 12 years ago

2012-02-12 09:45:11: wakefred@gmail.com commented

hi tegzed, this patch don't work... I would create a map from Switzerland and I get this message in the terminal:

...
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
OSM Warning:http://www.openstreetmap.org/browse/relation/16239 Broken country polygon 'AT'
navit:attr_data_size:size for (null) unknown
OSM Warning:http://www.openstreetmap.org/browse/relation/51477 Broken country polygon 'de'
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
navit:attr_data_size:size for (null) unknown
Speicherzugriffsfehler

After the message "Speicherzugriffsfehler" it stops.

I've installed the svn-4936 and the new patch polygon_hole.diff (on a Ubuntu 11.10). On my Ubuntu the old patch area_relation.diff with svn-4854 work's perfekt.

aerostitch commented 12 years ago

2012-02-19 05:49:56: tegzed commented

Hi wakefred,

Thanks for your feedbacks again. I uploaded another version which should behave better in cases where the previous one crashed. Please try it and let me know if this fixes the problems on your side too.

aerostitch commented 12 years ago

2012-02-19 08:40:40: wakefred@gmail.com commented

Hi tegzed,

I've tested this Patch again. This time without the error as above. But the holes in the Multipolygons are still not visible (p.e. http://www.openstreetmap.org/?lat=46.68156&lon=7.0957&zoom=17&layers=M ). And with this patch, there are also a lot of Multipolygons (without holes) not visible (p.e. the MP with landuse=residential in my village http://www.openstreetmap.org/?lat=46.74153&lon=7.28581&zoom=16&layers=M ). The old patch area_relation.diff with svn-4854 show's these landuses correctly.