Miter calculation

[ham_and_cheese]

Hi, hopefully someone can help with a math problem. I'm trying to get the coordinates of the points that make up a corner miter. When you draw using the Flash drawing API it will miter your corners for you. I need to do the same things except I need to calculate those coordinates myself for other uses. See below

I
__
| |
| |
| |
| |
| |b_______
|__________| II
a

The things we know:
The rotation of segments I and II
The "thickness" of the line is 20, so perhaps adjacent=20/2=10 ?
The angle of ab is the average of angles I and II ?
The position of a and b will be relative to their midpoint

The formula will have to work for every possibility of I and II rotations.

I've done a lot of research and tried many things, but I just can't seem to get this to work correctly. Any help is appreciated.

Thanks.

[TOdorus]

this is some pretty basic geometry really. If you know one corner of a triangle to be 90° you know a lot of other stuff including:

Sin(alpha) = b/c
Cos(alpha) = a/c
Tan(alpha) = b/a

from which follows:

a = c*Cos(alpha)
b = c*Sin(alpha)
c = a/Cos(alpha) or c = b/Sin(alpha)

And then there's Pythogoras:
c² = a²+b²

I'm assuming you know the location of what you called point a in your ascii drawing, then the rest should be some real basic geometry.



You said you know angle e and angle f, so you can easly calculate the two points on their sloped side using the above formulas. You should also know the length of the sloped side (or else the segments would be endless, in a mathematical sense). Since you already know the thickness you have two sides per point to calculate the other two points from.

As for your point b, the angle from the origin would be: ((90-e-f)/2)+f

http://en.wikipedia.org/wiki/Law_of_sines
http://en.wikipedia.org/wiki/Law_of_cosines
http://en.wikipedia.org/wiki/Law_of_tangents

http://en.wikipedia.org/wiki/Pythagorean_theorem

http://en.wikipedia.org/wiki/Angle

[lordofduct]

There are no 90 degree angles to be found though...

dot product!

The shortest angle between any two vectors (and a miter is drawn in the direction of the shortest angle) is arcCos( dot product of the two lines unit vectors )

unit vector is a vector normalized (not a vectors normal, actual a vector normal is the most poorly chosen term I've ever heard in programming... it's very misleading as to what the word normal means. Curves have normals, parametric vector equations have normals, but a vector itself... well it's not quite the same thing.) It's a vector of length 1.

Dot product is as follows:

v1 = <a,b>
v2 = <c,d>
v1 dot v2 = a * c + b * d

to normalize a vector you divide it by it's length:
v1 = <a,b>
v1Normalized = < a / sqrt(a*a + b*b), b / sqrt(a*a + b*b)>

thusly your answer is:

arcCos[ ( a * c + b * d ) / ( sqrt(a*a + b*b) * sqrt(c*c + d*d) ) ]

[TOdorus]

There are no 90 degree angles to be found though...

....

[lordofduct]

in that drawing there are, not in the original miter

but in that you make a few 90 degree angles by comparing the positions of angles e and f... but how do you compare these angles mathematically around an entire circel? Which direction are they pointing? You can't mathematically draw all those lines with out more information then just e and f. Maybe when both lines exist in the first quadrant, but not when one is in the 4 quadrant and one is in the 2nd quadrant.

But you can't just subtract the two because you don't know which is further then the other resulting in negative angles or angles going the opposite direction around the circle and measuring the longest angle, instead of the shortest. As I said the miter is always drawn in the direction of the shortest angle.

Take your drawing, we do not know e in the sense of how you drew e... we know the angle e off the positive x axis.



now we can find it off the negative x axis like in your drawing by just subtracting e from 180 degrees. But then say e is all the way in the 3rd quadrant. What do you get then?



Now of course we can use a whole **** load of geometry to figure out where we are, what each line is in corrolation together, and do a ton of work to get to the answer doing a million sqrts along the way and the sort. Then still have a chance of finding the longest angle, instead of the shortest, and have to check that. Or we could use a couple steps of trig and basic vector algebra:

var angleE:Number = *someAngle*;
var angleF:Number = *someAngle*;

var angleBetweenEAndF:Number = Math.acos( Math.cos(angleE) * Math.cos(angleF) + Math.sin(angleE) * Math.cos(angleE) );

done! And always results in the shortest angle.

which is a simplification of the following vector algebra and trig:

var angleE:Number = *someAngle*;
var angleF:Number = *someAngle*;

var v1:Point = new Point(Math.cos(angleE), Math.sin(angleE) );
var v2:Point = new Point(Math.cos(angleF), Math.sin(angleF) ); //from converting polar to cartesian formulas

//v1 and v2 are already unit vectors because of the trig, if they weren't:
//v1.normalize();
//v2.normalize();

var dotProduct:Number = v1.x * v2.x + v1.y * v2.y;
var angleBetween:Number = Math.acos( dotProduct );

As for the points on the miter, well we can ignore the angle between the two lines for that actually, we could use it again, but it would again result in yet another long geometric algorithm... vector algebra to the rescue again.

take the vectors we talked about before and just lerp halfway to the other. This works because we are in 2 dimensions, and because we only want halfway... half rotation is the only clean part of a rotation, the rest of it depends on cos and sin... so unless you are rotating halfway, the lerp method will not work.

var angleE:Number = *someAngle*;
var angleF:Number = *someAngle*;
var pnt:Point = *the point of intersection*;
var w:Number = *lineWidth*;

var v1:Point = new Point(Math.cos(angleE), Math.sin(angleE) );
var v2:Point = new Point(Math.cos(angleF), Math.sin(angleF) ); //from converting polar to cartesian formulas

var v3:Point = Point.interpolate(v1,v2,0.5);
v3.normalize();
v3.x *= w / 2;
v3.y *= w / 2;

var p1:Point = pnt.clone();
p1.add(v3);
var p2:Point = pnt.clone();
p2.subtract(v3);

p1 and p2 are the points of the miter OP is looking for.

[TOdorus]

Ok... here we go:

in that drawing there are, not in the original miter

Actually yes: 4 to be exact, as the two lengths per segment need to be parallel

You can't mathematically draw all those lines with out more information then just e and f.

You also know the lengths and widths of the two segments, which makes the laws of sines, cosines and tangents applicable.

[QUOTE=lordofduct]Take your drawing, we do not know e in the sense of how you drew e... we know the angle e off the positive x axis.[/QOUTE]

Agreed, that is a better way to handle things. It isn't impossible to do it in the opposite direction however. It adds the action of making a negative out of the cosine sine functions.

[QUOTE=lordofduct]Now of course we can use a whole **** load of geometry to figure out where we are, what each line is in corrolation together, and do a ton of work to get to the answer doing a million sqrts along the way and the sort. [/QOUTE]

GROSS overstatement I'll point out next.


[QUOTE=lordofduct]
which is a simplification of the following vector algebra and trig:

var angleE:Number = *someAngle*;
var angleF:Number = *someAngle*;

var v1:Point = new Point(Math.cos(angleE), Math.sin(angleE) );
var v2:Point = new Point(Math.cos(angleF), Math.sin(angleF) ); //from converting polar to cartesian formulas

[/QOUTE]

You find the first two points by using the laws of sines and cosines, which basicly is calling geometry vector algebra. I'd rather not argue semantics. The next two points can be found in exactly the same way. By using an angle and the length of the now known side (or vector in your case). Hardly a load of square roots and whatnot

var dotProduct:Number = v1.x * v2.x + v1.y * v2.y;
var angleBetween:Number = Math.acos( dotProduct );

I never had a proper explanation of dotproduct during math or physics, but from what I understand angleBetween = angleE-angleF. If so that uses a lot less computation.

The end product of your algorithm is 2 vectors and the angle between them. You can get the coordinates for only of 1 the points out of them (the origin of the two vectors), while the Miter consists of 6 points. Ofcourse you can find 3 points if you don't use unit vectors. That still leaves you short of 3 coordinates.

The easiest way I can think of to find them, is to either make calculate the angles between the known vector and the vector needed (as we know the adjecent side as the known vectors length and the opposite side as the Miters width) and add or subtract that to the known vector angle (depends on which of the two segments you're using).



angle e = Known
angle f = Known
side 01 = 20
side 02 = 20

Point 0 = Known
Point 1 = (01*Cos(f), 01*Sin(f))
Point 2 = (02*Cos(e), 02*Sin(e))

angle e2 = Tan(13/01) // = Tan(side13 / side01)
side03 = sqrt(01*01+13*13)

Point 3 = (03*Cos(e2+f), 03 Sin(e2+f))

angle e5 = tan(24/02) // = Tan(side24/side02
angle e1234 = angle e - angle e5
side 04 = sqrt(02*02+04*04)

Point 4 = (04*Cos(e1234),04*Sin(e1234))

Which leaves point 5. This can be found by translating line 01 so that it intersects point 3 and translating line 02 so that it intersects point4. The intersection of those lines is point 5.

[lordofduct]

You find the first two points by using the laws of sines and cosines, which basicly is calling geometry vector algebra. I'd rather not argue semantics.

no I called that part Trigonometry... I called dot product vector algebra. Trig is the mathematics of triangles with respect to the 3 base trig functions: sine, secant, and tangent... then their reciprocals: cosine, cosecant, and cotangent... and lastly their all 6 inverses: arcosine, arcsine, etc...

The "Law of Sines" is not a geometric rule, it is a trigonometric rule.

The beauty of trig is you can ignore all that visualization and just look at the vector algebra... all you are now concerned about is: direction and magnitude. No longer are you worried about position or width or anything else. And the math can be simplified into much fewer steps... getting to the root of your issue.

but from what I understand angleBetween = angleE-angleF.

dotproduct is the length of one vector projected onto the other. It is defined as:
a dot b = |a||b|cos(theta)
where theta is the angle between them

vector algebra says you can also solve it the way I mentioned earlier. But by switching around the definition of dot product you will find that theta (the angle between is:
arcCos( (a dot b) / ( |a||b| ) )

Now this is best in the situation of using vectors... he only has angles. Now of course you bring up a good point, why not just subtract the two angles! But wait, let's say are vectors have the respective angles:

-170 and 175... the smallest angle between each is 15 degrees... but by subtracting the angles we get:

-345, or 345 depending the order we subtract. Not the smallest angle. Further more what if we record the angles at different times... a circle can be rotated around infinitely. we get 0 degrees and 721 degrees... the smallest angle is 1, but the subtraction will yield 721.


Further more he only asks for points 0 and 5 in your image. 2,4,3, and 1 can be just as easily found in any number of methods while again avoiding any visualization and there is the large part.

We don't want to have to visualize this diagram each time. And we need the algorithm to accept all possible rotation values known... and the two lines in any order. We don't want our algorithm to be forced to have line one be counterclockwise with respect to line 2. It makes utilizing the algorithm a headache.


It's equal to my aggrivation with Physics class in general, they hand you a formula and tell you it works... but never bother defining it mathematically. Due to the fact it can take Differential Equations to prove why this works. But instead they just say that torque is equal to some ridiculous algebraic formula and changes depending on the type of force that is being performed. Where as if you just remember the basic formulas you can derive to the torque and never bother remembering all these formulas.

I remember in highschool kids complained that math was hard because there was so many formulas to memorize... but there isn't, if you can add and if you can draw Sine you are set for the rest of your math carrier until you get to Calculus 3 or Diffy Q. Nothing more then addition and Sine is needed, all other formulas are assumed as an extended definition of Sine and Adding.



[edit]

oh and in your algorithm at the end, you might have to fix something. Point 0 is not known, the point of intersection of a line is through it's middle so the known point is half way between 0 and 5... not at 0.


at the red dot is known

in my algorithm to get 2,4,1 and 3 you can take the vectors of the two lines, and the points 0 and 5 that I solved and just scale the vector up to the length needed and add them to the points 0 and 5.


I didn't say you were wrong in any way... I was saying geometry is long and very hard to bring into perspective programmatically for infinitely possible values of rotation. I guarantee mine is flawed in some respects as well because there is even faster ways to do it... if I was in DirectX with C++ right now, I could probably tell you all these points in a matter of a couple lines of code due to all the mathematical algorithms they have available, Flash doesn't offer them though.

[TOdorus]

Gotten some z's, which is what I should've done a lot earlier last night. Would also fix my use of the word "qoute" too

no I called that part Trigonometry... I called dot product vector algebra. Trig is the mathematics of triangles with respect to the 3 base trig functions: sine, secant, and tangent... then their reciprocals: cosine, cosecant, and cotangent... and lastly their all 6 inverses: arcosine, arcsine, etc...

The "Law of Sines" is not a geometric rule, it is a trigonometric rule.

I stand corrected. I can't remember my books calling it trigonometry specificly.

-345, or 345 depending the order we subtract. Not the smallest angle. Further more what if we record the angles at different times... a circle can be rotated around infinitely. we get 0 degrees and 721 degrees... the smallest angle is 1, but the subtraction will yield 721.

So that's how it should be done! I always redefine it so the absolute rotation is less then 1pi rads. Although it has the advantage of bieng more easily interpretable, it can overshoot. Actually a movieclip in Flash does this automaticly, but with the right results.

It's equal to my aggrivation with Physics class in general, they hand you a formula and tell you it works... but never bother defining it mathematically. Due to the fact it can take Differential Equations to prove why this works. But instead they just say that torque is equal to some ridiculous algebraic formula and changes depending on the type of force that is being performed.

That is so true But to be fair, I can remember the disciminant for quadratic formula's to be quite magical too. What I actually like about physics is that they visualize it more. And most of the time I can see the connections in the visual. It did get a bit hard when I got to proving Pythogoras, Ceva and the like.

oh and in your algorithm at the end, you might have to fix something. Point 0 is not known, the point of intersection of a line is through it's middle so the known point is half way between 0 and 5... not at 0.

No it's solid. Point 0 is actually the origin and the points are relative to it. I was looking at the miter as more than two lines, as a shape, so that isn't the midde of "my" line. Since line01 is parallel to line35 that line can be found using a translation intersecting point 3.

I hope you also know some stuff about rigidbody's too, as that probably my next topic in this section of flashkit. Then you can keep me up all night again when I try to argue on that topic

Hope we haven't scared Ham & Cheese away though.

[lordofduct]

What I meant by point 0 not being known is when you use the line draw tool in Flash, it sticks the point at that red dot. That's how it is known, it's the point chosen when using the draw tool.

Also I think Ham&Cheese left a long time ago.

I actually don't know a whole lot about rigid bodies. But I'm always willing to learn new things. I hope you have some good questions to stimulate me into researching stuff. Either way nearly all Physics is a basic application of mathematics. I found this image on 4chan, made me laugh so hard!

[ham_and_cheese]

Hi guys, thank you for your in depth debate! I greatly appreciate your help. Sorry for the delay, I thought the I would continue to be notified via email when there were new replies to the post! Now I know better. I've tried the code below that was supplied by lordofduct, but it doesn't work as expected. The largest the miter seems to go is the total of 'w' which is the linewidth.

var angleE:Number = *someAngle*;
var angleF:Number = *someAngle*;
var pnt:Point = *the point of intersection*;
var w:Number = *lineWidth*;

var v1:Point = new Point(Math.cos(angleE), Math.sin(angleE) );
var v2:Point = new Point(Math.cos(angleF), Math.sin(angleF) ); //from converting polar to cartesian formulas

var v3:Point = Point.interpolate(v1,v2,0.5);
v3.normalize();
v3.x *= w / 2;
v3.y *= w / 2;

var p1:Point = pnt.clone();
p1.add(v3);
var p2:Point = pnt.clone();
p2.subtract(v3);

var pnt:Point = *the point of intersection*;
-- How do I find the point of intersection?

v3.normalize();
-- normalize requires a value or else it turns to NaN.

var p1:Point = pnt.clone();
p1.add(v3);
var p2:Point = pnt.clone();
p2.subtract(v3);
-- should these be p1 = p1.add(v3) and p2 = p2.subtract(v3) ?

Thanks again for all your help!

[TOdorus]

Nice to hear from you h&c!

I just finished a biggie draft for a research article and celebrating it with whiskey, so I'm gonna be wise here and only answer the easy one.

A normalized vector is a unit vector (but not necessarily vice versa), which is a vector with the length of one. Basicly a vector, but in a practical sense it only stores the direction of the vector and possibly it's origin.

Looking up the definition of the Point.normalize method in the Flash documention tells me that you need to feed the method the value 1 to get a unit vector.

[ham_and_cheese]

Congrats on your research article.

If I normalize the point to 1, then the points go out only half the thickness because the following:
v3.normalize(1);
v3.x *= w/2;
v3.y *= w/2;

If you see my attached image, it goes as such:
The black lines and green dots represent what the code produced
The blue lines and orange dots represent what should happen

Any ideas?

[lordofduct]

I don't know why I said w / 2... thinking back I'm I don't know... I'm tired all the time and make arithmetic mistakes randomly.

Anyways, the distance there isn't w / 2, it's the hypotenuse / 2 of a right triangle who has one leg of length w and an angle of length theta / 2 where theta is the angle between each line.

Ummm, yeah.

var h_2:Number = w / Math.cos( Math.abs(angleE - angleF) / 2 ) / 2;
v3.normalize(h_2);

and leave out the v3.x *= and the v3.y *=

[rachil0]

If you're still stuck, here is an alternate solution also based on vector arithmetic. The code is internally commented, consistent with the picture that Todorus posted on 08-29-2008 10:35 PM. The caller provides three points A,B,C that layout the miter. A,B,C are the midpoints of segment24, segment05 and segment13, respectively. The routine computes the six points, 0-5.

It will fail when the three points A,B,C are collinear to machine precision. If this is a common case that you need solved, I can post the fix. IMO it's somewhat a non-issue, because the mitered bend is really a straight line in this case.

Hope it's some use

[lordofduct]

Math.sin

[ham_and_cheese]

Thank you for all your help lordofduct. I'm still having some issues. I've posted the code based on what you provided. Let me know if I missed something. I've also attached the .swf so you can see what is happening. rachil0, thank you for attaching that archive. I will poke through that as well to see what I can gain from it.

-----------------------------------------------
var angAB = Math.atan2(ptB._y-ptA._y, ptB._x-ptA._x);
var angBC = Math.atan2(ptB._y-ptC._y, ptB._x-ptC._x);

var angleBetweenABC = Math.acos( Math.cos(angAB) * Math.cos(angBC) + Math.sin(angAB) * Math.cos(angAB) );

var v1:Point = new Point( Math.cos(angAB), Math.sin(angAB) );
var v2:Point = new Point( Math.cos(angBC), Math.sin(angBC) );

var pnt:Point = new Point(ptB._x, ptB._y);
var w:Number = 30;
var h_2:Number = w / Math.cos( Math.abs(angAB - angBC) / 2 ) / 2;

var v3:Point = Point.interpolate(v1, v2, 0.5);
var ang:Number = Math.atan2(v3.y, v3.x);

v3.normalize(h_2);

var p1:Point = pnt.clone();
p1 = p1.add(v3);
var p2:Point = pnt.clone();
p2 = p2.subtract(v3);
--------------------------------------------------


Thanks again!