Jump to content
  • Sky
  • Blueberry
  • Slate
  • Blackcurrant
  • Watermelon
  • Strawberry
  • Orange
  • Banana
  • Apple
  • Emerald
  • Chocolate
  • Charcoal

Leaderboard


Popular Content

Showing content with the highest reputation on 05/31/13 in all areas

  1. 1 point
    Well, as I had nothing else to do I figured I could give a short "tutor" about measuring the distance between points, and how different implementations works. It's not a lot of reading and shit, mostly just straight forward. I'm going to walk trough the few methods that are normal to use in different context's. ================================================= Euclidean distance: This is the `line of sight` version of distance, which uses Pythagorean theorem. Stretch out your arm, and turn 360 degrees, no matter direction, you always reach `so far`. Euclidean distance will always return a floating-point value due to a call to square-root. Math formula: dist(q,p) = sqrt((px-qx)^2 + (py-qy)^2) Pascal implementation: function Euclidean(pt1,pt2:TPoint): Double; begin Result := Sqrt(Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y)); end; Thoughts: It's a bit slow for performance applications, mostly due to complecities of computing square root. This can be be avoided to a degree with Squared Euclidean distance. Take for example if your just computing difference between two Euclidean distances, and it's just too slow with Sqrt, then you can do this without any losses: function SqEuclidean(pt1,pt2:TPoint): Double; begin Result := Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y); end; Now the resulting number will differ as we are not calculating the square root, but it's a faster algorithm for comparing, which is almost always the case. Edit: Replaced Power(.., 2) with Sqr(): Sqr(pt1.x - pt2.x) is the same as Power((pt1.x - pt2.x), 2), but in compiled code Sqr(x) translates to the same as x*x, a IMUL or FMUL instruction, which is faster then whatever long asm code Power translates to. To use Squared Euclidean as a distance test, it's needed to square the radius on the other side of the comparison-operator (<,=,>), example: function InRadius(pt1,pt2:TPoint; Distance:Extended): Double; begin Result := Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y) <= Sqr(Distance) end; ================================================= City Block .. or as some might know it as: Manhattan distance. This is much more friendly to performance. Now think about the pixels on the screen, you can see that it's IMPOSSIBLE to draw a straight 45 degree line, there will be a gap between each point/pixel, it's like walking in the City, you cant drive over the buildings, you need to drive around. This algorithm walks around each pixel/building (unlike Euclidean, which flies over am in a straight line). Math formula: dist(q,p) = |px - qx| + |py - qy| Pascal implementation: function Manhattan(pt1,pt2:TPoint): Double; begin Result := abs(pt1.x - pt2.x) + abs(pt1.y - pt2.y); end; Thoughts: As it's a different algorithm, its uses are not always the same as Euclidean-distance. The result area of a distance of EG. `8` can be visualized as a tilted square at 45 degrees, with far fewer points (or pixels if you like) within the same distance compared to Euclidean, and Chebyshev (see next). ================================================= Chebyshev distance This is one I find my self using very often. It's a quick way to measure distance, it's also the simplest to understand by just looking at it. This time you can imagine a chessboard (assuming you know the game), the King can walk one step in any direction, including one step at 45 degrees: That is Chebyshev distance = 1. Math formula: dist(q,p) = max(|px - qx|, |py - qy|) Pascal implementation: function Chebyshev(pt1,pt2:TPoint): Double; begin Result := max(abs(pt1.x - pt2.x), abs(pt1.y - pt2.y)); end; Thoughts: It's similar to Manhattan distance. It also results in a square, but you can think of it as aligned with the horiz. and vertical axes. The amount of points within an area of the distance `8` contains many more points than ether of the other methods. ================================================= Now that's those... But I bet you can't yet visualize the result, so I will give you this image just to demonstrate the result after using each algorithm to draw each there area/block given a distance of 5: This picture also shows you that the distance in vertical and horizontal directions are the same no matter algorithm. PS: I can only hope that the pascal examples work, haven't touched pascal in quite some time, and I'm not able to test it now... This is also the result of me not having anything better to do.
×
×
  • Create New...