mark-p-thomas : Polyline Data Structure

Sections

Premise

Polylines are commonly represented as an array of coordinates, used as vertices, with ordering inferring connectivity and segments. While this is an efficient way to store fundamental properties for data transfer, it has shortcomings:

1. There is no location for derived vertex properties or any attributed properties.

2. There is no location for derived segment properties or any attributed properties.

3. Insertions, deletions, etc. have O(n) time complexity. In CAD, GIS & other modeling software, polylines may undergo many modifications on a large set of n vertices & segments..

4. Users cannot traverse segments.

5. Accessing vertices of segments or segments of vertices requires further code development and adds complexity.

Clearly, for any use beyond the literal coordinates passed & their ordering, additional programming is needed & the size and complexity of the additional code written increases quickly. This indicates that when such needs arise, a custom data structure should be created, rather than loosely organized properties referenced to the coordinate vertices in the original storage array.

Proposal

After some consideration, I realized that a cross-linked double-linked list could work great.

Above shows a polyline translation to a cross-linked double-linked list. Below is a more detailed diagram showing the resulting data structure.

The data structure has the following form:

1. Vertices are represented by one double-linked list. Additional properties can be stored on extended objects that are referenced by the node value property. This allows easy & infinite extension.

2. Segments are represented by another linked-list. Properties can be stored on extended objects that are referenced by the node value property for easy & infinite extension.

3. The two linked lists reference each other. That is, each segment as a previous vertex & next vertex, while each vertex potentially has a previous segment or next segment.

Result

Although this adds complexity, especially in modification cases, once the behavior is adequately programmed & validated, it is a very easy & efficient data structure to work with, with the following benefits.

This new structure has the following benefits:

1. O(1) time complexity for any modifications.

2. O(1) time complexity is possible for accessing elements at a space cost of a paired hash map with a unique key & a value referencing a vertex node. This can often be useful. A few examples:

   1. For CAD & BIM software, the coordinates should be locally unique & therefore serve as keys. Additionally, it may not be necessary to store all vertices in the hash map, but just ones at useful reference points, such as intersections or a cached set of recently accessed vertices (assuming in editing that these are closer to additional editing operations in the near future).

   2. For GIS when working with GPS Tracks, the recorded timestamps associated with lat/long coordinates are locally unique. Timestamps/duration are often a simpler & easier way in which to conceptualize & execute operations rather than coordinates.

3. It is easy to traverse just the vertices, just the segments, or iterate between vertices & segments for higher order calculations, such as speed, acceleration, curvature, moment forces (in beams), etc.

Above is a class diagram of the polyline data structure & its inheritance tree.

Deep Dive

The following pages discuss more in depth the development & behavior of this data structure.

• Polyline Modifications - Discusses in depth the different ways a polyline may be modified.

• Polyline Property Updates - Updating properties for vertices & segments is a cross-cutting concern dealt with here.

• Polyline Stats - Describes how data along the overall polyline or any subsection can be calculated in the data structure & any extended classes.