data structure question (2D array pointers in a struct)

[uer166]

I have a goal of statically generating some large arrays of geographic coordinates with some minimal metadata (source is GeoJSON but it's irrelevant). I'm trying to figure out how to format my data, and want something resembling an array of structs, where each struct contains metadata, and a pointer to coordinates. Something like the following seems to work:

Code: [Select]

#include <stdint.h>
#include <stdio.h>

float coords1[3][2] =
{
{123.4f, 321.3f},
{65.21, 322.3f},
{01.2f, 21.0f},
};

float coords2[5][2] =
{
{132.2f, 3.3f},
{6.121, 32.3f},
{01.232f, 211.0f},
{0.2f, 0.3f},
{0.121, 0.3f},
};

/* Hundreds of coordinate arrays */

/* Section definition */
typedef struct
{
uint32_t id;
uint32_t coords_num;
float * coords_p;
} section;

/* Array of sections to be rendered */
section secs[2] = { {1, 3, &(coords1[0][0])},
{1, 5, &(coords2[0][0])}};

int main(void)
{
printf("sec2: %f, %f\n", secs[1].coords_p[0], secs[1].coords_p[1]);
}

What I do not like is the fact that the pointer in the struct loses the 2D array properties, and becomes a dumb pointer to a float array. I would like it to still be a 2D array instead (albeit incomplete, something of type float[][2]), since that would at least inform the compiler of the pointer math, and I can do something like coords_p[4][1] to access a coordinate, instead of doing pointer arithmetic. Ideally there would be static bounds checking also. I can't seem to figure out a way to do that in C however.

[zapta]

The requirements are not clear. For example,

1. Are the points (lat/lng) known at compile time or are the collected at runtime?
2. What happens at runtime, you get an event with some coordinates and need to count the number of events for this lat/lng point?
3. Do you need metadata just of the coordinates (e.g. lat/lng and count) or also of individual events (e.g. time of arrival)?
3. Considering that the coordinates are in floating point format, do you expect to get events with exact same coordinates or in the vicinity?

Clarifying the requirements will help you selecting on a good design.

[uer166]

Sure: all coordinates are known at compile time, they are a static database of a map. Nothing here should be dynamic.

At runtime, I am only drawing lines based on these coordinates on the device to make a map on 240x400 monochrome LCD.

[hans]

What about making a coordinate struct with 2 floats, and then initialize an array of them?
That would solve the problems of mapping a const 2D array to 2D pointer type-mess.

Code: [Select]

#include <stdint.h>
#include <stdio.h>

typedef struct {
    float lat;
    float lon;
} coord_t;

const coord_t coords1[3] =
{
{123.4f, 321.3f},
{65.21, 322.3f},
{01.2f, 21.0f},
};

const coord_t coords2[5] =
{
{132.2f, 3.3f},
{6.121, 32.3f},
{01.232f, 211.0f},
{0.2f, 0.3f},
{0.121, 0.3f},
};

/* Hundreds of coordinate arrays */

/* Section definition */
typedef struct
{
uint32_t id;
uint32_t coords_num;
const coord_t * coords_p;
} section;

/* Array of sections to be rendered */
section secs[2] = {
    {1, 3, coords1},
    {1, 5, coords2}
};

int main(int argc, char** argv)
{
printf("sec2: %f, %f\n", secs[1].coords_p[0].lat, secs[1].coords_p[0].lon);
}

[AVI-crak]

It is a familiar topic, and the solution is very simple.
Floating-point numbers have a huge range, but in real tasks a small part of the range of values is used. If you set aside a few rare numbers for markup and commands, there will be no victims.
Oh yes, the time of direct comparison on equality for floating point. Just don't show the code to outsiders, they will throw poop on it.

[uer166]

What about making a coordinate struct with 2 floats, and then initialize an array of them?
That would solve the problems of mapping a const 2D array to 2D pointer type-mess.

Code: [Select]

#include <stdint.h>
#include <stdio.h>

typedef struct {
    float lat;
    float lon;
} coord_t;

const coord_t coords1[3] =
{
{123.4f, 321.3f},
{65.21, 322.3f},
{01.2f, 21.0f},
};

const coord_t coords2[5] =
{
{132.2f, 3.3f},
{6.121, 32.3f},
{01.232f, 211.0f},
{0.2f, 0.3f},
{0.121, 0.3f},
};

/* Hundreds of coordinate arrays */

/* Section definition */
typedef struct
{
uint32_t id;
uint32_t coords_num;
const coord_t * coords_p;
} section;

/* Array of sections to be rendered */
section secs[2] = {
    {1, 3, coords1},
    {1, 5, coords2}
};

int main(int argc, char** argv)
{
printf("sec2: %f, %f\n", secs[1].coords_p[0].lat, secs[1].coords_p[0].lon);
}

I like quite this, thank you.

@AVI-crack: I have no issues with the float quantization here, it is quite handy (I have FPU), and the effective accuracy from single precision latitude/longitude is plenty good at my latitudes.

[Sacodepatatas]

I have a goal of statically generating some large arrays of geographic coordinates with some minimal metadata (source is GeoJSON but it's irrelevant). I'm trying to figure out how to format my data, and want something resembling an array of structs, where each struct contains metadata, and a pointer to coordinates. Something like the following seems to work:

Code: [Select]

#include <stdint.h>
#include <stdio.h>

float coords1[3][2] =
{
{123.4f, 321.3f},
{65.21, 322.3f},
{01.2f, 21.0f},
};

float coords2[5][2] =
{
{132.2f, 3.3f},
{6.121, 32.3f},
{01.232f, 211.0f},
{0.2f, 0.3f},
{0.121, 0.3f},
};

/* Hundreds of coordinate arrays */

/* Section definition */
typedef struct
{
uint32_t id;
uint32_t coords_num;
float * coords_p;
} section;

/* Array of sections to be rendered */
section secs[2] = { {1, 3, &(coords1[0][0])},
{1, 5, &(coords2[0][0])}};

int main(void)
{
printf("sec2: %f, %f\n", secs[1].coords_p[0], secs[1].coords_p[1]);
}

What I do not like is the fact that the pointer in the struct loses the 2D array properties, and becomes a dumb pointer to a float array. I would like it to still be a 2D array instead (albeit incomplete, something of type float[][2]), since that would at least inform the compiler of the pointer math, and I can do something like coords_p[4][1] to access a coordinate, instead of doing pointer arithmetic. Ideally there would be static bounds checking also. I can't seem to figure out a way to do that in C however.

Try defining type of coord_p as a pointer to an array of floats...

Code: [Select]

#include <stdint.h>
#include <stdio.h>

float coords1[3][2] =
{
{123.4f, 321.3f},
{65.21, 322.3f},
{01.2f, 21.0f},
};

float coords2[5][2] =
{
{132.2f, 3.3f},
{6.121, 32.3f},
{01.232f, 211.0f},
{0.2f, 0.3f},
{0.121, 0.3f},
};

/* Hundreds of coordinate arrays */

/* Section definition */
typedef struct
{
uint32_t id;
uint32_t coords_num;
float (*coords_p)[2];
} section;

/* Array of sections to be rendered */
section secs[2] = { {1, 3, coords1},
{1, 5, coords2}};

int main(void)
{
printf("sec2: %f, %f\n", secs[1].coords_p[1][0], secs[1].coords_p[1][1]);
}



[zapta]

A few suggestions:

1. Have the const coordinate array as an array of lat/lng.
2. Represents lat/lng as 32 bit fix point (integers). This will give you all the accuracy you need.  Google for example use a grid to represent any point on their maps.  https://s2geometry.io/devguide/s2cell_hierarchy.  You can for example a bucket for every 180 deg / 2^31 range. This will avoid the nastiness of floating points and will make your program easier to work with.

struct Point {
  int32_t lat;
  int32_t lng;
};

const Point array_of_points = {
   {.lat=???, .lng=???},
   ...
}

3. As for the other array, I am not clear what you want to capture. If it's a list of coordinates as they are arrive at runtime, you can have an array of max size of events you expect and refer to the coordinates by their index in the const array.

struct Event {
  uint16_t coordinate_index;
}

Event event_array[1000] = {}

uint16_t num_of_events_so_far = 0;  // Increment with each event.

4. If you also want to count the number of events with each coordinate, add another array, of the exact same size of the coordinate array and have in each cell a counter for that coordinate.

uint16_t coordinate_count[size_of_coordinate_array]

Hope it helps.

[uer166]

https://s2geometry.io/devguide/s2cell_hierarchy.

This is cool, but man it's an insane amount of over-engineering for my purposes, and to be honest I don't quite understand the larger purpose of that system. As I mentioned I need to render some collection of coordinate sections/lines onto a flat screen. A simple projection defined by a pixels per degree of lat/lon scale works great for that in 4 lines of code. The larger the projected area, the more error there will be around periphery, but for a few miles it's negligible.

The reason for the array of pointers is to have a top-level handle containing all the coordinate sections to iterate upon and filter layers based on the metadata.

[zapta]

This is cool, but man it's an insane amount of over-engineering for my purposes

The point was that you can represent every point or lat/lng using ints (fixed point) rather than floating points.