Koch curve tekenen met opengl en c++

[sdy]

Mensen, ik ben wanhopig aan het worden. Vorig jaar heb ik een programmaatje geschreven in c++ met opengl dat een koch curve tekent.
Ik ben de source ervan op een of andere manier kwijtgeraakt (was destijds een programmeeropdracht voor mijn studie). Nu probeer ik het programma opnieuw te schrijven maar ik kom er gewoon niet uit. De oplossing is simpel, maar ik zie door de bomen het bos niet meer. enfin, het probleem.
Ik wil een functie drawKoch(Point p, Point q, order)
Hierin is p het beginpunt en q het eindpunt (punten hebben een x en een y), order is een integer die aangeeft wel orde getekent moet worden. De functie is recursief. Als order 0 is dan wordt er gewoon een lijn tussen de twee punten getekend. Bij een hogere waarde moeten drie extra punten worden berekend (voor de vorm _/\_). Hier zit het probleem, bij het vinden van het punt boven in de driehoek.
de functie ziet er tot nu toe zo uit:

C++: koch.cpp

 
void drawKoch(Point p, Point q, int order)
{
    if(order>0)
    {
         float dx = q.x - p.x;
         float dy = q.y - p.y;
         float length = sqrt(pow(dx,2) + pow(dy,2));
         float segmentLength = length/3f;
         Point l; //het linkerpunt van de driehoek
         Point r; //het rechterpunt van de driehoek
         Point m; //het middelpunt van de driehoek, hoe te vinden?
         l.x = p.x + dx/3f;
         l.y = p.y + dy/3f;
         r.x = p.x + 2*dx/3f;
         r.y = p.y + 2*dy/3f;
         //en nu dus m.x en m.y bereken. Dit moet onafhankelijk van de hoek 
         //van de lijn pq. Het lukt me gewoon niet meer...

         drawKoch(p, l, n-1);
         drawKoch(l, m, n-1);
         drawKoch(m, r, n-1);
         drawKoch(r, q, n-1);
    }
    else
    {
         glBegin(GL_LINES);
             glVertex2f(p.x, p.y);
             glVertex2f(q.x, q.y);
         glEnd();
    }
}

Een van de dingen die ik probeerde (en geweldig faalde) was om het punt op het midden van de lijn te bereken (punt h) en de afstand van dat punt tot aan punt m. En dan

C++:

m.x = h.x - cos(PI/2 - atan(dy/dx)) * segmentLength;
m.y = h.y + sin(PI/2 - atan(dy/dx)) * segmentLength;

Ik hoop dat een van jullie handig is met geometrie. Ik weet zeker dat de oplossing simpel is want vorige keer heb ik de complete functie in no-time gemaakt. Maar nu ben ik twee dagen bezig en ik zie het gewoon niet...
Voor de duidelijkheid, ik vraag niet of iemand even het programma voor me afmaakt, maar ik denk dat de berekening simpel moet zijn en hoop dat iemand met op weg kan helpen met deze berekening.

Alvast bedankt voor alle input!

[ Voor 3% gewijzigd door sdy op 20-02-2009 17:34 . Reden: uitleg dat het niet een "maak dit eens voor me"-topic is ]

[.oisyn]

Dat hele trigonometrie is niet nodig. Als je een horizontale lijnstuk hebt van (0, 0) naar (1, 0) dan is de delta (1, 0)-(0, 0) = (1, 0). Vervolgens kun je die delta 90 graden draaien zodat hij loodrecht op de lijn staat. Dit kun je simpelweg door (x, y) om te zetten naar (-y, x) (of (y, -x), afhankelijk van welke kant je op wilt draaien en hoe je coordinatenstelsel in elkaar zit).

En dan is het een kwestie van het middelpunt van het lijnstuk te bepalen en vandaaruit 'naar boven' te gaan met de gedraaide delta. De daadwerkelijke hoogte moet je dan weer uitdrukken in de lengte van je lijnstuk.

[sdy]

eehm, ja. Het probleem is dat is dus een x en een y van dat punt moet bereken. Wat jij bedoelt heb ik al ongeveer geprobeerd. Het probleem zit hem in de draaing van het lijnstuk. Als de lijn niet horizontaal loopt dan komt de hoek of aan de verkeerde kant van de lijn, of de hoek is scheef, een meestal beide. Blijkbaar die ik iets fout met het 'naar boven gaan' zoals jij het noemt met de gedraaide delta

[.oisyn]

Je leest niet wat ik zeg . De derde en vierde zin in mijn post. Als ik een vector V=(34, 65) heb en die omzet naar V' = (-65, 34) dan is V' 90 graden gedraaid tov V.

[ Voor 84% gewijzigd door .oisyn op 20-02-2009 17:48 ]

[sdy]

Het klopt wat je zegt. Volgens mij is het eigenlijk zo simpel en denk ik zo moeilijk dat ik hier zelf niet opkwam. Het gebouw waar ik nu zit gaat sluiten. Als ik straks thuis ben ga ik het nog eens proberen. Alvast bedankt, ik laat weten of het gelukt is.

UPDATE:

AARCH, ook al klopt het helemaal wat je zegt. Het gaat toch fantastisch mis. Het probleem is dat ik echt een x en een y coordinaat moet weten van dat punt. En Het lukt me niet om het uit te rekenen. Op papier klopt het allemaal, althans, zo lijkt het. Zou iemand me misschien een voorbeeld van de berekening kunnen laten zien? Ik schaam me diep dat ik zoiets simpels moet vragen, maar ik begin er nu toch echt een beetje depressief van te worden, ik zit maar te malen en denk daarom te moeilijk. Ergo, ik kom er niet uit...

UPDATE 2:
Ik heb de functie nu zo gemaakt dat hij het zou moeten doen (op papier) voor het geval dat dx (delta x) en dy beiden positief zijn. Echter nu komt de hoek er toch scheef op te staan . Als we dan de figuur draaien klopt er helemaal niks van. Dit is de functie tot zover:

C++: koch.cpp

void drawKoch(Point p, Point q, int n)
{
    if(n>0)
    {
        float dx = q.x - p.x;
        float dy = q.y - p.y;
        float length = sqrt(pow(dx, 2) + pow(dy, 2));
        float segmentLength = length/3.0f;
        float alpha = atan(dy/dx);
        float beta = PI/2.0f - alpha;
        float lengthMH = sin(PI/3.0f) * segmentLength;
        Point l;
        Point m;
        Point r;
        Point h;
        l.x = p.x + dx/3.0f;
        l.y = p.y + dy/3.0f;
        r.x = p.x + 2*dx/3.0f;
        r.y = p.y + 2*dy/3.0f;
        h.x = p.x + dx/2.0f;
        h.y = p.x + dy/2.0f;
        m.x = h.x - cos(beta) * lengthMH;
        m.y = h.y + sin(beta) * lengthMH;

        drawKoch(p, l, n-1);
        drawKoch(l, m, n-1);
        drawKoch(m, r, n-1);
        drawKoch(r, q, n-1);
    }
    else
    {
        glBegin(GL_LINES);
            glVertex2f (p.x, p.y);
            glVertex2f (q.x, q.y);
        glEnd();
    }
}

UPDATE 3:
Om te laten zien wat er gebeurt heb ik even een afbeelding gemaakt met daarin de punten (afbeelding is niet 100% correct qua hoeken en afmetingen maar laat zien wat de functie doet):

[ Voor 101% gewijzigd door sdy op 21-02-2009 18:45 . Reden: better image ]

[sdy]

Om even te laten zien wat er nu gebeurt, heb een screenshot gemaakt van het resultaat bij een order van 2. het beginpunt van het lijnstuk aan de linkerkant is punt p en punt q is het einde van het lijnstuk (rechts):

[.oisyn]

Nou ga je toch weer met sin/cos aan de gang.

C++:

         Point l; //het linkerpunt van de driehoek 
         Point r; //het rechterpunt van de driehoek 
         Point m; //het middelpunt van de driehoek 
         l.x = p.x + dx/3f; 
         l.y = p.y + dy/3f; 
         r.x = p.x + 2*dx/3f; 
         r.y = p.y + 2*dy/3f; 

         Point c; // midden van het lijnstuk
         c.x = p.x + dx / 2.f;
         c.y = p.x + dy / 2.f;
         m.x = c.x - dy * hoogte_factor;
         m.y = c.y + dx * hoogte_factor;

Klaar. De waarde van hoogte_factor is in principe de lengte van hm in je figuur tov de lengte pq. Ik neem aan dat je elk sublijnstuk uiteindelijk even lang wilt hebben, en dus lengte ml een derde van pq moet zijn, en dus moet je even met de hand uitrekenen hoe lang mh dan is in termen van pq.

Verder wat opmerkingen:
- pow() is relatief duur, doe gewoon dx*dx als je dx² uit wilt rekenen. Overigens is die hele waarde die je daar uitrekent dus in mijn berekening verder niet nodig.
- de 'f' postfix van floating point getallen mag in principe alleen na de decimale punt komen. Dus "3.f" ipv "3f". VC++ slikt allebei maar "3f" is dus geen standaard C++.

[ Voor 18% gewijzigd door .oisyn op 22-02-2009 16:39 ]