Хранение площадей перекрывающихся фигур

@Gepar · Регистрация: 01.07.2009

Author24 — интернет-сервис помощи студентам

Перефразирую свою старую тему, видать намудрил я там с описанием.

Задача: как-нибудь (вообще как-угодно, лишь бы побыстрее работало) в классе хранить площади фигур которые нам дают через функцию Add. У каждой фигуры, кроме координат, есть свой номер (ID).
Часть координат будут давать в виде структуры (чтобы меньше параметров передавать).

C++

struct CCoord
{
    int   m_X;
    int   m_Y;
};

Возможные фигуры:
CRectangle ( int ID, int x1, int y1, int x2, int y2 ) - координаты противоположных углов
CCircle ( int ID, int x, int y, int r) - середина и радиус
CTriangle ( int ID, CCoord a, CCoord b, CCoord c) - треугольник, 3 вершины
CPolygon ( int ID, int n, const CCoord * v ) , многоугольник, n вершин, координаты вершин дают в массиве v.

Предположительно что координаты дают с левой по правую (тоесть для треугольника дают точку слева, потом вершину, потом точку справа).

Формально нужно хранить это всё так чтобы можно было потом по координате x,y определить что пересекает эту точку (нужно вернуть ID фигуры что пересекает). Any ideas?

Теоретически получается что когда вызывают метод Add и дают фигурку можно даже не заморачиваться с хранением оригинала, нужно только как-то запомнить те координаты что она накрывает и пометить эти координаты её ID, но как это сделать ... Или же можно хранить оригиналы и как-то пересчитывать потом накрывают ли они какую точку ... желательно ещё чтобы это всё работало быстро.

Тоже самое что я написал, но в виде кода (написаны сами классы, метод Add ничего никуда не добавляет так как не решился как это всё хранить):

код

C++

#include <iostream>
#include <string>
using namespace std;
 
struct CCoord
{
    CCoord (int x = 0,int y = 0 )
    : m_X(x), m_Y(y) {}
 
    int   m_X;
    int   m_Y;
};
 
//базовый класс для фигур
class CObject
{
public:
    CObject(int _id)
    :ID(_id) {}
 
    int ID;
};
 
class CRectangle: public CObject
{
public:
    CRectangle(int ID,int _x1,int _y1,int _x2,int _y2)
    :CObject(ID), x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}
 
private:
    //верхняя левая координата
    int x1;
    int y1;
 
    //нижняя правая коордианата
    int x2;
    int y2;
};
 
class CCircle: public CObject
{
public:
    CCircle(int ID, int _x, int _y, int _r)
    :CObject(ID), x(_x), y(_y), r(_r) {}
 
private:
    //координата центра
    int x;
    int y;
 
    //радиус круга
    int r;
};
 
class CTriangle: public CObject
{
public:
    CTriangle(int ID, CCoord _a, CCoord _b, CCoord _c)
    : CObject(ID), a(_a), b(_b), c(_c) {}
 
private:
    CCoord a;//левая
    CCoord b;//средняя
    CCoord c;//правая
};
 
class CPolygon: public CObject
{
public:
    CPolygon(int ID, int n, const CCoord* v)
    : CObject(ID),size(n), coord(new CCoord[size])
    {
        for(int i=0;i<size;i++)
         coord[i]= v[i];
    }
 
    CPolygon(const CPolygon& right)
    :CObject(right.ID), size(right.size), coord(new CCoord[size])
    {
        for(int i=0;i<size;i++)
         coord[i]=right.coord[i];
    }
 
    virtual CObject* clone()
    {
        return new CPolygon(*this);
    }
 
private:
    int size;//сколько координат
 
    //указатель на массив координат. Координаты располагаются от левой до правой
    CCoord* coord;
};
 
 
class CScreen
{
public:
    Add(CObject* toAdd)//должна хранить как-то координаты фигуры что дают
    {
 
    }
 
    //должна вернуть сколько(resLen) фигур пересекают точку x,y и их id(массив res)
    void Test(int x, int y, resLen, int res* )
    {
 
    }
 
 
private:
};
 
int main()
{
    CScreen  S1;
    S1 . Add ( CCircle ( 1, 10, 10, 15 ) );
    S1 . Add ( CCircle ( 2, 30, 10, 15 ) );
    S1 . Add ( CCircle ( 3, 20, 20, 15 ) );
    S1 . Optimize();
    S1 . Test ( 0, 0, resLen, res );
}

	10.05.2012, 15:11