К оглавлению

Список точек на плоскости

С.И.Хашин


pvectors.h - заголовочный файл
pvectors.cpp - реализация.

В начале реализован совсем простой класс "точка на плоскости": 

class pnt {
public:
    int x, y;
    pnt(int x_ = 0, int y_ = 0) { x = x_; y = y_; };
    bool operator==(pnt& rhs) { return x == rhs.x && y == rhs.y; };
};

Затем описываем массив точек: 

class pvector{  // вектор точек
    vector v;
    pvector(int n);             // конструктор
    void    setSize(int n);     // задать размер
    ...
};

Помимо естественных основных методов имеются нахождение максимумов и минимумов каждой из координат, а также: 

    int     getX(int i);    // x-координата i-й точки
    int     getY(int i);    // y-координата i-й точки
    void    add(pnt  &p);   // добавить точку в вектор
    void    add(int x, int y);// добавить точку в вектор
    void    add(pvector &w);
    int     maxX();             // максимальное значение x-координаты
    int     maxY();             // максимальное значение y-координаты
    int     minX();             // минимальное значение x-координаты
    int     minY();             // минимальное значение y-координаты
    void    del(int k0, int k1);// delete points [k0..k1] exactly
    int     indexOf(pnt p);     // поиск точки p в массиве, -1 - не найдено

Сохранение в файл и чтение из файла: 

    void    save(char *filename, char *msg, int k = 1, char *frm = " (%4d,%4d)");   // сохранить в файл по k штук в строку по формату frm
    void    load(char *filename);   // прочитать из файла

При сохранении вектора точек в файле, обычно вектор сохраняется по одной точке в строке: 

    list.save("t:\\list.txt", "source " );

Результат (121 – количество элементов вектора): 

   1) source , #121
   0) (  30,  10)
   1) (  31,  10)
   2) (  32,  10)
   3) (  33,  10)
…

Можно сохранить по нескольку точек в строке (например, 3): 

    list.save("t:\\list2.txt", "source (square)", 3 );

Результат: 

   3) source (square), #121
   0(   0):  (  30,  10) (  31,  10) (  32,  10)
   3(   1):  (  33,  10) (  34,  10) (  35,  10)
   6(   2):  (  36,  10) (  37,  10) (  38,  10)
…

Можно, кроме того, задать формат вывода каждой пары координат: 

    hull.save("t:\\list3.txt", "save-load-save", 3, " (x=%2d, y=%2d)" );

Результат: 

   3) save-load-save, #121
   0(   0):  (x=30, y=10) (x=31, y=10) (x=32, y=10)
   3(   1):  (x=33, y=10) (x=34, y=10) (x=35, y=10)
   6(   2):  (x=36, y=10) (x=37, y=10) (x=38, y=10)
   9(   3):  (x=39, y=10) (x=40, y=10) (x=30, y=11)
…

Можно создать список, содержащий все точки круга или прямоугольника: 

    void    createCircle( int x0, int y0, double rad, int mx=0, int my=0);  
        // построить круг. Если mx,my>0, то точки не должны заходить за эти пределы

    void    createBox   ( int x0, int y0, int dx, int dy);
        // построить прямоугольник

А теперь то же самое, но только точки, обе координаты которых делятся на k: 

    void    createCircleK(int x0, int y0, double rad, int K, int mx = 0, int my = 0);
    void    createBoxK(int x0, int y0, int dx, int dy, int K);

сортировка 

    void    sortByX ();             // отсортировать список по убыванию    X
    void    sortByX_();             // отсортировать список по возрастанию X
    void    sortByY ();             // отсортировать список по убыванию    Y
    void    sortByY_();             // отсортировать список по возрастанию Y

средние и далекие точки 

double middPoint_(pnt &m);  // m - среднее значение векторов p[i], возвращает 
                            // среднеквадратичное расстояние до центра
double middPoint(double &x1, double &y1);   // (x1,y1) среднее значение векторов p[i], возвращает среднеквадратичное расстояние до центра
int    mostFarPoint(pnt &a);    // индекс в списке p самой дальней от a точки
int    nearestPoint(pnt &a);    // индекс в списке p самой близкой к  a точки

сократить список до заданного размера: 

void reduceList( pvector &list, int newSize); // this:= проредить список точек list 
                                              // так, чтобы осталось ~newSize точек

// Координаты всех точек поделить на k (точки должны остаться различными)
// Если заданы mx, my, то новые координаты не должны превышать (mx,my)
void listDividQ( pvector &list, int k, int mx=0, int my=0);

Нахождение выпуклой оболочки множества точек: 

    void    convexHull(pvector &p);// this = выпуклая оболочка(p)

Пример. 

    pvector l,l1;               // создали объекты
    l.createCircle(10, 10, 3);  // l:= круг радиуса 3
    l.save("l.txt", "circle", 10, "(%2d,%2d)"); // сохранить по 10 в ряд
    l1.convexHull(l);           // l1:=выпуклая оболочка
    l1.save("l1.txt", "Hull");  // сохранить по одной точке в ряд.

В файле l.txt получим: 

  10) circle, #29
   0(   0): (10, 7)( 8, 8)( 9, 8)(10, 8)(11, 8)(12, 8)( 8, 9)( 9, 9)(10, 9)(11, 9)
  10(   1): (12, 9)( 7,10)( 8,10)( 9,10)(10,10)(11,10)(12,10)(13,10)( 8,11)( 9,11)
  20(   2): (10,11)(11,11)(12,11)( 8,12)( 9,12)(10,12)(11,12)(12,12)(10,13)

В файле l1.txt получим: 

  10) circle, #29
   0(   0): (10, 7)( 8, 8)( 9, 8)(10, 8)(11, 8)(12, 8)( 8, 9)( 9, 9)(10, 9)(11, 9)
  10(   1): (12, 9)( 7,10)( 8,10)( 9,10)(10,10)(11,10)(12,10)(13,10)( 8,11)( 9,11)
  20(   2): (10,11)(11,11)(12,11)( 8,12)( 9,12)(10,12)(11,12)(12,12)(10,13)

К оглавлению


free counters