Interesting Problem - Finding the closest coordinate.... 2

[golcarlad]

This is a problem I have been trying to figure out - but I guess because I'm not so good with maths - Im always on the back foot - so maybe (hopefully) there is someone out there who could come up with a snazzy algorithm to do the following - as fast as possible really - as speed is the issue here.


I have a coordinate pair (lets call these Base Coordinates") in space, and they look something like the following:

X Y
234, 456


And I have a whole list (array) of other coordinates I want to test against (lets call them Target Coordinates) e.g.

X Y
534, 345
768, 457
32, 256
744, 435
211, 565.......

there may be 2 - 10 or 10,000 coordinate pairs to test against.



GOAL TO ACHIEVE

I want to try and find the CLOSEST pair out of the Target Coordinate list in relation to the Base Coorinate pair - so the code should just return the index of the closest pair at the end of the day - simple eh? Well, I would be interested in testing different algorithms against my own (mine just relied on Pythagoras - finding distance between two pairs, store the distance, then sort to find the shortest distance).

Look forward to seeing any responses.

 

[monkhandle]

Why sort ? Sorting is slow and unneeded here. Just remember calculated distance, and when you calculate next one, compare it with this one. Keep the smaller one.

 

[AlexCuse]

Do you have any idea what the maximum distance your closest coordinate pair will be is?

If so you might be able to use a "bounding box" (not sure if this is the right term) to exclude the coordinate pairs that you "know" will not be the closest?

The pythagorean theorem ought to be plenty fast, but you might consider creating a class called CoordinatePair (or something) and using a list of these. You could give CoordinatePair class a method to calculate the distance to another CoordinatePair. This might not make it faster (I don't know how lists compare to arrays in terms of performance) but it would make your code much cleaner.

Using this approach you ought to be able to use Linq (depending on framework version) or other methods to get the minimum distance without storing it, which could improve performance. I'll see if I can throw together an example.

Hope this helps,

Alex

[small]----signature below----[/small]
Majority rule don't work in mental institutions

My Crummy Web Page

 

[jmeckley]

public class Point
{
   double x, y;
   public Point(double x, double y)
   {
      this.x = x;
      this.y = y;
   }

   public double X { get { return x; } }
   public double y { get { return y; } }

   public Double CalculateDistanceFrom(Point point)
   {
      //a^2 + b^2 = c^2
      //or c = sqaure root of a^2 + b^2
      double a = x - point.x;
      double b = y - point.y;
      return  Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2));
   }
}

public class NullPoint : Point
{
   public NullPoint()
      : base (0, 0)
   {
   }
}

public interface IRichList<T> : IList<T>
{
   void VisitItemUsingA(IVisitor<T> visitor);
   Result GetResultOFVisitingItemUsingA<Result>(IValueReturingVisitor<Result, T> visitor);
}

public class RichList<T> : List<T>
{
   public void VisitItemUsingA(IVisitor<T> visitor)
   {
      ForEach(visitor.Visit);
   }

   public Result GetResultOFVisitingItemUsingA<Result>(IValueReturingVisitor<Result, T> visitor)
   {
      VisitItemUsingA(visitor);
      return visitor.GetResult();
   }
}

public interface IVisitor<T>
{
   void Visit(T item);
}

public interface IValueReturningVisitor<Result, T> : IVisitor<T>
{
   Result GetResult();
}

public class DermineCloestsPoint ToIValueReturningVisitor<Point, Point>
{
  private Point origin;
  private Point closestPoint = new NullPoint;
  double shortestDistance = double.MaxValue;

  public DermineCloestsPointTo(Point origin)
  {
     this.origin = origin;
  }

  void Visit(Point item)
  {
      if(origin.CalculateDistanceFrom(item) < shortestDistance) closestPoint = item;
  }

  Point GetResult()
  {
     return closestPoint;
  }
}

IRichList<Point> listOfPoints = new RichList<Point>();
//load points

Point source = new Point(123, 456);
Point closest = listOfPoints.GetResultOFVisitingItemUsingA(DermineCloestsPointTo(source));

I haven't tested this, but it should be close. the real magick happens here Point.CalculateDistanceFrom(Point point)

Jason Meckley
Programmer
Specialty Bakers, Inc.

 

[AlexCuse]

This is kinda half-baked, but it should give you an idea what I mean (just paste it into a new console app)

using System;
using System.Collections.Generic;
using System.Text;

namespace CoordinatePairs
{
    class Program
    {
        static void Main(string[] args)
        {
            CoordinatePair baseCoordinates = new CoordinatePair(153, 135);

            List<CoordinatePair> coordinates = new List<CoordinatePair>();

            Random r = new Random();

            for (int i = 0; i <= 100; i++)
            {
                coordinates.Add(new CoordinatePair(Convert.ToInt16(r.NextDouble() * 300), Convert.ToInt16(r.NextDouble() * 300)));
            }

            //look at all your points, with distances
            foreach (CoordinatePair cp in coordinates)
            {
                Console.WriteLine("Point at " + cp.X + ", " + cp.Y + " is " + baseCoordinates.Distance(cp) + " away from baseCoordinates");
            }

            Console.WriteLine();

            int idx = SearchCoordinates(coordinates, baseCoordinates);
            

            Console.WriteLine("Point at " + coordinates[idx].X + ", " + coordinates[idx].Y + " is the closest, with a distance of " + coordinates[idx].Distance(baseCoordinates));


            Console.ReadLine();
        }

        private static int SearchCoordinates(List<CoordinatePair> coordinates, CoordinatePair baseCoordinates)
        {
            int idx = 0;
            double minDist = double.MaxValue;
            double testDist;

            for (int i = 0; i <= 100; i++)
            {
                testDist = baseCoordinates.Distance(coordinates[i]);

                if (testDist < minDist)
                {
                    idx = i;
                    minDist = testDist;
                }
            }
            return idx;
        }

        class CoordinatePair
        {
            public CoordinatePair(int x, int y)
            {
                _x = x;
                _y = y;
            }

            private Int32 _x;
            private Int32 _y;

            public Int32 X
            {
                get { return _x; }
                set { _x = value; }
            }

            public Int32 Y
            {
                get { return _y; }
                set { _y = value; }
            }

            public Double Distance(CoordinatePair comp)
            {
                int a = Math.Abs(this.X - comp.X);
                int b = Math.Abs(this.Y - comp.Y);

                return Math.Sqrt((a * a) + (b * b));
            }

        }
    }
}

Hope it helps,

Alex

[small]----signature below----[/small]
Majority rule don't work in mental institutions

My Crummy Web Page

 

[AlexCuse]

Derr, I'm sure Jason's example is more fully-baked than mine ;-)

I didn't read it all, but looking over it I realized you could do without the Math.Abs in the assignment (in my example) of a and b (because you are going to square them anyways).

[small]----signature below----[/small]
Majority rule don't work in mental institutions

My Crummy Web Page

 

[jmeckley]

i found some syntax errors in my code. here's the updated objects

public interface IVisitor<T>
{
   void Visit(T item);
}

public interface IValueReturningVisitor<Result, T> : IVisitor<T>
{
   Result GetResult();
}

public class DermineCloestsPointTo : IValueReturningVisitor<Point, Point>
{
        private Point origin;
        private Point closestPoint = new NullPoint();
        private double shortestDistance = double.MaxValue;

        public DermineCloestsPointTo(Point origin)
        {
            this.origin = origin;
        }

        public void Visit(Point item)
        {
            double distance = origin.CalculateDistanceFrom(item);
            if (distance < shortestDistance)
            {
                shortestDistance = distance;
                closestPoint = item;
            }
        }

        public Point GetResult()
        {
            return closestPoint;
        }
}

    public class RichList<T> : List<T>, IRichList<T>
    {
        public void VisitItemUsingA(IVisitor<T> visitor)
        {
            ForEach(visitor.Visit);
        }

        public Result GetResultOFVisitingItemUsingA<Result>(IValueReturningVisitor<Result, T> visitor)
        {
            VisitItemUsingA(visitor);
            return visitor.GetResult();
        }
    }

here's a simple example

using System;

namespace ClosestPoint
{
    internal class Program
    {
        private static readonly Random random = new Random((int) DateTime.Now.Ticks);

        private static void Main()
        {
            IRichList<Point> points = new RichList<Point>();
            for (int i = 0; i < 10; i++)
            {
                Point point = GeneratePoint();
                points.Add(point);
                Console.WriteLine("Adding {0}", point);
            }
            Point origin = GeneratePoint();
            Console.WriteLine("Origin is {0}", origin);

            Point closest = points.GetResultOFVisitingItemUsingA(new DermineCloestsPointTo(origin));
            Console.WriteLine("{0} is the closest point to {1}.", closest, origin);
            Console.ReadKey();
        }

        private static Point GeneratePoint()
        {
            return new Point(GetCoordinate(), GetCoordinate());
        }

        private static double GetCoordinate()
        {
            int integerValue = (int)(random.NextDouble() * 10000D);
            return integerValue / 100D;
        }
    }
}

Adding 41.83,80.2
Adding 73.83,30.37
Adding 72.55,27.89
Adding 71.88,71
Adding 67.84,18.22
Adding 47.38,55.89
Adding 6.29,43.31
Adding 95.76,11.61
Adding 53.91,59.67
Adding 62.07,49.94

Origin is 73.81,40.37

The distance from 73.81,40.37 to 41.83,80.2 is 51.0798326152308
The distance from 73.81,40.37 to 73.83,30.37 is 10.00001999998
The distance from 73.81,40.37 to 72.55,27.89 is 12.5434445030063
The distance from 73.81,40.37 to 71.88,71 is 30.690744533165
The distance from 73.81,40.37 to 67.84,18.22 is 22.9404315565335
The distance from 73.81,40.37 to 47.38,55.89 is 30.6498825446363
The distance from 73.81,40.37 to 6.29,43.31 is 67.5839773910947
The distance from 73.81,40.37 to 95.76,11.61 is 36.1792772177665
The distance from 73.81,40.37 to 53.91,59.67 is 27.7218325512582
The distance from 73.81,40.37 to 62.07,49.94 is 15.1463692018913

73.83,30.37 is the closest point to 73.81,40.37.

i added a Console.WriteLine to the CalculateCosestDistanceTo and override Point.ToString

Jason Meckley
Programmer
Specialty Bakers, Inc.

 

[golcarlad]

Hey guys - This is so much more than I expected!! thanks for your contributions - I am going to put them to the test and take it from there, but it has put me on the right track anyway

- so thanks to

Jason Meckley and AlexCuse who took the time to come up with some very worthy solutions.

Cheers
Simon

 

[jmeckley]

didn't take that long. I use most of the interfaces above in my projects. the "hardest" part was the math

once you break the objects out into single responsiblity it simply becomes a matter of putting the pieces together.

Jason Meckley
Programmer
Specialty Bakers, Inc.