LEDA Guide: Associating Information with Geometric Objects

Algorithmic Solutions > LEDA > LEDA Guide > Geometry > Associate Information with Geometric Objects

Associating Information with Geometric Objects

Maps and Hashing Arrays

Points, lines, segments, rays, and circles have id-numbers and hence Hashing Arrays and Maps can be defined for them. Maps and Hashing Arrays associate information with representation objects, i.e., only identical objects share their information.

Example

The following example shows how to use a map to associate a "color" with two-dimensional points. We write POINT to make the program independent of the kernel used. Notice that r and p are identical. Therefore, r "inherits" the color of p.

#include <LEDA/geo/point.h>
#include <LEDA/geo/float_kernel_names.h>
#include <LEDA/core/map.h>

using namespace leda;

int main()
{ 
  map<POINT,int> color;

  POINT p(0,0); color[p]=0;
  POINT q(0,0); color[q]=1;
  POINT r=p;
  std::cout << color[p] << color[q] << color[r] << std::endl; 
  //outputs 010

  return 0;
}

Dictionaries and Dictionary Arrays

For points we can also use Dictionaries and Dictionary Arrays. For the other geometric objects this requires the definition of a compare function. In Dictionaries and Dictionary Arrays equal objects share the same information.

Example 1

We replace in the above example the map by a d_array. The points p and q are equal and hence the assignment to color[q] also changes the color of p.

#include <LEDA/geo/point.h>
#include <LEDA/geo/float_kernel_names.h>
#include <LEDA/core/d_array.h>

using namespace leda;

int main()
{ 
  d_array<POINT,int> color;

  POINT p(0,0); color[p]=0;
  POINT q(0,0); color[q]=1;
  POINT r=p;
  std::cout << color[p] << color[q] << color[r] << std::endl; 
  //outputs 111

  return 0;
}

Example 2

Dictionary Arrays are useful for removing multiple occurrences of equal objects. This program removes all but the first occurrence of every point from L. If a Map is used instead of a Dictionary Array this will not work.