Calculate normals from vertices Assume you have a list of vertices and their connectivity information. (I.e you can find all the adjacent edges and faces to each vertex).

What is a good approach to calculate a normal from this information?

Currently I first tried naive averaging, i.e:

$\frac{\sum n_i}{N}$

Where $n_i$ are the face normals and $N$ is the total number of faces

And I also tried:

$\frac{\sum n_i * a_i}{A}$

Where $a_i$ are the respective areas of each face and $A$ is the sum of the areas of all adjacent faces.

The first gave me this:



The second gave me this:



What I want is:



That last image I obtained by setting the normal to be the vector from the origin to the vertex position, but this is only true for highly regular meshes like cubes and spheres, it doesn't hold generally. The data I am using to make this is just the default blender cube.

Increasing precision to doubles doesn't seem to affect the result. This is the wiremesh:



Obviously the issue occurs because the number of faces adjacent to a vertex isn't balanced, which skews the normals into certain directions, but I don;t know how to compensate for that
You are not too far off with your second averaging approach. The problem is, that the area is the wrong weighting factor for what you want to achieve. You want each of the 3 sides of the cube to contribute equally to the vertex normal, but you need to extract the information from the adjacent triangles. The area and the number of triangles are bad weighting factors since they vary with the number of triangles per side. But one thing stays always the same at each vertex: The angle between two edges at the side. So you just need to take the angle of each triangle connected to the vertex and use it as a weighting factor for its normalized face normal. The weighting factors will always sum up to 90°/$\frac{\pi}{2}$ per side of the cube. Look for example at the bottom left vertex at the front in the image you posted.

Your first approach fails because it yields:

$$N_v = \frac{2*N_l + 2 \cdot N_f + 1 \cdot N_b}{5}$$

where $N_l$ is the left, $N_f$ the front and $N_b$ the bottom side normal. Assume them to be normalized. The factors result from the triangle count at the vertex and their sum.

Your second approach fails because it yields: 

$$N_v = \frac{N_l + 0.5 \cdot N_f + 0.5 \cdot N_b}{2}$$

Here the factors result from the fact, that only the left face has all its triangles connected to the vertex. The bottom face connects only 1 of 2 and front face only 2 of 4 equally sized triangles to the vertex.

If you take the angles, you get:

$$N_v = \frac{2\cdot 45 \cdot N_l + 2 \cdot 45 \cdot N_f+ 90 \cdot N_b}{270}$$

Now each side contributes equally and independent of the number and size of triangles connected to the vertex.

EDIT:

I just realized, that the front face also contains only 2 triangles. The diagonal of the back face triangles irritated me. However, this will not affect the conclusion but the weigting factors change. For the fist approach you get:

$$N_v = \frac{2*N_l + 1 \cdot N_f + 1 \cdot N_b}{4}$$

The second remains unchanged and for the angles you get:

$$N_v = \frac{2\cdot 45 \cdot N_l + 90 \cdot N_f+ 90 \cdot N_b}{270}$$

which is still correct. What is interesting is that both your approaches give the same results for the shown cube, since a connection of the vertex to 2 triangles also means that the area weight is doubled. You can also see this if you compare both pictures.