Новичок
Джуниор
Регистрация: 15.06.2009
Сообщений: 1
|
Точки и нахождение ближайшей пары точек
Здравствуйте!
Написал такую программку для нахождение ближайшей пары точек.
Писал по примеру из книги Ласла "Вычислительная геометрия".
Вот код программы
Код:
#include <math.h>
#include <iostream>
using namespace std;
class Point{
public:
Point(double _x=0.0, double _y=0.0);
double length(void);
double x;
double y;
int operator< (Point&);
/* возвращает координату х, если в качестве индекса координаты указано значение О, или координату у при индексе 1*/
double operator[] (int);
friend Point operator* (double, Point&);
};
class Edge{
public:
Point org;
Point dest;
Edge(Point &_org, Point &_dest);
Edge(void);
};
Код:
// 4сем.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include "unit1.h"
#include <iostream>
#define DBL_MAX 1;
using namespace std;
Point::Point (double _x, double _y):x (_x), y (_y)
{
}
Edge::Edge (Point &_org, Point &_dest) :
org (_org), dest (_dest)
{
}
Edge::Edge (void) :
org (Point (0,0)), dest (Point (1,0))
{
}
double Point::length (void)
{
return sqrt(x*x + y*y);
}
double Point::operator[](int i)
{
return (i==0)?x:y;
}
Point operator*(double s , Point &p)
{
return Point(s*p.x, s*p.y);
}
int Point::operator<(Point &p)
{
return ((x < p.x)||((x == p.x)&&(y < p.y)));
}
template <class T>
void mergeSort(T a[], int n, int (*cmp)(T,T))
{
mSort(a, 0, n-1, cmp);
}
template <class T>
void mSort(T a[], int l, int r, int (*cmp)(T,T))
{
if (l<r){
int m = (l+r)/2;
mSort(a, l, m, cmp);
mSort(a, m+1, r, cmp);
merge(a, l, m, r, cmp);
}
}
template <class T>
void merge(T x[], int l, int m, int r, int (*cmp)(T,T))
{
T *a = x+1;
T *b = x+m+1;
T *c= new T[r-l+1];
int ax = 0, bx = 0, cx = 0;
int alm = m-l+1, blm = r-m;
while ((ax < alm) && (bx < blm))
if ((*cmp)(a[ax], b[bx]) <0)
c[cx++] = a[ax++];
else
c[cx++] = b[bx++];
while (ax < alm)
c[cx++] = a[ax++];
while (bx < blm)
c[cx++] = b[bx++];
for (ax = cx = 0; ax <= r-1; a[ax++] = c[cx++]);
delete c;
}
int BottomToTopCmp(Point *a, Point *b)
{
if ((a->y < b->y)||((a->y == b->y)&&(a->x < b->x)))
return -1;
else if ((a->y > b->y)||((a->y == b->y)&&(a->x > b->x)))
return 1;
return 0;
}
int leftToRightCmp(Point *a, Point *b)
{
if (a->x < b->x) return -1;
if (a->x > b->x) return 1;
return 0;
}
void splitY(Point *y[], int n, Point *p, Point *yL[], Point *yR[])
{
int i, lindx, rindx;
i = lindx = rindx = 0;
while (i < n)
if (*y[i] < *p)
yL[lindx++] = y[i++];
else
yR[rindx++] = y[i++];
}
double checkStrip(Point *y[], int n, Point *p, double delta, Edge &c)
{
int i, striplen;
Point *s = new Point[n];
for (i = striplen = 0; i<n;i++)
if ((p->x - delta < y[i]->x) && (y[i]->x < p->x + delta))
s[striplen++] = *y[i];
for (i=0; i<striplen;i++)
for (int j = i+1; j< striplen; j++)
{
//if (s[j])
if ((s[i],s[j]).length()<delta)
{
delta = (s[i],s[j]).length();
c = Edge(s[i],s[j]);
}
}
delete s;
return delta;
}
double cPoints(Point *x[], Point *y[], int n, Edge &c)
{
if (n == 1)
{
return DBL_MAX;
}
else {
int m; m = n/2;
int ttt=n-m;
Point **yL = new (Point*);
Point **yR = new (Point*);
splitY (y, n, x[m], yL, yR);
Edge a, b;
double deltaL = cPoints(x, yL, m, a);
double deltaR = cPoints(x+m, yR, n-m, b);
delete yL;
delete yR;
double delta;
if (deltaL<deltaR)
{
delta = deltaL;
c = a;
}
else {
delta = deltaR;
c = b;
}
return checkStrip(y, n, x[m], delta, c);
}
}
double closestPoints(Point s[], int n, Edge &c){
int i;
Point **x = new (Point*);
Point **y = new (Point*);
for (i = 0; i < n; i++)
x[i] = y[i] = &s[i];
mergeSort(x, n, leftToRightCmp);
mergeSort(y, n, BottomToTopCmp);
return cPoints(x,y,n,c);
}
int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
double s; Edge e; Point p[3];
p[0].x = 0.1; p[0].y=1.1;
p[1].x = 0.5; p[1].y=3.1;
p[2].x = 0.6; p[2].y=2.1;
s = closestPoints(p,4,e);
cout<<s;
return 0;
}
Проблема в том, что не знаю как задать множество точек. Если делать как я, то, почему-то, массив p[] не передается в функцию и массив Point s[] в функции closestPoints остается пустым.
Кто-нибудь может подсказать как правильно задать множество точек?
|