Help needed....math problem

Replies to This Discussion

Permalink Reply by Lucas Epp on April 7, 2011 at 5:44pm

An interesting geometrical problem - but I think this particular one is intractable, i.e. cannot be expressed in closed form algebraically.

I first approached the problem using trigonometry and the cosine law to find two equivalent expressions for the angles adjacent to the two equal angles formed by the bisection.  Equating these and using the fact that the point must lie on the circle results in a system of two equations with two unknowns (the x and y coordinates of the point on the circle).  However these equations are implicit in the two variables to several levels and I couldn't see any solution by hand... then a quick search led to the following article.

http://mathcentral.uregina.ca/QQ/database/QQ.09.99/adami1.html

This problem is equivalent to finding the ellipse with foci at the two points outside the circle which is also tangent to the circle.  Seems an iterative methodology is the only way to solve this problem - which is a common one in computer graphics.

Luke

Permalink Reply by Chris Tietjen on April 7, 2011 at 6:23pm

I don't think that Fermat's principle will help.  You need to know a priori where the tangent line would hit the circle to determine a and b but that same tangent point is what you're trying to find via Fermat's principle so immediately you're into a recursive scenario.

 

Chris

Permalink Reply by David Rutten on April 11, 2011 at 1:20pm

So, I couldn't find an actual analytic solution to this. Tried again today at the cafe over a fresh ginger+darjeeling tea, but I get stuck every time. I put my dad on the case, he's a maths teacher.

 

In the meantime, I wrote a little numeric solver for this in a VB script. If the accuracy is not to your liking I can improve it. It only works (or rather, is only tested) on the World XY plane.

 

Hope it helps.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Attachments:

• BisectorProblem.ghx, 77 KB

Permalink Reply by Pieter Segeren on April 11, 2011 at 4:32pm

It looks to me like you've allready cracked it David:)
I was going to ask you what the involved math was, because I'm not educated in scripting. But I tried my interpretation of it, and it works.
Man, am I glad you solved this, it was keeping me occupied... I think Kimu will be very pleased as well. Thank you very much!

Permalink Reply by benmo on April 11, 2011 at 4:52pm

this is crazy!!!!!! thanks david and pieter and everyone else!!!! i'm trying to understand how you did at the moment right now i have one more question tho does this vb script can be also used in any kind of curves?? but not just circles???

 

Pieter-

I tried to see if the angles were the same somehow they are not exactly the same. I think i tried that method but didn't work.

Attachments:

• grasshopper.jpg, 224 KB

Permalink Reply by David Rutten on April 12, 2011 at 2:15am

Hi Kimu,

 

the algorithm is a simple binary-search implementation. It basically picks a point in the middle between A and B, measures the angles, then moves left or right based on angle discrepancy, measures again, moves again, measures again, moves again, etc. until the accuracy is deemed sufficient. Here's a step by step:

 

 

These are the inputs. Three points and a Radius. The script performs a bunch of checking to make sure that the inputs are valid. For example, A and B must both be outside of the circle and must not be positioned in such a way as to be co-linear with M. The first step in the algorithm is to find the portion of the curve in which it will make sense to search for our solution. This is basically the arc between the the projections of A and B onto the Circle, A' and B'.

 

 

Since I didn't feel like doing any difficult math, I make both arcs, then pick the shorter one. All I need for this is A' and B' as start/end points for the arc and t as a tangent vector. Once I determined the thick arc is shorter than the dashed arc, I pick a point P in the middle of the thick arc. (Although in the script I work with arc-parameters, not 3D points as that is easier to, but it's harder to explain that graphically.) 

 

 

So at this stage we have a point P which allows us to compute the angles α and β (APM and BPM respectively). These two angles need to be the same for your bisector to be valid. If α is smaller than β, it means that point P needs to move towards A', if α is larger than β, P needs to move towards B'. In this image, we move to the left. And we need to move the new P halfway between A' and the old P.

 

At this stage, we simply need to keep repeating the logic until α and β are similar enough. At every recursion, we double the accuracy.

 

As you can see, there's quite a lot of assumptions build into this algorithm that would have to be revised when you go from circles to freeform curves. It would become quite a bit more complex.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Alpha222 on April 13, 2011 at 5:54am

Hi David,

 

did you draw these diagrams by using xarax??

Permalink Reply by David Rutten on April 13, 2011 at 9:07am

Yes. Normally I draw my base geometry with Rhino and only apply line and fill styles in Xara, but in this case it was easy enough to draw directly.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Pieter Segeren on April 12, 2011 at 4:10am

You're right Kimu, how I interpreted David's VB was wrong. Sorry about that, I guess I just wanted to see the answer. I've spend a lot of time trying to determin if there is a variable too much for this to be solvable, but so far without succes.

I'll delete the definition I posted yesterday, and show you where I am now. I've isolated the normal in this setup to try and find the relation between angles and lengths, but i still very much in the dark... Maybe you can spot the relation, maybe there still is a variable too much, I really don't know.

(Do I understand correctly if I say the vb script is doing it the galapagos way?)

Attachments:

• bisect_wonormal.ghx, 1.5 MB

Permalink Reply by David Rutten on April 12, 2011 at 4:21am

"Do I understand correctly if I say the vb script is doing it the galapagos way?"

 

Hmm, maybe. On a very abstract level both search for a solution by taking a number of steps, but it's a very different kind of algorithm. The script takes informed decisions at every iteration while Galapagos is just wildly shooting at quail with buck shot and hitting the odd republican every now and again.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Pieter Segeren on April 12, 2011 at 4:46am

Thanks David, for pointing out there is a difference in the search method, and putting it so funny:)
So the question still stands...
I hope your dad can help us here, or just point out we've got a variable too much.

Permalink Reply by David Rutten on April 12, 2011 at 4:54am

It's certainly not about too many variables. There's always two well defined solutions (on opposite sides of the circle), the problem may be finding the intersection between two unintersectable functions.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

• ‹ Previous
• 1
• 2
• 3
• Next ›
• Page