C++

Forum

 
 
Help with "Closest Pair Problem" using Divide and Conquer

SaeedOmnia (9)
Hi
First of all sorry for my bad english :-))

I am trying to write a program to solve the closest pairs problem using divide and conquer in C#.net. i get points x and y and save them in a array(555*555). i read a lot of articles (including CLRS) about solving this problem but i really don't know how to write the code. first i am supposed to divide the matrix but i don't know how much?
the other question is should i check only x or both x and y??


Thank You
Last edited on
webJose (2948)
This is not a C# forum. Ask your question @ the MSDN forums instead.
SaeedOmnia (9)
Thanks for your answer but i don't need the exact c# code. c or c++ or an algorithm would solve the problem that i'm having.
webJose (2948)
Learn to Google. If you Google "closest pair problem", the Wikipedia link, which is the first one, contains the algorithm explained.
SaeedOmnia (9)
i have googled it but i couldn't find the DIVIDE AND CONQUER algorithm.
can you send the wikipedia link plz.
thanks
webJose (2948)
If you Google "closest pair problem", the Wikipedia link, which is the first one, contains the algorithm explained.

Read the page. At least use Ctrl+F in your browser to find the words "divide and conquer".
SaeedOmnia (9)
ok thanks
SaeedOmnia (9)
Hi
I wrote this code but i does not work correctly (works but returns wrong points). can anyone tell me whats wrong with this??

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
        public Point[] findClosest(Point[] points)
        {
            Point[] result=new Point[2];
            
            if (points.Length <= 3)
            {
                double distant=Math.Sqrt(panelMaxSize);
                int i, j;
                for (i = 0; i < points.Length; i++)
                    for (j = i + 1; j < points.Length; j++)
                    {
                        double dst = Math.Sqrt(Math.Pow(array[i].X - array[j].X, 2) + Math.Pow(array[i].Y - array[j].Y, 2));
                        if (distant > dst)
                        {
                            distant = dst;
                            result[0] = array[i];
                            result[1] = array[j];
                        }
                    }
                return result;
            }
            Point[] pairLeft = new Point[2];
            Point[] pairRight = new Point[2];
            int len = (int)points.Length / 2;
            Point[] pointsLeft = new Point[len];
            Point[] pointsRight = new Point[points.Length - len];

            for (int i = 0; i < len; i++)
                pointsLeft[i] = array[i];
            for (int i = 0; i < points.Length - len; i++)
                pointsRight[i] = array[i + len];

            pairLeft = findClosest(pointsLeft);
            pairRight = findClosest(pointsRight);

            double distant1 = Math.Sqrt(Math.Pow(pairLeft[0].X - pairLeft[1].X, 2) + Math.Pow(pairLeft[0].Y - pairRight[1].Y, 2));
            double distant2 = Math.Sqrt(Math.Pow(pairRight[0].X - pairRight[1].X, 2) + Math.Pow(pairRight[0].Y - pairRight[1].Y, 2));

            if (distant1 > distant2)
            {
                result = pairRight;
                distant = distant2;
            }
            else
            {
                result = pairLeft;
                distant = distant1;
            }

            int midCoordiante = points[len].X;
            int xDown = (int)midCoordiante - (int)distant;
            int xUpper = (int)midCoordiante + (int)distant;

            int count = 0;
            for (int i = 0; i < points.Length; i++)
            {
                if (points[i].X > xDown && points[i].X < xUpper)
                    count++;
            }

            Point[] mipoints = new Point[count];

            int index = 0;
            for (int i = 0; i < points.Length; i++)
            {
                if (points[i].X > xDown && points[i].X < xUpper)
                    mipoints[index++] = points[i];
            }

            for(int i=0;i<mipoints.Length;i++)
                for (int j = i + 1; j < mipoints.Length; j++)
                {
                    double dst = Math.Sqrt(Math.Pow(mipoints[i].X - mipoints[j].X, 2) + Math.Pow(mipoints[i].Y - mipoints[j].Y, 2));
                    if (dst < distant)
                    {
                        distant = dst;
                        result[0] = mipoints[i];
                        result[1] = mipoints[j];
                    }
                }
            return result;



        }
Gaminic (1621)
Your compiler might.
SaeedOmnia (9)
Solved. Thanks Everyone :-)
Topic archived. No new replies allowed.