Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Gerd/WanMil, I now have a mechanism working that has no performance overhead. I have derived a new class from Node and have moved the evaluation of the location to when getLocation is first called in the new class. I have also improved the algorithm by progressively using bigger bitmaps if a small one doesn't produce a suitable result. I'm now looking at doing the same for multi-polygons before putting together a patch. I should have something for you to try shortly. Regards, Mike From: Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] Sent: 08 January 2015 20:23 To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi WanMil, yes, I had something like this in mind. StyledConverter could call the POIGenerator for each polygon. The POIGenerator creates a dummy node, opies the tags, adds the mkgmap:area2poi=true tag and checks if the style produces a map element. If yes, it calculates the coords and returns the node which is than passed to addNode. Anyhow, this change is only useful when performance is a problem. I once had a similar idea for mp-processing. Gerd Date: Thu, 8 Jan 2015 20:55:46 +0100 From: wmgc...@web.de mailto:wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk mailto:mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Gerd, I think there are many drawbacks to move the POI generation into the style code. At least it will complicate the style code. Maybe it is better to implement your idea directly in the POIGeneratorHook. If it has access to the point style it could check itself if the polygon will (probably) create a POI. Maybe it could first test if there is any overlap of the polygon tags with the tags used in the points file. Then it could pass an artifical POI through the points style and check if a POI is created (finally rules might be disabled to speed up the processing). The hook might also decide how to proceed dependent on the complexity of the polygon. By the way: Did you think of having different methods depending on the use case? So one getCofG() for POI placement, one getHouseNumberPoint() for housenumber processing etc. It sounds like it is hard to find one algorithm that fits all. WanMil Hi Mike, reg. POI for polygons like rivers etc: The current algo calculates a POI for each polygon before any style rule is applied. If the calculation of the Coord takes a lot of time, and many of the POI are later dropped in the points rules, maybe it is possible to create a dummy object first, pass it through the style rules, check if it produces a map object, and calculate the exact position only for those. I think we would have to change/remove the POIGeneratorHook and call it on the fly, but I don't see any big problem with that. Gerd From: m...@tvage.co.uk mailto:m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk mailto:mkgmap-dev@lists.mkgmap.org.uk Date: Wed, 7 Jan 2015 09:29:51 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() HI Gerd, the method I've used won't work if the polygon is thinner than the resolution of the bitmap. I hadn't considered that it might be used on rivers; my main testing has been on car parks, which although they may be irregularly shaped are not normally very long and very thin (I handle river names from the underlying lines). There are two possible problems that could occur - if a polygon is thin enough that it renders in the bitmap as a line that is nowhere wider than 2 pixels the POI could be placed just outside the polygon. I haven't checked what fillPolygon does if the points have no volume and form a line. If this renders nothing, then the algo will just return the centre point, which could be nowhere near the polygon. A simple solution to the first problem would be to examine the biggestSquaredDistanceToBlack figure before returning the coordinate and if the value is 1, repeat the operation on a small area around the point to get a better accuracy. I'll look into that. For the second problem I'll add an error message, so we can determine if it actually occurs (biggestSquaredDistanceToBlack is 0). I've also thought that having drawn the bitmap, it might be more efficient to then copy its contents out into an array so that finding the distances from pixels inside the polygon to those outside become simple array lookups instead of graphics function calls. I'll look into that as well. Cheers, Mike *From:*Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] *Sent:* 07 January 2015 06:55 *To:* mkgmap-dev@lists.mkgmap.org.uk mailto:mkgmap-dev@lists.mkgmap.org.uk *Subject:* Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, on my PC the performance of your algo is quite good. Attached is a patch
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Miike, sounds great! Reg. mp-processing: Not sure what you plan to do here. Maybe that is not so easy, keep in mind that we have the area_size() style function, so you probably have to calculate at least the outer shape before you can check if the style is creating a map object. Gerd From: m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk Date: Fri, 9 Jan 2015 00:20:56 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Gerd/WanMil, I now have a mechanism working that has no performance overhead. I have derived a new class from Node and have moved the evaluation of the location to when getLocation is first called in the new class. I have also improved the algorithm by progressively using bigger bitmaps if a small one doesn’t produce a suitable result. I’m now looking at doing the same for multi-polygons before putting together a patch. I should have something for you to try shortly. Regards,Mike From: Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] Sent: 08 January 2015 20:23 To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi WanMil, yes, I had something like this in mind. StyledConverter could call the POIGenerator for each polygon. The POIGenerator creates a dummy node, opies the tags, adds the mkgmap:area2poi=true tag and checks if the style produces a map element. If yes, it calculates the coords and returns the node which is than passed to addNode. Anyhow, this change is only useful when performance is a problem. I once had a similar idea for mp-processing. Gerd Date: Thu, 8 Jan 2015 20:55:46 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Gerd, I think there are many drawbacks to move the POI generation into the style code. At least it will complicate the style code. Maybe it is better to implement your idea directly in the POIGeneratorHook. If it has access to the point style it could check itself if the polygon will (probably) create a POI. Maybe it could first test if there is any overlap of the polygon tags with the tags used in the points file. Then it could pass an artifical POI through the points style and check if a POI is created (finally rules might be disabled to speed up the processing). The hook might also decide how to proceed dependent on the complexity of the polygon. By the way: Did you think of having different methods depending on the use case? So one getCofG() for POI placement, one getHouseNumberPoint() for housenumber processing etc. It sounds like it is hard to find one algorithm that fits all. WanMil Hi Mike, reg. POI for polygons like rivers etc: The current algo calculates a POI for each polygon before any style rule is applied. If the calculation of the Coord takes a lot of time, and many of the POI are later dropped in the points rules, maybe it is possible to create a dummy object first, pass it through the style rules, check if it produces a map object, and calculate the exact position only for those. I think we would have to change/remove the POIGeneratorHook and call it on the fly, but I don't see any big problem with that. Gerd From: m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk Date: Wed, 7 Jan 2015 09:29:51 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() HI Gerd, the method I’ve used won’t work if the polygon is thinner than the resolution of the bitmap. I hadn’t considered that it might be used on rivers; my main testing has been on car parks, which although they may be irregularly shaped are not normally very long and very thin (I handle river names from the underlying lines). There are two possible problems that could occur – if a polygon is thin enough that it renders in the bitmap as a line that is nowhere wider than 2 pixels the POI could be placed just outside the polygon. I haven’t checked what fillPolygon does if the points have no volume and form a line. If this renders nothing, then the algo will just return the centre point, which could be nowhere near the polygon. A simple solution to the first problem would be to examine the biggestSquaredDistanceToBlack figure before returning the coordinate and if the value is 1, repeat the operation on a small area around the point to get a better accuracy. I’ll look into that. For the second problem I’ll add an error message, so we can determine if it actually occurs (biggestSquaredDistanceToBlack is 0). I’ve also thought that having drawn the bitmap, it might be more efficient to then copy its contents out into an array so that finding the distances from pixels inside the polygon to those outside become simple array lookups instead of graphics function calls. I’ll look into that as well. Cheers, Mike *From:*Gerd
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Mike, reg. POI for polygons like rivers etc: The current algo calculates a POI for each polygon before any style rule is applied. If the calculation of the Coord takes a lot of time, and many of the POI are later dropped in the points rules, maybe it is possible to create a dummy object first, pass it through the style rules, check if it produces a map object, and calculate the exact position only for those. I think we would have to change/remove the POIGeneratorHook and call it on the fly, but I don't see any big problem with that. Gerd From: m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk Date: Wed, 7 Jan 2015 09:29:51 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() HI Gerd, the method I’ve used won’t work if the polygon is thinner than the resolution of the bitmap. I hadn’t considered that it might be used on rivers; my main testing has been on car parks, which although they may be irregularly shaped are not normally very long and very thin (I handle river names from the underlying lines). There are two possible problems that could occur – if a polygon is thin enough that it renders in the bitmap as a line that is nowhere wider than 2 pixels the POI could be placed just outside the polygon. I haven’t checked what fillPolygon does if the points have no volume and form a line. If this renders nothing, then the algo will just return the centre point, which could be nowhere near the polygon. A simple solution to the first problem would be to examine the biggestSquaredDistanceToBlack figure before returning the coordinate and if the value is 1, repeat the operation on a small area around the point to get a better accuracy. I’ll look into that. For the second problem I’ll add an error message, so we can determine if it actually occurs (biggestSquaredDistanceToBlack is 0). I’ve also thought that having drawn the bitmap, it might be more efficient to then copy its contents out into an array so that finding the distances from pixels inside the polygon to those outside become simple array lookups instead of graphics function calls. I’ll look into that as well. Cheers,Mike From: Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] Sent: 07 January 2015 06:55 To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, on my PC the performance of your algo is quite good. Attached is a patch that contains your patch as well as my quick implementation of the algo described here: http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf The patch tests only performance, it computes the center with the 3 different algos, I've commented the part that prints times and GPX data for debug purposes. I noticed that the results between both algos are very different, I did not yet try to find out which one is better, but mine is much slower on my PC. I also noticed that your algo doesn't always calculate a point in the polygon, see e.g. way 178708143. If you like, please try to find a better compromise, I like to fix a problem in splitter first. I also did not yet look at the effect on the house number code, as there are many more small open problems, but I think it should be easy to sort that out. Gerd Date: Tue, 6 Jan 2015 13:23:57 -0700 From: gpetermann_muenc...@hotmail.com To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, I like the idea, but it seems to be slow. Is it possible that your algo suffers when no fast graphics card is available? On my netbook the performance is very poor, did not yet try on the PC, but that also has no high speed graphics. Gerd GerdP wrote Hi Mike, 50% sounds better than my algo, but still quite a lot. I'll have a closer look at your algo later. Please note that your change has a side effect on the house number generator. Up to now this doesn't contain a filter for generated POI, so each polygon with a house number is processed twice, once because of the POI, once because the Generator uses Way.getCofG(). If both have different positions this might have a negative impact. Gerd From: mike@.co To: mkgmap-dev@.org Date: Tue, 6 Jan 2015 14:56:30 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() I have a working solution for ensuring that the created point is placed within the polygon when using --add-pois-to-areas, based on drawing the polygon on to a small monochrome bitmap and then looking for the point that is furthest from the surrounding area. I used a 9x9 bitmap for polygons having a small number of points and 15x15 for longer polygons. There is however a performance penalty. My standard map takes about 1 hour 20 minutes; using this algorithm the time increases by about 50% to about 2 hours. I am not currently able to commit changes to SVN (perhaps someone can help out with that) but I have attached the code changes. I suggest
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi WanMil, yes, I had something like this in mind. StyledConverter could call the POIGenerator for each polygon. The POIGenerator creates a dummy node, opies the tags, adds the mkgmap:area2poi=true tag and checks if the style produces a map element. If yes, it calculates the coords and returns the node which is than passed to addNode. Anyhow, this change is only useful when performance is a problem. I once had a similar idea for mp-processing. Gerd Date: Thu, 8 Jan 2015 20:55:46 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Gerd, I think there are many drawbacks to move the POI generation into the style code. At least it will complicate the style code. Maybe it is better to implement your idea directly in the POIGeneratorHook. If it has access to the point style it could check itself if the polygon will (probably) create a POI. Maybe it could first test if there is any overlap of the polygon tags with the tags used in the points file. Then it could pass an artifical POI through the points style and check if a POI is created (finally rules might be disabled to speed up the processing). The hook might also decide how to proceed dependent on the complexity of the polygon. By the way: Did you think of having different methods depending on the use case? So one getCofG() for POI placement, one getHouseNumberPoint() for housenumber processing etc. It sounds like it is hard to find one algorithm that fits all. WanMil Hi Mike, reg. POI for polygons like rivers etc: The current algo calculates a POI for each polygon before any style rule is applied. If the calculation of the Coord takes a lot of time, and many of the POI are later dropped in the points rules, maybe it is possible to create a dummy object first, pass it through the style rules, check if it produces a map object, and calculate the exact position only for those. I think we would have to change/remove the POIGeneratorHook and call it on the fly, but I don't see any big problem with that. Gerd From: m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk Date: Wed, 7 Jan 2015 09:29:51 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() HI Gerd, the method I’ve used won’t work if the polygon is thinner than the resolution of the bitmap. I hadn’t considered that it might be used on rivers; my main testing has been on car parks, which although they may be irregularly shaped are not normally very long and very thin (I handle river names from the underlying lines). There are two possible problems that could occur – if a polygon is thin enough that it renders in the bitmap as a line that is nowhere wider than 2 pixels the POI could be placed just outside the polygon. I haven’t checked what fillPolygon does if the points have no volume and form a line. If this renders nothing, then the algo will just return the centre point, which could be nowhere near the polygon. A simple solution to the first problem would be to examine the biggestSquaredDistanceToBlack figure before returning the coordinate and if the value is 1, repeat the operation on a small area around the point to get a better accuracy. I’ll look into that. For the second problem I’ll add an error message, so we can determine if it actually occurs (biggestSquaredDistanceToBlack is 0). I’ve also thought that having drawn the bitmap, it might be more efficient to then copy its contents out into an array so that finding the distances from pixels inside the polygon to those outside become simple array lookups instead of graphics function calls. I’ll look into that as well. Cheers, Mike *From:*Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] *Sent:* 07 January 2015 06:55 *To:* mkgmap-dev@lists.mkgmap.org.uk *Subject:* Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, on my PC the performance of your algo is quite good. Attached is a patch that contains your patch as well as my quick implementation of the algo described here: http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf The patch tests only performance, it computes the center with the 3 different algos, I've commented the part that prints times and GPX data for debug purposes. I noticed that the results between both algos are very different, I did not yet try to find out which one is better, but mine is much slower on my PC. I also noticed that your algo doesn't always calculate a point in the polygon, see e.g. way 178708143. If you like, please try to find a better compromise, I like to fix a problem in splitter first. I also did not yet look at the effect on the house number code, as there are many more small open problems, but I think it should be easy to sort that out
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Gerd, I think there are many drawbacks to move the POI generation into the style code. At least it will complicate the style code. Maybe it is better to implement your idea directly in the POIGeneratorHook. If it has access to the point style it could check itself if the polygon will (probably) create a POI. Maybe it could first test if there is any overlap of the polygon tags with the tags used in the points file. Then it could pass an artifical POI through the points style and check if a POI is created (finally rules might be disabled to speed up the processing). The hook might also decide how to proceed dependent on the complexity of the polygon. By the way: Did you think of having different methods depending on the use case? So one getCofG() for POI placement, one getHouseNumberPoint() for housenumber processing etc. It sounds like it is hard to find one algorithm that fits all. WanMil Hi Mike, reg. POI for polygons like rivers etc: The current algo calculates a POI for each polygon before any style rule is applied. If the calculation of the Coord takes a lot of time, and many of the POI are later dropped in the points rules, maybe it is possible to create a dummy object first, pass it through the style rules, check if it produces a map object, and calculate the exact position only for those. I think we would have to change/remove the POIGeneratorHook and call it on the fly, but I don't see any big problem with that. Gerd From: m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk Date: Wed, 7 Jan 2015 09:29:51 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() HI Gerd, the method I’ve used won’t work if the polygon is thinner than the resolution of the bitmap. I hadn’t considered that it might be used on rivers; my main testing has been on car parks, which although they may be irregularly shaped are not normally very long and very thin (I handle river names from the underlying lines). There are two possible problems that could occur – if a polygon is thin enough that it renders in the bitmap as a line that is nowhere wider than 2 pixels the POI could be placed just outside the polygon. I haven’t checked what fillPolygon does if the points have no volume and form a line. If this renders nothing, then the algo will just return the centre point, which could be nowhere near the polygon. A simple solution to the first problem would be to examine the biggestSquaredDistanceToBlack figure before returning the coordinate and if the value is 1, repeat the operation on a small area around the point to get a better accuracy. I’ll look into that. For the second problem I’ll add an error message, so we can determine if it actually occurs (biggestSquaredDistanceToBlack is 0). I’ve also thought that having drawn the bitmap, it might be more efficient to then copy its contents out into an array so that finding the distances from pixels inside the polygon to those outside become simple array lookups instead of graphics function calls. I’ll look into that as well. Cheers, Mike *From:*Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] *Sent:* 07 January 2015 06:55 *To:* mkgmap-dev@lists.mkgmap.org.uk *Subject:* Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, on my PC the performance of your algo is quite good. Attached is a patch that contains your patch as well as my quick implementation of the algo described here: http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf The patch tests only performance, it computes the center with the 3 different algos, I've commented the part that prints times and GPX data for debug purposes. I noticed that the results between both algos are very different, I did not yet try to find out which one is better, but mine is much slower on my PC. I also noticed that your algo doesn't always calculate a point in the polygon, see e.g. way 178708143. If you like, please try to find a better compromise, I like to fix a problem in splitter first. I also did not yet look at the effect on the house number code, as there are many more small open problems, but I think it should be easy to sort that out. Gerd Date: Tue, 6 Jan 2015 13:23:57 -0700 From:gpetermann_muenc...@hotmail.com mailto:gpetermann_muenc...@hotmail.com To:mkgmap-dev@lists.mkgmap.org.uk mailto:mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue withWay.getCofG() Hi Mike, I like the idea, but it seems to be slow. Is it possible that your algo suffers when no fast graphics card is available? On my netbook the performance is very poor, did not yet try on the PC, but that also has no high speed graphics. Gerd GerdP wrote Hi Mike, 50% sounds better than my algo, but still quite a lot. I'll have a closer look at your algo later. Please note that your change has a side effect on the house number generator. Up to now this doesn't contain a filter for generated POI, so each
Re: [mkgmap-dev] small issue with Way.getCofG()
HI Gerd, the method I've used won't work if the polygon is thinner than the resolution of the bitmap. I hadn't considered that it might be used on rivers; my main testing has been on car parks, which although they may be irregularly shaped are not normally very long and very thin (I handle river names from the underlying lines). There are two possible problems that could occur - if a polygon is thin enough that it renders in the bitmap as a line that is nowhere wider than 2 pixels the POI could be placed just outside the polygon. I haven't checked what fillPolygon does if the points have no volume and form a line. If this renders nothing, then the algo will just return the centre point, which could be nowhere near the polygon. A simple solution to the first problem would be to examine the biggestSquaredDistanceToBlack figure before returning the coordinate and if the value is 1, repeat the operation on a small area around the point to get a better accuracy. I'll look into that. For the second problem I'll add an error message, so we can determine if it actually occurs (biggestSquaredDistanceToBlack is 0). I've also thought that having drawn the bitmap, it might be more efficient to then copy its contents out into an array so that finding the distances from pixels inside the polygon to those outside become simple array lookups instead of graphics function calls. I'll look into that as well. Cheers, Mike From: Gerd Petermann [mailto:gpetermann_muenc...@hotmail.com] Sent: 07 January 2015 06:55 To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, on my PC the performance of your algo is quite good. Attached is a patch that contains your patch as well as my quick implementation of the algo described here: http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf The patch tests only performance, it computes the center with the 3 different algos, I've commented the part that prints times and GPX data for debug purposes. I noticed that the results between both algos are very different, I did not yet try to find out which one is better, but mine is much slower on my PC. I also noticed that your algo doesn't always calculate a point in the polygon, see e.g. way 178708143. If you like, please try to find a better compromise, I like to fix a problem in splitter first. I also did not yet look at the effect on the house number code, as there are many more small open problems, but I think it should be easy to sort that out. Gerd Date: Tue, 6 Jan 2015 13:23:57 -0700 From: gpetermann_muenc...@hotmail.com mailto:gpetermann_muenc...@hotmail.com To: mkgmap-dev@lists.mkgmap.org.uk mailto:mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, I like the idea, but it seems to be slow. Is it possible that your algo suffers when no fast graphics card is available? On my netbook the performance is very poor, did not yet try on the PC, but that also has no high speed graphics. Gerd GerdP wrote Hi Mike, 50% sounds better than my algo, but still quite a lot. I'll have a closer look at your algo later. Please note that your change has a side effect on the house number generator. Up to now this doesn't contain a filter for generated POI, so each polygon with a house number is processed twice, once because of the POI, once because the Generator uses Way.getCofG(). If both have different positions this might have a negative impact. Gerd From: mike@.co mailto:mike@.co To: mkgmap-dev@.org mailto:mkgmap-dev@.org Date: Tue, 6 Jan 2015 14:56:30 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() I have a working solution for ensuring that the created point is placed within the polygon when using --add-pois-to-areas, based on drawing the polygon on to a small monochrome bitmap and then looking for the point that is furthest from the surrounding area. I used a 9x9 bitmap for polygons having a small number of points and 15x15 for longer polygons. There is however a performance penalty. My standard map takes about 1 hour 20 minutes; using this algorithm the time increases by about 50% to about 2 hours. I am not currently able to commit changes to SVN (perhaps someone can help out with that) but I have attached the code changes. I suggest that due to the performance penalty, if we adopt this, then the --add-pois-to-areas option be extended to be --add-pois-to-areas[=centre|optimised] or something similar, with the default being centre and functioning as now and the optimised option invoking the new code. Please try out the suggested change. Note I don't expect this to work properly where a polygon is formed from a multiploygon relation, but the code could quite easily be adapted for this circumstance. Regards, Mike ___ mkgmap-dev mailing list
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi, I coded the described algo, it contained a small error, but seems to work, but it is much slower than the simple existing algo, esp. in those cases were the simple algo works fine, as it requires tons of rather complex distance calculations for each polygon. I will look for some optimization, but I think the improvement is too small for now. Gerd Date: Sun, 4 Jan 2015 22:08:51 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Gerd, yep, good catch. Seems to be a good solution for mkgmap! WanMil Hi WanMil, I think the problem is similar to finding the largest circle in a concave polygon, and we are not interested in the exact solution, any point close enough to the center is good. See e.g. http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf which contains an iterative algo. Gerd WanMil wrote Hi Gerd, a good algorithm to find a point for the --add-pois-to-areas option would be to use the straight skeleton algorithm (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012394.html). This might be used to find a point with maximum distance to the border of a polygon. Anyhow it seems to be a complex algorithm so maybe not the ideal solution for mkgmap. WanMil Hi Steve, Steve Ratcliffe wrote On 03/01/15 08:15, Gerd Petermann wrote: @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Seems like the current method would tend to place the point near the most complex part of the boundary. This may not be bad, I would have to see lots of real examples to be sure. Yes, correct. I compared these three algos: 1) the existing 2) my patched one 3) center of bbox For complex shapes (many points), 1) and 2) produce almost equal results, and in fact the point was more often within the shape. For simple polygons like small parks, buildings, etc. 1) is worst, 2) is better and 3) is best. My conclusion: the patch is a simple and good improvement, for housenumber location calculation maybe it would be better to use algo 3). Steve Ratcliffe wrote Anyway there are no easy (or even any difficult!) methods that work in all cases, so I would just keep it as it is and perhaps should the calculated point be outside the box, move it to the closest point inside. I already looked at the link provided by Andrzej. If I got that right, we have two different problems regarding the generated POI: We calculate it once for the whole polygon, before clipping it to the bbox of the tile, and it might be outside of the polygon as well as outside of the bbox. This brought me back to the non-rectangular tile problem and I stop searching for a solution for the POI problem. Reg. non-rectangular tiles: I fear we can't use any of the existing algos in mkgmap to implement this, I'll report details in a different post. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828952.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ 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/small-issue-with-Way-getCofG-tp5828821p5828986.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
I have a working solution for ensuring that the created point is placed
within the polygon when using --add-pois-to-areas, based on drawing the
polygon on to a small monochrome bitmap and then looking for the point that
is furthest from the surrounding area. I used a 9x9 bitmap for polygons
having a small number of points and 15x15 for longer polygons. There is
however a performance penalty. My standard map takes about 1 hour 20
minutes; using this algorithm the time increases by about 50% to about 2
hours. I am not currently able to commit changes to SVN (perhaps someone can
help out with that) but I have attached the code changes. I suggest that due
to the performance penalty, if we adopt this, then the --add-pois-to-areas
option be extended to be --add-pois-to-areas[=centre|optimised] or something
similar, with the default being centre and functioning as now and the
optimised option invoking the new code. Please try out the suggested change.
Note I don't expect this to work properly where a polygon is formed from a
multiploygon relation, but the code could quite easily be adapted for this
circumstance.
Regards,
Mike
Additions to Way.java:
import java.awt.image.BufferedImage;
/*
* Find a point that is farthest from the edge of the shape
* by drawing the shape onto a small monochrome bitmap and
* then finding the point that is farthest from a black pixel.
* The shape is scaled differently in X and Y to fit a square bitmap.
* The size of the bitmap depends on the number of points in the shape.
*/
public Coord getPointWithinArea() {
// if shape is not closed or must be convex, use getCofG
if ((points.size() 5) || !isClosed())
return getCofG();
// first get the coordinates of the rectangle containing the way
int minLat = Integer.MAX_VALUE;
int minLon = Integer.MAX_VALUE;
int maxLat = Integer.MIN_VALUE;
int maxLon = Integer.MIN_VALUE;
for(Coord p : points) {
int lat = p.getHighPrecLat();
int lon = p.getHighPrecLon();
minLat = Math.min(minLat, lat);
minLon = Math.min(minLon, lon);
maxLat = Math.max(maxLat, lat);
maxLon = Math.max(maxLon, lon);
}
if ((maxLon == minLon) || (maxLat == minLat))
return Coord.makeHighPrecCoord((maxLat + minLat) / 2,
(maxLon + minLon) / 2);
// choose a bitmap resolution based on the number of points
int bitmapSize = points.size() 10 ? 9 : 15;
int halfBitmapSize = bitmapSize / 2;
int halfBitmapSize2 = bitmapSize - halfBitmapSize;
// create a polygon scaled to fit the resolution
double xScale = (double)(bitmapSize - 1) / (double)(maxLon -
minLon);
double yScale = (double)(bitmapSize - 1) / (double)(maxLat -
minLat);
Polygon polygon = new Polygon();
for(Coord p : points)
polygon.addPoint((int)((p.getHighPrecLon() - minLon) *
xScale), (int)((p.getHighPrecLat() - minLat) * yScale));
// draw the polygon as a white shape on a black background
BufferedImage image = new BufferedImage (bitmapSize,
bitmapSize, BufferedImage.TYPE_BYTE_BINARY);
Graphics2D graphics = image.createGraphics();
graphics.setColor(Color.black);
graphics.fillRect(0, 0, bitmapSize, bitmapSize);
graphics.setColor(Color.white);
graphics.fillPolygon(polygon);
// set the default coordinate to the middle of the bitmap
int bestX = halfBitmapSize;
int bestY = halfBitmapSize;
// examine each point in the bitmap, to see whether it is
farthest from a black pixel
// start at the centre point and move outwards in concentric
squares
// we can stop looking when we are closer to the edge than the
biggest distance
int biggestSquaredDistanceToBlack =
getSquaredDistanceToBlack(image, bestX, bestY);
for (int start = 1; (start = halfBitmapSize)
(biggestSquaredDistanceToBlack (halfBitmapSize2 - start) * (halfBitmapSize2 -
start)); start++) {
for (int i = 0; i = start; i++) {
int x = halfBitmapSize + i;
int y = halfBitmapSize + start;
int squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Mike, 50% sounds better than my algo, but still quite a lot. I'll have a closer look at your algo later. Please note that your change has a side effect on the house number generator. Up to now this doesn't contain a filter for generated POI, so each polygon with a house number is processed twice, once because of the POI, once because the Generator uses Way.getCofG(). If both have different positions this might have a negative impact. Gerd From: m...@tvage.co.uk To: mkgmap-dev@lists.mkgmap.org.uk Date: Tue, 6 Jan 2015 14:56:30 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() I have a working solution for ensuring that the created point is placed within the polygon when using --add-pois-to-areas, based on drawing the polygon on to a small monochrome bitmap and then looking for the point that is furthest from the surrounding area. I used a 9x9 bitmap for polygons having a small number of points and 15x15 for longer polygons. There is however a performance penalty. My standard map takes about 1 hour 20 minutes; using this algorithm the time increases by about 50% to about 2 hours. I am not currently able to commit changes to SVN (perhaps someone can help out with that) but I have attached the code changes. I suggest that due to the performance penalty, if we adopt this, then the --add-pois-to-areas option be extended to be --add-pois-to-areas[=centre|optimised] or something similar, with the default being centre and functioning as now and the optimised option invoking the new code. Please try out the suggested change. Note I don't expect this to work properly where a polygon is formed from a multiploygon relation, but the code could quite easily be adapted for this circumstance. Regards, Mike ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Mike, I like the idea, but it seems to be slow. Is it possible that your algo suffers when no fast graphics card is available? On my netbook the performance is very poor, did not yet try on the PC, but that also has no high speed graphics. Gerd GerdP wrote Hi Mike, 50% sounds better than my algo, but still quite a lot. I'll have a closer look at your algo later. Please note that your change has a side effect on the house number generator. Up to now this doesn't contain a filter for generated POI, so each polygon with a house number is processed twice, once because of the POI, once because the Generator uses Way.getCofG(). If both have different positions this might have a negative impact. Gerd From: mike@.co To: mkgmap-dev@.org Date: Tue, 6 Jan 2015 14:56:30 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() I have a working solution for ensuring that the created point is placed within the polygon when using --add-pois-to-areas, based on drawing the polygon on to a small monochrome bitmap and then looking for the point that is furthest from the surrounding area. I used a 9x9 bitmap for polygons having a small number of points and 15x15 for longer polygons. There is however a performance penalty. My standard map takes about 1 hour 20 minutes; using this algorithm the time increases by about 50% to about 2 hours. I am not currently able to commit changes to SVN (perhaps someone can help out with that) but I have attached the code changes. I suggest that due to the performance penalty, if we adopt this, then the --add-pois-to-areas option be extended to be --add-pois-to-areas[=centre|optimised] or something similar, with the default being centre and functioning as now and the optimised option invoking the new code. Please try out the suggested change. Note I don't expect this to work properly where a polygon is formed from a multiploygon relation, but the code could quite easily be adapted for this circumstance. Regards, Mike ___ 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/small-issue-with-Way-getCofG-tp5828821p5829247.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Mike, on my PC the performance of your algo is quite good. Attached is a patch that contains your patch as well as my quick implementation of the algo described here: http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf The patch tests only performance, it computes the center with the 3 different algos, I've commented the part that prints times and GPX data for debug purposes. I noticed that the results between both algos are very different, I did not yet try to find out which one is better, but mine is much slower on my PC. I also noticed that your algo doesn't always calculate a point in the polygon, see e.g. way 178708143. If you like, please try to find a better compromise, I like to fix a problem in splitter first. I also did not yet look at the effect on the house number code, as there are many more small open problems, but I think it should be easy to sort that out. Gerd Date: Tue, 6 Jan 2015 13:23:57 -0700 From: gpetermann_muenc...@hotmail.com To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] small issue with Way.getCofG() Hi Mike, I like the idea, but it seems to be slow. Is it possible that your algo suffers when no fast graphics card is available? On my netbook the performance is very poor, did not yet try on the PC, but that also has no high speed graphics. Gerd GerdP wrote Hi Mike, 50% sounds better than my algo, but still quite a lot. I'll have a closer look at your algo later. Please note that your change has a side effect on the house number generator. Up to now this doesn't contain a filter for generated POI, so each polygon with a house number is processed twice, once because of the POI, once because the Generator uses Way.getCofG(). If both have different positions this might have a negative impact. Gerd From: mike@.co To: mkgmap-dev@.org Date: Tue, 6 Jan 2015 14:56:30 + Subject: Re: [mkgmap-dev] small issue with Way.getCofG() I have a working solution for ensuring that the created point is placed within the polygon when using --add-pois-to-areas, based on drawing the polygon on to a small monochrome bitmap and then looking for the point that is furthest from the surrounding area. I used a 9x9 bitmap for polygons having a small number of points and 15x15 for longer polygons. There is however a performance penalty. My standard map takes about 1 hour 20 minutes; using this algorithm the time increases by about 50% to about 2 hours. I am not currently able to commit changes to SVN (perhaps someone can help out with that) but I have attached the code changes. I suggest that due to the performance penalty, if we adopt this, then the --add-pois-to-areas option be extended to be --add-pois-to-areas[=centre|optimised] or something similar, with the default being centre and functioning as now and the optimised option invoking the new code. Please try out the suggested change. Note I don't expect this to work properly where a polygon is formed from a multiploygon relation, but the code could quite easily be adapted for this circumstance. Regards, Mike ___ 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/small-issue-with-Way-getCofG-tp5828821p5829247.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev pointInPolygon-v0.patch Description: Binary data ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Gerd, a good algorithm to find a point for the --add-pois-to-areas option would be to use the straight skeleton algorithm (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012394.html). This might be used to find a point with maximum distance to the border of a polygon. Anyhow it seems to be a complex algorithm so maybe not the ideal solution for mkgmap. WanMil Hi Steve, Steve Ratcliffe wrote On 03/01/15 08:15, Gerd Petermann wrote: @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Seems like the current method would tend to place the point near the most complex part of the boundary. This may not be bad, I would have to see lots of real examples to be sure. Yes, correct. I compared these three algos: 1) the existing 2) my patched one 3) center of bbox For complex shapes (many points), 1) and 2) produce almost equal results, and in fact the point was more often within the shape. For simple polygons like small parks, buildings, etc. 1) is worst, 2) is better and 3) is best. My conclusion: the patch is a simple and good improvement, for housenumber location calculation maybe it would be better to use algo 3). Steve Ratcliffe wrote Anyway there are no easy (or even any difficult!) methods that work in all cases, so I would just keep it as it is and perhaps should the calculated point be outside the box, move it to the closest point inside. I already looked at the link provided by Andrzej. If I got that right, we have two different problems regarding the generated POI: We calculate it once for the whole polygon, before clipping it to the bbox of the tile, and it might be outside of the polygon as well as outside of the bbox. This brought me back to the non-rectangular tile problem and I stop searching for a solution for the POI problem. Reg. non-rectangular tiles: I fear we can't use any of the existing algos in mkgmap to implement this, I'll report details in a different post. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828952.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi WanMil, I think the problem is similar to finding the largest circle in a concave polygon, and we are not interested in the exact solution, any point close enough to the center is good. See e.g. http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf which contains an iterative algo. Gerd WanMil wrote Hi Gerd, a good algorithm to find a point for the --add-pois-to-areas option would be to use the straight skeleton algorithm (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012394.html). This might be used to find a point with maximum distance to the border of a polygon. Anyhow it seems to be a complex algorithm so maybe not the ideal solution for mkgmap. WanMil Hi Steve, Steve Ratcliffe wrote On 03/01/15 08:15, Gerd Petermann wrote: @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Seems like the current method would tend to place the point near the most complex part of the boundary. This may not be bad, I would have to see lots of real examples to be sure. Yes, correct. I compared these three algos: 1) the existing 2) my patched one 3) center of bbox For complex shapes (many points), 1) and 2) produce almost equal results, and in fact the point was more often within the shape. For simple polygons like small parks, buildings, etc. 1) is worst, 2) is better and 3) is best. My conclusion: the patch is a simple and good improvement, for housenumber location calculation maybe it would be better to use algo 3). Steve Ratcliffe wrote Anyway there are no easy (or even any difficult!) methods that work in all cases, so I would just keep it as it is and perhaps should the calculated point be outside the box, move it to the closest point inside. I already looked at the link provided by Andrzej. If I got that right, we have two different problems regarding the generated POI: We calculate it once for the whole polygon, before clipping it to the bbox of the tile, and it might be outside of the polygon as well as outside of the bbox. This brought me back to the non-rectangular tile problem and I stop searching for a solution for the POI problem. Reg. non-rectangular tiles: I fear we can't use any of the existing algos in mkgmap to implement this, I'll report details in a different post. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828952.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ 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/small-issue-with-Way-getCofG-tp5828821p5828986.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Gerd, we are not interested in the exact solution See example from QGIS plugin, function centroids(self): https://github.com/zsiki/realcentroid/blob/master/realcentroid.py -- Best regards, Andrzej ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
On 03/01/15 08:15, Gerd Petermann wrote: @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Seems like the current method would tend to place the point near the most complex part of the boundary. This may not be bad, I would have to see lots of real examples to be sure. Anyway there are no easy (or even any difficult!) methods that work in all cases, so I would just keep it as it is and perhaps should the calculated point be outside the box, move it to the closest point inside. ..Steve ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Steve, Steve Ratcliffe wrote On 03/01/15 08:15, Gerd Petermann wrote: @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Seems like the current method would tend to place the point near the most complex part of the boundary. This may not be bad, I would have to see lots of real examples to be sure. Yes, correct. I compared these three algos: 1) the existing 2) my patched one 3) center of bbox For complex shapes (many points), 1) and 2) produce almost equal results, and in fact the point was more often within the shape. For simple polygons like small parks, buildings, etc. 1) is worst, 2) is better and 3) is best. My conclusion: the patch is a simple and good improvement, for housenumber location calculation maybe it would be better to use algo 3). Steve Ratcliffe wrote Anyway there are no easy (or even any difficult!) methods that work in all cases, so I would just keep it as it is and perhaps should the calculated point be outside the box, move it to the closest point inside. I already looked at the link provided by Andrzej. If I got that right, we have two different problems regarding the generated POI: We calculate it once for the whole polygon, before clipping it to the bbox of the tile, and it might be outside of the polygon as well as outside of the bbox. This brought me back to the non-rectangular tile problem and I stop searching for a solution for the POI problem. Reg. non-rectangular tiles: I fear we can't use any of the existing algos in mkgmap to implement this, I'll report details in a different post. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828952.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Gerd, yep, good catch. Seems to be a good solution for mkgmap! WanMil Hi WanMil, I think the problem is similar to finding the largest circle in a concave polygon, and we are not interested in the exact solution, any point close enough to the center is good. See e.g. http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf which contains an iterative algo. Gerd WanMil wrote Hi Gerd, a good algorithm to find a point for the --add-pois-to-areas option would be to use the straight skeleton algorithm (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012394.html). This might be used to find a point with maximum distance to the border of a polygon. Anyhow it seems to be a complex algorithm so maybe not the ideal solution for mkgmap. WanMil Hi Steve, Steve Ratcliffe wrote On 03/01/15 08:15, Gerd Petermann wrote: @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Seems like the current method would tend to place the point near the most complex part of the boundary. This may not be bad, I would have to see lots of real examples to be sure. Yes, correct. I compared these three algos: 1) the existing 2) my patched one 3) center of bbox For complex shapes (many points), 1) and 2) produce almost equal results, and in fact the point was more often within the shape. For simple polygons like small parks, buildings, etc. 1) is worst, 2) is better and 3) is best. My conclusion: the patch is a simple and good improvement, for housenumber location calculation maybe it would be better to use algo 3). Steve Ratcliffe wrote Anyway there are no easy (or even any difficult!) methods that work in all cases, so I would just keep it as it is and perhaps should the calculated point be outside the box, move it to the closest point inside. I already looked at the link provided by Andrzej. If I got that right, we have two different problems regarding the generated POI: We calculate it once for the whole polygon, before clipping it to the bbox of the tile, and it might be outside of the polygon as well as outside of the bbox. This brought me back to the non-rectangular tile problem and I stop searching for a solution for the POI problem. Reg. non-rectangular tiles: I fear we can't use any of the existing algos in mkgmap to implement this, I'll report details in a different post. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828952.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ 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/small-issue-with-Way-getCofG-tp5828821p5828986.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi, forgot to attach the patch. Note that points added by --add-pois-to-areas are more likely in the middle of a shape. @Steve: The routine was initially created for the --check-roundabouts option. Later it was also used for --add-pois-to-areas and the --housenumbers option. I got the impression that it might be better to calculate the center of the way bbox for those two, I am not so sure about the roundabout code. What do you think? Gerd Date: Fri, 2 Jan 2015 21:34:14 -0700 From: gpetermann_muenc...@hotmail.com To: mkgmap-dev@lists.mkgmap.org.uk Subject: [mkgmap-dev] small issue with Way.getCofG() Hi all, We use the method Way.getCofG() to calculate a single coordinate for shapes, e.g. for buildings with house numbers. The routine calculates the avg. latitude and longitude of all points, which typically gives a point somewhere close to the middle of the shape, but it seems to ignore the fact that the first and last point in a shape are equal to close it, means, the result will be a bit too close to that closing point. Is there a good reason for this? We use it also to calculate the POI in --add-pois-to-areas. Gerd P.S. I guess a better formular could calculate the convex hull first, but I doubt that the additional CPU time would really improve the result that much. -- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821.html Sent from the Mkgmap Development mailing list archive at Nabble.com. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev getCofG.patch Description: Binary data ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] small issue with Way.getCofG()
Hi Gerd, when using --add-pois-to-areas I would prefer to get a point inside a polygon. See some ideas here: http://mathoverflow.net/questions/56655/get-a-point-inside-a-polygon But I accept average as a simple practical solution, in most cases point will be inside. -- Best regards, Andrzej ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
