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.
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_muenchen@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
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
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
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-tp5828821p582895... Sent from the Mkgmap Development mailing list archive at Nabble.com.
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-tp5828821p582895... 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
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-tp5828821p582895... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p582898... Sent from the Mkgmap Development mailing list archive at Nabble.com.
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
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-tp5828821p582895... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p582898... 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
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: wmgcnfg@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-tp5828821p582895... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p582898... 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
participants (5)
-
Andrzej Popowski -
Gerd Petermann -
GerdP
-
Steve Ratcliffe -
WanMil