Ellipse kenmerken van SVG naar VML (wiskunde)

[Juup]

Een ellipse(sectie) wordt in SVG (<path d="M0,50 A200,100 0 0,0 200,50 z"/>)gekenmerkt door de volgende kentallen:
x₁: startpunt x
y₁: startpunt y
x₂: eindpunt x
y₂: eindpunt y
a: straal x
b: straal y

In VML (<path v="m100,100 wa0,0 200,100 0,50 200,50x"/>)wordt hij echter gekenmerkt door andere parameters:
left
top
right
bottom
startpunt x
startpunt y
eindpunt x
eindpunt y

Om nu van SVG naar VML te vertalen moet dus de top,left,right en bottom van de "bounding box" van de ellipse berekend worden. (er zijn m.i. 2 mogelijkheden hiervoor, aangenomen dat de ellipse niet "gedraaid" is, dus de assen lopen in de x- of y-richting)
Als ik begin te rekenen:
c: x-verplaatsing van het middelpunt van de ellipse
d: y-verplaatsing van het middelpunt van de ellipse

Basisvergelijking ellipse:


punt 1 en punt 2 invullen en aan elkaar gelijk stellen:


Of andersom:


Hier loopt het een beetje vast. Als ik nu verder ga krijg ik die wortel er niet uit, ook niet als ik de hele vergelijking kwadrateer (dubbelterm blijft wortel hebben). Iemand enig idee hoe nu verder?

[MrBucket]

Ik heb niet de oplossing voor je, maar in plaats van puur vergelijkingen in te vullen en op te lossen misschien de volgende overweging:

Als je van de SVG-vergelijking van de ellipsesectie kan bepalen wat het middelpunt van deze ellipse is, dan heb je je oplossing. Immers, je kan dan met behulp van de SVG-parameters straal-x en straal-y de bounding box bepalen die je nodig hebt voor de VML vergelijking.

-edit-
Morgen meer, ik moet nu weg

[Verwijderd]

Ik lurk al jaren sinds mijn laatste reactie, maar dit probleem kon ik even niet laten schieten

Het lijkt mij vrij eenvoudig: als je a en b weet (de beide stralen), dan is de top-left toch (-a, b) en de bottom-right (a, -b)?
Als je probleem ligt in het feit dat SVG niet aangeeft waar het middelpunt van je ellipse ligt, heb ik hieronder nog een leuke theorie voor je. Onderstaande theorie heb ik ooit eens af moeten leiden, maar het is het resultaat dat telt, nietwaar?

---

Stel, de 2xn matrix C bevat n punten op de eenheidscirkel en de 2x2 matrix A is in de vorm

code:

 [a11 a12
  a12 a22]

Dit vermeld ik alleen voor de volledigheid; niet noodzakelijk
Laat V een matrix zijn met de eigenvectoren van A en L een matrix met de eigenwaarden van A op de diagonaal.
We kunnen nu een ellipse maken door:

V^T sqrt(L) C

Dit resulteert in een ellips georienteerd langs de vectoren van V en geschaald volgens sqrt(L).
Nu zul je je ongetwijfeld afvragen waar dit in vredesnaam heen gaat, maar dat zal ik weldra onthullen.

Neem aan dat de eigenvectoren de e_i vectoren zijn. Ofwel, de x- en y-as. Je weet de beide stralen, a en b, uit je SVG file, dus je L matrix wordt diag{a²,b²}. V is de eenheidsmatrix I₂ (geen gedraaide ellipse).
Om rekenkracht te besparen, neem voor C een klein aantal slim gekozen punten op de eenheidscirkel (bv. 10). Merk op dat de eerste rij van C de x-coordinaten van de eenheidscirkel bevat en de tweede rij de y-coordinaten. Omdat je de x en y coordinaten van het begin en einde van je sectie weet, kan je een aantal punten op de eenheidscirkel zo kiezen zodat deze na bewerking in de buurt of zelfs op je start- en eindpunten komen te liggen.

Goed. We hebben nu V, L en C. Pas de formule E = V^T sqrt(L) C toe (merk op dat V weggelaten kan worden, omdat deze de eenheidsmatrix is) en je krijgt een ellipse in dezelfde vorm als je in je SVG had, maar gecentreerd rond (0,0). Je kan nu aan de hand van je start- en eindpunt bepalen hoeveel je de ellips moet verplaatsen om ze samen te laten vallen.

In combinatie met eerder genoemde opmerking dat als je a en b weet (de beide stralen), de top-left in (-a, b) en de bottom-right (a, -b) liggen weet je de coordinaten van de hoeken van je bounding box.

---

Misschien wat wazige wiskunde, maar het zijn allemaal kleine matrices die je in C++ (of whatever) eenvoudig uit kan schrijven. Je oplossing zal, afhankelijk van je keuze van C en de tijd (lees: rekenkracht) die je tot je beschikking hebt tot op de pixel nauwkeurig kunnen zijn. Merk echter op dat je oplossing niet exact is, maar een benadering van de oplossing is. (edit: mits C goed is gekozen, zal je oplossing exact zijn).
Merk tevens op dat door V anders te kiezen deze theorie ook toepasbaar is op gedraaide ellipsen.
Merk daarnaast op dat het hier nu 12pm is en ik al flink wat bier op heb

[ Voor 1% gewijzigd door Verwijderd op 18-11-2006 05:39 . Reden: Correctie mbt exactheid, typo. ]

[Juup]

Wow sir5, bedankt voor de uitleg. Ht centrum van de ellipse zit inderdaad niet in de oorsprong.
Ik weet eigenlijk alleen niet goed hoe ik hem hier toe moet passen.

Ik heb zelf ook nog e.e.a. gevonden:

Als
x - c = a cosφ
y - d = b sinφ

gebruik, invul en doorreken komt er dit uit:

b²(x₁ - x₂)² + a²(y₁ - y₂)² = a²b² cos(φ₁ + φ₂)

[Verwijderd]

even niet alles doorgelezen en gerekend, maar als je de vergelijking voor je ellips hebt, kun je de extrema uitrekenen door de afgeleiden naar x resp y te pakken en die 0 stellen.

[MrBucket]

Hier loopt het een beetje vast. Als ik nu verder ga krijg ik die wortel er niet uit, ook niet als ik de hele vergelijking kwadrateer (dubbelterm blijft wortel hebben). Iemand enig idee hoe nu verder?

Ik kan je vast uit de droom helpen: deze vergelijking is niet op te lossen (althans, niet in een vorm die nog enigszins bruikbaar is). Ik heb 'm net voor de grap eens ingevuld in een applicatie die wiskundige vergelijkingen op kan lossen, en er komt een resultaat uit met een stuk of 80 termen.

Trouwens, als je 2 punten op een ellipse weet en je weet de straal van deze ellipse in de x- en y-richting, dan zijn er altijd 2 mogelijke ellipsen die door deze punten lopen. Hoe weet je welke van de twee ellipsen je moet hebben?

Wat wil je precies gaan doen met deze conversie van SVG naar VML? Heb je het nodig om 1 enkele instantie van het probleem op te lossen, of ben je bezig met een converter van SVG naar VML? In het laatste geval, in welke taal doe je dat?

Wat evt. nog mogelijk is, is om iets extra's te proberen af te leiden uit de geometrie van het probleem, maar ik zie zo 1, 2, 3 niet echt een ingang hiervoor.

Een andere mogelijkheid op dit probleem op te lossen is om een numerieke benadering te zoeken van het antwoord, m.a.w.: gewoon gokken met parameters en deze stapsgewijs aanpassen zodat je steeds dichter bij het echte antwoord komt.

Functies die je hierbij zou kunnen gebruiken zijn:

code:

ellipse_y(x) = (a*d+(-b^2*x^2+2*b^2*x*c-b^2*c^2+a^2*b^2)^(1/2))/a
en (a*d-(-b^2*x^2+2*b^2*x*c-b^2*c^2+a^2*b^2)^(1/2))/a

ellipse_x(y) = (c*b+(2*a^2*y*d-a^2*d^2-a^2*y^2+a^2*b^2)^(1/2))/b 
en (c*b-(2*a^2*y*d-a^2*d^2-a^2*y^2+a^2*b^2)^(1/2))/b

[ Voor 17% gewijzigd door MrBucket op 18-11-2006 19:11 ]

[Verwijderd]

Juup schreef op zaterdag 18 november 2006 @ 12:02:
Wow sir5, bedankt voor de uitleg. Ht centrum van de ellipse zit inderdaad niet in de oorsprong.
Ik weet eigenlijk alleen niet goed hoe ik hem hier toe moet passen.

En terecht, want bij het schrijven van die tekst had ik een aanname gedaan die bij nader inzien niet waar is. Zo zie je maar weer dat bier en wiskunde niet altijd goed samen gaan
Wat je nog wel kan doen is aan de hand van bovengeschrevene een ellipse tekenen die dezelfde afmetingen heeft als je SVG ellipse, en dan deze gaan 'curve fitten'. Je kan dan, mits je genoeg rekenkracht en -tijd hebt, vrij nauwkeurig uitkomen. Maar dan denk ik dat mophor's oplossing sneller is. Die oplssing is echter alleen werkbaar als je minimaal 2 extrema hebt.

[MrBucket]

Alvast een beginnetje...

C#:

public class Ellipse
{
    public double CenterX;
    public double CenterY;
    public double RadiusX;
    public double RadiusY;

    public Ellipse(double centerX, double centerY, double radiusX, double radiusY)
    {
        CenterX = centerX;
        CenterY = centerY;
        RadiusX = radiusX;
        RadiusY = radiusY;
    }

    public Pair GetYCoordsForX(double x)
    {
        double rxSquared = RadiusX * RadiusX;
        double rySquared = RadiusY * RadiusY;
        double cxSquared = CenterX * CenterX;

        double t = Math.Sqrt(-rySquared*(x*x) + 2*rySquared*x*CenterX - rySquared*cxSquared + rxSquared*rySquared);
        double y1 = (RadiusX*CenterY + t)/RadiusX;
        double y2 = (RadiusX*CenterY - t)/RadiusX;

        return new Pair(y1, y2);
    }

    public Pair GetXCoordsForY(double y)
    {
        double rxSquared = RadiusX * RadiusX;
        double rySquared = RadiusY * RadiusY;
        double cySquared = CenterY * CenterY;

        double t = Math.Sqrt(2*rxSquared*y*CenterY - rxSquared*cySquared - rxSquared*(y*y) + rxSquared*rySquared);
        double x1 = (CenterX*RadiusY + t)/RadiusY;
        double x2 = (CenterX*RadiusY - t)/RadiusY;

        return new Pair(x1, x2);
    }
}

[Juup]

Wat wil je precies gaan doen met deze conversie van SVG naar VML? Heb je het nodig om 1 enkele instantie van het probleem op te lossen, of ben je bezig met een converter van SVG naar VML? In het laatste geval, in welke taal doe je dat?

het gaat om een converter. Ik ben hem nu voor het gemak in javascript aan het doen maar uiteindelijk mak ik hem in xslt denk ik.

Als niets werkt kan ik inderdaad altijd nog de numerieke kant opgaan mar ik kan me niet voorstellen dat de svg jongens een spec hebben gemaakt waarmee ze het zich zo moeilijk maken. Hoe tekenen de huidige SVG renderers dan die curve?
Ik ga nog wat verder puzzelen aan de φ kant.

[MrBucket]

Juup schreef op zondag 19 november 2006 @ 12:12:
[...]

het gaat om een converter. Ik ben hem nu voor het gemak in javascript aan het doen maar uiteindelijk mak ik hem in xslt denk ik.

Dan wordt numerieke interpolatie idd een beetje lastig, ja... het zou wel moeten kunnen, maar het is in ieder geval een stuk moeilijker te implementeren dan een closed form oplossing.

Als niets werkt kan ik inderdaad altijd nog de numerieke kant opgaan mar ik kan me niet voorstellen dat de svg jongens een spec hebben gemaakt waarmee ze het zich zo moeilijk maken. Hoe tekenen de huidige SVG renderers dan die curve?

Je hoeft waarschijnlijk niet per se het middelpunt van de ellipse te weten om 'm te kunnen tekenen.

Overigens, je had natuurlijk allang de (engelse) wiki-pagina bekeken? Daar staan misschien ook nog wat handige eigenschappen op.

[MrBucket]

Verwijderd schreef op zaterdag 18 november 2006 @ 19:49:
Wat je nog wel kan doen is aan de hand van bovengeschrevene een ellipse tekenen die dezelfde afmetingen heeft als je SVG ellipse, en dan deze gaan 'curve fitten'. Je kan dan, mits je genoeg rekenkracht en -tijd hebt, vrij nauwkeurig uitkomen.

Ik realiseer me opeens dat ik al deze tijd al iets heb verondersteld als zijnde 'bekend', terwijl ik het nog niet expliciet in dit topic terug heb zien komen:

Het gaat erom dat we van een ellipse E waarvan de RadiusX en RadiusY bekend zijn, aan de hand van 2 punten p1 en p2 die op E liggen kunnen bepalen waar het middelpunt p0 van E zich bevind. Immers, als je p0 weet, dan is de bounding box van E bepalen een eitje.

Nu, als je een ellipse E1 neemt die als middelpunt p1 heeft en met dezelfde RadiusX en RadiusY, en je neemt nog een ellipse E2 met p2 als middelpunt en weer dezelfde RadiusX en RadiusY, dan snijden E1 en E2 elkaar in twee* punten. En 1 van deze 2 punten is p0 (het middelpunt van E).

Het bepalen van het middelpunt van E komt dus neer op het uitrekenen van de snijpunten van E1 en E2. Als je voor een numerieke interpolatie-aanpak kiest is dit probleem een stuk makkelijker op te lossen dan te gaan gokken met het middelpunt, omdat je nu maar in 1 dimensie hoeft te zoeken.

* = Als p1 en p2 precies 180 graden van elkaar verwijderd liggen heb je maar 1 snijpunt.

[Verwijderd]

MrBucket schreef op zondag 19 november 2006 @ 20:24:
Ik realiseer me opeens dat ik al deze tijd al iets heb verondersteld als zijnde 'bekend', terwijl ik het nog niet expliciet in dit topic terug heb zien komen:

Ik had in den beginne aangenomen dat de getekenden punten op de ellipse bekend waren, maar dat is niet zonder meer waar (je hebt misschien de pixel-coordinaten, maar ik weet niet of dat zo nuutig is).

Het gaat erom dat we van een ellipse E waarvan de RadiusX en RadiusY bekend zijn, aan de hand van 2 punten p1 en p2 die op E liggen kunnen bepalen waar het middelpunt p0 van E zich bevind. Immers, als je p0 weet, dan is de bounding box van E bepalen een eitje.

Nu, als je een ellipse E1 neemt die als middelpunt p1 heeft en met dezelfde RadiusX en RadiusY, en je neemt nog een ellipse E2 met p2 als middelpunt en weer dezelfde RadiusX en RadiusY, dan snijden E1 en E2 elkaar in twee* punten. En 1 van deze 2 punten is p0 (het middelpunt van E).

Het bepalen van het middelpunt van E komt dus neer op het uitrekenen van de snijpunten van E1 en E2. Als je voor een numerieke interpolatie-aanpak kiest is dit probleem een stuk makkelijker op te lossen dan te gaan gokken met het middelpunt, omdat je nu maar in 1 dimensie hoeft te zoeken.

* = Als p1 en p2 precies 180 graden van elkaar verwijderd liggen heb je maar 1 snijpunt.

Dit lijkt mij de beste aanpak, had ik nog niet aan gedacht.

[MrBucket]

Even voortbordurend op het probleem uit mijn vorige post:

Nu, als je een ellipse E1 neemt die als middelpunt p1 heeft en met dezelfde a en b, en je neemt nog een ellipse E2 met p2 als middelpunt en weer dezelfde a en b, dan snijden E1 en E2 elkaar in twee* punten. En 1 van deze 2 punten is p0 (het middelpunt van E).

Ik heb een manier gevonden om dit snijpunt uit te rekenen. Om het onderstaande verhaal wat makkelijker te kunnen uitleggen doe ik twee aannames (maar deze methode werkt evengoed zonder deze aannames):
- We hebben het over ellipsen waarbij a > b (dus zeg maar dezelfde vorm die een bal krijgt als je erop gaat zitten).
- p2 ligt ten noordoosten van p1 (oftewel p1.x < p2.x en p1.y < p2.y).

Als je kijkt naar de formule voor een as-parallele ellipse:

code:

(x - c)^2   (y - d)^2
--------- + --------- = 1   Deze kan herschreven worden naar:
   a^2        b^2

                         a^2
(x - c)^2 + (y - d)^2 * -----  = a^2
                         b^2

Als je de (a^2 / b^2) wegdenkt, dan heb je de formule voor een cirkel met straal a. Met andere woorden: we hebben het hier over een cirkel waarvan de y-as met een factor (a / b) in elkaar is gedrukt. Omgekeerd kunnen we dus alle y-coordinaten van deze ellipse met de omgekeerde factor (b / a) vermenigvuldigen om zo een cirkel te krijgen

Nu, het plan is als volgt:
• Verschuif de middelpunten p1 en p2 met (-p1.x, -p1.y). We noemen deze operatie S, zodat S(p1) = (0, 0) en S(p2) = (p2.x - p1.x, p2.y - p1.y).
• Vermenigvuldig de y-coordinaten van E1 en E2 met een factor (b / a), zodat deze cirkels worden met straal a. (Let wel: dit mag alleen omdat a en b voor beide ellipsen gelijk zijn!). Deze operatie zullen we F noemen, zodat F(E1) een cirkel vormt. (btw: Omdat F(S(p1)) op (0, 0) ligt, snijdt F(S(E1)) de x- en y-as in resp. (a, 0) en (0, a)).
• Reken de 2 snijpunten q1 en q2 van de cirkels F(S(E1)) en F(S(E2)) uit. Dit is nog niet helemaal triviaal, maar hier staat een uitwerking.
• Schaal de 2 snijpunten terug naar hun 'niet-uitgerekte' coordinaten F^-1(q1) en F^-1(q2).
• De echte coordinaten van de snijpunten van E1 en E2 verkrijg je door ook de verschuiving uit stap 1 ongedaan te maken: S^-1(F^-1(q1)) en S^-1(F^-1(q2))

Volgens mij zou dit moeten werken

[ Voor 0% gewijzigd door MrBucket op 20-11-2006 19:36 . Reden: Schaalfactor verbeterd van (b^2 / a^2) naar (b / a) ]

[MrBucket]

Yup, hij werkt _{of althans, lijkt te werken}

Let wel: deze implementatie werkt alleen met as-parallele ellipsen (d.w.z. ellipsen waarvan de grootst mogelijke diagonaal parallel loopt aan de x- of y-as)!

Implementatie:

C#:

/// <summary>
/// Given the radii of an axis-alligned ellipse, and two sample points 
/// p1 and p2 on that ellipse, determines the midpoints of the 2 ellipses
/// that have the given radii and that have p1 and p2 on their boundary.
/// </summary>
public static PointF[] GetEllipseMidpoint(PointF p1, PointF p2, float radiusX, float radiusY)
{
    //1) Displace p1 to origin
    float displacementX = p1.X;
    float displacementY = p1.Y;
    p1 = new PointF(0.0f, 0.0f);
    p2 = new PointF(p2.X - displacementX, p2.Y - displacementY);

    //2) Determine y scale factor and use it to scale p2 with.
    float scaleFactorY = radiusX / radiusY; //(radiusX*radiusX) / (radiusY*radiusY);
    p2.Y = p2.Y * scaleFactorY;

    //3) Treating p1 and p2 as circles with radiusX, get their intersections
    PointF[] intersections = GetCircleIntersections(p1, radiusX, p2, radiusX);
    PointF q1 = intersections[0];
    PointF q2 = intersections[1];

    //4) Scale q1 and q2 back again using the inverse scale factor
    q1.Y = q1.Y / scaleFactorY;
    q2.Y = q2.Y / scaleFactorY;

    //5) Perform the inverse displacement on q1 and q2.
    q1 = new PointF(q1.X + displacementX, q1.Y + displacementY);
    q2 = new PointF(q2.X + displacementX, q2.Y + displacementY);

    return new PointF[]{q1, q2};
}

/// <summary>
/// Given two circles with the specified center points and radii, return 
/// the 2 points in which they intersect.
/// </summary>
public static PointF[] GetCircleIntersections(PointF center1, float radius1, PointF center2, float radius2)
{
    //Let the centers be: (a,b), (c,d)
    //Let the radii be: r, s
    //
    //  e = c - a                          [difference in x coordinates]
    //  f = d - b                          [difference in y coordinates]
    //  p = sqrt(e^2 + f^2)                [distance between centers]
    //  k = (p^2 + r^2 - s^2)/(2p)         [distance from center 1 to line
    //                                      joining points of intersection]
    //  x = a + ek/p + (f/p)sqrt(r^2 - k^2)
    //  y = b + fk/p - (e/p)sqrt(r^2 - k^2)
    //OR
    //  x = a + ek/p - (f/p)sqrt(r^2 - k^2)
    //  y = b + fk/p + (e/p)sqrt(r^2 - k^2)

    float deltaX = center2.X - center1.X;
    float deltaY = center2.Y - center1.Y;
    double pSquared = deltaX * deltaX + deltaY * deltaY;
    double p = Math.Sqrt(pSquared);
    double k = (pSquared + radius1*radius1 - radius2*radius2)/(2 * p);

    PointF q1 = new PointF(0.0f, 0.0f);
    q1.X = (float)(center1.X + deltaX*k/p + (deltaY/p) * Math.Sqrt(radius1*radius1 - k*k));
    q1.Y = (float)(center1.Y + deltaY*k/p - (deltaX/p) * Math.Sqrt(radius1*radius1 - k*k));

    PointF q2 = new PointF(0.0f, 0.0f);
    q2.X = (float)(center1.X + deltaX*k/p - (deltaY/p) * Math.Sqrt(radius1*radius1 - k*k));
    q2.Y = (float)(center1.Y + deltaY*k/p + (deltaX/p) * Math.Sqrt(radius1*radius1 - k*k));

    return new PointF[]{q1, q2};
}

[ Voor 3% gewijzigd door MrBucket op 20-11-2006 19:47 ]

[DroogKloot]

Het lijkt me dat je om goed met niet as-parallele ellipsen om te gaan gewoon nog een extra transformatie R kunt toepassen door na de translatie S even te roteren om de hoek tussen de grootste diagonaal en de x-as, en op de terugweg natuurlijk zijn inverse R^-1 uit te voeren?

[ Voor 18% gewijzigd door DroogKloot op 20-11-2006 20:05 ]

[MrBucket]

DroogKloot schreef op maandag 20 november 2006 @ 20:02:
Het lijkt me dat je om goed met niet as-parallele ellipsen om te gaan gewoon nog een extra transformatie R kunt toepassen door na de translatie S even te roteren om de hoek tussen de grootste diagonaal en de x-as, en op de terugweg natuurlijk zijn inverse R^-1 uit te voeren?

Dat klopt, mits je als gegeven meekrijgt onder welke hoek de ellipse gedraaid is. Als je dit ook zou moeten afleiden uit de radii en de twee punten op de ellipse, dan zijn er in principe een oneindig aantal ellipsen die daaraan voldoen.

[Juup]

Ja dat is het inderdaad.
zeg
y' = y.a/b
d' = d.a/b

als we zoals MrBucket voorstelt de y schalen dan wordt het ineens een stuk makkelijker:

Tadaa.

[ Voor 22% gewijzigd door Juup op 21-11-2006 14:29 . Reden: y' en d' gespecificeerd. En gecorrigeerd naar a/b duh! ]

[Juup]

En dan voor de liefhebbers / het nageslacht / future reference ook nog de uiteindelijke javascript code om de 2 centra te berekenen:

JavaScript:

function getEllipseCenter(x1,y1,x2,y2,a,b)
{
    var asqr = a*a;
    var y1a = y1 * a/b; //y1' op aangepaste schaal waar ellipsen cirkels worden
    var y2a = y2 * a/b; //y2' op aangepaste schaal waar ellipsen cirkels worden
    var deltaX = x2-x1;
    var deltaY = y2a-y1a; //op aangepaste schaal
    var deltaXsqr = deltaX * deltaX;
    var deltaYsqr = deltaY * deltaY;
    var bigroot = Math.sqrt(asqr/(deltaXsqr + deltaYsqr) - 0.25);
    var c1 = 0.5 * (x1 + x2) + bigroot * (y1a - y2a);
    var d1a = 0.5 * (y1a + y2a) + bigroot * (x2 - x1);
    var c2 = 0.5 * (x1 + x2) - bigroot * (y1a - y2a);
    var d2a = 0.5 * (y1a + y2a) - bigroot * (x2 - x1);
    var d1 = d1a * b/a;
    var d2 = d2a * b/a;
    return [c1,d1,c2,d2];
}