In the GIS/GPS world, we represent a position on Earth with three variables XYZ (for Earth centered coordinates) or latitude (phi) , longitude (lambda) and height (h) in polar (PLH) representation. Three-D graphic applications also requires processing of XYZ data. Creating such applications requires keeping track of the triplets of data.
When it comes to processing the triplet data, such as adding or removing coordinate points, or linking the points to form lines or polygons, and performing various geometrical calculations we inevitably need some sort of arrays or linked list. There are many methods that you could use eg: -
structs or a 3-dimensional arrays as the container for the triplets or perhaps linked structure list depending on the requirements. Alternatively one can also use
CList class. I believe these are fairly generic such that many commercial development environments support them.
Then there is the Standard Template Library (STL) which comes in many flavors. Popular libraries include STLPort and Boost. These template libraries provide excellent support for manipulation of vector and list data in a generic manner. In this article, when I refer to STL I mean STL in general - even though particular library(ies) does not support a certain style implementation.
Unfortunately, whilst STL containers such as
vector<> makes processing of arrays easy, it is not easy to use as is. For example how do we create lists of XYZ coordinates using
vector<>? The standard STL
vector<> only provides for scalar or "1 variable" arrays and many articles available on the web illustrates creation of 1-dimensional arrays.
The next best thing is to use
struct as a parameter for the STL
vector<> - but then the
vector<> template does not fully support
structs. Back to square one. The only way is to use the
pair<> template in conjunction with the
vector<> to create multi-pairs
pairs<> to achieve n-dimensions> Otherwise you have to create your own
struct STL template.
This article is not about which algorithm or library has a better data structure or better algorithm, but to present an alternative to existing methodology in relation to storing and processing of triplet data such as geographical coordinates above.
Here I shall present the use of the
"triplet<>" template which I created for use with the Standard Template Library (STL) to support such 3D vectors. ("triplet" is an STL template adapted from VS2008 and STLPort templates - see note at end of article). The triplet template is a specialized template that extends the
map<> templates and is compatible with MS's or STLPort's libraries.
There are some comprehensive and powerful STL libraries that supports n-dimensional arrays such as Boost. You have to download megabytes and then spend some time in figuring out the build options and then a couple of hours letting it compile/build. If you only need a few containers and not all the Boost's features, then it is too much bloat.
Simulating Multi-Dimension Arrays Using Pair<> Template
vector< pair<double,double> > vArray2d;
double x1, x2;
vArray2d.push_back ( make_pair(x1,x2) );
x1 = vArray2d[id].first;
x2 = vArray2d[id].second;
vector< pair< pair<double,double>, pair<double,double> > > vArray4d;
double x1, x2, x3, x4;
vArray4d.push_back ( make_pair( make_pair(x1,x2), make_pair(x3,x4) ) );
x1 = vArray4d[id].first.first;
x2 = vArray4d[id].first.second;
x3 = vArray4d[id].second.first;
x4 = vArray4d[id].second.second;
vector< pair< pair<double,double>, pair<double,double> > > vArray3d;
double x1, x2, x3, dummy;
vArray3d.push_back ( make_pair< make_pair(x1,x2), make_pair(x3,dummy) );
There are quite a number of ways to provide support for XYZ coordinates using STL:
- make XYZ into strings and store them as a list of strings (messy & huge programming overhead)
- store XYZ as arrays (not much better than normal array)
- create an array of XYZ and store pointers to the XYZ array
The outline code below illustrates these methods.
In the examples and code below I shall use XYZ to mean coordinate (X,Y,Z). The units could be in feet, meters, kilometers, etc.
Storing as Strings
double X, Y, Z;
for ( int i=0; i<NoCoords; i++)
sprintf (szXYZ, "%lf %lf %lf", X, Y, Z);
strXYZ = szXYZ;
for ( int i=0; i<NoCoords; i++ )
szXYZ = vXYZStr[i];
sscanf ("%lf %lf %lf", &X, &Y, &Z);
... process XYZ ...
Storing as Values
vector< pair< pair<double,double>, pair<double,double> > > vXYZ;
double X, Y, Z, t; for (int i=0; i<=NoCoords; i++)
... read/get XYZ from somewhere ...
vXYZ.push_back ( make_pair( make_pair(X,Y), make_pair(Z,t) ) );
for ( int idx=0; idx<=1 ; idx++)
X = ComplexVector[idx].first.first; Y = ComplexVector[idx].first.second; Z = ComplexVector[idx].second.first;
t = ComplexVector[idx].second.second; ... process XYZ ...
vXYZ.push_back ( make_pair( make_pair(id,X), make_pair(Y,Z) ) );
for ( int idx=0; idx<=1 ; idx++)
id = ComplexVector[idx].first.first; X = ComplexVector[idx].first.second; Y = ComplexVector[idx].second.first; Z = ComplexVector[idx].second.first; ... do something with the XYZ ...
Storing as Pointers to an Array
vector<double* /> dVector<double *>;
#define VECTOR_SIZE 1000 double dArray[VECTOR_SIZE];
for ( int idx=0; idx<=NoOfCoordinates ; idx++)
dArray[i] = i+0.1;
dArray[i] = i+0.2;
dArray[i] = i+0.3;
The above shows three very simple methods that enable us to use STL to provide support for 3D vectors - such as XYZ coordinates. However, the code looks horrible and is difficult to maintain. The most efficient of the above is the third method (storing as pointers to an array), but it comes at a price! In the 3rd example above, the
dArray is created as a static allocation. If you need dynamic allocation, you have to manage the allocation/destruction of your coordinate array dynamically. In addition you have to be careful of referential integrity.
If you use a linked list instead of an array to store your coordinates, then there is quite a high probability that you will hit the referential integrity problem. Consider if you have implemented your coordinate array as a linked list, then sort the list, the
vector<> which you previously created may not point to the correct sequence of your link list elements. Another potential source of problem is when you delete the elements from the array and forget to delete the
vector<> pointer. You have to perform messy manual synchronization between the linked list and the
Of course you can create a
Class to provide support for 3D vectors, but then you will need quite a number of overloaded functions to cater for a mix of variable types if you want it to be generic and re-usable. Again this is not an attractive option although feasible. So templates are the way to go.
For a long time I have been using MS
CArray and CList Classes and they are not well documented and this is my chance of jumping out! Writing a new
Class from scratch will take too much time not to mention of portability issues. Thus I decided to write a 3D vector/array support for STL.
There are many variants of STL. Microsoft's STL does not supports multi-dimension arrays natively and so too STLPort. I believe that Boost's version 5.20 supports multi-dimension arrays (maybe even earlier version, but this is the first time I am looking at STL - I am still a beginner in STL!). Boost supports multi-dimension arrays - in this case 3 dimensions. However, Boost lacks the certain features that STLPort possess. All I needed was some quick and simple code. So "
triplet<>" template was born!
I shall not go into the details of the
triplet<> template code itself in this article, rather I shall illustrate the use of the template instead. The template code is provided in the above download link so you can peruse it at your own leisure.
The triplet<> Template
I am using Microsoft Visual Studio 2008 (MS) so there may be references specific to this tool. I am not familiar with Linux nor GCC so I shall not discuss them. But suffice to say the
triplet<> template should work with any STLPort v5.2.0 environment. There are two versions of
triplet<> - one for MS and one for STLPort. If there is time I may release a version suitable for BOOST at a later date (but may defeat the purpose of Boost's n-dimensional templates). The template code is different for the MS STL and STLPort, but the usage is the same:
- Include the
- Declare your vector eg
vector< triplet<int,int,int> > myIntVector;
- Enter values into vector via
Thats it! There are only 2 functions to remember -
make_triplet<>. The rest of the
vector<> functionality is provided by the base class itself and supporting routines like sort are provided for by the standard library.
#include <span class="code-keyword"><map></span>
#include <span class="code-keyword"><vector></span>
#include <span class="code-keyword"><iostream></span>
#include <span class="code-string">"triplet" // This is the triplet template</span>
using namespace std;
vector<triplet>< triplet<double,double,double> > Vector3d;
cout << "Generating vectors using triplet<>:" << endl;
double x = 1.1;
double y = 1.2;
double z = 1.3;
int NoOfCoords = 5;
for ( int id=0; id<NoOfCoords; id++)
cout << "\tVector[" << id << "]"
<< "\tx=" << x
<< "\ty=" << y
<< "\tz=" << z
Vector3d.push_back ( make_triplet(x, y, z) );
x += 1;
y += 1;
z += 1;
cout << "Retrieving data via operator :" << endl;
for ( idx=0; idx<NoOfCoords; idx++)
cout << "\tVector[" << idx << "]"
<< "\tx=" << Vector3d[idx].first
<< "\ty=" << Vector3d[idx].second
<< "\tz=" << Vector3d[idx].third
cout << endl;
cout << "Retrieving data via iterator:" << endl;
vector<triplet>< triplet<double,double,double> >::iterator Vector3d_Iter;
Vector3d_Iter = Vector3d.begin();
int idx = 0;
while ( Vector3d_Iter != Vector3d.end() )
cout << "\tVector[" << idx << "]"
<< "\tx=" << Vector3d_Iter->first
<< "\ty=" << Vector3d_Iter->second
<< "\tz=" << Vector3d_Iter->third
cout << endl;
The above code snippet shows usage of 3D vector of type
double. It is much cleaner. The use of
first, second and
third to reference X,Y,Z makes the program more readable.
In essence you can also use it for
int, bytes, words, long int, bools and
chars. The only type it does not yet support is
strings. It will certainly be nice to do things like:
vector< triplet<double,double,string> > Vector3d;
Vector3d.push_back ( make_triplet (X,Y, "Front of house") );
Vector3d.push_back ( make_triplet (X,Y, "Archeological treasure!") );
Vector3d.push_back ( make_triplet (X,Y, "End of road") );
I shall look into this again when I have some time.
The next step is to add support for GPS trackpoints (latitude, longitude, height and time) for GPS tracking. This is easy to do as you can enhance the
triplet<> template to create your own
quad<> template. I shall release this in future if there is demand for it.
In a test of 50,000 loops of 10,000 vector allocations and retrievals (done separately), the results are as follows:
* All above timings are in seconds (resolution is 1 second). Above tests were from an Athlon XP 2400 cpu.
The sample code includes a routine to perform the timing test above. In MS STL implementation, there is a substantial performance penalty to be paid for using the
triplet<> code! But this is not so in the STLPort's implementation of
triplet<>. The timings are almost identical whether you use
At this moment,
triplet<> is still new to myself and I have not had the time to benchmark some real world applications as yet. I would certainly appreciate if anyone who use the
triplet<>template post some real-world timing data.
I have created lots of linked lists and vector based code through a few years of programming. Not only were they non-portable, they were also tightly optimized into the application. Until recently when I came across some STL articles, read it and realize that STL is an extremely useful tool. I thought that its about time I made my code more portable and thus reducing the maintenance burden.
Although STL is useful, there were a few features that I really wanted but did not have. I needed support for 3D (x,y,z) and 4D (x,y,z,t) vectors which could only be created indirectly in STL - using either the
vector<> templates in conjunction with
pair<> template. The
pair<> template requires the creation of extra filler value (when the array dimension is odd) which I did not like. In addition, the code to retrieve the (x,y,z) values gets more convoluted as the dimension increases.
So, I thought why not create my very own 3D vector template? I then looked at the VS2008 STL map and vector templates code. Its frightening to look at template sources - especially for a beginner! Then I realize that what I really needed was a
triplet<> template and that would solve the problem.
Using the Code
Refer to "The
triplet<> template" above section for usage example.
Points of Interest
It was surprisingly easy to modify the
pair<> template to become a
triplet<> template. It would have taken me very much longer if I had to create a new
Class or just write code to perform link list operations. I think this is an avenue many developers seem to miss. Instead of writing new
Class, why not write supporting templates? I know there are some potential dangling and null pointers in my older code that I know have a very small probably being triggered - the
triplet<> will be a good replacement.
triplet<> template was derived from the
utility<> templates in VS2008 and STLPort. Required member template functions were extracted and enhanced to support 3D vectors. Additional code were written where required. The original
utility<> templates style and structure was maintained as far as possible in the
triplet<> template to allow easy maintenance and cross referencing.
Triplet<> is open source. You may use it wherever you wish. However, since this code was derived from MS and STLPort, you may have to consult them for commercial distribution. However, a note crediting me as the author of the
triplet<> template would be nice.
2008-12-22 - Ver 1.0
Adapted triplet<> from pair<> template found in the file "utility" from VS2008.
Adapted _pair.h file from STLPort v5.20
2008-12-24 - Ver 1.1
Fixed predicate functions
to return true only when strictly "less than" to satisfy MS requirements for strict weak ordering. This will
prevent MS from runtime abort.