1

Here is the problem, I have this equation system (as an example) that I need to solve and find x and y values:

(x-0)^2+(y-5)^2=12,25
(x-0)^2+(y-0)^2=2,25

Don't worry about 0'os, this changes according to detected point and this is just an example.

As I understand, I am not able to use Craner's rule here, so I am lost and I have no idea how to program this. It is simple to do it by hand, but how to write algorithm for this? Any tips?

Edit: here is a picture of how equations look like and how I solve them by hand: https://i.stack.imgur.com/gYsav.jpg (step by step solution: https://i.stack.imgur.com/Sa2bg.jpg) The process of solving it by hand is pretty simple: I have quadratic equation system. Then, I take the second equation and find what x is equal to in that equation. So, by doing this now I know what x is equal to. After this step I take that x value and put it in the first value. By doing so I make sure that first equation has only one missing variable. I solve it normally and get what y is equal to. Then, I put y value to the x value and I get my answer.

  • You need to provide your attempt at implementing the algorithm. – Binary Nerd May 17 '16 at 07:35
  • @BinaryNerd I am sorry, but I don't know where should I start. I have no idea how to tackle this, that is why I am asking for help. I googled and found Craner's rule. For minute I was happy until I realized that my equations are quadratic, so Craner's rule is not a solution. –  May 17 '16 at 07:36
  • 1
    [How to Solve Equations with java?](http://stackoverflow.com/q/1431885) – Tom May 17 '16 at 07:38
  • @Tom yes but once again, they are not talking about quadratic linear equations. –  May 17 '16 at 07:40
  • Above were LINEAR equations. These are quadratic. Anyway, solving above equation is easy: Subtract the second line from the first line, then (x-0)² cancels and you have (y-5)²-y² = 10 ==> y²-10y+25-y²=10 ==> -10y+25=10 ==> y = (10-25)/(-10) ==> y= 1.5 and thus x=0. Generally, the solution formula seems to be more complicated. (http://www.wolframalpha.com/input/?i=solve+%28x-a%29^2%2B%28y-b%29^2+%3D+c_1+and+%28x-d%29^2%2B%28y-d%29^2%3Dc_2+for+x,y) – Maximilian Gerhardt May 17 '16 at 07:40
  • @MaximilianGerhardt as I mentioned, you shouldn't look at the numbers, they will change according to detected points, so subtraction between two equations might not be an option at all. –  May 17 '16 at 07:43
  • You know how to solve by hand, what difficulty are you hitting trying to convert that approach into code? – weston May 17 '16 at 07:43
  • @weston - simple. There are two variables that I am looking for and both depend on each other. –  May 17 '16 at 07:44
  • What? So how do you solve it by hand, you said you knew how. – weston May 17 '16 at 07:45
  • Also if we shouldn't look at the numbers, specify the form of the equations, in terms of other variables e.g. `ax^2+by^2=c` ? – weston May 17 '16 at 07:45
  • @weston. Okay. Here is a picture of how equations and my method of solving them looks like: http://i.imgur.com/Gm29Cfw.jpg –  May 17 '16 at 07:52
  • That's like looking at a trace output of the algorithm to solve the equations. What are your thought processes behind the steps? As that's what needs to become software. How would you tell an alien how to solve the equations (no matter what the specific numbers are)? – weston May 17 '16 at 07:55
  • I'm voting to close this question as off-topic because it is simply a "write my code for me" task. The user has not even attempted to provide an algorithm in pseudocode. – weston May 17 '16 at 07:59
  • @weston sorry for not being clear enough. The process is pretty simple: I have quadratic equation system. Then, I take the second equation and find what x is equal to in that equation. So, by doing this now I know what x is equal to. After this step I take that x value and put it in the first value. By doing so I make sure that first equation has only one missing variable. I solve it normally and get what y is equal to. Then, I put y value to the x value and I get my answer. –  May 17 '16 at 07:59
  • @weston please, don't be so harsh. I am not asking anyone to write me code. I really am just trying to find out if there is easy solution for this because I really don't know how to write algorithm for this. No need to write code for me, just a few tips on that path would be amazing starting point. –  May 17 '16 at 08:01
  • You need to expand on the technique you use to solve them. Like I said, how would you give foolproof instructions to an alien to follow that would allow them to solve the equations? e.g. "I take the second equation and find what x is equal to in that equation" is not a suitable step. – weston May 17 '16 at 08:06
  • 1
    For a computer to be able to work on the systems, you need to generalize them. This is a case where it is easy for you as a human to think more broad and see intuitively what approach to take and how the two equations are related. As for the computer, it works strictly on simple logic that you need to provide. So you need to establish rules, that the computer may follow, that is general for any input case. These rules will be the basis of the algorithm. Start by finding the general form of any input equation, so as to tell the machine what rules will apply. Then you can add further rules. – Richard Tyregrim May 17 '16 at 08:09
  • Define language (operators, precedence etc), write a parser, add mathematical functions you want to evaluate, there you go... http://stackoverflow.com/a/26227947/150830 – ata May 17 '16 at 08:10
  • Could [Apache Commons Math](https://commons.apache.org/proper/commons-math/) be useful for you? – cassiomolin May 17 '16 at 08:10
  • @weston maybe this is more helpful: http://i.imgur.com/ZvraQoZ.jpg –  May 17 '16 at 08:14
  • No, because it's in Maths language, The alien (your computer) doesn't understand maths beyond add, subtract, multiply, divide, so it needs to be in those basic terms. – weston May 17 '16 at 08:17

1 Answers1

0

Okay, here is an idea, but I have yet to implement it and check if this actually works.

Mathematically, the two equations describe circles.

Let (a,b) be the center of the first circle and sqrt(r_1) its radius, and let (c,d) be the center of the second circle and sqrt(r_2) its radius. Then, in cartesian coordinates, the points on the circle fullfull respectivelly

(x - a)^2 + (y-b)^2 = r_1

or

(x - c)^2 + (y-d)^2 = r_2

We describe the circle now with two functions: The upper part and the lower part. These are functions involving square roots. So if we have

(x - a)^2 + (y-b)^2 = r_1

Then solving for y gives (via wolfram alpha)

(y-b)^2 = r_1 - (x-a)²

y = b + sqrt(-a²+2ax+r_1-x²)

or

y = b - sqrt(-a²+2ax+r_1-x²)

We can also express the lower and upper part of the other circle with these two equations by exchanging (a,b) with (c,d) and r_1 with r_2.

The point is, once we have two graphs with y_1 = f(x) and y_2 = g(x), then we can find their intersection with f(x) = g(x) or equivalently f(x) - g(x) = 0. For this, we can use approximate solutions found by the Newton's iteration method! We can also compute the needed derivatives:

deriv1

derive2

So, the whole idea is that we split each circle in two functions: Upper andl lower part. Then, we check if the upper part of the first circle intersects the function describing the upper part of the second circle or the lower part of the second circle. Same with the lower part, we check it agains the upper and lower part of the other function. And for finding the intersection, we can use the approximate Newton method.

So, for the above example:

(x-0)^2+(y-5)^2=12,25

We get the upper and lower functions as

y = 5 + sqrt(12.25-x^2) y = 5 - sqrt(12.25 -x^2)

And we can plot them nicely

circle2

Conversely, the second circle ((x-0)^2+(y-0)^2=2,25) is described by the equations

y = 0 + sqrt(2.25-x^2) y = 0 - sqrt(2.25-x^2)

Now, if we look at all these graphs at once:

googl3

We find that there is an intersection! :). Between the lower part of the first circle and the upper part of the second circle. If we now form the difference between these two functions, we get the following graph for the functions:

f(x) = 5 - sqrt(12.25 -x^2) g(x) = 0 + sqrt(2.25-x^2)

f(x)-g(x) = 5 - sqrt(12.25 -x^2) - sqrt(2.25-x^2)

And if we plot that

google3

We can see that if we find the zeroes of that graph, we will get the correct solution x = 0! :)

Once we have that solution, we can eliminate one variable in either of the equations

(x-a)^2 + (y-b)^2 = r_1

And we will receive an equation ONLY quadratic in y, which can be solved by the general solution formula (pq-formula or abc-formula).

Hope this gives you some ideas.

Maximilian Gerhardt
  • 5,188
  • 3
  • 28
  • 61
  • Thank you very much. I think this is a strong starting point for me :) –  May 17 '16 at 08:20
  • 1
    @Marius Actually, that above isn't even optimal. The keyword here is what I've said in the first lines: It's a CIRCLE-CIRCLE INTERSECTION problem. Googling that gives you plenty of other resources (http://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect , http://stackoverflow.com/questions/3349125/circle-circle-intersection-points). The answer should be in one of these links. Sometimes it's easier when you know the right terms >_>. – Maximilian Gerhardt May 17 '16 at 08:22
  • I know how to solve this by hand, that is not a problem. I just don't know how to write algorithm for this. Eh, well, nevermind. Most of stackoverflow users here think that I came here to get solution for my homework assignment or something like that. As I can see, I will have to tackle this on my own. Thank you non the less :) –  May 17 '16 at 08:30
  • 1
    When you solve something 'by hand', you are *using an algorithm*. Think clearly and precisely about what you do when you solve it by hand; then get the computer to do that. – AakashM May 17 '16 at 11:07