距離最近的點(diǎn)對(duì)問題算法

plscareme

最近在看Sedgewick的那本Algorithms in C++，里面在28章有一個(gè)關(guān)于最近距離的點(diǎn)隊(duì)的問題求解的算法，分析研究了2天還是有所疑惑，有幾個(gè)點(diǎn)比較以后，拿出來請(qǐng)教大家，希望能給以一些分析。
主要算法：
算法的主要思想是先比較x坐標(biāo)，然后比較y坐標(biāo)，然后用合并排序來選擇距離最小的點(diǎn)對(duì)：
主要的數(shù)據(jù)結(jié)構(gòu)，點(diǎn)和鏈表節(jié)點(diǎn)：
struct point
{
    int x;
    int y;
};

struct node
{
    struct point p;
    struct node *next;
};
//全局變量
/* global */
int pass; // 表明比較x還是y坐標(biāo)
struct node *z; // 尾節(jié)電，無限大
float min; // 最短距離
struct point cp1, cp2; // 最短距離點(diǎn)對(duì)

//坐標(biāo)比較函數(shù)，pass為一比較x坐標(biāo)，否則（2）比較y坐標(biāo)：

int comp(struct node *t)
  { return (pass == 1) ? t->p.x : t->p.y; }
//合并排序函數(shù)
struct node *merge(struct node *a, struct node *b)
  {
    struct node *c;
    c = z;
    do
      if (comp(a) < comp(b))
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    while (c != z);
    c = z->next; z->next = z;
    return c;
  }
//距離比較函數(shù)

void check(struct point p1, struct point p2)
{
    float dist;
    if ((p1.y != z->p.y) && (p2.y != z->p.y))
    {
        dist = sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
        if (dist < min)
        {
            min = dist; cp1 = p1; cp2 = p2;
        }
    }
}


// 主要核心比較函數(shù)
struct node *sort(struct node *c, int number)
{
    static int sort_i = 0;
    int i;
    struct node *a, *b, *tt;
    float middle;
    struct point p1, p2, p3, p4;
    if (c->next == z)
        return c;
    a = c;
    for (i = 2; i <= number/2; i++)
        c = c->next;
    b = c->next;
    c->next = z;
    if (pass == 2)
    {
        middle = b->p.x;
    }
    //按照Sedgewick的說法,在調(diào)用這個(gè)merge之前,鏈表是以x坐標(biāo)排好序的.
    c = merge(sort(a, number/2), sort(b, number - (number/2)));
    //按照Sedgewick的說法,在這個(gè)merge之后, midlle的左右兩半的內(nèi)部點(diǎn)之間的距離,都大于min
    // 這是為什么?
    //為什么這里要比較四個(gè)點(diǎn),為什么四個(gè)點(diǎn)足夠了,這又是為什么?
    if (pass == 2)
    {
        p1 = z->p; p2 = z->p; p3 = z->p; p4 = z->p;
        for (a = c; a != z; a = a->next)
            if (fabs(a->p.x - middle) < min)
            {
                check(a->p, p1);
                check(a->p, p2);
                check(a->p, p3);
                check(a->p, p4);
                p1 = p2; p2 = p3; p3 = p4; p4 = a->p;
            }
    }
    return c;
}


//主函數(shù)

int main()
{
z = new node; z->p.x = max;
              z->p.y = max; z->next = z;
h = new node; h->next = readlist();
min = max;
//第一次pass為1，對(duì)x坐標(biāo)排序
pass = 1; h->next = sort(h->next, N);
//第二次pass為2，對(duì)y坐標(biāo)排序
pass = 2; h->next = sort(h->next, N);
}

plscareme

以前看過一個(gè)實(shí)現(xiàn)這個(gè)問題的算法，也是用的分而治之的算法，但是很復(fù)雜，這個(gè)算法很簡單，可是里面sort函數(shù)的實(shí)現(xiàn)，確實(shí)有些疑惑，不知道怎么實(shí)現(xiàn)的左右兩個(gè)半?yún)^(qū)的點(diǎn)對(duì)的距離都比全局的min大，又怎么實(shí)現(xiàn)通過比較四個(gè)點(diǎn)就能確保一定找到最近點(diǎn)對(duì)的原因？

謝謝！

plscareme

自己頂一下 這個(gè)算法有什么問題么

plscareme

繼續(xù)關(guān)注

plscareme

readlist只是一個(gè)簡單的建立鏈表的偽函數(shù)，沒有什么特別的意義，這個(gè)算法的實(shí)現(xiàn)我是
第一次看到，我以前看到過一個(gè)實(shí)現(xiàn)，但是非常復(fù)雜。
這本書我看的是一本原版書，從別人手上借的，所以也沒有電子版。
我是有些迷迷糊糊，關(guān)于這個(gè)算法，尤其是比較四個(gè)點(diǎn)的那個(gè)地方，謝謝回復(fù)，我也在查找別的
資料，目前還沒有什么發(fā)現(xiàn)。