next topic »

[Reply #45 on:]

Thanks you guys for all the input, i have been busy with another project the past few months and did not get allot of time to work on this, but yes, it is not an easy solution but i am will find a way to make it work...

Thank you for all the new ideas, i must say the approach from necromancer sounds like it would be the simplest way..

I will keep you up to date as i make progress, still struggling to get the Comparator part sorted out, i am stupid with the electronics, so i need to go by trial and error..

Marcel

[Reply #46 on:]

This is an interesting thread as I've been trying something similar. I think I will give Necromancers approach a try as it sounds pretty simple and sensible at first glance.
On the sensor side I might have something to contribute. I need to detect a "knock" on a 2d surface so I am using piezo contact mikes. I posted my schematic here
http://hotchk155.blogspot.com/2011/10/musical-ping-pong-tables-and.html

[Reply #47 on:]

I'm just now having to leave for work. I'll try and get back later in detail. Know, however, that this equation can be solved WITHOUT angles using Law of Cosines, which is straightforward algebra without recourse to esoteric functions.

I did it once using string pots, where I had only three string potentiometers giving distance only from three corners of a right angle to the point of intersection. This was done to record the 3D displacement of a car axle being exercised on a tramp test machine for the automotive industry so as to calculate the angle of oversteer.

I saved that info someplace. I'll try to find it for you, if you care to go that route.

[Reply #48 on:]

I've been looking at this some more, based on Necromancers iterative method (which I think might be quite slow in practice). I think I'm getting somewhere with a fast and dirty calculation to get the start point for the iteration, but it seems to show potential as a method by itself. I wanted to share the idea (and also see if anyone can suggest where to go with it  ) here http://hotchk155.blogspot.com/2011/11/lost-in-maths.html

[Reply #49 on:]

which I think might be quite slow in practice

Can you share the arguments for that thought? in short why?

What is the speed you want?

In my simulation to solve this problem I came to ~100 msec  (code see - http://arduino.cc/forum/index.php/topic,52583.msg379029.html#msg379029 - )

[Reply #50 on:]

@Rob,

You can speed up your simulator/trial/error approach by a factor of about 4.

say the  sound arrives in sequence abcd on mic's a,b,c and d.
then you know the point of origin is closer to a than to b, closer to b as to c, etc.
draw the line between a & b; find the point in the middle on the line and draw line 90deg perpendicular
to first line. you only need to search the points on a's side of that line.
same  for b-c and c-d (and a-d as well and maybe even for the diagonals a-c and d-b).
so it is quick to create a sector where to look. then in the sector use the simulation.

strangely, the more regular you position the mic's, the bigger the sector seems to get.
for a square arrangement, a-b and c-d are parallel and their perpendiculars are the same so you loose information.
therefore for a square of mic's you only have two perpendicular lines and 4 sectors (if you do not use the diagonals). 
It somehow seems to pay off to place the mic's in an irregular pattern

[Reply #51 on:]

@robtillaart - the reason for thinking the iterative method would be slow is that it would need a lot of calls to sqrt() as the intersection points of the circles are repeatedly recalculated...  Perhaps I'm worrying too much, but I can happily trade off some accuracy for speed in my application. Basically I want to react to an impact to produce a sound (via a MIDI synthesiser) without any perceivable delay, and I'd want to be ready to detect the next impact very soon after. The surface would be divided into a number of areas triggering different sounds (e.g. imagine someone playing drums by tapping fingers on a tabletop)

[Reply #52 on:]

@raalst

You can speed up your simulator/trial/error approach by a factor of about 4.

I know, you are right - in fact one can speed up even more

- assume a square with mic on the corners and M in the middle
   A  B
    M
   C  D

- the first mic (A) divides the area in two. All the points that are closer to A than to the others.
  That is the quadrant around A  == your optimization

The next mic to trigger is either B or C as these are closest to A. (only for the exact middle M this is not true)
The cases B and C are symmetrical / identical so I refer to B as the second one

- the second mic (B) divides the initial quadrant in the triangle  A-M- (mid-AB)

- the third mic will allways be C but that will not decrease the area as all points in the triangle are closer to C than to B
  except for the line M - (mid-AB) in which case C and D will trigger simultaneously.

- D will allways be last ...

So only after the first two signals coming in you can choose the right enclosing triangle meaning a factor 8 smaller area. However the algorithm would become more complex as iterating through a triangle is not as straightforward as a square. Furthermore as the simulation does a first iteration with big steps the gain will not be an extra factor 2. OK one can optimize the code so there will be a gain, but mostly at costs of complexity and I've learned throught the years that you don't need to optimize an algorithm for speed if it is fast enough.

Note that the simulation approach is in fact independant of the position of the microphones, only the distance function changes of course.

It somehow seems to pay off to place the mic's in an irregular pattern

This might be true and needs some thinking....

Thinking which positions would be hit most we will see a concentration of points in the middle (M) and points becoming less near the sides. points near the middle also mean that the arrival times or better said the difference in arrival times of the sound will be smaller (assuming corner mic's). And this leads to less precision in the math given the inaccuracy of the mic readings themselves. This leads me to the statement (not proofed) that the microphones should have different distances to the center of concentration of points to increase the precision. In theory you want a mic near the center but in practice it will not survive ....

I propose 3 micros on one side and one in the corner. Then there is no point causing the sound to arrive simultaneously.

[Reply #53 on:]

@hotchk155

the reason for thinking the iterative method would be slow is that it would need a lot of calls to sqrt() as the intersection points of the circles are repeatedly recalculated.

All the floating point math can slow down an algorithm, but there are several optimizations that could speed it up process. Not looked at that algorithm in detail
1) use an integer sqrt function, ==> less precise but might be precise enough until a certain level, 
    see picture - http://ww1.microchip.com/downloads/en/AppNotes/91040a.pdf  -
1) use an approx sqrt function, a lookup table with interpolation. see -http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

2) if you need to compare a distance A-B  with another distance  C-D you don't need the sqrt as one can compare the "squared" values

d1 = (Ax - Bx)^2 + (Ay - By)^2;
d2 = (Cx - Dx)^2 + (Cy - Dy)^2;

just test d1 > d2  iso sqrt(d1) > sqrt(d2) => same result, less math => faster,

just a few thought...

[Reply #54 on:]

I know this is a necro-post, but here I go anyway:

Basically this is the same problem as in sound ranging an artillery piece.

Sir William Lawrence Bragg, one of the grand men of crystallography, did his share of the math (ensuring that it is not a trivial problem!) during WW I.

http://en.wikipedia.org/wiki/Sound_ranging is absolutely worth reading.

And http://www.waterloolabs.com/#!episode-02/cgue is worth seeing.

[Reply #55 on:]

INteresting (and fun) material,

Thanks for posting!