Kurvenwindung feststellen, positiv oder negativ

[echo5-7]

Hi,

das hat zugegeben nichts mit Actionscript im speziellen zu tun, gehört aber eher in die Ecke der Programmierung.

Ich grübel mir grade einen ab, wie ich feststellen kann, ob eine Kurve die Richtung ändert. Sprich, erst ist sie linksherum gewunden und dann windet sie sich rechts herum.

Hat dazu irgendjemand ein Snippet, oder besser: eine Erklärung?

Danke
echo

[echo5-7]

ein beispielbild findet ihr im anhang. Gelb sind die Normalen, Pink sind die um 180° gedrehten Normalen, und Hellgrau die Winkelhalbierenden.

Was ich möchte, ist die Winkelhalbierenden alle auf einer "Seite" der Kurve haben. Die Normalen sind ja schließlich auch da. Im Moment versuche ich noch per if-Abfrage das Problem zu lösen, aber das scheint mir wohl nicht der Weißheit letzter Schluss zu sein.

[hgseib]

die ecken der strecke plus das ende deiner winkelhalbierenden sind drei punkte, das ergibt ein dreieck.

H.G.Seib
Flächenberechnung in der Ebene
Wenn die Punkte nicht 'rechts herum' durchnummeriert werden, dann wird der Flächeninhalt als Negativ ausgegeben.

// abc sind drei punkte
function fPoly_flaeche3Eck(a, b, c)
{ return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))/2;
}

sinngemäss das selbe
http://www.seibsprogrammladen.de/fra.../Schnittpunkte
fGross:
Kreuzprodukt für 2D. Gibt -1 bzw. 1 zurück. je nachdem, ob die Fläche nach oben oder nach unten orientiert ist.
d.h. ob die Punkte links- oder rechtsherum durchnummeriert sind.

function fCross(a, b, c) {
 return ((a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x)<0) ? -1 : 1;
}

[echo5-7]

ok, ich kapiere was die funktionen machen, aber kann es sein, dass ich die punkte automatisch übergeben muss? dh. wenn ich die punkte willkürlich übergebe, dann kommt dabei was willkürliches raus?

ich muss das grade mal durchtesten.

edit: ok, funzt irgendwie kapier ich's immer noch nicht ganz, aber hauptsache es geht erstmal. danke dir!

[hgseib]

du gehst deinen linienzug kante für kante durch, da hast du punkt a und b
du berechnest wie jetzt auch deine mittelsenkrechte, das ende ist punkt c
jetzt fCross aufrufen.
ist der rückgabewert 1, dann die mittelsenkrechte in die andere richtung zeichnen.
ist der rückgabewert -1, dann zur nächsten kante.
nächste kante. das vorhergehende b ist jetzt punkt a, punkt b kommt neu dazu.

[echo5-7]

hmmmmm... ich habs jetzt mit dem flächeninhaltsdingens gelöst. und mir ist klar, dass es negativ werden muss, wenn was negatives dabei ist... aber das das funktioniert ist immer noch erstaunlich

[hgseib]

ja,
programmieren ist ein wunder
mathe ist ein wunder
das leben ist ein wunder

wen wunderts ;-)

[echo5-7]

^^

[echo5-7]

ok, es gibt doch noch probleme, die mir aber nicht so ganz klar sind. im anhang ist ein bild des ausgeführten codes. es funktioniert soweit ganz gut, nur dass es ab und an zu einem unerwünschten flip kommt.

die funktion sieht so aus:

		private function schnittchen ():void {
			
			// Richtungsvektor von P2 aus
			var rv1 : Point = new Point();
			rv1.x = (p2.x - p1.x)*-1;
			rv1.y = (p2.y - p1.y)*-1;
			
			var rv2 : Point = new Point();
			rv2.x = (p2.x - p3.x)*-1;
			rv2.y = (p2.y - p3.y)*-1;
			
			// einheitsvektoren 
			var ev1:Point = new Point();
			ev1.x = (rv1.x / Math.sqrt(rv1.x * rv1.x + rv1.y * rv1.y)) ;
			ev1.y = (rv1.y / Math.sqrt(rv1.x * rv1.x + rv1.y * rv1.y)) ;
			
			var ev2:Point = new Point();
			ev2.x = (rv2.x / Math.sqrt(rv2.x * rv2.x + rv2.y * rv2.y)) ;
			ev2.y = (rv2.y / Math.sqrt(rv2.x * rv2.x + rv2.y * rv2.y)) ;
			
			// winkelhalbierende
			w = new Point();
			w.x = ev1.x + ev2.x;
			w.y = ev1.y + ev2.y;
			
			// normale und gegennormale auf w  
			var wn : Point = new Point();
			var cwn : Point = new Point();
			
			if (w.x != 0 && w.y != 0) {
				
				wn.x  = (radius / Math.sqrt(w.x * w.x   + w.y*w.y)) *  w.x ;
				wn.y  = (radius / Math.sqrt(w.x * w.x   + w.y*w.y)) *  w.y ;
				cwn.x  =  wn.x*-1;
				cwn.y  =  wn.y * -1;
				
			} else {
				
				w.x = (p1.y-p3.y) *-1 ;
				w.y = p1.x - p3.x ;				
				
				wn.x  = (radius / Math.sqrt(w.x * w.x   + w.y * w.y)) *  w.x ;
				wn.y  = (radius / Math.sqrt(w.x * w.x   + w.y * w.y)) *  w.y ;
				
				cwn.x  =  wn.x*-1;
				cwn.y  =  wn.y*-1;
				
			}
			
			// orientierung feststellen
			
			if (fPoly_flaeche3Eck(p3, p2, p1) <= 0 ) {
				
				trace("x poly: " + (fPoly_flaeche3Eck(p1, p2, p3) < 0?"" + fPoly_flaeche3Eck(p1, p2, p3):" " + fPoly_flaeche3Eck(p1, p2, p3)) +" w " + w.x + "/" + w.y + " wn: " + wn.x + "/" + wn.y + " cwn: " + cwn.x + "/" + cwn.y );
				
				canvas.graphics.lineStyle(1, 0xCC0000, 1);
				canvas.graphics.moveTo( p2.x + wn.x,  p2.y + wn.y);
				canvas.graphics.lineTo( p2.x , p2.y );
				canvas.graphics.lineStyle(1, 0x00CC00, 1);
				canvas.graphics.lineTo( p2.x + cwn.x, p2.y + cwn.y);
				
			} else {
				
				trace("x poly: " + (fPoly_flaeche3Eck(p1, p2, p3) < 0?"" + fPoly_flaeche3Eck(p1, p2, p3):" " + fPoly_flaeche3Eck(p1, p2, p3)) +" w " + w.x + "/" + w.y + " wn: " + wn.x + "/" + wn.y + " cwn: " + cwn.x + "/" + cwn.y );
				
				canvas.graphics.lineStyle(1, 0xCC0000, 1);
				canvas.graphics.moveTo(p2.x + cwn.x,  p2.y + cwn.y);
				canvas.graphics.lineTo(p2.x , p2.y );
				canvas.graphics.lineStyle(1, 0x00CC00, 1);
				canvas.graphics.lineTo(p2.x + wn.x, p2.y + wn.y);	
				
			}
		}

in den anhang habe ich alle klassen gepackt, so dass man das auch ausprobieren kann.

was mir aufgefallen ist:

jedesmal wenn die orientierung/fläche des dreiecks = 0 ist, kommt es zum flip. woran kann das jetzt liegen?

danke
echo

[hgseib]

ich gucke mal nach. kann allerdings etwas dauern, ist ja ne menge script.

und wieso hast du flächen mit 0 ??? das kann es garnicht geben. dann sind 2 punkte identisch somit gibt es garkeine linie auf deren hälfte du das lot setzt.

[echo5-7]

danke dir

das ist die frage, eigentlich sollte es diese flächen mit 0 nicht geben. ich kann mir nur vorstellen, dass die 3 punkte in einer reihe liegen und dadurch dann eine 0 zustande kommt.... was irgendwie auch das problem erklären würde... sekunde, ich guck nochmal nach.


edit: das problem liegt eigentlich nur in der Main.as... alles andere ist Beiwerk und funktioniert so wie es soll.

ich hab grade noch mal geguckt, wenn ich ne abfrage für die fläche 0 in diesen schnipsel mit einbaue, drehts mir zwar alles um, aber das zumindestens konstant ^^

if (w.x != 0 && w.y != 0
nach
if (w.x != 0 && w.y != 0 && fPoly_flaeche3Eck(p3, p2, p1) != 0

edit2: wer lesen kann ich klar im vorteil, hast du ja schon geschrieben

[thomas_E]

dürfte ich wohl deinen Code etwas zusammenfassen?

PHP-Code:

//1:
var rv1 : Point = p1.subtract(p2);
var rv2 : Point = p2.subtract(p3);
var ev1:Point = rv1.clone();
    ev1.normalize();
    
var ev2:Point = rv2.clone();
    ev2.normalize();

w = new Point(ev1.x + ev2.x, ev1.y + ev2.y);

// normale und gegennormale auf w  
var wn : Point = w.clone();
    wn.normalize(radius);
var cwn : Point = new Point(-wn.x, -wn.y);
//... 


PHP-Code:

//2:
w = ev1+ev2         //ev1.length = ev2.length = 1 => w.length = 2
w = p1-p2 + p2-p3    //todo normalize to length=2
w = p1-p3            //...
w *= 2/w.length;

//wn = w rotated by 90° and normalized to a length of "radius"
wn.x = w.y;
wn.y = -w.x;
wn *= radius/wn.length;
cwn = -wn; 


PHP-Code:

//3 (final):
private function schnittchen ():void {
    var wn:Point = new Point(p1.y-p3.y, p3.x-p1.x);
        wn.normalize(radius);
    canvas.graphics.lineStyle(1, 0xCC0000, 1);
    canvas.graphics.moveTo( p2.x + wn.x,  p2.y + wn.y);
    canvas.graphics.lineTo( p2.x, p2.y );
    canvas.graphics.lineStyle(1, 0x00CC00, 1);
    canvas.graphics.lineTo( p2.x - wn.x, p2.y - wn.y);
} 


[echo5-7]

oha, danke schön was für ein service