Can LV solve these three simultaneous quadratic equations?

[george seifert]

I have three simultaneous quadratic equations that I need to solve.

(x-x1)^2 + (y-y1)^2 - (r-r1)^2=0

(x-x2)^2 + (y-y2)^2 - (r-r2)^2=0

(x-x3)^2 + (y-y3)^2 - (r-r3)^2=0

x1, x2, x3, y1, y2, y3, r1, r2 and r3 are known. I need to solve for x, y and r.

I've expanded them by hand and tried to solve the whole mess that way, but my answers aren't making any sense. It's such a long, drawn out process that I'm sure I made several mistakes that I'm not catching. It's been far too many years since I've done math like this and I can't remember all the tricks. Can LV matrix operations be used somehow? There's a Solve Linear Equations VI, but I don't see how to apply it to this situation. Any hints would be greatly appreciated.

George

[Justin Goeres]

QUOTE(george seifert @ Mar 7 2008, 08:24 AM)

It's been far too many years since I've done math like this and I can't remember all the tricks. Can LV matrix operations be used somehow? There's a Solve Linear Equations VI, but I don't see how to apply it to this situation. Any hints would be greatly appreciated.

I'm in the same boat. If I had a nickel for everything I've forgotten, I could pay people to remember things for me. There might be some magic in a MathScript node that you could bring to bear on it?

Meanwhile, I worked it out by hand and it doesn't seem terribly complicated. Since x1, x2, x3, etc., are all known, those terms collapse into a constant in each equation. From there you can write a matrix equation and it all falls out pretty easily. Obviously you could do the last part with LabVIEW's matrix tools, but the gymnastics of expanding the original equation are something you might have to help LabVIEW with?

VB VISA.zip

EDIT: On second thought, now that I've written all that out I'm not convinced that the system is fully determined. If x^2+y^2-r^2 equals c1, c2, AND c3, doesn't it follow that c1==c2==c3? But if at least two of c1, c2, c3 are equal to each other, then your system isn't determined.

[george seifert]

QUOTE(Justin Goeres @ Mar 7 2008, 11:17 AM)

EDIT: your system is undetermined. Apparently the little online matrix inverter I had bookmarked happily inverts even singular matrices :headbang: and I wasn't paying enough attention to recall that a matrix where any row or column is a linear combination of the other rows or columns is singular (even though it's blindingly obvious in this case). Oops! I fixed my equations screenshot accordingly .

I'm still kind of lost. After your edit you make it sound like it can't be done. I know there's a solution since it's a well known problem (http://mathworld.wolfram.com/ApolloniusProblem.html). I'll have to chew on your answer for awhile and see if any of the math comes back to me.

George

[Justin Goeres]

QUOTE(george seifert @ Mar 7 2008, 10:59 AM)

I'm still kind of lost. After your edit you make it sound like it can't be done. I know there's a solution since it's a well known problem (http://mathworld.wolfram.com/ApolloniusProblem.html). I'll have to chew on your answer for awhile and see if any of the math comes back to me.

Oh, CRAP. I expanded the terms wrong.

Every term in the expansion where I had, for instance, 2*x1, it should've been 2*x*x1. Sheesh. That makes everything else I did wrong, so I just removed all the content . If you really want the screenshot I posted, PM me and I'll send it to you. All it's really good for is admiring the pretty formatting of poor math .

[TobyD]

QUOTE(george seifert @ Mar 7 2008, 09:59 AM)

I'm still kind of lost. After your edit you make it sound like it can't be done. I know there's a solution since it's a well known problem (http://mathworld.wolfram.com/ApolloniusProblem.html). I'll have to chew on your answer for awhile and see if any of the math comes back to me.

George

Hi George,

In http://forums.lavag.org/index.php?showtopic=10261&view=findpost&p=42378' target="_blank">your original post you wanted to find the smallest circle that fully encompassed a mass. Now you are trying to solve apollonius. Although similar, an apollonius solution will not necesarily be the smallest circle to encompass your mass. Apollonius requires that the new circle is tangent to all 3 of the other circles, whereas a solution to your original problem only has to be tangent to the "mass" at one point (it may be tangent at many points).

Which of these are you actually trying to solve? Or is it both? Either way it's an interesting problem. I thought I had it figured out but the results aren't coming out quite right. I'm sure I messed up the math somewhere - there's a lot to keep track of when you're manipulating those equations.

Toby

[Francois Normandin]

Hi Georges,

Eight solutions. Here are solutions for the four (x,y) couples. Then resolve r for ± signs in the original equation: (x-x1)^2 + (y-y1)^2 - (r±r1)^2=0 to get the other four solutions.

x1 = [2(y1-y3)(x1^2+y1^2-r1^2) - 2(y1-y2)(x3^2+y3^2-r3^2) - 4(y1-y3)(r1-r2)r + 4(y1-y2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

y1 = [-2(x1-x3)(x1^2+y1^2-r1^2) + 2(x1-x2)(x3^2+y3^2-r3^2) + 4(x1-x3)(r1-r2)r - 4(x1-x2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

x2 = [2(y1-y3)(x1^2+y1^2-r1^2) - 2(y1-y2)(x3^2+y3^2-r3^2) - 4(y1-y3)(r1-r2)r + 4(y1-y2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

y2 = [-2(x1-x3)(x1^2+y1^2-r1^2) + 2(x1-x2)(x3^2+y3^2-r3^2) - 4(x1-x3)(r1-r2)r + 4(x1-x2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

x3 = [2(y1-y3)(x1^2+y1^2-r1^2) - 2(y1-y2)(x3^2+y3^2-r3^2) + 4(y1-y3)(r1-r2)r - 4(y1-y2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

y3 = [-2(x1-x3)(x1^2+y1^2-r1^2) + 2(x1-x2)(x3^2+y3^2-r3^2) + 4(x1-x3)(r1-r2)r - 4(x1-x2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

x4 = [2(y1-y3)(x1^2+y1^2-r1^2) - 2(y1-y2)(x3^2+y3^2-r3^2) + 4(y1-y3)(r1-r2)r - 4(y1-y2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

y4 = [-2(x1-x3)(x1^2+y1^2-r1^2) + 2(x1-x2)(x3^2+y3^2-r3^2) - 4(x1-x3)(r1-r2)r + 4(x1-x2)(r1-r3)r ] / [ 4(x1-x2)(y1-y3) - 4(x1-x3)(y1-y2) ]

[george seifert]

QUOTE(TobyD @ Mar 7 2008, 01:47 PM)

Hi George,

In http://forums.lavag.org/index.php?showtopic=10261&view=findpost&p=42378' target="_blank">your original post you wanted to find the smallest circle that fully encompassed a mass. Now you are trying to solve apollonius. Although similar, an apollonius solution will not necesarily be the smallest circle to encompass your mass. Apollonius requires that the new circle is tangent to all 3 of the other circles, whereas a solution to your original problem only has to be tangent to the "mass" at one point (it may be tangent at many points).

Which of these are you actually trying to solve? Or is it both?

Toby

That's an excellent question. I thought they were the same problem, but now that you made me think about it, Apolllonius' problem might not always apply in my case. The smallest circle may not always touch all three of the inner circles. Wow, it sure helps to have a few extra heads involved - and ones with better brains than mine. So it looks like I'm back to my original solution (Use IMAQ Find Circular Edge VI to define the encompasing circle. If the fit isn't prefect, subtract the mass from the circle found to give the area that's not covered and slowly increment the radius of the encompasing circle until the area is 0.) I tried the IMAQ Centroid VI, but that didn't come out anywhere close.

Thanks for help. I'd still like to find a mathematical solution if one exists.

George

[Matt W]

QUOTE(george seifert @ Mar 10 2008, 04:42 AM)

That's an excellent question. I thought they were the same problem, but now that you made me think about it, Apolllonius' problem might not always apply in my case. The smallest circle may not always touch all three of the inner circles. Wow, it sure helps to have a few extra heads involved - and ones with better brains than mine. So it looks like I'm back to my original solution (Use IMAQ Find Circular Edge VI to define the encompasing circle. If the fit isn't prefect, subtract the mass from the circle found to give the area that's not covered and slowly increment the radius of the encompasing circle until the area is 0.) I tried the IMAQ Centroid VI, but that didn't come out anywhere close.

Thanks for help. I'd still like to find a mathematical solution if one exists.

George

[edit]Never mind this doesn't work[/edit]

I really surprised noone else has figured this out.

See attached for a VI that should solve your original miniimum radius problem.

Matt W

[george seifert]

QUOTE (MATTW @ Mar 10 2008, 08:06 PM)

[edit]Never mind this doesn't work[/edit]

I really surprised noone else has figured this out.

See attached for a VI that should solve your original miniimum radius problem.

Matt W

There's an edit saying it doesn't work. I checked it out with some of my data and it looks pretty good to me. Why do you think it doesn't work?

George

[Matt W]

The generated encompassing circle can be too big when three (or more) of the sub circles touch the edge of the true minimum circle, the one I posted will work with all cases when only two or one sub circles touch the true minimum circle. So while it'll always generate an encompassing circle in many cases it may not generate the minimum encompassing circle.

Matt W

QUOTE (george seifert @ Mar 11 2008, 07:46 AM)

There's an edit saying it doesn't work. I checked it out with some of my data and it looks pretty good to me. Why do you think it doesn't work?

George

[TobyD]

QUOTE (george seifert @ Mar 10 2008, 04:42 AM)

That's an excellent question. I thought they were the same problem, but now that you made me think about it, Apolllonius' problem might not always apply in my case. The smallest circle may not always touch all three of the inner circles. Wow, it sure helps to have a few extra heads involved - and ones with better brains than mine. So it looks like I'm back to my original solution (Use IMAQ Find Circular Edge VI to define the encompasing circle. If the fit isn't prefect, subtract the mass from the circle found to give the area that's not covered and slowly increment the radius of the encompasing circle until the area is 0.) I tried the IMAQ Centroid VI, but that didn't come out anywhere close.

Thanks for help. I'd still like to find a mathematical solution if one exists.

George

I found this website - I think it might have what you want if you have the time to parse through it...

http://www.inf.ethz.ch/personal/gaertner/miniball.html

You can feed this guys algorithm a series of points and it will generate the minimum encompassing circle. If you compiled his code into a dll you could call it directly from LabVIEW. To find the points use the edge detection functions at multiple points around your odject. The more points you put in the more precise your result will be.