Jan Pytel
Katedra mapování a kartografie, Stavební fakulta ČVUT
Thákurova 7,
166 29 Praha 6
E - mail: pytel@gama.fsv.cvut.cz
First part of the article is aimed to introduce project GNU Gama and data structures which are used in this project. Second part cover informations about model "Acyclic Visitor" (model is explained and compared with other models).
Příspěvek se zabývá projektem GNU Gama a datovými strukturami v tomto projektu použitými. Zvláštní pozornost je věnována modelu "Acyclic Visitor".
Příspěvek popisuje datové struktury projektu GNU Gama a objektový model "Acyclic Visitor" použitý v tomto projektu. Podstatná část prvních dvou kapitol byla převzata z článku Pytel, J. - Čepek, A. : Projekt vyrovnávání geodetických sítí GNU Gama.
Většina zdrojových kódů, použitých v příspěvku, byla pro účely příspěvku zkrácena a upravena. Kompletní zdrojové kódy lze nalézt na domovské stránce projektu GNU Gama.
Projekt GNU Gama je věnován vyrovnávání geodetických sítí, jde o GNU projekt a je proto volně šiřitelný, včetně zdrojových kódů, pod licencí GNU General Public Licence (GPL)
http://www.gnu.org/software/gama.
Začátky projektu GNU Gama se datují rokem 1998 a u zrodu stál Aleš Čepek z Katedry mapování a kartografie FSV ČVUT. Projekt GNU Gama je založen na C++ knihovně tříd pro vyrovnání a organizaci geodetických měření (maximální důraz je kladen na přenositelnost zdrojového kódu), součástí projektu je též C++ knihovna gmatvec pro práci s maticemi a vektory.
GNU Gama poskytuje kromě "klasického" vyrovnání sítí i řadu informací pro analýzu vyrovnané sítě. Vyrovnání měření řeší projekt GNU Gama přímým řešením rovnic oprav (ortogonalizační algoritmy SVD anebo GSO), tj. bez nutnosti sestavování tzv. normálních rovnic. Jako základní numerické metody pro řešení soustavy rovnic oprav se využívají algoritmy singulárního rozkladu (SVD), k dispozici je i Gram-Schmidtova ortogonalizace. Samozřejmostí je automatický výpočet přibližných souřadnic a iterativní zpřesnění výsledků vyrovnání (pokud je potřeba).
Vstupní data pro projekt GNU Gama jsou definována v souladu se standardem metajazyka Extended Markup Language (XML) pro popis strukturovaných dat
Projekt GNU Gama je rozdělen na dvě vývojové větve:
Pro projekt GNU Gama též existuje grafické uživatelské rozhraní (GUI) Rocinante, které je založeno na grafické knihovně Qt. Domovská stránka projektu Rocinante se nachází na adrese
http://sourceforge.net/projects/roci.
Nosnou částí návrhu projektu GNU Gama je objektová realizace observačních dat, vybudovaná na konceptu tzv. clusterů (z anglického slova cluster - hrozen). Koncept clusterů umožňuje spravovat (vyrovnávat) libovolné kombinace korelovaných (a samozřejmě též nekorelovaných) měření.
Pokud popíšeme cluster C++ terminologií, pak cluster je objekt obsahující seznam ukazatelů na objekty měření (směry, délky, úhly) a obsahující jednu kovarianční matici odpovídající daným měřením.
Vztah clusterů s ostatními objekty je znázorněn na obr. 1.
Obr. č. 1 Datové struktury - použití koncepce clusterů
Váhy byly odstraněny z observací (bázová třída Observation) a nahrazeny ukazatelem na cluster ke kterému náleží. Všechny clustery jsou seskupeny v objektu ObservationData a každý cluster obsahuje ukazatel na tento objekt.
Observační datové struktury byly navrženy tak, aby umožňovaly jednoduchou implementaci nových observačních typů. Pokud chceme implementovat nový observační typ, je nutné pouze odvodit novou třídu z bázové třídy Observation a definovat několik virtuálních funkcí (např. virtuální funkci pro linearizaci), případně ještě odvodit vhodnou třídu z třídy Cluster. V současné době jsou podporovány následující typy měření:
Předpokladem pro vyrovnání metodou MNČ je lineární tvar rovnic oprav. Každé měření je nutno nejprve linearizovat vzhledem k neznámým (neznámé souřadnice x, y, z a orientační posuny).
Pokusme si naznačit jakým způsobem probíhá linearizace měření v projektu GNU Gama. Způsob linearizace měření se liší dle vývojové a stabilní verze projektu.
Měření jsou linearizována dle neznámých parametrů, kterými v této větvi projektu mohou být pouze neznámé souřadnice x, y, z a orientační posuny o.
Třída Cluster obsahuje seznam ukazatelů observation_list na objekty měření. Při linearizaci všech měření v daném clusteru je pro každý prvek seznamu volána členská funkce
void Observation::linearization(const Linearization* lin) const
{
lin->linearization(this);
}
tato metoda interně volá členskou funkci
void Linearization::linearization(const Observation* o) const
{
rhs = size = 0;
if (const Direction *dir =
dynamic_cast<const Direction *>(o))
direction(dir);
else if(const Distance *dis =
dynamic_cast<const Distance *>(o))
distance(dis);
else if(const Angle *ang =
dynamic_cast<const Angle *>(o))
angle(ang);
else if(const H_Diff *h_d =
dynamic_cast<const H_Diff *>(o))
h_diff(h_d);
else if(const S_Distance *s_d =
dynamic_cast<const S_Distance*>(o))
s_distance(s_d);
else if(const Z_Angle *z_a =
dynamic_cast<const Z_Angle *>(o))
z_angle(z_a);
}
Členská funkce Linearization::linearization pomocí dynamického přetypování (operátor dynamic_cast) zjistí typ instance ukazatele o a volá členskou funkci odpovídající typu instance.
Například pro délku (třída Distance) vypadá členská funkce takto:
void Linearization::distance(const Distance* obs) const
{
LocalPoint& sbod = PD[obs->from()];
LocalPoint& cbod = PD[obs->to()];
Double s, d;
bearing_distance(PD[obs->from()], PD[obs->to()], s, d);
// Double p = M_0 / stdDev();
Double ps = sin(s);
Double pc = cos(s);
// Double w = p*p; // weight
rhs = (obs->value() - d)*1e3; // abs. term in mm
size = 0;
if (sbod.free_xy())
{
if (!sbod.index_x()) sbod.index_x() = ++maxn;
if (!sbod.index_y()) sbod.index_y() = ++maxn;
index[ size ] = sbod.index_y();
coeff[ size ] = -ps;
size++;
index[ size ] = sbod.index_x();
coeff[ size ] = -pc;
size++;
}
if (cbod.free_xy())
{
if (!cbod.index_x()) cbod.index_x() = ++maxn;
if (!cbod.index_y()) cbod.index_y() = ++maxn;
index[ size ] = cbod.index_y();
coeff[ size ] = ps;
size++;
index[ size ] = cbod.index_x();
coeff[ size ] = pc;
size++;
}
}
Předešlý kód popisuje linearizaci ("plnění" matice oprav) dle jednotlivých parametrů (pro délku jsou to souřadnice x, y, z počátečního a koncového bodu).
Takto navržený způsob datových struktur ve stabilní větvi umožňuje jednoduchou implementaci nových observačních typů. V případě implementace nového observačního typu, je nutné pouze odvodit novou třídu z bázové třídy Observation, definovat několik virtuálních funkcí (např. virtuální funkci pro linearizaci) a případně odvodit vhodnou třídu z třídy Cluster. Tento návrh však nepočítá s přidáváním nových parametrů (neznámých) pro linearizaci.
Linearizace měření ve stabilní větvi předpokládá, že neznámými parametry jsou pouze souřadnice a orientační posuny. Toto pojetí není v globálním vyrovnání dostačující, zvláště má-li být návrh maximálně flexibilní (možnost budoucího přidávání libovolných parametrů, například zavedení refrakce jako dalšího neznámého parametru).
Z těchto důvodů byl ve vývojové větvi projektu zaveden pojem parametr. Pojem parametr je reprezentován třídou Parameter, obsahující následující informace: počáteční hodnotu, vlastní korekce (opravu parametru získanou z vyrovnání), odpovídající číslo sloupce v matici oprav a typ parametru (nepoužitý, volný, opěrný, ...). Třída Parameter dále obsahuje atribut ParameterList parlist; reprezentující seznam parametrů (seznam parametrů na kterých je daný parametr závislý).
Ve vývojové větvi každý druh měření obsahuje (svou vlastní) řadu parametrů, při linearizaci je měření dle těchto parametrů linearizováno. Abstraktní třída Observation má definován atribut ParameterList parlist; obsahující seznam parametrů. Změněna též byla členská funkce zajišťující linearizaci měření
void Observation::linearization(GNU_gama::SparseVector<>&)
{
prepare_to_linearization();
row.reset();
ParameterTree tree(parlist);
ParameterTree::iterator b=tree.begin(), e=tree.end();
double d;
Parameter* p;
while (b != e)
{
p = *b;
if (p->free())
{
d = derivative(p);
if (d) row.add(p->index(), d);
}
++b;
}
}
Linearizace daného měření se provádí dle všech parametrů, které jsou obsaženy v atributu parlist (poznámka: parametry mohou rekurzivně obsahovat další parametry). Jestliže pro danou kombinaci typu měření a parametru není definována analytická derivace, je vypočtena derivace numerická.
Pokud je do projektu přidán nový parametr, je nutné nadefinovat analytické derivace pro všechna odpovídající měření. Jak však implementovat metody double typ_mereni::derivate(Parameter*) a navrhnout příslušný model (popisující vztahy mezi měřeními a parametry)? Model musí být navržen tak, aby poskytoval možnost korektně rozpoznat, je-li pro kombinaci daného měření a parametru definována analytická derivace a tuto derivaci "zavolat".
Možná řešení jsou naznačena v následující kapitole.
Tato kapitola (resp. její podkapitoly) obsahuje možnosti, jak implementovat model řešící problém s analytickými derivacemi. Tedy model zajišťující volání odpovídajících analytických derivací pro dané kombinace měření a parametrů.
"Procedurální" model řeší problém vytvořením dvojrozměrného (jedna dimenze pole reprezentuje měření, druhá dimenze reprezentuje parametry) pole ukazatelů na funkce (analytické derivace).
Nejprve je nutné definovat dva výčtové typy:
enum type_observation {
obsDistance = 0,
obsAngle
};
enum type_parameter {
paramB,
paramL,
paramH
};
Poté je definováno dvojrozměrné pole ukazatelů na funkce ListDerFun. Pole obsahuje pro všechny kombinace měření a parametrů ukazatel na příslušnou funkci (pokud analytická derivace pro danou kombinaci neexistuje, je ukazatel roven 0) ve tvaru double (*derivative)(Observation*).
Řešení:
#include <iostream>
enum type_observation {
obsDistance = 0,
obsAngle,
e_number_of_observations
};
enum type_parameter {
paramB = 0,
paramL,
paramH,
e_number_of_parameters
};
struct Observation
{ Observation(type_observation i):type(i) {} type_observation type; };
struct Distance: public Observation
{ Distance():Observation(obsDistance) {} };
struct Angle : public Observation
{ Angle ():Observation(obsAngle ) {} };
struct Parameter
{ Parameter(type_parameter i):type(i) {} type_parameter type; };
struct L: public Parameter { L():Parameter(paramL) {} };
struct B: public Parameter { B():Parameter(paramB) {} };
typedef double (*derivative)(Observation*);
double derivation_distance_L(Observation* obs)
{
return 100;
}
double derivation_angle_H(Observation* obs)
{
return 200;
}
int main()
{
derivative ListDerFun[e_number_of_observations]
[e_number_of_parameters ] = { 0 };
ListDerFun[obsDistance][paramL] = derivation_distance_L;
ListDerFun[obsAngle ][paramH] = derivation_angle_H;
for (int obs = 0; obs < e_number_of_observations; obs++)
{
for (int par = 0; par < e_number_of_parameters; par++)
std::cout << ListDerFun[obs][par] << " ";
std::cout << std::endl;
}
std::cout << std::endl;
for (int obs = 0; obs < e_number_of_observations; obs++)
{
for (int par = 0; par < e_number_of_parameters; par++)
if ( derivative d = ListDerFun[obs][par])
std::cout << "[" << obs << "," << par
<< "] existuje" << std::endl;
else
std::cout << "[" << obs << "," << par
<< "] neexistuje" << std::endl;
}
Angle* a = new Angle;
Distance* d = new Distance;
L l;
B b;
if (derivative der = ListDerFun[a->type][l.type])
std::cout << "\nAL " << ListDerFun[a->type][l.type](a);
if (derivative der = ListDerFun[a->type][b.type])
std::cout << "\nAB " << ListDerFun[a->type][b.type](a);
if (derivative der = ListDerFun[d->type][l.type])
std::cout << "\nDL " << ListDerFun[d->type][l.type](d);
if (derivative der = ListDerFun[d->type][b.type])
std::cout << "\nDB " << ListDerFun[d->type][b.type](d);
}
Výstup programu:
0 1 0
0 0 1
[0,0] neexistuje
[0,1] existuje
[0,2] neexistuje
[1,0] neexistuje
[1,1] neexistuje
[1,2] existuje
DL 100
Problém tohoto řešení spočívá v přidávání nových typů měření a parametrů. Neustále je nutné udržovat výčtové typy type_observation, type_parameter a pole ListDerFun (přiřazováním vhodných funkcí) "aktuální". Přidání jednoho parametru (či měření) ovlivní řadu ostatních datových struktur. Podobné (ne-li větší) problémy lze očekávat též v případě odstranění některých typů měření. Režie nutná k udržování takto navrženého modelu je značná.
Základem návrhu je abstraktní bázová třída Parameter, která představuje "visitora" (návštěvníka). Třída obsahuje čistě virtuální metody (reprezentující analytickou derivaci pro všechny typy měření XXXX)
virtual double Parameter::deriveXXXX (XXXX&) = 0;.
Každý nový parametr musí být odvozen od třídy Parameter a definovat všechny metody deriveXXXX pro všechna měření.
Neboť ukazatel (resp. reference) na odvozenou třídu (např. ParameterB) lze použít všude tam, kde je očekáván ukazatel (resp. reference) na bázovou třídu (třída Parameter), je možno ve třídě Observation definovat pouze jednu čistě virtuální metodu
Pokud je pro jednotlivé typy měření vhodně definována metoda derive, díky polymorfizmu bude pro danou kombinaci měření a parametru volána korektní derivace.
Řešení pro dva typy měření (Distance, Angle) a tři parametry:
#include <iostream>
class Angle;
class Distance;
class Parameter
{
public:
virtual double deriveDistance (Distance&) = 0;
virtual double deriveAngle (Angle&) = 0;
};
class ParameterB : public Parameter
{
public:
double deriveDistance (Distance&) { return 10; }
double deriveAngle (Angle& ) { return 20; }
};
class ParameterL : public Parameter
{
public:
double deriveDistance (Distance&) { return 30; }
double deriveAngle (Angle& ) { return 40; }
};
class ParameterH : public Parameter
{
public:
double deriveDistance (Distance&) { return 50; }
double deriveAngle (Angle& ) { return 60; }
};
class Observation
{
public:
virtual double derive(Parameter& v) = 0;
};
class Distance: public Observation
{
public:
double derive(Parameter& v)
{
return v.deriveDistance(*this);
}
};
class Angle : public Observation
{
public:
double derive(Parameter& v)
{
return v.deriveAngle(*this);
}
};
int main()
{
ParameterL l;
ParameterB b;
ParameterH h;
Angle a;
std::cout << "\nAngleL " << a.derive(l);
std::cout << "\nAngleB " << a.derive(b);
std::cout << "\nAngleH " << a.derive(h);
Distance d;
std::cout << "\nDistance " << d.derive(l);
std::cout << "\nDistance " << d.derive(b);
std::cout << "\nDistance " << d.derive(h);
}
Výstup programu:
AngleL 40
AngleB 20
AngleH 60
Distance 30
Distance 10
Distance 50
Režie nutná k údržbě tohoto modelu je stále značná. V případě přidání nového typu měření (odvozeného od třídy Observation), je nutné modifikovat třídu Parameter přidáním příslušné čistě virtuální metody. Ve všech potomcích třídy Parameter musíme příslušnou metodu též definovat a to i v případě, kdy neexistuje pro danou kombinaci parametr-měření analytická derivace (zde by metoda vyvolala výjimku). Vzájemné závislosti mezi třídami, viz. obr. 2.
Obr. č. 2 Vztahy tříd - model "Visitor"
Model "Acyclic Visitor" odstraňuje nedostatky předchozích dvou řešení. Roli "návštěvníka" (visitora) v tomto modelu představuje degenerovaná třída Parameter, která má definován pouze virtuální destruktor (pro pozdější dynamické přetypování je nezbytně nutné, aby třída obsahovala alespoň jednu virtuální metodu). V tomto modelu bázová abstraktní třída Observation obsahuje čistě virtuální metodu
virtual double Observation::derivation(Parameter* v) = 0;.
Dále je nutné definovat abstraktní třídy derivací DeriveXXX pro každou třídu (typ měření)odvozenou od třídy Observation. V ukázce se jedná o třídy: DeriveAngle a DeriveDistance. Tyto třídy poskytují čistě virtuální funkce
virtual double derive(Angle*) = 0;
resp.
virtual double derive(Distance*) = 0;.
V případě definice nového typu měření (odvozením od abstraktní třídy Observation) je nezbytné definovat metodu double derivation(Parameter* v);, např.:
double Distance::derivation(Parameter* v)
{
DeriveDistance* ad = dynamic_cast<DeriveDistance*>(v);
if (ad)
return ad->derive(this);
else
return 0;// nonsence value
}
Výše uvedená metoda obsahuje operátor dynamic_cast pro dynamické přetypování, pokud je tedy žádoucí pro danou kombinaci typu měření a parametru definovat analytickou derivaci, stačí definovat parametr takto (v ukázce je definice analytické derivace délky dle parametru B):
class ParameterB : public Parameter,
public DeriveDistance,
{
public:
double derive(Distance*) { return 10; }
};
Třída ParameterB je odvozena od tříd Parameter a DerivativeDistance, musí tedy definovat metodu double derive(Distance*);. Má-li být další měření Angle analyticky derivovatelné dle parametru typu ParameterB, definice třídy musí být definována následovně:
class ParameterB : public Parameter,
public DeriveDistance,
public DeriveAngle
{
public:
double derive(Distance*) { return 10; }
double derive(Angle* ) { return 20; }
};
Nyní jsou definovány analytické derivace měření typu Distance a Angle dle parametru ParameterB. Zde je důležité uvědomit si, jakým způsobem pracuje operátor dynamic_cast:
Parameter* p = new ParameterB;
DeriveDistance* dd = dynamic_cast<DeriveDistance*>(p);
Řešení - model "Acyclic Visitor":
#include <iostream>
class Angle;
class Distance;
class Parameter
{
public:
virtual ~Parameter() {}
};
class Observation
{
public:
virtual double derivation(Parameter* v) = 0;
};
class Angle;
class DeriveAngle
{
public:
virtual double derive(Angle*) = 0;
};
class Distance;
class DeriveDistance
{
public:
virtual double derive(Distance*) = 0;
};
class ParameterB : public Parameter,
public DeriveDistance,
public DeriveAngle
{
public:
double derive(Distance*) { return 10; }
double derive(Angle* ) { return 20; }
};
class ParameterL : public Parameter,
public DeriveDistance,
public DeriveAngle
{
public:
double derive(Distance*) { return 30; }
double derive(Angle* ) { return 40; }
};
class ParameterH : public Parameter,
public DeriveDistance
{
public:
double derive(Distance*) { return 50; }
};
class Distance: public Observation
{
public:
double derivation(Parameter* v)
{
DeriveDistance* ad = dynamic_cast<DeriveDistance*>(v);
if (ad)
return ad->derive(this);
else
return 0;// nonsence value
}
};
class Angle : public Observation
{
public:
double derivation(Parameter* v)
{
DeriveAngle* aa = dynamic_cast<DeriveAngle*>(v);
if (aa)
return aa->derive(this);
else
return 0;// nonsence value
}
};
int main()
{
ParameterL* l = new ParameterL;
ParameterB* b = new ParameterB;
ParameterH* h = new ParameterH;
Angle a;
std::cout << "\nAngleL " << a.derivation(l);
std::cout << "\nAngleB " << a.derivation(b);
std::cout << "\nAngleH " << a.derivation(h);
Distance d;
std::cout << "\nDistanceL " << d.derive(l);
std::cout << "\nDistanceB " << d.derive(b);
std::cout << "\nDistanceH " << d.derive(h);
}
Výstup programu:
AngleL 40
AngleB 20
AngleH 0
DistanceL 30
DistanceB 10
DistanceH 50
Předchozí ukázku lze přepsat (mírně zkrátit) s využitím šablon:
#include <iostream>
class Angle;
class Distance;
class Parameter
{
public:
virtual ~Parameter() {}
};
class Observation
{
public:
virtual double derive(Parameter* v) = 0;
};
template <typename TypeOfObservation>
class Derive
{
public:
virtual double derive(TypeOfObservation*) = 0;
};
class ParameterB : public Parameter,
public Derive<Distance>,
public Derive<Angle>
{
public:
double derive(Distance*) { return 10; }
double derive(Angle* ) { return 20; }
};
class ParameterL : public Parameter,
public Derive<Distance>,
public Derive<Angle>
{
public:
double derive(Distance*) { return 30; }
double derive(Angle* ) { return 40; }
};
class ParameterH : public Parameter,
public Derive<Distance>
{
public:
double derive(Distance*) { return 50; }
};
class Distance: public Observation
{
public:
double derive(Parameter* v)
{
Derive<Distance>* ad = dynamic_cast<Derive<Distance>*>(v);
if (ad)
return ad->derive(this);
else
return 0;// nonsence value
}
};
class Angle : public Observation
{
public:
double derive(Parameter* v)
{
Derive<Angle>* aa = dynamic_cast<Derive<Angle>*>(v);
if (aa)
return aa->derive(this);
else
return 0;// nonsence value
}
};
int main()
{
ParameterL* l = new ParameterL;
ParameterB* b = new ParameterB;
ParameterH* h = new ParameterH;
Angle a;
std::cout << "\nAngleL " << a.derive(l);
std::cout << "\nAngleB " << a.derive(b);
std::cout << "\nAngleH " << a.derive(h);
Distance d;
std::cout << "\nDistanceL " << d.derive(l);
std::cout << "\nDistanceB " << d.derive(b);
std::cout << "\nDistanceH " << d.derive(h);
}
Jestliže ve výše uvedeném zdrojovém kódu budeme chtít např. definovat analytickou derivaci měření typu Angle dle parametru typu ParameterH, je nutné pouze třídu ParameterH odvodit též od třídy DeriveAngle a definovat virtuální metodu
double ParameterH::derive(Angle*);.
Oproti modelu "Visitor" není nutné definovat analytické derivace pro všechny kombinace měření-parametry (třída Parameter již nemá definovány virtuální funkce analytických derivací pro všechny typy měření). Výhodou tohoto modelu je značné snížení "režie" při definování nových typů měření či parametrů. Další výhodou je porušení "cyklu závislostí" mezi třídami, viz. obr. 3.
Obr. č. 3 Vztahy tříd - model "Acyclic Visitor"
Více o modelu "Acyclic Visitor", viz. [1].
Cílem příspěvku bylo poukázat na existenci projektu GNU Gama a seznámit účastníky konference s datovými strukturami použitými v projektu. Zvláštní důraz byl položen na model "Acyclic Visitor", jehož výhody byly demonstrovány na jednoduché ukázce. Příspěvek obsahuje porovnání tři modelů ("procedurální" model, model "Visitor" a model "Acyclic Visitor") pro řešení analytických derivací.
Tento článek vznikl za podpory Grantové agentury České republiky při řešení projektu Vyrovnání a analýza geodetických měření, registrovaného pod číslem 205/03/0017 GA ČR.