Hi all, for improvements in the housenumber2 branch I have to split a road segment into two parts. Given: the two (Garmin) points p1 and p2 that build the road segment and a distance d with d < p1.distance(p2). The normal way to calculate the wanted point is to use the Coord.makeBetweenPoint() method. The problem: the simple algo in makeBetweenPoint() calculates the point without looking at the rounding for the Garmin raster, so for line segments with a small slope the calculated point might be too far away from the displayed line. The effect is that the splitted line has a rather large angle while the originial line looks - of course - perfectly straight. I am sure this problem was already solved, but up to now I did not find an algo that works without a loop to calculate a set of points and chose the best one, e.g. using the Bresenham algo. Any hints? Gerd
Hi Gerd, I guess it is about small distances, this part of makeBetweenPoint(): // distances are rather small, we can use flat earth approximation int lat30 = (int) (getHighPrecLat() + dLat30 * fraction); int lon30 = (int) (getHighPrecLon() + dLon30 * fraction); return makeHighPrecCoord(lat30, lon30); I think lat30 and lon30 can be rounded up and down to grid value, which would give 4 points nearest to required coordinate. Then we could select the most suitable, for example comparing angle of segments. But does it actually matter? Maybe only for very sort line? -- Best regards, Andrzej
Hi Gerd, one more notice - for splitting very short lines could be better to calculate intermediate point using grid coordinates of line instead of high precision like in makeBetweenPoint(). -- Best regards, Andrzej
Hi Andrzej, Mike, I am not splitting short lines here, I talk about lines of > 50 m. If you have such a rather long line with delta_lat = 1 and delta_lon > 50 there is no point where I can split the line without creating one horizontal part and another that still has delta_lat = 1, both parts building a visible angle, so in that case I would not split. With delta_lat > 10 it is likely to find a point that is close to the straight line and not too far away from the calculated cut point. If you take my "bed of nails" example, I am searching for a nail that is close enough (~10m) to a given point on the rubber band and very close to the rubber band itself (< 0.5m). My current solution is to raster the line with the Bresenham algo and check the points which are close to the wanted one. I think it is no problem regarding performance, but it seems not very elegent. Gerd popej wrote
Hi Gerd,
one more notice - for splitting very short lines could be better to calculate intermediate point using grid coordinates of line instead of high precision like in makeBetweenPoint().
-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-for-graphical-problem-tp5833271p5... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd, I have attached picture with 2 lines split around middle point. Upper line is about 50m, lower 500m. Both have delta_lat equal to 1 grid step. I don't think that splitting make big problem here. If you allow for 10m of offset for splitting point, then Bresenham's algorithm has to calculate only 8 points. For me it looks like a good solution. Are you going to insert multiple points into a line? -- Best regards, Andrzej
Hi Andrzej, Yes, very long lines are no problem regarding optics, but may cause trouble when the bresenham algo iterates very often. Or do you see a simple way to limit the iteration to a part of the way near the wanted point? My current algo tries to split the line when the address search for a house returns a point that is more than 40 m away from the closest possible point. If that is not possible without visible distortion, it may also add an empty segment. Maybe 20m are also reasonable, but a much smaller value doesn't improve much while it will incease img size a lot. Maybe I add an option to configure the threshold values. Anyway, it seems that there is no simple solution so I'll continue with what I have. A first usable version should be ready within the next days. It will also support the typically random numbers from addr:place=* tags. Gerd popej wrote
Hi Gerd,
I have attached picture with 2 lines split around middle point. Upper line is about 50m, lower 500m. Both have delta_lat equal to 1 grid step. I don't think that splitting make big problem here.
If you allow for 10m of offset for splitting point, then Bresenham's algorithm has to calculate only 8 points. For me it looks like a good solution.
Are you going to insert multiple points into a line?
-- Best regards, Andrzej
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
split.png (16K) <http://gis.19327.n5.nabble.com/attachment/5833378/0/split.png>;
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-for-graphical-problem-tp5833271p5... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd,
Or do you see a simple way to limit the iteration to a part of the way near the wanted point?
I have looked at algorithm here: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm It looks simple, it calculates error to grid at each step by adding a value representing ascent (or descent) of a line. If error is bigger than 0.5 grid, then coordinate is increased and error recalculated against new coordinate. State of algorithm is defined by 3 values: grid coordinates and error. I think there shouldn't be a problem, to restore these 3 variables for any point (grid point) of a line and then make next 10 iterations. -- Best regards, Andrzej
Hi Andrzej, I took the one below "Kompakte Variante" from the german wiki http://de.wikipedia.org/wiki/Bresenham-Algorithmus Maybe I miss something, but I don't see how I could calculate a grid point on the line as I think that's the initial problem that I try to solve with the loop. I guess I should get my result by calculating the intersections of the given line with a few horizontal and vertical lines going through the grid points next to the calculated point on the line (using float arithmetic) Not sure if the code for that is simpler... Gerd popej wrote
Hi Gerd,
Or do you see a simple way to limit the iteration to a part of the way near the wanted point?
I have looked at algorithm here: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
It looks simple, it calculates error to grid at each step by adding a value representing ascent (or descent) of a line. If error is bigger than 0.5 grid, then coordinate is increased and error recalculated against new coordinate. State of algorithm is defined by 3 values: grid coordinates and error. I think there shouldn't be a problem, to restore these 3 variables for any point (grid point) of a line and then make next 10 iterations.
-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-for-graphical-problem-tp5833271p5... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd, looking at "Kompakte Variante" i think that for each calculated point (x,y) this is true: err = (x - xS +1)*dy + (y - yS +1)*dx where xS and yS are start coordinates - initial value for x0, y0. If you find arbitrary intermediate point on the line and round its position to nearest Garmin grid point, then you get values for x, y and you can calculate err. And simply make some more iteration, finding a point, where err is the lowest. Ok, I can make a mistake somewhere, I haven't tested it, but it looks for me as a valid solution. -- Best regards, Andrzej
participants (3)
-
Andrzej Popowski -
Gerd Petermann -
GerdP