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

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: (ys-y)^2 = (x1-x)^2 + (y1-y)^2 = (x2-x)^2 + (y2-y)^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

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.

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.

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!

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.

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/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&s=books&qid=1227945892&sr=1-1[^] 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.

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).

I think you have some errors in the list of edges. For instance, your polygons include an edge from (2,0) to (2,3) but there is no such edge in your list of edges. Anyway, I think what you're suggesting here is that you've got a list of edges and vertices which define a mesh (often referred to a "boundary representation") and you want to find the polygons in that mesh. I'd suggest that you look at Winged Edge representation, turn your edges into a winged edge rep and get your polys from that. Essentially, you'd have to keep a list of vertices with the edges around them in clockwise order, then traverse each vertex and trace out each poly between adjacent edges. You have to be careful about skipping over polys that have already been listed which means you have to keep track of the polygons each edge separates. It'd be a bit ugly, but I think that's pretty much what's required. It would also mean that the area surrounding the entire mesh will be represented as a "polygon". You can recognize that polygon by looking at the rightmost vertex, getting the first edge from it that is CCW from vertical and the flagging the polygon clockwise from that edge as the "exterior polygon". If you're looking for a Voronoi diagram that keeps a record of all the polygons, I've got one that I've been thinking about putting up on CodeProject. There's a fortune algorithm already out there on CodeProject, but it has some bugs and pretty much has a dump of edges like you're talking about without an indication of the polygons each edge goes with. Mine gives a full winged edge representation of the diagram which includes all the polygons, edges and vertices with them all hooked together intelligently. If that's what you're looking for, perhaps I'll put my fortune algorithm up earlier rather than later.

This is a standard question in probability, primarily because people find it counterintuitive. The first hint that it's a little odd is when you realize that if you have 366 people the odds are 100% that two of them have the same birthday. It's not quite so hard at that point to imagine the the 50% mark is around 30 or so. It's easier to ask what the chances of them all having different birthdays is and subtract that from one. So for two people, the chances that both birthdays are different is 364/365 (only a 1/365 chance that the second person's birthday matches whatever birthday the first has). For three people, the chances that all their birthdays are different is (364/365)*(363/365) - i.e. the second person's birthday must be different than the first's (364/365) and the third person's must be different than both the first two (363/365). Similarly, for four people, the chances are (364/365)*(363/365)*(362/365) and the pattern is obvious. I believe that this does, in fact, drop under 0.5 around 30 people or so and there you have the answer. Also, I believe that conventionally, oddes of 2:1 means the first alternative has a 2/3 chance and the second has a 1/3 chance. Hence, one to one odds means 50%. :)

This is probably one of the strangest things I think I've seen while working in .NET and I have yet to figure out even a workaround, much less why it might be occurring. I've got a very strange bug happening which I was finally able to distill down to a problem with writing to ..\..\app.config after a file open dialog. It appears that if a standard file open dialog is closed with the "open" button then any future writes to app.config just magically disappear into the bit bucket (am I the only one still using that term?). No errors, no exceptions thrown. In fact, if you close the app.config stream and open it from scratch, the changes just written appear to be there but when the app finishes, they aren't there. This sounds like a buffering problem but I'm setting the stream to autoflush and flushing/closing it after the save. Also, if you have the file open in the IDE at the time, you can write to it and save it just fine. None of this happens when you hit the cancel key in the open file dialog even though I'm totally ignoring the return from the dialog in both cases. None of it happens with files other than ..\..\app.config (at least not with the sample file I tried in my temp directory). :confused::confused::confused::confused: I have no idea why the file open dialog and app.config would be tied together in such an inextricable manner. I don't know how I'd simulate such a strange situation WRT app.config even if I tried. The best I can think of is to overwrite app.config and change it's creation date back to what it was originally but this isn't happening because I can write to it from the IDE while this is happening and those writes aren't overwritten. This one definitey has me scratching my head. To illustrate the bug I wrote a tiny app with a single button which calls the following function when the button is pressed. This pretty much illustrates everything I'm talking about (forgive the formatting - all my blank lines seem to drop out in the <pre> block - anybody know how to get them to show up?):

private void XMLBugSave()
{
// Everything works fine if you use a file other than ..\..\app.config...

// const string strFile = @"d:\\temp\\testbug.xml"; 
const string strFile = @"..\\..\\app.config"; 

XmlTextReader xr = new XmlTextReader(strFile); 
xdoc = new XmlDocument(); 
xdoc.Load(xr); 
xr.Close(); 

Random rnd = new Random(); 
string strNodeName = "NODE\_" + rnd.Next().ToString(); 
Console.WriteLine("Attempting to add Element " +