Data model for meridians and parallels

Question

I'm thinking about some suitable model for storing meridians and parallles. Meridians and parallels should be kept as lines.

Possible models:

A) "Topologic" model Each point stores pointer to north, south, east and west points.

class Point
{
    private:
            double lat;
            double lon;
            Point *north;
            Point *south;
            Point *east;
            Point *west;
            ...
};

class Meridian
{
    private:
            double longitude;
            Point *start;
            Point  *end;
            unsigned int points_total;
};

class Parallel
{
    private:
            double latitude;
            Point *start;
            Point  *end;
            unsigned int points_total;
};

Pros:

• We can traverse each meridian in north-south direction and vice versa. We can traverse each parallel in east-west direction and vice versa.
• We determine whether each point is inside meridian or parallel (using pointers).
• Small storage requirements...

Cons:

• Only sequential access to every meridian/parallel point
• Problems with copy constructors and operator =. A copy of a set of points should be done in several phases: Create a new instance of points, adding topological relations between points using std::map, change the endpoints of the meridian/parallel... It is rather slow...

The second disadvantage has led me to abandon the model.

B) List of points. Meridian/parallel stores list of points, there are no topological relationship.

class Point
{
    private:
            double lat;
            double lon;
};

class Meridian
{
    private:
            double longitude;
            std::vector <Point> points;
};

class Parallel
{
    private:
            double latitude;
            std::vector <Point> points;
};

Pros:

• We can traverse each meridian in north-south direction and vice versa. We can traverse each parallel in east-west direction and vice versa.
• No problems with copy constructors and operator =
• Sequential and direct access to every point.

Cons:

• We can not determine whether each point belongs to any meridian/parallel (using pointers) or not.
• Larger storage requirements.
• At any point we are not able to find previous / next point of the meridian / parallel, we do not have pointers...

The last disadvantage could lead to the abandonment of a model and leads me to think about a modified variant of topological model....

I am performing some spatial simulations and representing results in several cartografic projections, so efficient data storage is very important for me.

Maybe someone could propose a better model :-). Thanks for your answers...

Answer 1

If you're storing meridians and parallels on the curved surface of the earth, you may be interested in looking at some of the data structures that are used in computational geometry to represent closed two-dimensional manifolds. Structures like the quad-edge or winged-edge are specifically designed to allow for fast lookup of the edges, points, or sectors close to a given edge, point, or sector in a way that can easily be updated by the addition or removal of new edges. I'm not sure how useful this will be in your particular application, but I think that they might be a good starting point. There are certainly good implementations of these structures online in C++, though I don't know of any off the top of my head.