Hi WanMil, before I start thinking about a different algorithm, I just want to make sure that I understood the cause of the problem in the existing one: 1) mkgmap complains when a subdivision has an area with a width > 0x7fff (if resolution is 24) 2) we add elements to the area and update the with and height of the area whenever an added element has a point that lies outside of the previous bounds. 3) the methods in PolygonSubdivSizeSplitterFilter and LineSizeSplitterFilter should make sure that a single element is not larger than the maximum size of 0x7fff (I think LineSizeSplitterFilter doesn't even do this correctly, but a corrected version did not solve the problem) The error message "Subdivision width is 36627..." is produced because of a long MapLine with a width of ~72000 that has just 7 points. The line between the first 6 points has a width < 30000, the last point is far away and adds the ~ 42000. That also means, the middle of the line is far away from any point that belongs to the line. Since LineSizeSplitterFilter just splits the line into parts that have a width < 0x7fff, we still add a part of the line that is far away from the middle of the MapArea and therefore outside of the maximum area size. Is that correct? To solve the problem, I think we have to find the first and last point which is not too far away from the center, and then split the element into 2 or 3 parts. Would that work? Gerd Gerd WanMil wrote
I think (for quite a while) that the subdivision split code requires a complete rework to get rid of problems with it.
A broad algorithm how subdivisons are created is: 1. Create subdivisions with maximum allowed size 2. Add all elements to their subdivision. An element is added to a subdivision if its center point lied within the subdivision. 3. For all subdivisions that are too big: Divide them into two halves and assign the elements again.
The fact that lines and shapes do not have one point only is completely ignored. So it might be possible that the center point lies within a subdivison but the bounding box of the element exhausts the max size of a subdivision.
I think the algorithm should be the other way round: Create a subdivision with minimum size and add (in an intelligent way) elements until the subdivision is full.
The problem is "in an intelligent way" because there are multiple restrictions for a subdivison so that it is not so easy to optimize the algorithm. I started with an improvement some time ago but did not finish it. Maybe I can dig out the old source code and post it so that you can have a look on it and use it as one idea how to improve the situation.
So long if you are interested in understanding what's happening there start with the classes MapSplitter MapArea all filter classes in uk.me.parabola.mkgmap.filters and of course Subdivision
WanMil
Hi,
I think the problem is not a polygon or something like this. MapSplitter contains a lot of tests to make sure that an area doesn't contain too many objects, but the test doesn't check for the case that the area is too large, so it skips the split process for a large almost empty area: if (area.getNumLines() > MAX_NUM_LINES || area.getNumPoints() > MAX_NUM_POINTS || (sizes[MapArea.POINT_KIND] + sizes[MapArea.LINE_KIND] + sizes[MapArea.SHAPE_KIND]) > MAX_RGN_SIZE || sizes[MapArea.XT_POINT_KIND] > MAX_XT_POINTS_SIZE || sizes[MapArea.XT_LINE_KIND] > MAX_XT_LINES_SIZE || sizes[MapArea.XT_SHAPE_KIND] > MAX_XT_SHAPES_SIZE){ ... }
log.debug("adding area unsplit", ",has points" + area.hasPoints());
later, in MapBuilder, this part causes the warning message: int w = ((area.getWidth() + 1)/2 + mask) >> shift; if (w > 0x7fff) { log.warn("Subdivision width is " + w + " at " + new Coord(latitude, longitude)); w = 0x7fff; }
I am not sure what kind of test we have to add in MapSplitter.
Gerd
Date: Sun, 22 Apr 2012 23:39:28 +0300 From: marko.makela@ To: mkgmap-dev@.org Subject: Re: [mkgmap-dev] Subdivision width is 36627 at 3230916/1236133
Hi WanMil,
AFAIK 3230916/1236133 is only the center point of the problematic polygon. I thought that my commit r2028 has fixed problems where a single polygon is too big to fit into a subdivision. This is done by the class PolygonSubdivSizeSplitterFilter.
Could the diagnostics be extended to show more details of the polygon, such as the WGS84 coordinates of some nodes (or the OSM id or tags, if they are available)? I am happy to apply such a patch and rerun, and narrow down the input if it is of any help. Currently, I am using mkgmap r2272.
The MapSplitter/MapArea class should be a good starting point to track down the problem.
I hope you or Gerd can figure this out. Sorry, my day job keeps me so busy that I do not have any spare brain power for coding or debugging at the moment.
Best regards,
Marko _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Subdivision-width-is-36627-at-3230916-1236133... Sent from the Mkgmap Development mailing list archive at Nabble.com.