

I doubt he was the univoter here.
Unfortunately Mr.Univoter appears quite often in replies to Mr. Chesnokov Yuriy's posts.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke
[My articles]





1. It wasn't me, I don't vote on forum articles
2. The question didn't place any requirements on edge lengths, and if it did my original solution would provide all 4 nontrivial solutions.
3. Can you provide some code to your solution, it would be interesting to see.
4. You provided a solution, others read it and decided to give a rating, no need to get your knickers in a knot.





I didn't look carefully over the other answers but glancing at them, I didn't see anybody mention the obvious: C is on the circle whose diameter is AB. So it amounts to finding the intersection of two circles  one centered at the midpoint of AB with a radius of AB/2, the other with a center at A with a radius of AC. Pretty simple algebra. There will be two answers (one on each side of AB) unless AC = 0 or AC = AB in which case the unique answer is B or A respectively (in which case the "angle" ACB is really not well defined so my claim would be that this case wouldn't fit the requirements of the original question where it was claimed that this angle was unambiguously a right angle  so I would claim there are always two answers).





darrellp wrote: didn't see anybody mention the obvious: C is on the circle whose diameter is AB. So it amounts to finding the intersection of two circles  one centered at the midpoint of AB with a radius of AB/2, the other with a center at A with a radius of AC
This was cross posted, and there was a link on the other page that explained it, and Member 4194593 also explained this.
darrellp wrote: Pretty simple algebra.
Try it  you end up with a quartic for the general case.
If, however, you rotate the triangle so that AB lies on the xaxis, and move A to the origin, the algebra becomes much simpler, you end up with a quadratic that is easily solved. All you have to do then is rotate the result and move it back into position and you have the general solution as I explained. There may be other ways to solve it, but this is the simplest I have found. My solution is correct, as are others (except for those claiming 4 solutions), for some reason the univoters didn't like it.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





I don't understand the crossposting stuff  I just did a response to the original query. If I screwed up, I apologize but I'm not sure what I need to do differently. If you would enlighten me, that would be great!
I'm glad to hear I just didn't look carefully enough. I'll take your word on complexity. I just saw two second degree polynomials and two solutions and assumed it all boiled down to a simple quadratic. That'll teach me to assume in the future!





Sorry, didn't mean to offend.
Like many things  the devil is in the detail  and solving those intersecting circles is tricky.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





No offense taken. I was serious  if I did some stupid crossposting thing, I really didn't mean to and I'd love to learn what I did so I could avoid it in the future.





The crossposting reference was about the original post (not you)  Cpallini's reply linked to the an identical post on another forum that had some useful discussion.
What i'd like to know is why folk want to solve this particular problem?
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Ah  okay. Sorry to be so dense. I don't often interact with these forums (fora?) so assumed I'd made some sort of boneheaded blunder.
Don't know about a motive. Could just be "recreational math". I think the original poster was under the impression that there was a single unique solution which suggests to me that he/she really was trying to solve a "real world" problem, but who knows?
I do know that my estimation of the simplicity of finding intersections of quadrics hasn't been good. There's a similar problem in the Fortune algorithm for Voronoi diagrams where you have to find the intersection of a couple of parabolas and I went in with the assumption that it would be a trivial problem. I was way off. Eventually, I just dumped everything into Mathematica and let it solve the problem. Every description I've ever seen of this algorithm passes this problem off as "find the interesection of the parabolas" as if it was some of throw away detail. You'd think somebody would stop and note that this is a damnedly difficult problem and here is the (rather ugly)solution. Oh well  if only the world were run the way I think it ought to be...
Just FYI, the problem is essentially that you're given two focii of parabolas with a common horizontal line as the directrix for both parabolas. Find the (two) intersections between the parabolas. Seemed simple. Wasn't. I'm still not sure of any terribly "intuitive" way of solving this. No obvious transform to do on this one since the directrix is already horizontal.





Now here's my chance to overestimate the simplicity of a problem, surely the equation of a parabola with horizontal directrix is y = P(x) where P(x) is a quadratic, so for two such parabolas you need to solve
P1(x) = P2(x)
which is a 'simple' quadratic. I can see that the coefficients may be messy, but straightforward (?).
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Yes, that's the kind of thinking I had for both of these questions  equating two quadratics shouldn't be that tough. It's the fact that you've got two quadratic equations in two unknowns in both cases that complicate matters. In the Fortune case, the equations are:
(ysy)^2 = (x1x)^2 + (y1y)^2 = (x2x)^2 + (y2y)^2
where ys is the y coordinate of the sweepline and (x1,y1), (x2,y2) are the two points. Using one equation, you can get y as a quadratic function of x. Substituting that into the other equation gives a quartic equation in x and you have similar problems to the ones you deal with in the original problem of this thread. I'm glad I'm not the only one who can be misled by these problems! What's more, like I said, I don't see any nice intuitive transforms or any other easy way, geometric or otherwise, of coming up with the solution for this one. Certainly doesn't mean there isn't one  in fact I suspect that there is such a thing  I just haven't seen it yet. When I got the solution from Mathematica, I was able to break it into lots of redundant pieces to improve performance which suggests to me that there ought to be a way. Perhaps if I meditated on the solution long enough, I could see it, but I haven't spent the time.
Minus some exceptional cases, here's the code I ended up with (directly from my code):
double a1 = 1 / (2 * (pt1.Y  ys));
double a2 = 1 / (2 * (pt2.Y  ys));
double da = a1  a2;
double s1 = 4 * a1 * pt1.X  4 * a2 * pt2.X;
double dx = pt1.X  pt2.X;
double s2 = 2 * Math.Sqrt(2 * (2 * a1 * a2 * dx * dx  da * (pt1.Y  pt2.Y)));
double m = 0.25 / da;
double xs1 = m * (s1 + s2);
double xs2 = m * (s1  s2);
It's been a long time since I did this. I think the rounding was done to avoid some numerical instability problems.
xs1 and xs2 are the x coordinates of the two solutions. For my purposes, I didn't really care about the y coordinates.
Darrell





Oops  okay  I see what you mean. Doh! I think you're right. I'm sorry to be so dim witted! Since you end up with the y^2 terms dropping out, you can solve for y, set the resulting two quadratics in x equal to each other for one quadratic in x and solve. Man, I better just stop before I stick my foot in my mouth again!
Darrell





Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Peter,
cp9876 wrote: as are others (except for those claiming 4 solutions)
Unless the triangle has the same length legs (ac=bc), there will be 4 solutions. Nothing in the stated problem indicated any orientation. For example, line ab can be taken as a vertical line starting with a at the bottom and b at the top, or, flip that upside down, then point c can be on either side of that vertical line, in either orientation of ab. Essentially, you need to draw two circles of radius ac, one at one end of the diameter ab and one at the other end of the diameter ab. There will be 4 points of intersection of these two circles with the circle drawn from the midpoint of ab with radius of ab/2. There is also no constraint on whether ac is the longest or shortest leg.
Dave.





Chesnokov Yuriy wrote: There is ABC triangle randomly rotated on XY plane. A,B coords are known, ACB angle is 90'. AC length is known. How to find C coords????
Member 4194593 wrote: Nothing in the stated problem indicated any orientation.
We seem to be solving different problems, I assumed that as the poster says that the coordinates of A and B are known that he knows which are which, in particular which coordinates are the end of the side AC. i.e. we are given (xa, ya), (xb, yb) and the length AC.
If he really doesn't know which is which, he can easily get the other solutions by swapping the A and B coords.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Peter,
You are correct as usual. You cannot draw the circle of length AC at B, it has to be drawn at A, thus only two solutions, one on either side of line AB.
One solution could be to start at the origin and call the point A, drop down distance AC on the y axis and call the point C, move to the right (the mirrored solution would be obtained by moving to the left) a distance sqrt(AB^2ac^2) and call that point B. Now rotate ABC about A until the line AB matches the original slope of the given line AB, then translate ABC to position A at the origin to the original given position of A.
Dave.





Dave,
Neat constructional idea, but the algebra looks nasty to work out the sin and cosine of that angle for the rotation,
Peter.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





I would like to check if a segment and a polygon have some intersections. Could you plz indicate me some algorithms to solve it. I knew Ray Casting algorithm and I wonder if there are other algorithms ?






The above algorithm won't detect the case where the segment is entirely contained in the polygon, without intersecting any edge. Let me know if you need to detect this case too.





Plz show me if that is the most optimal algorithm ? I really want to know the most optimal algorithm to solve this problem. So, would you mind helping me ?





If it isn't optimal it's pretty close. The calculation to determine if two segments intersect isn't time consuming. The only case it doesn't handle, as I've mentioned, is when the segment is entirely contained within the polygon.
modified on Friday, October 17, 2008 9:55 AM





OK. Thanks so much for replying





Alan,
Does it handle the case where the intersection is at the node between two line segments of the polygon?
Dave.





It does if your algorithm to detect linesegment intersection will detect a segment intersecting the end point of another segment.





Alan,
My question was about the suggested algorithm you gave above and whether it returned an intersection for a crossing at a node.
Dave.





Yes it does; if you follow the link there's a Java applet that lets you draw two line segments and tells you if they intersect. You can draw two segments that intersect at an end, and it does detect the intersection.





Alan,
Thank you for the answer.
I did start to try the link. First it wanted to install a plugin in FF, OK, I'll go with that. That failed, and the next thing it wanted to do was install a Sun DLL. I decided to quit at that point because the next thing it would want to do would be enable Java Script which I have disabled.
I'm happy that that solution will work if I ever need it.
Dave.





Depends on your situation. You should probably do a bounding box check first since it's simple, quick and will eliminate a lot of lines.
There's an entire book essentially on this subject:
http://www.amazon.com/RealTimeCollisionDetectionInteractiveTechnology/dp/1558607323/ref=sr_1_1?ie=UTF8&s=books&qid=1227945892&sr=11[^]
Some of the things you need to think about:
Are your polygons convex or can they be concave?
Are you testing fixed polygons against a series of lines or does the polygon change with each test?
Are your lines more likely to miss than not?
BSP trees are worth looking into if you really want to squeeze every last drop of performance. They're a bit complex, though and mostly good for lots of lines testing against a single polygon.





Iam student have aproject about retreiving image
,so Iwant agood algorithm about analysis images to find the signature of it and uses this step to retreive...
plz plz plz help me in a shortest possible time ..
thanks alot..





luna2010 wrote: plz plz plz help me in a shortest possible time ..
Done.
BTW: Google & CodeProject's article search engine are your best friends (reading the forum guidelines will be a plus).
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke
[My articles]





Sendme ur codez, plz. Urgent!
"If only God would give me some clear sign! Like making a large deposit in my name in a Swiss bank."





luna2010 wrote: plz plz plz help me in a shortest possible time ..
No. It might be more time efficient for you to google it
"The clue train passed his station without stopping."  John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks"  Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago."  Rob Graham





Google is ur best friend. Google it.





I need to figure out the formula/pattern/algorithm needed to convert the number on the left into a checksum on the right. Here are a few examples
6789542137 ; 53426
7274707623 ; 13890
7608909976 ; 21097
7866018419 ; 46204
8185833863 ; 59982
8052724826 ; 68535
Please help
Thanks






Can you supply any more information? A bunch of numbers and their checksum isn't much to go on...
"If only God would give me some clear sign! Like making a large deposit in my name in a Swiss bank."





unfortunately that is all the information I have. What i am trying to do is find out what formula/algorithm when applied to the 10 digit number will get me the 35 digit code. Any help would be great





hdsouza1 wrote: unfortunately that is all the information I have. What i am trying to do is find out what formula/algorithm when applied to the 10 digit number will get me the 35 digit code. Any help would be great
I'm afraid that's nearimpossible. It's equivalent to trying to decrypt an encrypted message given no information about the encryption. You have to have some idea how it functions otherwise it could, quite literally, be among hundreds of thousands of possible algorithms. For all I know, these could be nothing but randomly generated numbers...
"If only God would give me some clear sign! Like making a large deposit in my name in a Swiss bank."





Good luck.
"The clue train passed his station without stopping."  John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks"  Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago."  Rob Graham





a * x ^ 6 + b * x ^ 5 + c * x ^4 + d * x ^ 3 + e * x ^ 2 + f * x = y
use you data you can solute a、b、c、d、e、f.





Hi Shrewdlin, Thanks for your reply. Need a little more help. What is
1) x and y
2) Does x^5 mean x to the power of 5
Thanks





1) x and y is variable
2) yes, it means x to the power of 5
yan can use your data to make six equation for example:
a * 6789542137 ^ 6 + b * 6789542137 ^ 5 + c * 6789542137 ^ 4 + d * 6789542137 ^3 + d * 6789542137 ^ 2 + f * 6789542137 = 53426 (this is the first one, you can do the other)
six equation to solve six variable can you calculate the a、b、c、d、e、f
then use the known a、b、c、d、e、f to rebuild the equation
the data is very big you can use maple software for you!!!good luck!!





The problem will arise with the seventh line of the sequence.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke
[My articles]





Hi Shrewdlin,
Thanks for the detailed explanation. I guess I will have to buy the maple software. before I buy I was wondering how you got to this formula. Did you run the numbers through some program of yours to get this formula
Thanks





You can solve it in a spreadsheet, for the theory see Polynomial Interpolation[^], but unless you know that the answer you are looking for is a polynomial it is almost certainly wrong.
A 5th order polynomial can be fitted to your data:
a * x ^ 5 + b * x ^ 4 + c * x ^3 + d * x ^ 2 + e * x ^ 1 + f = y
but so can a 6th
a * x ^ 6 + b * x ^ 4 + c * x ^3 + d * x ^ 2 + e * x ^ 1 + f = y
a 7th
a * x ^ 7 + b * x ^ 4 + c * x ^3 + d * x ^ 2 + e * x ^ 1 + f = y
or a different 7th
a * x ^ 7 + b * x ^ 6 + c * x ^3 + d * x ^ 2 + e * x ^ 1 + f = y
or a Fourier series
a * sin(x) + b * sin(2*x) + c * sin(3*x) + d * sin(4*x) + e * sin(5*x) + f = y
or basically a linear combination of any collection of 6 functions (some collections of 6 functions will fail, but most will succeed). There are also a wide range of possible solutions that don't fall into these categories.
So unless you can state why any of the above solutions should or shouldn't be the one you are looking for, you don't know enough about the problem to solve it.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Wait! Don't buy Maple! You need to tell us something about what you expect out of this "decoder". If you just want any function that will match up at these points, sure, the polynomial will work but it will go crazy outside of these points. I'm assuming you're trying to "reproduce" some other function which spat out these values, in which case the polynomial is pretty much guaranteed to be the wrong thing. On the other hand, if you're just looking for a rule that takes on those values, you can use the function which takes on those specific values at those specific points and is zero everywhere else. It's about as likely as the polynomial and you don't have to buy Maple to compute it.
In general, if you are trying to reproduce the function that somebody else carefully chose to produce these values you're probably out of luck. There are an infinite number of functions that will do that. If you're looking for any function at all, then either take the one I mentioned above or explain whatever other details you've got that keep that one from working. You see these sort of questions in "brainteasers" where you have a chance of solving them, but if this was designed to prevent cracking, you're not likely to chance across the right answer.





The question as you have posed it is nonsense. There are an infinite number of solutions. For example, I guess this is not useful, but the formula f(n) defined by:
f(6789542137) = 53426
f(7274707623) = 13890
f(7608909976) = 21097
f(7866018419) = 46204
f(8185833863) = 59982
f(8052724826) = 68535
f(n) = 0 for all other n
actually answers your question.
Perhaps you could explain what you are trying to do?
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





why is it assumed that f(n) = 0 for all other n





Because based on the finite sample population he posted, it is a valid assumption.
"If only God would give me some clear sign! Like making a large deposit in my name in a Swiss bank."



