Help with geometry calculation for CALayer

Discussion in 'Mac Programming' started by GorillaPaws, Feb 8, 2010.

  1. GorillaPaws macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #1
    So I'm trying to derive the value of point (p, q) and the rotation value r in terms of the other variables, and I'm having a hard time figuring out how to get there. It's been over 10 years since I took trig and I'm not sure how best to go about tackling this one.
    [​IMG]

    The rotated box is a CALayer, and I have previously figured out how to make it work when I used (x, (y + height)) as the layer's (0, 0) anchor point and rotated from the corner down, but now that I'm trying to use the default center (0.5, 0.5) as the anchor, I'm having a hard time figuring out the math. The reason for wanting to use the center for my anchor point is so when I apply layer transformations to my layer (such as scaling) the effect is properly centered on the layer instead of being skewed to the side.

    I should mention that although I've drawn my layer as a square, the height of my layer can be arbitrarily defined to any reasonably sized positive value (obviously the width is necessarily determined by the pythagorean theorem).

    I hope I was able to clearly explain the problem, and I appreciate any help you could send my way.
     
  2. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #2
    So I figured this out, and feel stupid for the answer being so simple. Basically all you need to do is calculate the midpoint of the hypotenuse and come off perpendicular to it by half the layer's height.
    [​IMG]
    Here's the method I wrote that calculates the shift. It doesn't have any error checking and uses a lot more variables than necessary to help make the process easier to follow:
    Code:
    -(CGPoint) calculateHypotenuseLayerAnchorPointWithOrigin: (CGPoint)theOrigin 
    		 	                    triangleBase: (CGFloat)theTriangleBase 
    				          triangleHeight: (CGFloat)theTriangleHeight 
    			      		     layerHeight: (CGFloat)theLayerHeight
    {
    	CGFloat tAngleOfShift = atan( theTriangleBase / theTriangleHeight );
    	CGFloat tMidpointX = theTriangleBase / 2;
    	CGFloat tMidpointY = theTriangleHeight / 2;
    	CGFloat tAngularShiftX = cos( tAngleOfShift ) * (theLayerHeight / 2);
    	CGFloat	tAngularShiftY = sin( tAngleOfShift ) * (theLayerHeight / 2);
    	CGFloat tTotalXShiftValue = tMidpointX + tAngularShiftX;
    	CGFloat	tTotalYShiftValue = tMidpointY + tAngularShiftY;
    	
    	CGPoint nHypotenuseLayerAnchorPoint = CGPointMake( theOrigin.x + tTotalXShiftValue, theOrigin.y + tTotalYShiftValue );
    	return nHypotenuseLayerAnchorPoint;
    }
    
     
  3. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #3
    Something I came up with real fast, try it out if you can.

    Code:
    #define xShift (theTriangleHeight*ratio)
    #define yShift (theTriangleBase*ratio)
    -(CGPoint) calculateHypotenuseLayerAnchorPointWithOrigin: (CGPoint)theOrigin 
    								triangleBase: (CGFloat)theTriangleBase 
    							 triangleHeight: (CGFloat)theTriangleHeight 
    								layerHeight: (CGFloat)theLayerHeight
    {
    	// ratio = (LayerHeight/2)/ hypotenuse of "theTriangle"
    	CGFloat ratio = (theLayerHeight/2.0f) / sqrtf(powf(theTriangleBase, 2.0f)+powf(theTriangleHeight, 2.0f));
    	return CGPointMake(theOrigin.x+(theTriangleBase/2.0f)+xShift, theOrigin.y+(theTriangleHeight/2.0f)+yShift);
    }
    
    Tried to use fewer variables, and no angle calculations. Let me know if you need some background theory on how I came up with this solution.
     
  4. lloyddean macrumors 6502a

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #4
    For the Peanut gallery how did you come up with the illustrations?
     
  5. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #5
    I know right? they're pretty awesome
     
  6. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #6
    Glad you guys like them. I just whipped them up in DrawIt. It's a great little indie Mac app for sketching up stuff. It can be a bit glitchy at times, but it's great for light-duty jobs like this. I've never tried to do anything hardore with it though, although from the video on their site it seems possible to do some neat stuff if you had the skill/inclination. There's a free trial, so it's worth checking out.

    Thanks for the code, I haven't had the chance to incorporate it yet. As I said earlier, it's been a WHILE since I've had trig (or had to use it), so my knowledge of triangular ratios is a bit foggy. If you could explain how you were able to avoid the angle calculations, I would be interested to see it.
     
  7. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #7
    Assuming you are correct that angle a is the same in both smaller right triangles, gaurentees that the two triangles are "similar triangles". (which I should hope is true since you say you already solved it)

    Meaning "theTriangle" and shiftTriangle are scalar multiples of each other.

    so shiftX is theTriangle.height*thatScalar
    and shiftY is theTriangle.width*thatScalar
    and shiftTriangle.hypotenuse is layerHeight/2 AND theTriangle.hypotenuse*thatScalar

    Solving for thatScalar
    layerHeight/2 = theTriangle.hypotenuse*thatScalar
    layerHeight/2 = (sqrt(theTriangle.height^2+theTriangle.width^2))*thatScalar

    (layerHeight/2)/theTriangle.hypotenuse = thatScalar


    Optimizations, use f compiler term in places like layerHeight/2.0f to make sure the compiler reserves a float size constant memory instead of double (no conversion and saves memory). And uses float based math.h functions sqrtf() and powf() so that all the floats do not need conversion to and from doubles.

    #define xShift etc. to compromise between readability and not having more local variables.
    I have heard that the naive algorithm xSquared = x*x is not as efficient as pow(x, 2.0), so I personally make it a point to use math.h's pow functions unless I'm dealing with integer types (to avoid confusion and since the square of any integer is an integer)
     
  8. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #8
    I just wanted to thank you again for your help. Your code works great, and it feels awesome to delete those trig functions from my method.

    Angle a should be the same in both triangles. Here's a diagram that shows why, I added complement angle b and some parallel lines to help make the relationships more clear:
    [​IMG]

    I somehow totally overlooked this. It seems I'm developing the worrisome habit of making problems more complicated than they need to be. Thanks for setting me back on course.

    I never understood why people wrote 2.0f and then assigned it to a float, it seemed redundant. Your explanation totally makes sense in terms of cluing in the compiler to your intent. What happens if you're compiling for 64-bit?

    I'm still trying to find my way as far as learning how to make these style-based judgment calls. It seems I have a tendency to create lots of very explicitly named local variables and then to incorporate those abstractions into my final calculation to avoid longer/messier lines of code. Also, I'm not sure what to think about using #defines instead of locals. The nice thing about locals is that I try to declare them right before I need them so I dont' have to hunt around to find the definition. I'm not saying I disagree with you, only that I don't know enough to have formed much of an opinion on the subject and would be interested to hear what you/others thought on the issue.

    This is a very handy tip. Thanks.
     
  9. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #9
    I was pretty sure it was correct, but when drawing squares and assuming equality with rectangles eyes can be deceiving ;)

    I honestly do not know. I've always assumed that floats are just 1/2 the bits of doubles. So if your doubles are 64bit then the floats would be 32 bit floats. Thats just what I've always thought in the back of my mind.

    I agree (that readability can be more important than brevity and a low memory footprint), but I abhor using local variables for placeholder text. I usually use a local when I will use it more than once.

    for example
    Code:
    + (double) erf: (double) x {
    	double c;
    	double xSquared = pow(x, 2.0);
    	
    	c  = 4/Stat_pi;
    	c += Stat_a *xSquared;
    	c /= 1+Stat_a*xSquared;
    	c *= -xSquared;
    	c  = 1 - exp(c);
    	c  = sqrt(c);
    	return c;
    }
    
    function for computing something called the error function. http://en.wikipedia.org/wiki/Error_function
    Stat_a and Stat_pi are #defines obviously.

    Almost all my math like functions follow the same pattern. Decide on bare minimum local variables/ variables that will be used more than once or twice. (if xSquared had only been used once or twice in the formula, I probably would have opted for replacing it with pow(x, 2.0), but my optimization sense tells me its better to calculate it once and store it)
     
  10. autorelease macrumors regular

    Joined:
    Oct 13, 2008
    Location:
    Achewood, CA
    #10
    The compiler is very good at optimizing away variables that are only used once or not that often, as well as expressions that are repeated. Creating local variables for clarity most likely will not slow down the code.

    Also: pow(x, 2.0) is a bad idea. The pow() function is usually implemented using the identity b^x = e^(x*log(b)), which is certainly overkill for taking the square of a number. gcc might catch this and reduce it a multiplication, but I'm not sure.

    Also also: there's no reason to create your own error function, erf() and erfc() are part of the C standard library, and thus are written in highly tuned assembly language.
     
  11. lloyddean macrumors 6502a

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #11
    I believe this is incorrect!

    I stand corrected. I thought these were extensions.
     
  12. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #12
    I like to test things...
    Code:
    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    #include <time.h>
    
    int main (int argc, const char * argv[]) {
        register double counter, counterSquared;
    	time_t t0, tMultiply, tPow;
    	
    	t0 = time(NULL);
    	
    	//multiply only
    	for (counter = 0.0; counter <= 100000000000.0; counter += 1.0) {
    		counterSquared = counter * counter;
    	}
    	tMultiply = time(NULL);
    	// pow only
    	for (counter = 0.0; counter <= 100000000000.0; counter += 1.0) {
    		counterSquared = pow(counter, 2.0);
    	}
    	tPow = time(NULL);
    	
    	
    	printf("multiply time %ld\n", (long)(tMultiply-t0));
    	printf("pow time %ld\n", (long)(tPow-tMultiply));
        return 0;
    }
    
    Code:
    [Switching to process 8614]
    Running…
    multiply time 404
    pow time 405
    
    I attribute the 1 second difference to the fact that the multiply block was all executed on one core of my computer, while the pow code ran for a couple seconds on one core then switched to a different one... that and function overhead. I hypothesize that pow checks to see if the exponent is 2 and then just returns the multiplication.

    Whats odd is that I distinctly remember watching an MIT OCW video on algorithms that claimed that xSquared = x*x; was not the most efficient algorithm. So I assumed pow was using whatever the most efficient algorithm was.
     
  13. chown33 macrumors 604

    Joined:
    Aug 9, 2009
    #13
    You originally posted powf(), but you tested pow(), which works on doubles, not floats.

    You might test the "check for 2" hypothesis by using a variable instead of a literal constant. You might also be able to trick the compiler using the float literal ((float)2.000000001) as the powf() arg. This has more precision than a float carries, but is not exactly 2.0 as a double.

    If you can find it, I'd be interested in what the algorithmic efficiencies break down to.
     
  14. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #14
    I had remembered a bit about this in an NSBlog Article about the Volatile keyword, which is why I never really worried about the performance implications.

    Stylistically, I realize that many may "abhor" the look of code like this, and it does make me a bit self-consious that my code looks a bit childish. Then again, it's easier for me to follow, so that's a plus. I suspect that the more experienced I become reading and writing code, the fewer in number and less wordy my variables will become.

    I do find it interesting that because coding style is such a subjective thing it gets treated like politics, religion, favorite programming language, etc. I think figuring out a style is important, and wish people were more comfortable explaining the logic behind their style decisions without fear of the conversation degenerating into a non-sensical flamewar.

    I really appreciate everyone's input.
     
  15. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #15
    Right... because I assume pow and powf are internally identical except for the choice of memory. I posted powf in my code because we were working with floats, and thus wanted to avoid float to double conversion twice.
    I may try. For now I have .... THE TEST OF THE TWO ALGORITHMS
    Code:
    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    #include <time.h>
    
    typedef struct {
    	float x;
    	float y;
    } FPoint;
    
    void testMultiplySquared(void) {
    	register double counter, counterSquared;
    	for (counter = 0.0; counter <= 10000000000.0; counter += 1.0) {
    		counterSquared = counter * counter;
    	}
    }
    void testPowSquared(void) {
    	register double counter, counterSquared;
    	for (counter = 0.0; counter <= 10000000000.0; counter += 1.0) {
    		counterSquared = pow(counter, 2.0);
    	}
    }
    
    FPoint calculateHypotenuseWithTrig( FPoint origin, float TB, float TH, float LH ){
    	float tAngleOfShift = atan( TB / TH );
    	float tMidpointX = TB / 2;
    	float tMidpointY = TH / 2;
    	float tAngularShiftX = cos( tAngleOfShift ) * (LH / 2);
    	float	tAngularShiftY = sin( tAngleOfShift ) * (LH / 2);
    	float tTotalXShiftValue = tMidpointX + tAngularShiftX;
    	float	tTotalYShiftValue = tMidpointY + tAngularShiftY;
    	
    	FPoint nHypotenuseLayerAnchorPoint;
    	nHypotenuseLayerAnchorPoint.x = origin.x + tTotalXShiftValue;
    	nHypotenuseLayerAnchorPoint.y = origin.y + tTotalYShiftValue;
    	return nHypotenuseLayerAnchorPoint;
    }
    FPoint calculateHypotenuseWithTriangles( FPoint origin, float TB, float TH, float LH ){
    	float ratio = (LH/2.0f)/sqrtf(powf(TB, 2.0f)+powf(TH, 2.0f));
    	FPoint nHypotenuseLayerAnchorPoint;
    	nHypotenuseLayerAnchorPoint.x = origin.x+(TB/2.0f)+(TH*ratio);
    	nHypotenuseLayerAnchorPoint.y = origin.y+(TH/2.0f)+(TB*ratio);
    	return nHypotenuseLayerAnchorPoint;
    }
    
    void testTrig(void) {
    	register int counter;
    	float factorFloat;
    	FPoint o;
    	o.x = 1.0f;
    	o.y = 1.0f;
    	int factor;
    	
    	for (counter = 0 ; counter < 1000000000; counter++) {
    		factor = rand()%100000;
    		factorFloat = (float)factor/10000.0f;
    		o.x *= factorFloat;
    		o.y *= factorFloat;
    		o = calculateHypotenuseWithTrig(o, 5.0f*factorFloat, 3.0f*factorFloat, 6.0f*factorFloat);
    	}
    }
    void testTriangles(void) {
    	register int counter;
    	float factorFloat;
    	FPoint o;
    	o.x = 1.0f;
    	o.y = 1.0f;
    	int factor;
    	
    	for (counter = 0 ; counter < 1000000000; counter++) {
    		factor = rand()%100000;
    		factorFloat = (float)factor/10000.0f;
    		o.x *= factorFloat;
    		o.y *= factorFloat;
    		o = calculateHypotenuseWithTriangles(o, 5.0f*factorFloat, 3.0f*factorFloat, 6.0f*factorFloat);
    	}
    }
    int main (int argc, const char * argv[]) {
        //register double counter, counterSquared;
    	time_t t0;
    	
    	t0 = time(NULL);
    	time_t tMultiply, tPow;
    	testMultiplySquared();
    	tMultiply = time(NULL);
    	testPowSquared();
    	tPow = time(NULL);
    	printf("multiply time %ld\n", (long)(tMultiply-t0));
    	printf("pow time %ld\n", (long)(tPow-tMultiply));
    
    	t0 = time(NULL);
    	time_t tTrig, tTriangle;
    	srand(1);
    	testTrig();
    	tTrig = time(NULL);
    	srand(1);
    	testTriangles();
    	tTriangle = time(NULL);
    	printf("trig time %ld\n", (long)(tTrig-t0));
    	printf("similar Triangle time %ld\n", (long)(tTriangle-tTrig));
        return 0;
    }
    
    Output:
    Code:
    [Switching to process 8840]
    Running…
    multiply time 40
    pow time 40
    trig time 154
    similar Triangle time 44
    
    I've played with the numbers and the starting srand();'s for both tests.
    I always come up with a 3:1 ratio between the OP's trig based solution and my similar triangle solution.

    Not sure how much of that is allocating and securing extra local variables, and how much of that is the loss of effeciency using atan(), sin() cos()

    EDIT: pow is certainly doing something special with exponent 2.0
    making it 2.0000000000001 shoots the time up from 40 seconds to 871 seconds. Making it 1.5 shoots it up to 827
    3.0 goes up from 40 to 200, which is not bad and probably a "special case" input as well.
     
  16. iSee macrumors 68040

    iSee

    Joined:
    Oct 25, 2004
    #16
    Style aside, readability has direct benefits when it comes to code maintenance.

    Of course, I suspect that jared_kipe finds his concise style more readable -- you're probably both going for the same goal but prefer read code differently. :p

    Also: are you going to tell us how you create these professional diagrams???
     
  17. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #17
    On the use of pow(x, 2.0) vs x*x

    While trying different exponents I noticed a peculiar thing.
    x*x*x was much more efficient than pow(x, 3)

    This lead me to remove all the "register" keywords from my testing code since pow's copy of the variable wouldn't be on a register so it was unfair.

    Didn't help.

    I decided to make my own fuction that took a double and returned a double input*input.

    AH HA
    now pow(x, 2.0) was indeed faster than my own function. (55seconds to 40seconds)

    I decided to turn my function into a cube to test against pow(x, 3.0)

    Though my function did get slower (60 seconds), it is nowhere near pow's 200second time for cubing.


    This leads me to some conclusions.
    #1 using pow to an integer is most likely unnecessary and/or harmful
    #2 the compiler is probably using special code for handling x already, and either the compiler is replacing pow(x, 2) with x*x or pow itself is using that special code.

    #3 pow should be re-written for special cases like 0,1,3... to be faster. There is just no excuse :p

    EDIT: #4 must search code base and remove pow..........
     
  18. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #18
    I rewrote my function using new variables for everything.
    Code:
    FPoint calculateHypotenuseWithTriangles( FPoint origin, float TB, float TH, float LH ){
    	float hypo = sqrtf(TB*TB+TH*TH);
    	float LHMid = LH/2.0f;
    	float ratio = LHMid/hypo;
    	float xShift = TH*ratio;
    	float yShift = TB*ratio;
    	
    	float TBMid = TB/2.0f;
    	float THMid = TH/2.0f;
    	
    	FPoint nHypotenuseLayerAnchorPoint;
    	nHypotenuseLayerAnchorPoint.x = origin.x+TBMid+xShift;
    	nHypotenuseLayerAnchorPoint.y = origin.y+THMid+yShift;
    	return nHypotenuseLayerAnchorPoint;
    }
    
    Reran the test and there was no statistically relevant difference in run times. I am very impressed, and am now wondering if I should redo the test running on my iPhone for a slower memory/processor platform.
     
  19. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #19
    I'm not sure professional is the right word, but they look pretty decent for being so easy to make. Did you take a look at the demo version of DrawIt that I mentioned earlier?

    It's basically a nice interface for working with quartz and core image filters, which can be handy for development if you're trying to sketch-up what something might look like in code without having to do lots of re-compiles.

    The site has a few tutorial videos that do a much better job of showing off what's possible than I could ever describe here. It's worth taking a look at if you haven't yet.
     
  20. iSee macrumors 68040

    iSee

    Joined:
    Oct 25, 2004
    #20
    ^^^^

    Sorry, I scanned the thread but missed your previous mention of DrawIt... Thanks, I will check it out.
     

Share This Page