Punktar og röðun þeirra.

Ég var nýlega að vinna við þróun á hugbúnaði(í c++) sem notar punkta, þeas. hefðbundin hnit í þremur víddum. Það var áhugavert að búa til punkt-klasa, en mig vantaði líka að búa til “náttúrulega” röðun á þessum hnitum. Nokkru seinna fann ég leið til að setja röðun á hnitin.

Fyrst er að vita hvað við þurfum fyrir klasan. Hnit eru gjarnan lýst í þrívíðu rúmi sem x,y og z:

Sem breytur:

float x,y,z;

Þetta eru einu breyturnar sem klasinn þarf á að halda, og sem klasi:

class Point {
public:
float x,y,z;

// Operators … +,-,*,==,!=,<,>
//
….
};

Reyndar er það líklegast betra að hafa x,y og z sem private og hafa Point af gerðinni struct(eða álíka). En þetta er einungis sýnidæmi, engin þörf á fullri útlistun.

Þá kemur að því hvað við eigum að gera fyrir röðunina á þessum punktum, það vantar að skilgreina aðgerðina “minna en” (operator<). Þó að “stærra en” virkar líka, þá valdi ég að nota “minna en” vegna STL. Það notar “minna en” frekar en “stærra en”. Þetta krefur að tvö hnit eiga að berast saman með:

Point a,b;

if( a < b )
..// b is larger
else
..// a is larger

Þá er að skilgreina aðgerðina “minna en”, þá er hægt að nota töluvert mörg form af stærðargráðu milli tveggja hnita. Mín leið var að nota sjálf x,y,z gildin, þar sem x er mikilvægasta gildið og z er minst mikilvægasta gildið. Þetta er sama skilgreining og hjá bitatölum, þar sem við höfum MSB og LSB. Sem gefur:

Hnit |x|y|z|
Pláss |3|2|1|

sem fylgir skilgreiningunni:
x>y>z

Þá er átt við að x er plássið sem er alltaf stærra en y eða z undir öllum kringumstæðum. Núna verða málin svolítið einkennileg, þar sem gildið á x getur verið lægra en gildið á y. Þá er átt við:

a.x = -1;
a.y = 2;
a.z = 0;

b.x = 5;
b.y = 3;
b.z = 0;

og b er stærra en a, þar sem (b.x > a.x)

Þá ræður x plássið fyrst stærðargráðunni, síðan y og síðast z. Ef það er ekki hægt að finna stærðargráðu í ákveðnu plássi er farið á næsta pláss. Þessi aðstaða kemur þegar tölurnar sem eru skoðaðar í plássinu milli a og b eru jafn stórar, td:

a.x = 5;
a.y = 5;
a.z = 1;

b.x = 5;
b.y = 2;
b.z = 5;

Þá er a stærra en b, þar sem ( b.x == b.x ) verðum við að kíkja á y plássið og það þar er ( b.y < a.y ). Það er eigin þörf að skoða z plássið þar sem y plássið hefur meira mikilvægi en z plássið.

Þá er bara að skilgreina sjálfa aðferðina, í kóðanum sér hún svona út:

bool operator<( const Point & rhs){

if(

(x > rhs.x) ||
( (x == rhs.x) && (y > rhs.y) ) ||
( (x == rhs.x) && (y == rhs.y) && (z > rhs.z) ) ||
( (x == rhs.x) && (y == rhs.y) && (z == rhs.z) )

) return false;

return true;
};

Ég veit ekki hvernig þetta kemur á huga, vona að það sé skiljanlegt. Þarna er gildisprufun hluti af if setningunni, það er líka hægt að setja upp array eða álíka. Sérstaklega þegar maður er að vinna með fleiri en þrjár víddir.

Röðun hafði verið ómetanleg fyrir mig í síðsta verkefni, þar sem ég var að vinna með punktamengi. Mengin voru að meðaltali með 30 þúsund punkta, og bjóst við að fara seinna upp í 300-500 þúsund punkta. Ákveðin röðun opnaði möguleika fyrir því að nota leitaraðferðir sem margfalt hraðari en að skoða hvert hnit þar til ég myndi finna eitt ákveðið hnit.

Líka er hægt að setja klasan í Template form, það getur verið þægilegt. Þar sem ég skipti reglulega á milli heiltalna og rauntalna í forritinu mínu.

Kv. Lain.