So, if I'm given a set of points describing a curve, and the distance from each of them to a “main point" (not part of the curve)… how would you calculate the position of that “main point”?

I'd be thankful if anyone has ideas on how to approach this?

From your problem description it is nor relevant if the points form a curve. It seems only the points matter.
Also, if we have points and distances, there is only a guaranteed solution if it's just two points - actually two solutions, with the main point forming a triangle with the two given points which can be reflected over the line between the two points.

What do you try to do? Maybe an image would help.

Draw a circle with a radius of the distance around each point, if all circles intersect a common point that's your solution.

JoeJ said:

From your problem description it is nor relevant if the points form a curve. It seems only the points matter.

Yeah, it's probably true that having only the points could matter… but I was thinking that maybe having the curve defined in some parametric way could make it easier.

JoeJ said:
What do you try to do? Maybe an image would help.

Ok, so… suppose someone is playing an AR game walking with a virtual termometer in his cellphone, and he can ask for samples of the temperature at any given point… the further away from a point the colder it gets (so I can get a good idea of how far away he is from the heat-emmitting point)… 

now, the actual positon of the heat-emitting point is unknown (not only for the player, but for the app too), but based on the positions where the player has taken samples so far and their temperatures I want to make the AR app suggest where the emmiting spot could be…

Ok, so the first problem would be to get distance from heat, which seems difficult as it depends on average room temperature, heat of the source, and even duration of heat diffusion if temperature has not yet converged, or heat source is moving, etc.

Reminds me on the method to approximate distance over the surface of a mesh form given source vertices (geodesic distance). Here the source vertices diffuse energy over a known duration of time.
So, first problem is to diffuse heat correctly, which you don't have because you only measure the resulting temperature.
The second problem is to solve for distance. This works by first calculating the gradient of heat to get a direction towards the source, and then solve a linear system so all distances along those directions at all mesh vertices match up. It's a linear optimization problem.

Sounds useful for you, here's link to the paper: https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/

It also contains an approximate conversion of heat to distance, which can be used instead solving the second problem.
I did it like this:

geoDist[vI] = sqrt(-4 * diffusionDuration * log(v));

v = heat, diffusionDuration could be just a constant for you that works well in practice. But not sure.
The error was quite big in comparison to solving the linear system for me, but often result was good enough.

However, my personal first try would be to take 3 adjacent points from your curve, calculate gradient from the triangle they form, and take the average intersection of all the gradient directions.
I guess that's simple and works, depending on accuracy of measurements.

I'm not sure the above is correct, or situationally not correct:

If you triangulate a point location given 2 known points and their distances, then there are 2 possible answers. So multiple triangulation's will describe a set of results that don't correspond, and a set of results that are all close and therefore the better answer. Taking averages doesn't consider this, I would have thought you would discard the worst answer for each triangle and average the best. It also means using triangles further apart will be more reliable for estimating the better answer (as opposed to adjacent points).

A curve that is a straight line is the exception where you cant determine which point is correct. If you remember change because the point is moving or the curve is moving, then this becomes part of the location awareness algorithm and the straight line case is solvable. In this example, on the first set of values you would not know the answer, only after moving could you compare and estimate the best point.

TeaTreeTim said:
I'm not sure the above is correct, or situationally not correct: If you triangulate a point location given 2 known points and their distances, then there are 2 possible answers.

I mean to take 3 points from the curve to make a triangle, not 2 points plus the unknown source point.
If you have a piece wise linear function (like distance to a unknown point), sampled from 3 points, the direction of the gradient points towards the source and there is no uncertainty about two solutions.
But temperature does not diffuse linearly, so that's why making a approximate conversion from temperature to distance before calculating the gradient could improve results, i assume.

Here some example code i'm using to calculate gradient vector for all triangles of a mesh (Division by area seems not necessary if we only care about direction, also note there are multiple ways to calculate gradients from triangles AFAIK, but this worked for me):

static void TriangleGradientFromVertexMap (std::vector<vec> &amp;triangleGradient,
			const std::vector<float> &amp;vertexMap, // distance or temperature per vertex
			const LinkMesh &amp;mesh)
		{		
			triangleGradient.resize(mesh.mPolys.size());
			for (int pI=0; pI<mesh.mPolys.size(); pI++)
			{
				const LinkMesh::Poly &amp;poly = mesh.mPolys[pI];
				vec normal = mesh.mPolyNormals[pI];
				vec sum (0);
				for (int i=0; i<3; i++)
				{
					int vI = poly.vertexIndices[i];
					int evI0 = poly.vertexIndices[(i+1)%3];
					int evI1 = poly.vertexIndices[(i+2)%3];
					vec edge = mesh.mVertexPositions[evI1] - mesh.mVertexPositions[evI0];
					sum += normal.Cross(edge) * vertexMap[vI];
				}
				float area = mesh.mPolyArea[pI];
				vec gradient = sum / (2*area);
				triangleGradient[pI] = gradient;

				//RenderArrow (mesh.mPolyCenters[pI], gradient, 0.05f, 1,1,0);
			}
		}

I want to add taking 3 adjacent points from the curve might be a bad idea. Maybe taking sets of any 3 points where sampled temperature differs a lot would be better.

In 3D, using triangles of course gives gradient aligned to the plane of the triangle, So the ‘hight’ of source from that plane is unknown, which makes solution harder.

If the problem is 3D, i would insert the samples into a 3D voulme, set the samples as fixed boundary and solve for harmonic map to fill the whole volume with data. Then a gradient can be calculated at each cell of the volume which is not limited to planes of triangles.

…no idea how well any of this workes in practice, assuming differnces in temeprature are small and samples are noisy.

After thinking of it some more, i realize the source of error is the curve kind distribution of samples.

If you had a somewhat evenly distributed sparse set of samples around the source, you could make delauney triangulation of the samples, and then solving the second equation from linked paper would give a very accurate result.

Thanks JoeJ!

JoeJ said:
Ok, so the first problem would be to get distance from heat, which seems difficult as it depends on average room temperature, heat of the source, and even duration of heat diffusion if temperature has not yet converged, or heat source is moving, etc.

It's just a game, really… and the temperature measurements are fake, I'm just considering it to be inversely proportional to the distance at this point (though maybe at a later stage could be interesting to consider more complex stuff.. depending on how it goes).

JoeJ said:
If you have a piece wise linear function (like distance to a unknown point), sampled from 3 points, the direction of the gradient points towards the source and there is no uncertainty about two solutions.

Yeah… that makes sense, indeed… I'm going to give it a try.

JoeJ said:
If you had a somewhat evenly distributed sparse set of samples around the source, you could make delauney triangulation of the samples, and then solving the second equation from linked paper would give a very accurate result.

That would depend completely on how the player moves, so it would be hard to guarantee evenly distributed samples, but yeah, it could totally be an option.

Thanks!!