Mathematics desk
< April 25	<< Mar \| April \| May >>	April 27 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 26

Determining location of an arbitrary number of points in space

This is a real-world problem I'm trying to solve, but my math skills aren't up to it any more. Suggestions, descriptions and formulas greatly appreciated!

Assume a large room with an arbitrary number of speakers {S1..Sn} at various locations. There are >= 3 speakers. Assume I move to arbitrary >= 3 points {P1..Pn} in the room and from each point measure the distance to all of the speakers.

I do not know where in space the speakers are except in terms of linear distance from my selected measuring points. I do not know where my measuring points are in relationship to each other, except that they are within the space and they are all different points. We can assume that the points have been chosen "reasonably".

At the completion of my measurements I have a set of distances from P1 to {S1..Sn}, a set of measurements from P2 to {S1..Sn}, and so on for {P1..Pn}.

Given the above information, and only the above information, it is desired to construct the actual 3D locations of the speakers and the measuring points in space, ideally in a rectangular coordinate system.

Is there a way to do this, or a reasonable real world approximation to the locations? Loren.wilton (talk) 06:51, 26 April 2008 (UTC)[reply]

I'm not sure how helpful this is, but it might be a start at least. Pick any measuring point

P_{i}

and any two speaker positions

S_{j}

and

S_{k}

. Call

a

the distance

{\overline {P_{i}S_{j}}}

, call

b

the distance

{\overline {P_{i}S_{k}}}

, and call

c

the distance

{\overline {S_{j}S_{k}}}

. From the law of cosines:

c^{2}=a^{2}+b^{2}-2ab\cos \theta \geq a^{2}+b^{2}-2ab=(b-a)^{2}

c\geq |b-a|

{\overline {S_{j}S_{k}}}\geq \left|{\overline {P_{i}S_{k}}}-{\overline {P_{i}S_{j}}}\right|

and since i, j, and k were chosen arbitrarily:

{\overline {S_{j}S_{k}}}\geq \max(|{\overline {P_{i}S_{k}}}-{\overline {P_{i}S_{j}}}|)

Hope that helps at least a tiny bit. --Prestidigitator (talk) 09:07, 26 April 2008 (UTC)[reply]

Thanks! The first part of that I had worked out myself, albeit in a slightly different form. But I'm left with c >= |a-b| (in terms of side lengths on the triangle), and I'm unsure how to convert that into a reliable length. If I have a second triangle from p2 to Sj and Sk and c(p2) > c(p1) I think that I now have an actual length for c. If however c(p2) = c(p1) I'm not sure that I know the length of c.

If c(p2) != c(p1) I think that the longer length will be the true length, although again I'm not absolutely convinced of that. I now know two triangles with one shared leg, but there are still many possible placements of the 4 points in 3-space.

Perhaps I can continue constructing trangles with shared legs to develop the speaker constallation, but I don't feel completely comfortable with that; I keep thinking I'm missing something. Loren.wilton (talk) 09:53, 26 April 2008 (UTC)[reply]

I think that the best that you can hope for is knowledge of the relative positions of the measuring points and the speakers in 3D space, in that if all were given the same arbitrary displacement, your experience would be the same. If however the measuring points have been chosen sufficiently "reasonably", and in sufficient numbers, their mean position may possibly be assumably at the centre of the (presumed rectanguloid) room. Everything would be easier, of course, if the dimensions of the room are known, and even more so if the speakers are known to be on a room boundary.

Returning to the above analysis, can it be assumed that the measured distances are exact? If not, you'll have something analogous to the surveying problem of closure when distances and angles are subject to errors, e.g. http://fountainware.com/compass/closure.htm

—217.43.210.83 (talk) 12:39, 26 April 2008 (UTC)[reply]

Any 3D rotation of the positions of both speakers and measuring points will give you the same measured distances from each measuring point. So if you know nothing about the positions of the measuring points the best you can do is determine a relative configuration of the speakers modulo a 3D rotation. Gandalf61 (talk) 14:09, 26 April 2008 (UTC)[reply]

Same applies to reflections, too. --Tango (talk) 14:13, 26 April 2008 (UTC)[reply]

And for small translations keeping the points inside the room (in general for any isometry).--Pokipsy76 (talk) 14:18, 26 April 2008 (UTC)[reply]

Translations were what 217 was talking about. --Tango (talk) 15:37, 26 April 2008 (UTC)[reply]

I'm surprised no one has counted degrees of freedom yet. With n speakers and k points you have nk + 6 constraints on 3(n + k) variables (the extra six constraints are to get rid of the translational and rotational symmetry). So you can't expect to solve for the speaker positions unless nk + 6 ≥ 3(n + k), or equivalently unless (n − 3) (k − 3) ≥ 3. In particular the problem is unsolvable when there are just three speakers/points, no matter how many points/speakers you have. -- BenRG (talk) 18:53, 26 April 2008 (UTC)[reply]

This sounds like trilateration to me. To find the 3-D coordinates of an unknown point, you need the coordinates of four measuring points, and the distances from those measuring points to the unknown point. Then you just find the intersection of the four spheres. --Bavi H (talk) 23:49, 26 April 2008 (UTC)[reply]

Oops, I see you said I do not know where my measuring points are in relationship to each other. --Bavi H (talk) 23:54, 26 April 2008 (UTC)[reply]

Yup. And that is the crux of the problem for me, or as you say it would be a simple intersection of multiple spheres. I keep thinking that it should still be about that simple and I'm just missing something, but I don't know what. Loren.wilton (talk) 01:01, 27 April 2008 (UTC)[reply]

Let me add some details:

The speakers in all probability will not be on the perimiter of the room, they may be larrgely in one half of the room, but even this is not guaranteed in all cases. Thus "arbitrary" is probably a good description of location.
The room being measured would typically be a theater or ampitheater, and can logically be divided into a "stage end" and a "house end" which contains the seating area. The "room" is more aptly a "space" as there may or may not be walls involved.
As a matter of convenience the measuring locations will typically be in the seating area, which will form a rough plane. It least one measurement point (but probably not a lot) can be arranged to be higher, and thus out of the plane.
Note that physics is involved here, so calculated positions that would be "underground" or otherwise unresonable can be discarded. This can be done by a human, as the math is unlikely to know top from bottom. It might be reasonable to assume that all speakers are on one side of the measurement plane and discard other solutions.
It has been mentioned that absolute location is impossible from a measurement point cluster without knowing the absolute locations of the points. True and irrelevent in this case. The object is to locate the speakers in relation to the measurement points, not to the world outside the speakers and measurement points.
Degrees of freedom: as many measurement points as necessary can be selected, although ideally this would be a minimal number. A realistic measurement is likely to involve at least six measurement points, but they are all likely to be approximately in a plane. (But note the reflected solution can be ignored.) I'm not sure I want to say that there are necessarily more than 3 speakers, though in most cases there would be.
Measurements are not absolutely accurate, so as in any surveying there will be circles of confusion and the like. In general it is expected the error will be small in relation to the distances measured. Of course this might result in fairly large errors in location if acute angles are involved. Hopefully things can generally be arranged to not be a problem.

Does this help define my problem and the desired (range of) solution(s)? This is in the end a real-world physics problem, so close approximations are certainly acceptable. But I'd like a good mathematical footing under the whole thing, and that is what I'm having problems coming up with. Loren.wilton (talk) 01:01, 27 April 2008 (UTC)[reply]

And the requirement that you not know the positions--or at least the relative positions--of the measuring points a definite one? What about the distances between the measuring points? --76.191.195.155 (talk) 04:36, 27 April 2008 (UTC)[reply]

It is an awkward number to provide, especially with any accuracy. I certainly agree that knowing the measurement points were in an equalateral triangle or a tetrahedron arrangement with known sides makes everything much simpler. Loren.wilton (talk) 04:40, 27 April 2008 (UTC)[reply]

But in a real-world situation you must be able to get some information about the relative positions of your measuring points. Even if you can't measure the distances between them directly, you could get sightlines between them, or sightlines to common points in the auditorium, and then use trigonometry to work out their distances and positions. Note that they don't have to be in any special configuration as long as you know where they are relative to one another. If you know the configuration of the measuring points, the problem of locating the speakers is very simple - it only takes distance measurements from just four known points (not all in the same plane) to determine the exact position of any speaker. If you don't gather this information about the configuration of the measurement points then you are making the problem much, much harder. Gandalf61 (talk) 07:46, 27 April 2008 (UTC)[reply]

It might be easiest, if you're pretty good with computers, to just toss a bunch of points in a box and shake them until you get what you want. This is called local search, and can get you as much precision as you like in reasonable time. If you want a geometric solution, I can't think of anything more elegant than just writing out simultaneous equations and grinding through them. This is made even less elegant by their form - most of them will have cosines and stuff floating around, screwing things up. But, given that, and that everything's in a plane, you can do it using nothing but the law of cosines, and the rule that all the angles in sequence around a point must add to 0 mod 2pi. Black Carrot (talk) 19:22, 28 April 2008 (UTC)[reply]

If the degree of freedom is high, a purely random search may take an unacceptably long time to get anywhere near the optimal configuration. The search can be sped up by using a trilateration procedure that takes (guessed) positions for four speakers as input – although you may be unlucky if these four are coplanar. Then you only need to do a local search on a 12-D space. --Lambiam 09:34, 2 May 2008 (UTC)[reply]

Differential equasion

If f'(x) = 1/f'(x) + C, what functions could f be? Thanks, *Max* (talk) 18:17, 26 April 2008 (UTC).[reply]

I suppose you wanted to write

f'(x)={\frac {1}{f(x)}}+C

the solutions can be found by separation of variables, and for C≠0 you have:

x-a=\int _{f(a)}^{f(x)}{\frac {y}{Cy+1}}dy=\left[{\frac {y}{C}}-{\frac {\log(1+Cy)}{C^{2}}}\right]_{f(a)}^{f(x)}

and then you should find the inverse function, which seems not to have a simple analitical expression...--Pokipsy76 (talk) 18:46, 26 April 2008 (UTC)[reply]

If, on the other hand, you really mean what you wrote,