0

I have a randomly selected point in the 3-dimensional space. Also, I have four random points and their distances to the randomly selected point. These distances are radii of these four points. All the coordinates are integer numbers.

It is known that there's only one point in which these four spheres intersect.

What algorithm can I use to find coordinates of this point?

To better understand what I mean, check out the picture below:

enter image description here

Spektre
  • 49,595
  • 11
  • 110
  • 380
Serhii Chernikov
  • 353
  • 2
  • 11
  • 1
    Gradient descent to minimize the sum of the squares of the distances by which they are outside of the spheres. – btilly Aug 19 '23 at 15:08
  • 1
    I have reread the first paragraph over and over, and I can only conclude that you have guessed the point you are looking for. So you have its coordinates. Can you clarify? – trincot Aug 19 '23 at 15:39
  • 2
    If however you have not yet guessed the point, and only have the other four points with their radii, then apply mathematics: the intersection of two different, intersecting spheres is a circle (or possibly a single point), the intersection of that circle with another sphere is a set of at most two points. Choose the point that is on the fourth sphere. This is hardly an *algorithm*, but mathematics. See [How can I find the intersection of four spheres?](https://math.stackexchange.com/questions/2363127/how-can-i-find-the-intersection-of-four-spheres) on math.stackexchange.com – trincot Aug 19 '23 at 15:42
  • @trincot thank you. Also, to clarify the misunderstanding in the first paragraph – by "guessed point" I mean a randomly selected point in the 3D space. I want to find coordinates of this point by four other points (we know their coordinates, radii and assume that there's only one point where the spheres they form intersect). By using the term "guessed point" I made a mistake in translation from my native language into English, sorry. – Serhii Chernikov Aug 19 '23 at 17:02
  • 1
    Can you give an example input and the desired output? Also, can you explain `gps` in tags? – Marat Aug 19 '23 at 23:09
  • @Marat I added "gps" to the "tags" section just because GPS is using similar concept when determining where a person is located on the map. I want to pass four random points in 3D space (let's say 100x100x100 in size) and their respective distances to the unknown point we want to find. These distances are basically radii of the spheres with centers in those 4 points. We assume that there's only one point in the space where all 4 spheres intersect and this point has coordinates with integer values. Basically, this point of intersection is our unknown point we are looking for. – Serhii Chernikov Aug 20 '23 at 04:44
  • @Marat I want to find coordinates of that point (coordinates of intersection of 4 spheres). Did I explain it better? – Serhii Chernikov Aug 20 '23 at 04:46
  • @SerhiiChernikov yep, it seems clear - but an example would still be appreciated to test the solution. Note also that there might be zero, two, or infinitely many solutions – Marat Aug 20 '23 at 05:10
  • 1
    @SerhiiChernikov GPS odes not provide distances but relative time difference so its a way more complicated/hard to obtain the position using [TDoA](https://stackoverflow.com/a/64637495/2521214). Your case is simple just solve the system of 4 equations: `(x-x0)^2 + (y-y0)^2 + (z-z0)^2 == r0^2` for each reference point `(xi,yi,zi)` and distance `ri` where `i = 0,1,2,3` ... You can try any math SW to compute the algebraic equation if you not enough skilled in math , or you can fit the result using any usable method (gradient descent, RANSAC, approximation search,,,,) all of which is pure math – Spektre Aug 20 '23 at 08:15
  • however if your distances are not exact then you have to handle the equation as inequalities converting to minimizing error problem. `|(x-x0)^2 + (y-y0)^2 + (z-z0)^2 - r0^2| -> 0` – Spektre Aug 20 '23 at 08:19
  • btw [triangulation] is something different too and does not fit your question as [GPS] I retagged your question.... – Spektre Aug 21 '23 at 06:29

0 Answers0