Test, ob 4 Punkte konvexes Viereck bilden ?
Malte Lance
hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
Ich bin fuer jede Idee und jeden Hinweis dankbar.
Malte.
--
Malte Lance.
Steffen Wolf
du fragtest:
nur eine Idee:
(und auch nicht sehr ausgereift, aber vielleicht kennt jemand dies und
kann es weiterführen)
Viereck:
a---b
| \
c-----d
Man greife sich zwei der 4 Punkte, die Gerade hierdurch teilt R^2 in
zwei Halbebenen.
2 Fälle:
a: die beiden anderen Punkte befinden sich in derselben Halbebene
b: oder in zwei verschiedenen.
Nun nimmt man die anderen 2 Punkte, Gerade-Halbebene wie gewohnt
auch 2 Fälle
I: selbe
II: oder verschiedene
Fall IIb und Ia zeichnen konvexe Vierecke aus
Fall IIa und Ib zeichnen konkave Vierecke aus.
Mag sein, daß ich mich komplett irre. Aber die Idee dahinter ist
folgende:
b
a--+--c
d
konvex Fall IIa
b
a \
\ c
d
konvex Fall Ib
b
a----c-+-
d
konkav Fall Ib oder IIa
Den math. Beweis überlasse ich anderen, aber die programmtechnische
Umsetzung kann ich noch erläutern:
Zweipunktegleichung für Geraden oder gleich y=mx+n aufstellen.
Umwandeln in eine Ungleichung -> y<=mx+n o.so
Schon hast du den Test, ob ein gegebener Punkt auf einer best.
Halbebene liegt.
Zwei Tests ergeben gleiche HE oder verschiedene - und mehr muß man nicht
wissen.
viel Spaß beim Beweisen (oder Widerlegen)
cu,
stw
Rainer Rosenthal
Malte Lance <malte...@gmx.net> wrote in message
news:8oqe25$f46$18$1...@news.t-online.com...
| Hi,
|
| hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
| Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
| der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
|
Hallo Malte,
vorausgesetzt, Du hast eine Methode zum Feststellen, ob ein Punkt
P ausserhalb eines Dreiecks liegt, kannst Du den Test so durch-
führen:
Die vier Punkte A, B, C, D bilden die Ecken eines konvexen Vier-
ecks in der Ebene ganau dann, wenn gilt:
A liegt ausserhalb von Dreieck(B,C,D) und
B liegt ausserhalb von Dreieck(A,C,D) und
C liegt ausserhalb von Dreieck(A,B,D) und
D liegt ausserhalb von Dreieck(A,B,C)
Klingt auf Anhieb vielleicht etwas plump, ist aber eine saubere
Sache. Das Grundproblem ist elegant in kleinere Probleme
aufgeteilt.
In deinem nächsten Posting kannst Du dann ja fragen:
"Wie teste ich, ob ein Punkt ausserhalb eines Dreiecks liegt ?"
Die Gedanken von Steffen Wolf sind da sicher hilfreich.
Gruss
Rainer
--------------------------------------------------
P.S. Ich erinnere mich, dass ich mal mit Turbo-C einen
sich drehenden Würfel programmiert habe. Und da war
ich eine Weile beschäftigt, ein Kriterium zu finden, nach
dem ich die versteckten Kanten ermitteln konnte. Ich
wollte sie nur gestrichelt bzw. dünner zeichnen. Das hat
nach einer ganz ähnlichen Teile-und-herrsche-Strategie
funktioniert und ich habe mich sehr gefreut, wie die gute
alte Mathematik dem Rechner das "Sehen" beibrachte.
Florian Wessels
wrote:
>hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
Wenn es zwei Punktepaare (p1,p2), (p3,p4) gibt, so dass
sich L(p1,p2), L(p3,p4) im Innern schneiden. (L(x,y) Strecke
zwischen x,y)
----
Florian Wessels
florian...@deleteThis.math.uni-muenster.de
PGP-Schluessel erhaeltlich unter http://www.muenster.de/~fwessels
Jens Voss
>
> Malte Lance <malte...@gmx.net> wrote in message
> news:8oqe25$f46$18$1...@news.t-online.com...
> | Hi,
> |
> | hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
> | Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
> | der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
> |
>
> Hallo Malte,
>
> vorausgesetzt, Du hast eine Methode zum Feststellen, ob ein Punkt
> P ausserhalb eines Dreiecks liegt, kannst Du den Test so durch-
> führen:
>
> Die vier Punkte A, B, C, D bilden die Ecken eines konvexen Vier-
> ecks in der Ebene ganau dann, wenn gilt:
>
> A liegt ausserhalb von Dreieck(B,C,D) und
> B liegt ausserhalb von Dreieck(A,C,D) und
> C liegt ausserhalb von Dreieck(A,B,D) und
> D liegt ausserhalb von Dreieck(A,B,C)
>
> Klingt auf Anhieb vielleicht etwas plump, ist aber eine saubere
> Sache. Das Grundproblem ist elegant in kleinere Probleme
> aufgeteilt.
>
> In deinem nächsten Posting kannst Du dann ja fragen:
> "Wie teste ich, ob ein Punkt ausserhalb eines Dreiecks liegt ?"
>
Dreiecks") habe ich vor gut einem Jahr beantwortet; wer Lust hat,
kann ja bei deja.com in dsm nach dem Thread "Analytische Geometrie"
vom 24.-26. August 1999 suchen.
Schönen Gruß,
Jens
Rainer Rosenthal
Jens Voss <je...@poet.de> wrote in message news:39B1200D...@poet.de...
| >
| Diese Frage (bzw. die Frage "Wann liegt ein Punkt innerhalb eines
| Dreiecks") habe ich vor gut einem Jahr beantwortet; wer Lust hat,
| kann ja bei deja.com in dsm nach dem Thread "Analytische Geometrie"
| vom 24.-26. August 1999 suchen.
|
das ist ja das Gemeine an diesen Matheaufgaben: Sie
verlangen irgendwie, dass man sie weiter bearbeitet.
Die folgenden Gedanken muss ich erst noch loswerden,
bevor ich mir die Jens-Seite anschaue.
Die Frage war ja:
Wann liegt Punkt P ausserhalb von Dreieck(A,B,C) ?
Dazu habe ich mir den Schwerpunkt S = (1/3)*(A+B+C)
hergenommen, der ja sicher innerhalb des Dreiecks liegt.
Und dann kann ich sagen:
P liegt genau dann ausserhalb von Dreieck(A,B,C),
wenn gilt:
PS schneidet AB oder
PS schneidet AC oder
PS schneidet BC
Damit der Beitrag nicht zu lang wird, und weil dies ein prima
Ergebnis ist, höre ich hier auf.
Ich werde es mir aber nicht verkneifen, dieses Schneide-Thema
im nächsten Beitrag zu behandeln.
Gruss,
Rainer
--------------------------------------------------
A----------B P----------------S
Malte Lance
"Rainer Rosenthal" <r.ros...@ngi.de> writes:
>
> Malte Lance <malte...@gmx.net> wrote in message
> news:8oqe25$f46$18$1...@news.t-online.com...
>| Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>| der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Hallo Malte,
Hi Rainer,
> vorausgesetzt, Du hast eine Methode zum Feststellen, ob ein Punkt
> P ausserhalb eines Dreiecks liegt,
Sei p \in R^2 Testpunkt, p_1, p_2, p_3 \in R^2 Ecken eines Dreiecks.
Loese System (z.B. mit Cramer-Regel):
a p_1 + b p_2 + c p_3 = p
a + b + c = 1
mit a, b, c \in R.
Fuer a, b, c \in [0,1] liegt p im Inneren oder auf dem Rand des
Dreiecks mit Eckpunkten p_1, p_2, p_3; ansonsten liegt p ausserhalb.
Geht das so ? Oder gibt es da vielleicht eine elegantere Methode
(ohne auf 'Orientierung' zurueckzugreifen) ?
> kannst Du den Test so durch-
> führen:
>
> Die vier Punkte A, B, C, D bilden die Ecken eines konvexen Vier-
> ecks in der Ebene ganau dann, wenn gilt:
>
> A liegt ausserhalb von Dreieck(B,C,D) und
> B liegt ausserhalb von Dreieck(A,C,D) und
> C liegt ausserhalb von Dreieck(A,B,D) und
> D liegt ausserhalb von Dreieck(A,B,C)
>
> Klingt auf Anhieb vielleicht etwas plump, ist aber eine saubere
> Sache. Das Grundproblem ist elegant in kleinere Probleme
> aufgeteilt.
Ja, anschaulich ist das sofort klar. Hast Du vielleicht eine
Beweisidee, wie man zeigen kann, dass diese Bedingung(en)
notwendig und hinreichend dafuer sind, dass vier Punkte in der
Ebene Ecken eines konvexen Vierecks sind ?
> In deinem nächsten Posting kannst Du dann ja fragen:
> "Wie teste ich, ob ein Punkt ausserhalb eines Dreiecks liegt ?"
Wie teste ich, ob ein Punkt ausserhalb eines Dreiecks liegt ?
(ohne auf 'Orientierung' zurueckzugreifen)
> Die Gedanken von Steffen Wolf sind da sicher hilfreich.
>
> Gruss
> Rainer
Malte
--
Malte Lance.
Malte Lance
Jens Voss <je...@poet.de> writes:
> Rainer Rosenthal wrote:
>>
>> Malte Lance <malte...@gmx.net> wrote in message
>> news:8oqe25$f46$18$1...@news.t-online.com...
>> | Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>> | der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>>
>> P ausserhalb eines Dreiecks liegt, kannst Du den Test so durch-
>> führen:
>>
> Dreiecks") habe ich vor gut einem Jahr beantwortet; wer Lust hat,
> kann ja bei deja.com in dsm nach dem Thread "Analytische Geometrie"
> vom 24.-26. August 1999 suchen.
Gefunden und gelesen.
Problematisch (bilde ich mir zumindest ein):
Du benutzt in Deinen Formeln implizit den Begriff der Orientierung.
Du vermeidest es, ihn explizit zu nennen, indem Du alle Ergebnisse
fuer beide moeglichen Orientierungen aufzaehlst.
Wolltest Du erklaeren, warum Dein Verfahren funktioniert, kaemest
Du nicht um eine Erklaerung von 'Orientierung' herum. Bei einer
Orientierung im mathematisch positiven Sinn, muessen d_1, d_2, d_3
alle positiv sein, damit der betrachtete Punkt im Inneren oder auf
dem Rand des Dreiecks liegt. Bei umgekehrter Orientierung muessen sie
alle negativ sein, damit der betrachtete Punkt im Inneren oder auf dem
Rand des Dreiecks liegt.
Hm, ... vieleicht habe ich auch nur eine zu eingeengte Sichtweise.
Malte
--
Malte Lance.
Hermann Kremer
Malte Lance schrieb in Nachricht <8oqe25$f46$18$1...@news.t-online.com>...
Hallo Malte,
das Viereck A1-B1-C1-D1
D1
A1 C1
B1
ist konvex, das Viereck A2-B2-C2-D2
D2
A2 C2
B2
ist konkav. Wenn Du jetzt die Diagonalen Ax-Cx und Bx-Dx
einzeichnest und Flächen betrachtest, dann gilt für das
konvexe Viereck:
Fläche(Dreieck A1-C1-B1) + Fläche(Dreieck A1-C1-D1) =
= Fläche(Dreieck B1-D1-A1) + Fläche(Dreieck B1-D1-C1) =
= Viereckfläche.
konkave Viereck:
Fläche(Dreieck A2-C2-B2) + Fläche(Dreieck A2-C2-D2) =
= Fläche(Dreieck B2-D2-A2) - Fläche(Dreieck B2-D2-C2)
d.h. beim konvexen Viereck sind die beiden Dreiecksflächensummen
gleich, beim konkaven ungleich -- aber Achtung falls B2,C2,D2 auf
einer Linie liegen ....
Dreiecksflächen kann man mittels der Heron´schen Formel
nur aus den Dreiecksseiten berechnen ...
Vielleicht hilft Dir das ...
Grüße
Hermann
--
>Malte.
>
>--
>Malte Lance.
Rainer Rosenthal
| ...wie man testen kann, ob vier Punkte im R^2 | Ecken eines konvexen
| Vierecks sind, ohne dabei auf den Begriff | der 'Orientierung' bzw.
| 'orientierte Basis' zurueckzugreifen ?
|
Hallo Malte,
so gut mir die bisherige Herleitung mit ihren UND's und ODER's
auch gefällt, ich habe jetzt was richtig tolles gefunden.
Es steht ja noch das Kriterium aus, um festzustellen ob sich zwei
Strecken AB und CD mit gegebenen Endpunkten A, B, C, D
schneiden.
Mit diesem Kriterium ist aber die Ursprungsaufgabe ganz einfach
zu lösen !
Ich erfinde mal schnell folgende Notation:
AB (=) CD bedeutet, dass sich AB und CD nicht schneiden,
AB (x) CD bedeutet, dass sich AB und CD schneiden.
Betrachte ich ein KONVEXES Viereck, dann habe ich mindestens zwei
sich schneidende Strecken (die Diagonalen).
Ein NICHT KONVEXES Viereck hat keine sich schneidenden Diagonalen,
hier gilt immer:
AB (=) CD und AC (=) BD und AD (=) BC
Ich stoppe hier, weil die Info für einen Beitrag stark genug ist.
Als nächstes dann der fertige Formelkram.
Gruss,
Rainer
------------------------------------------------------------
444444444444456777654444444444444
Rainer Rosenthal
| ...wie man testen kann, ob vier Punkte im R^2 | Ecken eines konvexen
| Vierecks sind, ohne dabei auf den Begriff | der 'Orientierung' bzw.
| 'orientierte Basis' zurueckzugreifen ?
|
Hallo Malte,
basierend auf dem im letzten Beitrag angegebenen Gedanken
habe ich die Geschichte nicht nur theoretisch fertig gemacht
sondern vorsichtshalber gleich noch programmiert.
Rein: Die vier Punktei
Raus: "konvex" oder "nicht konvex".
Kernstück ist die Funktion "Schneidet", der man die Endpunkte
P und Q der einen Strecke sowie die Endpunkte R und S der
anderen Strecke eingibt und die dann den Wert 1 liefert, wenn
die Strecken sich schneiden, sonst liefert sie den Wert 0.
Das Programm macht dann den Test:
Schneidet( AB CD) oder
Schneidet( AD BC) oder
Schneidet( AC BD)
und meldet "konvex" im Ja-Fall, "nicht konvex" im Nein-Fall.
Die Schneide-Technik basiert auf folgender Überlegung:
Ich parametrisiere die Strecke PQ als P + t * ( Q - P).
Ich parametrisiere die Strecke RS als R + u * ( S - R).
Es gibt genau dann einen Schnittpunkt, wenn ich t und u im
abgeschlossenen Intervall [0,1] finde mit
P + t * ( Q - P) = R + u * ( S - R)
Bringe ich die x- und y-Koordinaten ins Spiel, dann läuft das
auf folgendes lineares Gleichungssystem hinaus:
( xQ-xP xR-xS ) ( t ) ( xR-xA )
( ) ( ) = ( )
( yQ-yP yR-yS ) ( u ) ( yR-yA )
Die Auflösung der Gleichung mittels Determinante und Inverser
Matrix wird vom Programm erledigt, wobei auf "entartete Vierecke"
hingewiesen wird, die als "konvex" bezeichnet werden.
Zuerst ein Beispiel-Lauf des Programms, dann der Code.
Für das Beispiel wurden Testausgaben in den Code eingefügt.
Testausgaben und GetPoints()-Funktion sind weggelassen in
dem angegebenen C-Quellcode.
Das Beispiel ( Programmasugaben mitgeschrieben):
Vorgelegtes Viereck hat die Punkte
A 0.0000 0.0000
B 1.0000 0.0000
C 2.0000 2.0000
D 0.0000 1.0000
Schneidet ( 0.00, 0.00)-( 1.00, 0.00)
dies: ( 2.00, 2.00)-( 0.00, 1.00)
t=-2.000000 u=2.000000
Nein
Schneidet ( 0.00, 0.00)-( 0.00, 1.00)
dies: ( 1.00, 0.00)-( 2.00, 2.00)
t=-2.000000 u=-1.000000
Nein
Schneidet ( 0.00, 0.00)-( 2.00, 2.00)
dies: ( 1.00, 0.00)-( 0.00, 1.00)
t=0.250000 u=0.500000
Ja
Das vorgelegte Viereck ist konvex
Der Programmcode ( Simples C). Weil meine fabs()-Funktion
gesponnen hat (oder ich ? Es ist ja wieder irre spät !), habe ich
die Determinanten-Prüfung etwas umständlich gemacht.
double Det( double a11, double a12, double a21, double a22)
{
return a11*a22 - a21*a12;
}
int Schneidet( double xP, double yP,
double xQ, double yQ,
double xR, double yR,
double xS, double yS)
{
int erg;
double d, t, u;
double g, a;
d = Det( xQ-xP, xR-xS, yQ-yP, yR-yS);
g = 0.000001;
if ( d < 0) {
a = -d;
} else {
a = d;
}
if ( a < g) {
fprintf( stderr, "Entartetes Viereck\n");
erg = 1;
} else {
t = ( (yR-yS)*(xR-xP) - (xR-xS)*(yR-yP)) / d;
u = ( (yR-yP)*(xQ-xP) - (xR-xP)*(yQ-yP)) / d;
if ( t < 0 || t > 1 || u < 0 || u > 1) {
erg = 0;
} else {
erg = 1;
}
}
return erg;
}
main()
{
if ( GetPoints()) {
printf( "Vorgelegtes Viereck hat die Punkte\n");
printf( "A %7.4lf %7.4lf\n", xA, yA);
printf( "B %7.4lf %7.4lf\n", xB, yB);
printf( "C %7.4lf %7.4lf\n", xC, yC);
printf( "D %7.4lf %7.4lf\n", xD, yD);
if ( Schneidet( xA, yA, xB, yB, xC, yC, xD, yD) ||
Schneidet( xA, yA, xD, yD, xB, yB, xC, yC) ||
Schneidet( xA, yA, xC, yC, xB, yB, xD, yD))
{
printf( "Das vorgelegte Viereck ist konvex\n");
} else {
printf(
"Das vorgelegte Viereck ist nicht konvex\n");
}
} else {
fprintf( stderr,
"Viereckspunkte A, B, C, D nicht lesbar\n");
}
return 0;
}
Alles in allem bin ich sehr zufrieden und haue mich jetzt auf's Ohr.
Gruss,
Rainer
---------------------------------------------------------------
33333333333333333334566665433333333
Helmut Kahovec
>| hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>| Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>| der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
Hallo Malte!
Eine Möglichkeit ist, mit Kanonen auf Spatzen zu schießen: Du bestimmst
zuerst das Convex Hull {H} der vier Punkte {P} und siehst nach, ob die
Mengendifferenz {P}-{H} gleich der leeren Menge {} ist. Diese Methode
hat den Vorteil, daß sie sofort auch auf mehr als vier Punkte anwendbar
ist.
Einen leicht zu implementierenden Algorithmus für das Convex Hull
findest Du in [1] auf Seite 845 oben. Es ist der Graham Scan, der bei n
Punkten eine Laufzeit von O(n*log(n) besitzt, die sich hauptsächlich
durch das geeignete Sortieren der Punkte ergibt.
Eine Implementierung des Graham Scan in maple6 findest Du im Anhang.
MfG, Helmut
---------------------------------------------------------------------
> restart;
Der nächste Befehl gewährleistet die Reproduzierbarkeit der Daten dieser
maple6 Session:
> randomize(967936858):
Wir definieren zuerst unseren Random Number Generator
> r:=rand(0..10):
und die Prozedur, die uns einen Zufallspunkt im Quadrat |x|<=10,|y|<=10
erzeugt:
> rpoint:=proc() [r()-5,r()-5] end:
Beachte, daß der nächste Befehl nur neun verschiedene Punkte generiert:
> points:=[op({seq(rpoint(),i=1..10)})];
points := [[-5, 1], [5, -5], [3, -2], [-5, 5], [-3, 5], [-3, 3],
[0, -2], [-5, -4], [1, 4]]
Wir bilden die Plotstruktur für die Darstellung dieser neun Punkte als
kleine Kreise in der Farbe Blau:
> p1:=plot(points,style=point,symbol=circle,color=blue):
Die folgende Prozedur ist die Implementierung des Graham Scan in maple6:
> GrahamScan:=proc(points::listlist)
> local p0,p,i,l,h,j,k;
> p0:=[infinity,infinity];
> for p in points do if p[2]<p0[2] then p0:=p end if end do;
> l:=map(
> u->[evalf(arctan(u[2]-p0[2],u[1]-p0[1])),u],
> remove(u->evalb(u=p0),points)
> );
> l:=sort(l,(u,v)->evalb(u[1]<v[1]));
> l:=[op(map2(op,2,l)),p0];
> h:=l[-1],l[1];
> j:=2;
> for i from 2 to nops(l) do
> while (h[j][1]-h[j-1][1])*(l[i][2]-h[j][2])-
> (l[i][1]-h[j][1])*(h[j][2]-h[j-1][2]) < 0
> do j:=j-1 end do;
> j:=j+1;
> h:=seq(h[k],k=1..j-1),l[i]
> end do;
> [op(1..-2,[h])]
> end proc:
Nun bilden wir die Plotstruktur für die Darstellung des Convex Hull als
kleine Kreise in der Farbe Rot:
> p2:=plot(GrahamScan(points),style=point,symbol=circle,color=red):
Unsere neun Punkte stellen keine konvexe Punktmenge dar:
> evalb({op(points)} minus {op(GrahamScan(points))}={});
false
Dies können wir unmittelbar sehen, wenn wir die beiden Plotstrukturen
gemeinsam in einer Grafik darstellen:
> plots[display]([p2,p1]);
Im folgenden sind noch weitere Beispiele mit jeweils vier Punkten
angeführt:
> points:=[op({seq(rpoint(),i=1..4)})];
> evalb({op(points)} minus {op(GrahamScan(points))}={});
> plot(points,style=point,symbol=circle);
points := [[-1, 3], [2, 5], [5, 3], [1, 4]]
false
> points:=[op({seq(rpoint(),i=1..4)})];
> evalb({op(points)} minus {op(GrahamScan(points))}={});
> plot(points,style=point,symbol=circle);
points := [[0, -4], [2, 3], [1, -2], [-5, -4]]
true
> points:=[op({seq(rpoint(),i=1..4)})];
> evalb({op(points)} minus {op(GrahamScan(points))}={});
> plot(points,style=point,symbol=circle);
points := [[2, 2], [-3, 3], [0, 5], [0, 3]]
false
> points:=[op({seq(rpoint(),i=1..4)})];
> evalb({op(points)} minus {op(GrahamScan(points))}={});
> plot(points,style=point,symbol=circle);
points := [[0, 1], [-5, 4], [4, 0], [5, 4]]
true
---------------------------------------------------------------------
Referenz:
[1] K.H. Rosen (editor), "Handbook of Discrete and Combinatorial
Mathematics", CRC Press 2000, ISBN 0-8493-0149-1
Malte Lance
Helmut Kahovec <helmut....@teleweb.at> writes:
> Malte Lance wrote:
>
>>| hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>>| Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>>| der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Hallo Malte!
Hallo Helmut,
> Eine Möglichkeit ist, mit Kanonen auf Spatzen zu schießen: Du bestimmst
> zuerst das Convex Hull {H} der vier Punkte {P} und siehst nach, ob die
> Mengendifferenz {P}-{H} gleich der leeren Menge {} ist. Diese Methode
> hat den Vorteil, daß sie sofort auch auf mehr als vier Punkte anwendbar
> ist.
Bei mir soll der Test immer nur fuer genau 4 Punkte durchgefuehrt werden.
Weiterhin muss ich diesen Test einige tausend Mal durchfuehren. Das ist
dann tatsaechlich ein Schiessen mit Kanonen (A-Bomben fuer die
martialische Variante ;) auf Spatzen.
> Einen leicht zu implementierenden Algorithmus für das Convex Hull
> findest Du in [1] auf Seite 845 oben. Es ist der Graham Scan, der bei n
> Punkten eine Laufzeit von O(n*log(n) besitzt, die sich hauptsächlich
> durch das geeignete Sortieren der Punkte ergibt.
Wenn ich mich nicht falsch erinnere, dann benutzt der Graham-Scan
auf jeden Fall den Begriff der Orientierung. Die Winkel werden im
Uhrzeigersinn oder gegen den Uhrzeigersinn sortiert (fuer die
initiale Sortierung der Punkte) und spaeter (im sweep-Schritt) wird
jeweil ein Punkt ((i-1) Vorgaengerpunkt) auf Lage (links
oder rechts) bezueglich der orientierten Halbgeraden mit Startpunkt
Vorvorgaengerpunkt (i-2) durch aktuellen Punkt (i). Fuer diese
Lagebestimmung ist auch der Begriff der Orientierung notwendig.
Hm ... lieg ich mit meiner Erinnerung vielleicht total daneben
(bin mir im Moment garnicht mehr sicher) ?
> Eine Implementierung des Graham Scan in maple6 findest Du im Anhang.
Vielen Dank fuer die Muehe. Graham-Scan in maple hat fuer sich genommen
schon eine posting-Berechtigung.
Malte
--
Malte Lance.
Klaus Nagel
Malte Lance schrieb:
Hallo Malte,
die Punkte seien A,B,C und D. Man stelle D dar als Linearkombination
von A,B und C, also
D=alpha*A+beta*B+gamma*C unter der zusätzlichen Voraussetzung alpha +
beta + gamma = 1.
Das sind die sogenannten baryzentrischen Koordinaten
(Schwerpunktskoordinaten, siehe dtv-Atlas zur Mathematik, Band , für
alpha=beta=gamma=1/3 ergibt sich für D der Schwerpunkt). Im Innern des
Dreiecks A,B,C sind die drei Gewichte positiv. Die vier Punkte bilden
genau dann ein konvexes Viereck, wenn genau zwei der Gewichte
(alpha,beta,gamma) nicht negativ sind.
Zur Berechnung der Gewichte löst man ein lineares Gleichungssystem:
Zwei Bedingungen aus den Koordinaten und eine aus der Gewichtsbedingung.
Klaus Nagel
Malte Lance
"Rainer Rosenthal" <r.ros...@ngi.de> writes:
>
> Malte Lance <malte...@gmx.net> wrote in message
> news:8oqe25$f46$18$1...@news.t-online.com...
>
>| ...wie man testen kann, ob vier Punkte im R^2 | Ecken eines konvexen
>| Vierecks sind, ohne dabei auf den Begriff | der 'Orientierung' bzw.
>| 'orientierte Basis' zurueckzugreifen ?
>
> Strecken AB und CD mit gegebenen Endpunkten A, B, C, D
> schneiden.
> Mit diesem Kriterium ist aber die Ursprungsaufgabe ganz einfach
> zu lösen !
> Ich erfinde mal schnell folgende Notation:
> AB (=) CD bedeutet, dass sich AB und CD nicht schneiden,
> AB (x) CD bedeutet, dass sich AB und CD schneiden.
> Betrachte ich ein KONVEXES Viereck, dann habe ich mindestens zwei
> sich schneidende Strecken (die Diagonalen).
> Ein NICHT KONVEXES Viereck hat keine sich schneidenden Diagonalen,
> hier gilt immer:
> AB (=) CD und AC (=) BD und AD (=) BC
Ja, das ist genau die Idee, die Florian Wessels schon erwaehnt hat
(in Message-ID: <hhk1rsg5r57upb80g...@4ax.com>).
Anschaulich ist das auch sofort klar. Hast Du vielleicht einen
Ansatz fuer eine Beweisidee oder eine Herleitung ?
Ohne Beweis werde ich es nicht implementieren duerfen.
Malte
--
Malte Lance.
Michael Hoppe
> Die vier Punkte A, B, C, D bilden die Ecken eines konvexen Vier-
> ecks in der Ebene ganau dann, wenn gilt:
>
> A liegt ausserhalb von Dreieck(B,C,D) und
> B liegt ausserhalb von Dreieck(A,C,D) und
> C liegt ausserhalb von Dreieck(A,B,D) und
> D liegt ausserhalb von Dreieck(A,B,C)
>
> Klingt auf Anhieb vielleicht etwas plump, ist aber eine saubere
> Sache.
Keineswegs. Das Viereck mit den Punkten A(0, 0), B(1, 1), C(1, 0) und
D(0, 1) (,,Fliege'') erfüllt das von Dir genannte Kriterium, ist aber
nicht konvex.
Michael
--
-= Michael Hoppe <www.michael-hoppe.de>, <m...@michael-hoppe.de> =------
-= Key fingerprint = 74 FD 0A E3 8B 2A 79 82 25 D0 AD 2B 75 6A AE 63
-= PGP public key (0xE0A5731D) available on request. =---------------
Rainer Rosenthal
Malte Lance <ma...@axon.yi.org> wrote in message
news:8otbf3$ppd$15$2...@news.t-online.com...
| > AB (=) CD und AC (=) BD und AD (=) BC
|
| Ja, das ist genau die Idee, die Florian Wessels schon erwaehnt hat
|
| Anschaulich ist das auch sofort klar. Hast Du vielleicht einen
| Ansatz fuer eine Beweisidee oder eine Herleitung ?
| Ohne Beweis werde ich es nicht implementieren duerfen.
|
Hallo Malte,
Du machst es aber spannend. Jetzt schau' Dir doch bitte mal die
Lösung von heute nacht an. Sie ist komplett fix und fertig.
Zum Beweis werde ich wieder ein Extra-Posting lossenden, das
mach' ich doch gerne noch.
Bitte beachte, dass bei Florians Beobachtung noch das Wort "Inneres"
vorkommt. Bei mir dagegen nicht. Und gerade weil das "Anschaulich
sofort klar" ist, bin ich so stolz darauf, dass diese einfache Beobachtung
zu eienr fix-fertigen Lösung aufbereitet werden kann.
Und es wird nicht mal mit Kanonen geschossen sondern eher mit
Pfeil und Bogen.
Was ist das eigentlich für eine tolle Aufgabe, bei der Du so viele
Vierecke auf Konvexität zu prüfen hast ?
Gruss
Rainer
------------------------------------------------------------------
12333333333333334566666666????5433333
Malte Lance
m...@michael-hoppe.de (Michael Hoppe) writes:
> Rainer Rosenthal <r.ros...@ngi.de> wrote:
>> Die vier Punkte A, B, C, D bilden die Ecken eines konvexen Vier-
>> ecks in der Ebene ganau dann, wenn gilt:
>> A liegt ausserhalb von Dreieck(B,C,D) und
>> B liegt ausserhalb von Dreieck(A,C,D) und
>> C liegt ausserhalb von Dreieck(A,B,D) und
>> D liegt ausserhalb von Dreieck(A,B,C)
>> Klingt auf Anhieb vielleicht etwas plump, ist aber eine saubere
>> Sache.
>
> Keineswegs. Das Viereck mit den Punkten A(0, 0), B(1, 1), C(1, 0) und
> D(0, 1) (,,Fliege'') erfüllt das von Dir genannte Kriterium, ist aber
> nicht konvex.
Sorry mein Fehler. Habe straeflicher Weise vergessen zu sagen, dass
ich an einfachen Vierecken interessiert bin, also solche, die keine
Kantenueberschneidung haben. Oder anders ausgedrueckt, die Vierecke
die ich betrachte entstehen aus zwei nichtentarteten Dreiecken, die
genau eine Kante gemeinsam haben.
Ich glaube so hat es Rainer auch aufgefasst.
Tut mir leid. Das haette ich definitiv in meinem ersten Posting
sagen muessen.
Malte
--
Malte Lance.
Malte Lance
Florian Wessels <no.spam.flo...@math.uni-muenster.de> writes:
> On Sat, 2 Sep 2000 10:34:13 +0200, malte...@gmx.net (Malte Lance)
> wrote:
>
>>hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>>Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>>der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Wenn es zwei Punktepaare (p1,p2), (p3,p4) gibt, so dass
> sich L(p1,p2), L(p3,p4) im Innern schneiden. (L(x,y) Strecke
> zwischen x,y)
Meinst Du mit "im Inneren", das Innere des betrachteten Vierecks,
oder das relative Innere der Liniensegmente ?
Hast Du vieleicht einen Ansatz fuer eine Herleitung oder eine
Beweisidee, wie man die Richtigkeit Deiner Behauptung zeigen
koennte ?
Malte
--
Malte Lance.
Florian Wessels
wrote:
>> Wenn es zwei Punktepaare (p1,p2), (p3,p4) gibt, so dass
>> sich L(p1,p2), L(p3,p4) im Innern schneiden. (L(x,y) Strecke
>> zwischen x,y)
>
>Meinst Du mit "im Inneren", das Innere des betrachteten Vierecks,
>oder das relative Innere der Liniensegmente ?
letzeres.
>Hast Du vieleicht einen Ansatz fuer eine Herleitung oder eine
>Beweisidee, wie man die Richtigkeit Deiner Behauptung zeigen
>koennte ?
Wenn du ein konvexes Viereck hast, dann nimm die Diagonalen.
Wenn sich zwei Segmente im Innern schneiden, dann nimm
die Segmente als Diagonale des 4ecks, dass es geben soll.
Gruesse, Florian
Malte Lance
Helmut Kahovec <helmut....@teleweb.at> writes:
> Malte Lance wrote:
>
>>| Bei mir soll der Test immer nur fuer genau 4 Punkte durchgefuehrt werden.
>>| Weiterhin muss ich diesen Test einige tausend Mal durchfuehren. Das ist
>>| dann tatsaechlich ein Schiessen mit Kanonen (A-Bomben fuer die
>>| martialische Variante ;) auf Spatzen.
>
>
>>| Wenn ich mich nicht falsch erinnere, dann benutzt der Graham-Scan
>>| auf jeden Fall den Begriff der Orientierung. Die Winkel werden im
>>| Uhrzeigersinn oder gegen den Uhrzeigersinn sortiert (fuer die
>>| initiale Sortierung der Punkte) und spaeter (im sweep-Schritt) wird
>>| jeweil ein Punkt ((i-1) Vorgaengerpunkt) auf Lage (links
>>| oder rechts) bezueglich der orientierten Halbgeraden mit Startpunkt
>>| Vorvorgaengerpunkt (i-2) durch aktuellen Punkt (i). Fuer diese
>>| Lagebestimmung ist auch der Begriff der Orientierung notwendig.
>>| Hm ... lieg ich mit meiner Erinnerung vielleicht total daneben
>>| (bin mir im Moment garnicht mehr sicher) ?
>
Hi Helmut,
> Du hast mit Deiner zweiten Bemerkung durchaus recht:
>
> (1) Der von mir zitierte Algorithmus sucht zunächst den Punkt P0 mit der
> kleinsten Ordinate.
>
> (2) Anschließend werden die anderen Punkte bezüglich P0 gegen den
> Uhrzeiger sortiert.
>
> (3) Schließlich wird eine Schleife durchlaufen, in der drei
> aufeinanderfolgende Punkte auf einen Rechtsschwenk hin überprüft werden.
>
> Meines Erachtens hat Schritt (2) nur wenig mit der Orientierung
> aufeinanderfolgender Punkte zu tun. In Schritt (3) sind bei der
> Bestimmung der Orientierung von drei aufeinanderfolgenden Punkten P,Q,R
> keine Fallunterscheidungen notwendig. Man prüft lediglich, ob das
> Vektorprodukt von (Q-P)x(R-Q) kleiner als Null ist (Rechtsschwenk). In
> Komponentenschreibweise ist dies ein sehr einfaches Kriterium.
Ja, und doch, wenn ich den Graham-Scan so verwenden wollte, kaeme ich
nicht drum herum, den Begriff der Orientierung einzufuehren, um den
Graham-Scan dann erklaeren zu koennen und ihn dann benutzen zu duerfen.
> Übrigens, was stört Dich an einem Algorithmus, der (nur an einer
> einzigen Stelle) einen (sehr transparenten) Bezug zur Orientierung
> dreier, aufeinanderfolgender Punkte hat?
Ich hab es bisher geschafft, meinen Algorithmus (Approximation
bivariater diskreter Funktionen durch Triangulationen) frei von
Orientierung herzuleiten. Das Problem mit den vier Punkten ist,
verglichen mit dem Gesamtalgorithmus, marginal und daher waere es
schoen, wenn ich es vermeiden koennte, aufgrund eines marginalen
Teilchens den Apparat orientierter Basen einzufuehren.
Vielen Dank fuer Deine Muehe, den Graham-Scan in Code zu giessen.
Malte
--
Malte Lance.
Hermann Kremer
Rainer Rosenthal schrieb in Nachricht <8otv22$pa6$1...@news.online.de>...
Hallo Rainer,
OT
was macht eigentlich unser Big-Acker-Number Spiel ?
OT
>Hermann Kremer <hermann...@online.de> wrote in message
>news:8orob5$ifa$1...@news.online.de...
>|
>| das Viereck A1-B1-C1-D1
>|
>| D1
>|
>| A1 C1
>|
>| B1
>|
>| ist konvex, das Viereck A2-B2-C2-D2
>|
>| D2
>|
>| A2 C2
>|
>| B2
>|
>| ist konkav
>
>Hallo Hermann,
>
>nachdem ich heute nacht eine "wunderbare Lösung" gefunden habe,
>brauche ich noch einen Beweis für die theoretische Grundlage. Tat-
>sächlich ist die Anschauung ja eine trügerische Sache, wie ich schon
>bei dem Versuch feststellen musste, die theoretische Grundlage
>überhaupt erst mal sauber zu formulieren. So gesehen bin ich schon
>mal zufrieden, wenn der folgende Satz kritischer Begutachtung stand-
>hält. Mit dem "können bilden" habe ich den Einwand von Michael
>Hoppe aufgegriffen, dass zu einem Viereck mehr gehört als die
>Angabe der 4 Eckpunkte, nämlich eine Reihenfolge-Angabe.
>
> Satz K:
> Vier Punkte in der Ebene können genau dann ein konvexes
> Viereck bilden, wenn alle Verbindungsstrecken ohne gemein-
> same Endpunkte auch sonst keine gemeinsamen Punkte haben.
>
>Deine anschaulichen Beispiele mal in der Notation, bei der
>a(x)b bedeutet, dass die Strecken a und b sich schneiden und
>a(=)b bedeutet, dass die Strecken a und b sich nicht schneiden
>nochmal durchgeschaut:
>
>Beispiel 1 von Dir:
> AB(=)CD AC(x)BD AD(=)BC
> AC und BD haben einen Schnittpunkt.
> A-B-C-D ist ein konvexes Viereck.
>
>Beispiel 2 von Dir:
> AB(=)CD AC(=)BD AD(=)BC
> AC und BD haben keinen Schnittpunkt.
> Weder A-B-C-D noch A-C-B-D noch
> A-C-D-B sind konvex. (Beachte, dass alle
> Durchlaufungen bis auf Umkehrung genannt wurden.)
>
>Frage 1: ist der Satz mathematisch einwandfrei formuliert und hat
> er Aussicht auf Beweisbarkeit ?
>Frage 2: Genügt der Beweis des Satzes als Beruhigung für Malte:
> "Ohne Beweis werde ich es nicht implementieren duerfen".
Zu 1) Ja. Der Satz schließt "gefaltete" Vierecke aus. (Könnte man die
als Möbius-Vierecke bezeichnen ???? ).
Als Beweis würde ich einfach eine Exhaustion durchführen - alle
6 möglichen Verbindungslinien paarweise kombinieren.
(Der Vierfarbensatz-Beweis tut das schließlich auch .... ;-)))
Man müßte imo dann allerdings noch irgendwie auf Kollinearität
von 3 Punkten prüfen.
Zu 2) Ja.
>Wenn ich Deine bisherige Präsenz in der NG so betrachte,
>liege ich mit diesen Fragen bei Dir gar nicht falsch. Wie üblich
>sind natürlich alle anderen herzlich zum Mitbeweisen eingeladen.
>Allen voran eigentlich Malte, dessen Problem das ja eigentlich ist.
Grüße
Hermann
------------------------------------------------------------
ack(1,1) ack(2,2) ack(3,3) ack(4,4) ack(5,5)
>Gruss,
>Rainer
>---------------------------------------------------------
>4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
>
>
>
Rainer Rosenthal
|
| #include <stdio.h>
| #include <stdlib.h>
| #include <math.h>
|
Geschenkt.
| Mit freundlichem Grinsen Hermann
|
Hoffentlich vergeht es Dir nicht nach meinem Posting von
vor einer Stunde, wo es nach Arbeit riecht ! (-:
Was ist hier eigentlich los ? Auch Du scheinst meine alten
Beiträge erst lesen zu können, wenn alles zu spät ist.
Stinkt mir jetzt aber.
Um mit C. Morgenstern zu sprechen: "Wo, wo ist der Herr
Stationsvorsteher ?".
Gruss,
Rainer
--------------------------------------------------
4444444444444444444444444444
Hermann Kremer
Rainer Rosenthal schrieb in Nachricht <8ou3oo$vkf$1...@news.online.de>...
Hallo Rainer,
das folgende bezog sich auf das spinnende fabs() ...
>|
>| #include <stdio.h>
>| #include <stdlib.h>
>| #include <math.h>
>|
>
>Geschenkt.
>
>| Mit freundlichem Grinsen Hermann
>|
>
>Hoffentlich vergeht es Dir nicht nach meinem Posting von
>vor einer Stunde, wo es nach Arbeit riecht ! (-:
>
Welches Posting von wann. Bei mir ist es jetzt 20.39 MESZ ....
>Was ist hier eigentlich los ? Auch Du scheinst meine alten
>Beiträge erst lesen zu können, wenn alles zu spät ist.
Scheint so ....
>Stinkt mir jetzt aber.
>Um mit C. Morgenstern zu sprechen: "Wo, wo ist der Herr
>Stationsvorsteher ?".
http://www.google.com ;-) ;-) ;-)
OT
What about the Big-Acker-Number game ?
OT
Viele Grüße
Hermann
--
>Gruss,
>Rainer
>--------------------------------------------------
>4444444444444444444444444444
>
>
>
>
Klaus Nagel
Malte Lance schrieb:
Ich verfolge die Diskussion und habe den Eindruck, daß bei der
Aufgabenstellung eine Unklarheit herrscht.
Heißt die Frage: Ist die konvexe Hülle der vier Punkte ein Viereck?
(Fall I)
oder : Bilden die vier Punkte in festgelegter Reihenfolge ein konvexes
Viereck? (Fall II)
Fall I :
Mein Vorschlag von 9:54 löst auch die Grenzfälle: Wird ein Gewicht 0, so
ist D mit zwei Punkten kollinear; liegen A,B und C auf einer Geraden, so
ist das Gleichungssystem nicht lösbar, es sei denn auch D liegt auf der
gleichen Geraden.
Hinter dem Vorschlag steht folgende Idee: Ich betrachte das Dreieck aus
drei der vier Punkte, ohne Einschränkung der Allgemeinheit die Punkte
A,B und C. Wo kann D liegen, damit AB,C und D die Ecken eines konvexen
Vierecks sind? Verlängert man die Dreiecksseiten, so bilden sich außen
sechs Sektoren, die abwechselnd an eine Seite oder an eine Ecke des
Dreiecks grenzen. Konvexe Vierecke entstehen für D in den Sektoren, die
an Seiten grenzen. Diese Sektoren sind dadurch gekennzeichnet, daß sie
zwei nichtnegative baryzentrische Koordinaten haben.
Fall II:
Die vier Punkte bilden genau dann ein konvexes Viereck, wenn für jede
der vier Seiten die beiden restlichen Punkte auf der gleichen Seite der
Verbindungsgeraden liegen. Es sind also viermal zwei Skalarprodukte zu
vergleichen.
Klaus Nagel
Malte Lance
Klaus Nagel <nagel...@t-online.de> writes:
>
> Malte Lance schrieb:
>> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Aufgabenstellung eine Unklarheit herrscht.
> Heißt die Frage: Ist die konvexe Hülle der vier Punkte ein Viereck?
> (Fall I)
> oder : Bilden die vier Punkte in festgelegter Reihenfolge ein konvexes
> Viereck? (Fall II)
Ich habe nach Fall I gefragt (zumindest habe ich daran gedacht; meine
Fragestellung war nicht eindeutig).
> Fall I :
> Mein Vorschlag von 9:54 löst auch die Grenzfälle: Wird ein Gewicht 0, so
> ist D mit zwei Punkten kollinear; liegen A,B und C auf einer Geraden, so
> ist das Gleichungssystem nicht lösbar, es sei denn auch D liegt auf der
> gleichen Geraden.
Das ist problematisch. Folgendes ist ein legitimes konvexes
Viereck (oder ?):
a--b--c
\ /
\ /
d
> Hinter dem Vorschlag steht folgende Idee: Ich betrachte das Dreieck aus
> drei der vier Punkte, ohne Einschränkung der Allgemeinheit die Punkte
> A,B und C. Wo kann D liegen, damit AB,C und D die Ecken eines konvexen
> Vierecks sind? Verlängert man die Dreiecksseiten, so bilden sich außen
> sechs Sektoren, die abwechselnd an eine Seite oder an eine Ecke des
> Dreiecks grenzen. Konvexe Vierecke entstehen für D in den Sektoren, die
> an Seiten grenzen.
Ja.
> Diese Sektoren sind dadurch gekennzeichnet, daß sie
> zwei nichtnegative baryzentrische Koordinaten haben.
Wie sieht man das. Kannst Du etwas genauer erlaeutern ?
Meinst Du hier vielleicht: genau zwei nichtnegative und eine negative
baryzentrische Koordinate haben ?
Malte
--
Malte Lance.
Thomas Haunhorst
>Das ist problematisch. Folgendes ist ein legitimes konvexes
>Viereck (oder ?):
>
>a--b--c
> \ /
> \ /
> d
>
Die Frage ist, ob das ueberhaupt ein Viereck ist. Sind {p_1,...,p_n} n
verschiedene Punkte, so bilden diese ein n-Eck, wenn es keine Gerade gibt,
die mit 3 verschiedenen Punkten von S inzediert. Nach dieser Def. ist obige
Figur dann kein Viereck.
Gruss
Thomas.
--
Thomas Haunhorst
>Viereck (oder ?):
>
>a--b--c
> \ /
> \ /
> d
>
Die Frage ist, ob das ueberhaupt ein Viereck ist. Sind S={p_1,...,p_n} n
Klaus Nagel
Malte Lance schrieb:
Ob das ein legitimes Viereck ist oder nicht, mag vom Rahmen abhängen, in
welchem das ganze Problem steht. Jedenfalls aber werden diese Kollinearitäten
erkannt.
> > Hinter dem Vorschlag steht folgende Idee: Ich betrachte das Dreieck aus
> > drei der vier Punkte, ohne Einschränkung der Allgemeinheit die Punkte
> > A,B und C. Wo kann D liegen, damit AB,C und D die Ecken eines konvexen
> > Vierecks sind? Verlängert man die Dreiecksseiten, so bilden sich außen
> > sechs Sektoren, die abwechselnd an eine Seite oder an eine Ecke des
> > Dreiecks grenzen. Konvexe Vierecke entstehen für D in den Sektoren, die
> > an Seiten grenzen.
>
> Ja.
>
> > Diese Sektoren sind dadurch gekennzeichnet, daß sie
> > zwei nichtnegative baryzentrische Koordinaten haben.
>
> Wie sieht man das. Kannst Du etwas genauer erlaeutern ?
> Meinst Du hier vielleicht: genau zwei nichtnegative und eine negative
> baryzentrische Koordinate haben ?
>
Schließt man aus, daß 3 Punkte auf einer Geraden liegen, dann heißt es: 2
Koordinaten sind positiv, eine negativ.
Zu den baryzentrischen Koordinaten: Liegt D auf der Geraden c durch A und B,
dann gilt die Darstellung D=alpha*A+beta*B, mit alpha + beta = 1, wobei
zwischen A und B alpha und beta nicht negativ sind (konvexe
Linearkombination); die dritte Koordinate, gamma, ist Null. Auf der Seite von
c, auf der der Punkt C liegt ist gamma positiv, auf der anderen negativ.
Entsprechendes gilt für die die Geraden BC und CA und die Gewichte alpha und
beta. Mit dieser Kenntnis kann man prüfen, wie die Vorzeichen der drei
Gewichte in den sechs Sektoren sind.
Klaus Nagel
Klaus Nagel München
> Die baryzentrischen Koordinaten klingen wohl zu gewaltig und schrecken
> deswegen ab. Dabei läßt sich die Methode ganz einfach programmieren,
> wie das folgende C-Programm zeigt:
>
>
> /* ----------------- Konvex 04.09.2000 K. Nagel --------------------
> */
> /*
> */
> /* Konvex prüft, ob die vier Punkte (a1,a1) ... (d1,d2) ein konvexes
> */
> /* Viereck aufspannen.
> */
> /* Ergebnis:
> */
> /* 0 bedeutet mindestens 3 Punkte kollinear.
> */
> /* 1 bedeutet konvex.
> */
> /* 2 bedeutet nicht konvex.
usw.
> */
> ------------------------------------------------------
Das Programm enthält einen Fehler,im Kommentar sind die Bedeutungen von
1 und 2 vertauscht. Unten steht das Programm verbessert, zusammen mit
einem Testrahmen für Druckergraphik:Übersetzen mit "cc -o viereck
viereck.c" und "viereck" aufrufen.
Außerdem wurde ich als Newsgroup-Neuling darauf hingewiesen, daß ich
keine HTML-Formatierung benutzen soll.
Ändert man die Routine so, daß sie statt 0,0,0,0 die Werte 0,3,4,5
liefert, dann lassen sich in der Druckergraphik auch die verschiedenen
Fälle der Kollinearitäten unterscheiden.
Klaus Nagel
#include <stdio.h>
/* ----------------- Konvex 04.09.2000 K. Nagel -------------------- */
/* */
/* Konvex prüft, ob die vier Punkte (a1,a1) ... (d1,d2) ein konvexes */
/* Viereck aufspannen. */
/* Ergebnis: */
/* 0 bedeutet mindestens 3 Punkte kollinear. */
/* 1 bedeutet nicht konvex.
*/
/* 2 bedeutet
konvex. */
/* */
/* Verfahren: */
/* Die baryzentrischen Koordinaten von D bezogen auf A,B und C */
/* werden nach der Kramerschen Regel berechnet. Die Division durch */
/* die Determinante wird nicht ausgeführt, weil nur die Anzahl der */
/* positiven Koordinatenwerte interessiert. */
/* --------------------------------------------------------*/
int konvex(int a1,int a2,int b1,int b2,int c1,int c2,int d1,int d2)
{
int det,det1,det2,det3,anzahl ;
det = a1*b2 + b1*c2 + c1*a2 - b2*c1 - c2*a1 - a2*b1 ;
if(det ==0) return(0); /* A B C kollinear */
det1 = d1*b2 + b1*c2 + c1*d2 - b2*c1 - c2*d1 - d2*b1 ;
if(det1==0) return(0); /* D B C kollinear */
det2 = a1*d2 + d1*c2 + c1*a2 - d2*c1 - c2*a1 - a2*d1 ;
if(det2==0) return(0); /* A D C kollinear */
det3 = a1*b2 + b1*d2 + d1*a2 - b2*d1 - d2*a1 - a2*b1 ;
if(det3==0) return(0); /* A B D kollinear */
anzahl = 0 ;
if ( det1 > 0) anzahl++ ;
if ( det2 > 0) anzahl++ ;
if ( det3 > 0) anzahl++ ;
if ( det < 0) anzahl = 3 - anzahl ;
if (anzahl == 3) return(1);
return(anzahl);
}
void main()
{
int a1,a2,b1,b2,c1,c2,d1,d2,ergebnis;
a1 = 20 ; a2 = 20 ;
b1 = 20 ; b2 = 40 ;
c1 = 40 ; c2 = 40 ;
for ( d2 = 0 ; d2 < 60 ; d2++)
{
printf("\n %2d : ",d2);
for ( d1 = 0 ; d1 < 60 ; d1++)
{
ergebnis=konvex(a1,a2,b1,b2,c1,c2,d1,d2);
printf("%1d",ergebnis);
}
}
printf("\n");
}
/* ------------------------------------------------------ */
Klaus Nagel München
> Alles in allem bin ich sehr zufrieden und haue mich jetzt auf's Ohr.
> Gruss,
> Rainer
Ich bin nicht so zufrieden. Ich habe die Unterprogramme "Schneidet"
und "Det" in meinen Testrahmen mit Druckergrafik gehängt und das
Ergebnis stimmte nicht (siehe Beitrag von heute, 5.9 08:00 Uhr, dort kann
man auch das richtige Ergebnis erzeugen) . Bei dem Testrahmen werden die
Punkte A=(20,20), B=(20,40) und C=40,40) festgehalten, beide Koordinaten
von D laufen unabhängig von 0 bis 59, das Prüfergebnis wird in Matrixform
ausgedruckt. Dabei habe ich die Ergebniswerte von "Schneidet" so
geändert, daß sie mit meinem Programm übereinstimmen: 0 für entartet, 1
für nicht konvex und 2 für konvex. Das vollständige Programm steht
unten.
Klaus Nagel
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double Det( double a11, double a12, double a21, double a22)
{
return a11*a22 - a21*a12;
}
int Schneidet( double xP, double yP,
double xQ, double yQ,
double xR, double yR,
double xS, double yS)
{
int erg;
double d, t, u;
double g, a;
d = Det( xQ-xP, xR-xS, yQ-yP, yR-yS);
g = 0.000001;
if ( d < 0) {
a = -d;
} else {
a = d;
}
if ( a < g) {
/* fprintf( stderr, "Entartetes Viereck\n"); */ /* Geaendert KN
*/
erg = 0; /* Geaendert KN */
} else {
t = ( (yR-yS)*(xR-xP) - (xR-xS)*(yR-yP)) / d;
u = ( (yR-yP)*(xQ-xP) - (xR-xP)*(yQ-yP)) / d;
if ( t < 0 || t > 1 || u < 0 || u > 1) {
erg = 1; /* Geaendert KN */
} else {
erg = 2; /* Geaendert KN */
}
}
return erg;
}
void main()
{
int a1,a2,b1,b2,c1,c2,d1,d2,ergebnis;
a1 = 20 ; a2 = 20 ;
b1 = 20 ; b2 = 40 ;
c1 = 40 ; c2 = 40 ;
for ( d2 = 0 ; d2 < 60 ; d2++)
{
printf("\n %2d : ",d2);
for ( d1 = 0 ; d1 < 60 ; d1++)
{
ergebnis=Schneidet((double)a1,(double)a2,(double)b1,(double)b2,(double)c1,(double)c2,(double)d1,(double)d2);
Klaus Nagel München
Ergänzung zu meinem vorherigen Beitrag:
Ich hatte übersehen, daß "Schneidet" nur ein Drittel des Problems löst. Dann bleibt nur eine Abweichung beim
Erkennen der entarteten Vierecke.
Klaus Nagel
Rainer Rosenthal
Klaus Nagel München <nagel...@t-online.de> wrote in message
news:39B4BB68...@t-online.de...
> Ergänzung zu meinem vorherigen Beitrag:
> Ich hatte übersehen, daß "Schneidet" nur ein Drittel des Problems löst.
> Dann bleibt nur eine Abweichung beim Erkennen der entarteten Vierecke.
Hallo Klaus,
bitte mehr Sorgfalt beim Zerpflücken der Konkurrenz bitte !
Ich habe mir ganz erschrocken anschauen wollen, wieso
denn mein Programm "falsch" sein soll. Dabei habe ich
gesehen, dass Du mein nächtlich gehacktes Programm
falsch abgetippt hast, indem Du statt meines
Schneidet oder Schneidet oder Schneidet
einfach nur
Schneidet
aufrufst. Die nachgereichte Bemerkung "...nur ein Drittel...löst"
klingt wie ein Makel der Funktion "Schneidet". Dabei gehört
zum Lösen des Problems nun mal der dreifache Test.
Die Bewertung entarteter Vierecke als "konvex" ist im Begleit-
text zur "Erstausgabe" schon so erklärt worden:
----------- Zitat ------
Die Auflösung der Gleichung mittels Determinante und Inverser
Matrix wird vom Programm erledigt, wobei auf "entartete Vierecke"
hingewiesen wird, die als "konvex" bezeichnet werden.
------------------------
Es war mir nur darum zu tun, bei entarteten Vierecken nicht so
klitzekleine Determinanten zu kriegen, dass ich beim Dividieren
in Floatingpoint-Calculation Probleme komme. Da ein Null-Test
bei Floatingpoint-Calculation Unsinn ist, habe ich eine gewisse
Grenze gesetzt und bei der Gelegenheit auf das "Entarten" hin-
gewiesen, weil die Applikation von Malte u.U. kritisch auf solche
Sonderfälle reagieren könnte. (Ich kenne sie immer noch nicht,
diese Applikation. Schade.)
Bezüglich "konvex" und "entartet" nehme ich eine total konservative
Haltung ein: Ich halte mich strikt an die Definition, dass ein Gebilde
als konvex zu bezeichnen ist, wenn mit je zwei Punkten des Gebildes
die gesamte Verbindungsstrecke darin enthalten ist. Und das ist
nun mal der Fall, wenn alles zusammenklatscht.
Die "Abweichung" beim Erkennen entarteter Vierecke muss erst
noch durch die Applikation gerechtfertigt werden.
Gruss,
Rainer
---------------------------------------------------------------
00000000000000044400000000000000000
Horst Kraemer
wrote:
> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Ich bin fuer jede Idee und jeden Hinweis dankbar.
Sorry, wenn ich so einfach hineinplatze, ohne alle 49 Antworten
ausfuehrlich gelesen zu haben. Eine IMHO recht elegante analytische
Bedingung ist folgende. Die Erklaerung ist leide laenger als die
Berechnung ;-)
Seien P1,P2,P3,P4 in der Ebene gegeben.
Vorbemerkung:
Wenn A,B,C drei nicht kollineare Punkte der Ebene sind, laesst sich
jeder Punkt P der Ebene auf genau eine Weise in der Form
P = a*A + b*B + c*C , a+b+c=1
mit gewissen reellen Zahlen a,b,c darstellen (baryzentrische oder
affine Koordinaten von P bez. des Dreiecks ABC). Andererseits
existiert genau dann eine eindeutige Darstellung der obigen Art fuer
beliebiges P,A,B,C wenn A,B,C _nicht_ kollinear sind.
P befindet sich genau dann im Dreieck (einschliesslich Rand), wenn
alle c_i >=0 sind.
Man kann sich leicht davon ueberzeugen, dass genau dann keiner der P_i
in dem aus den anderen P_j gebildeten Dreieck liegt, wenn o.B.d.A die
Darstellung
P4 = a*P1 + b*P2 + c*P3 , a+b+c=1
eindeutig ist (P1P2P3 ist ein echtes Dreieck), und genau eines der
(a,b,c) <0 ist und die anderen beiden >0 sind. Genau dann, wenn P1P2P3
nicht kollinear sind, gilt
det(Q1Q2Q3)*P4 = det(Q4Q2Q3)*P1 + det(Q1Q4Q3)*P2 +det(Q1Q2Q4)*P3
= det(Q4Q2Q3)*P1 + det(Q4Q3Q1)*P2 +det(Q4Q1Q2)*P3
wobei Qi jeweils der um eine kuenstliche z-Koordinate 1 "verlaengerte"
Koordinatenvektor von Pi ist.
[
Cramerscher Regel bei der Aufloesung des linearen GLS
x1 x2 x3 a x4
y1 y2 y3 * b = y4
1 1 1 c 1
Der Wert der Determinante ist uebrigens der doppelte orientierte
Flaecheninhalt des entsprechenden Dreiecks
]
Durch Subtrahieren der ersten Spalte von den Spalten 2 und 3 jeder
Matrix kann man die Determinanten leicht durch Entwicklung nach der
letzten Zeile berechnen. Es gilt dann:
d=det (Q1Q2Q3) = (x2-x1)(y3-y1)-(y2-y1)(x3-x1)
a=det (Q4Q2Q3) = (x2-x4)(y3-y4)-(y2-y4)(x3-x4)
b=det (Q4Q3Q1) = (x3-x4)(y1-y4)-(y3-y4)(x1-x4)
c=det (Q4Q1Q2) = (x1-x4)(y2-y4)-(y1-y4)(x2-x4)
Summa summarum: Die Punkte P1P2P3P4 sind genau dann "konvex
unabhaengig" (keiner liegt in der konvexen Huelle der anderen drei),
wenn
d>0 und genau eines der (a,b,c) < 0 und die restlichen >0
oder
d<0 und genau eines der (a,b,c) > 0 und die restlichen <0
MfG
Horst
Klaus Nagel München
> Wenn A,B,C drei nicht kollineare Punkte der Ebene sind, laesst sich
> jeder Punkt P der Ebene auf genau eine Weise in der Form
>
> P = a*A + b*B + c*C , a+b+c=1
>
> mit gewissen reellen Zahlen a,b,c darstellen (baryzentrische oder
> affine Koordinaten von P bez. des Dreiecks ABC).....
>
> MfG
> Horst
Hallo Horst,
schau Dir meine Beiträge an, die schlagen genau das vor . Im Beitrag von
gestern 08:00 steht ein C-Programm.
Gruß,
Klaus Nagel
Klaus Nagel München
>
> Hallo Klaus,
>
> bitte mehr Sorgfalt beim Zerpflücken der Konkurrenz bitte !
> Ich habe mir ganz erschrocken anschauen wollen, wieso
> denn mein Programm "falsch" sein soll. Dabei habe ich
> gesehen, dass Du mein nächtlich gehacktes Programm
> falsch abgetippt hast, indem Du statt meines
>
> Schneidet oder Schneidet oder Schneidet
>
> einfach nur
>
> Schneidet
>
> aufrufst.
Hallo Rainer,
entschuldige bitte, daß ich übersehen hatte, daß die "Schneidet" noch nicht
alle löst. Als ich das merkte , habe ich gleich die Ergänzung
hinterhergeschickt. Das "Drittel" ist nicht als Makel zu verstehen, sondern
sollte nur ausdrücken, daß man Schneidet dreifach verodern muß.
Ich wollte auch nicht die Konkurrenz zerpflücken, sondern mit Deinem
Programm meins verifizieren. Dabei stieß ich auf Ungereimtheiten: die eine,
mein Übersehen, ist geklärt.
> Die nachgereichte Bemerkung "...nur ein Drittel...löst"
> klingt wie ein Makel der Funktion "Schneidet". Dabei gehört
> zum Lösen des Problems nun mal der dreifache Test.
>
> Die Bewertung entarteter Vierecke als "konvex" ist im Begleit-
> text zur "Erstausgabe" schon so erklärt worden:
>
> ----------- Zitat ------
> Die Auflösung der Gleichung mittels Determinante und Inverser
> Matrix wird vom Programm erledigt, wobei auf "entartete Vierecke"
> hingewiesen wird, die als "konvex" bezeichnet werden.
> ------------------------
>
> Es war mir nur darum zu tun, bei entarteten Vierecken nicht so
> klitzekleine Determinanten zu kriegen, dass ich beim Dividieren
> in Floatingpoint-Calculation Probleme komme. Da ein Null-Test
> bei Floatingpoint-Calculation Unsinn ist, habe ich eine gewisse
> Grenze gesetzt und bei der Gelegenheit auf das "Entarten" hin-
> gewiesen, weil die Applikation von Malte u.U. kritisch auf solche
> Sonderfälle reagieren könnte. (Ich kenne sie immer noch nicht,
> diese Applikation. Schade.)
>
> Bezüglich "konvex" und "entartet" nehme ich eine total konservative
> Haltung ein: Ich halte mich strikt an die Definition, dass ein Gebilde
> als konvex zu bezeichnen ist, wenn mit je zwei Punkten des Gebildes
> die gesamte Verbindungsstrecke darin enthalten ist. Und das ist
> nun mal der Fall, wenn alles zusammenklatscht.
>
Die Frage ist nicht so sehr, ob ein entartetes Viereck konvex ist, sondern,
ob es ein Viereck ist, und das hängt, wie Du richtig sagst, von der
Applikation ab. Ein Programm sollte die Kollinearitäten richtig erkennen.
>
> Die "Abweichung" beim Erkennen entarteter Vierecke muss erst
> noch durch die Applikation gerechtfertigt werden.
Hier liegt die andere Ungereimtheit: Dein Programm bezeichnet manche
Vierecke als entartet, die es nun wirklich nicht sind, etwa das
Einheitsquadrat. Hier ist ein Ausdruck von Deinem Originalprogramm, nur die
Fehlerausgabe habe ich in stdout umgeleitet:
Vorgelegtes Viereck hat die Punkte
A 0.0000 0.0000
B 0.0000 1.0000
C 1.0000 1.0000
D 1.0000 0.0000
Entartetes Viereck
Das vorgelegte Viereck ist konvex
Vertauscht man B und C, so wird keine Entartung festgestellt:
Vorgelegtes Viereck hat die Punkte
A 0.0000 0.0000
B 1.0000 1.0000
C 0.0000 1.0000
D 1.0000 0.0000
Das vorgelegte Viereck ist konvex
Der Fehler hat folgende Ursache: Schneidet meldet "entartet", wenn die
beiden Geraden keinen Schnittpunkt haben, also parallel sind. Alle Trapeze
werden deshalb als entartet bezeichnet, wenn nicht das Diagonalenpaar vor
dem Parallelseitenpaar untersucht wird, denn sobald ein innerer Schnittpunkt
gefunden ist, bricht die weitere Untersuchung ab.
Ich hänge unten eine korrigierte Version an. Damit ich sie mit meinen
Ergebnissen besser vergleichen kann, habe ich sie auf Integer umgestellt und
alle Divisionen vermieden. Die Resultate unserer Verfahren stimmen jetzt
überein.
Gruß
Klaus Nagel
------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define PARALLEL 1
#define KOLLINEAR 2
#define AUSSEN 4
#define INNEN 8
int
Schneidet (int xP, int yP,
int xQ, int yQ, int xR, int yR, int xS, int yS)
{
int d, t, u;
d = (xQ - xP) * (yR - yS) - (xR - xS) * (yQ - yP);
if(d==0) return(PARALLEL) ;
t = (yR - yS) * (xR - xP) - (xR - xS) * (yR - yP);
u = (yR - yP) * (xQ - xP) - (xR - xP) * (yQ - yP);
if ( t == 0 || t == d || u == 0 || u == d ) return(KOLLINEAR) ;
if ( d < 0. )
{
d=-d ;
t=-t ;
u=-u ;
}
if ( t < 0 || t > d || u < 0 || u > d ) return(AUSSEN) ;
return(INNEN);
}
void main()
{
int a1,a2,b1,b2,c1,c2,d1,d2,erg1,erg2,erg3,erg,gesamt;
a1 = 20 ; a2 = 20 ;
b1 = 20 ; b2 = 40 ;
c1 = 40 ; c2 = 40 ;
for ( d2 = 0 ; d2 < 60 ; d2++)
{
printf("\n %2d : ",d2);
for ( d1 = 0 ; d1 < 60 ; d1++)
{
erg1=Schneidet(a1,a2,b1,b2,c1,c2,d1,d2);
erg2=Schneidet(a1,a2,d1,d2,b1,b2,c1,c2);
erg3=Schneidet(a1,a2,c1,c2,b1,b2,d1,d2);
erg = erg1 | erg2 | erg3 ;
gesamt = 1 ;
if(erg & INNEN) gesamt = 2 ;
if(erg & KOLLINEAR) gesamt = 0 ;
printf("%1d",gesamt);
}
}
printf("\n");
}
------------------------------------
Rainer Rosenthal
Hallo Klaus,
ich danke Dir herzlich für die ausführliche Antwort und den
eingehenden Test.
Genau so was entsetzliches, wie Du jetzt gefunden hast,
hatt ich ja gestern "irgendwie geahnt". Und als es bloss
was anderes war, habe ich etwas unsanft reagiert. Der
Tonfall war daneben, sorry.
Auf jeden Fall werde ich Malte per mail über den "Unfall"
informieren.
Wie sieht es bzgl. Theorie aus ? Hast Du Interesse daran,
das Fundament der Konvexerei genauer anzuschauen ?
Wir haben jetzt recht gute Anschauung und verschiedene
Algorithmen zur Vergabe des Stempels "konvex".
Was aber noch fehlt, ist doch ein Beweis dafür, dass das,
was wir als konvex ansehen bzw. erkennen lassen, auch
tatsächlich konvex IST.
Also der Beweis, dass mit je 2 Punkten die Verbindungs-
strecke im Inneren des Vierecks liegt. Wo ist denn über-
haupt das Innere ? Vielleicht sollte ich mir jetzt wirklich
die Idee mit den baryzentrischen Koordinaten zu Gemüte
führen, weil man da evtl. näher an der Theorie ist.
Nochmal vielen Dank für das saubere Zerpflücken und
auf weitere Unterhaltungen.
Rainer
-----------------------------------------------------
P.S. Wenn das Bier kommt, trinke ich auch auf Dein Wohl.
Michael Hoppe
> Ja. Allerdings brauchst Du fuer eine Reihenfolge den Begriff der
> Orientierung und den wollte ich gerade nicht verwenden.
> Ansonsten kannst Du nicht wissen, welche Punkte benachbart sind und
> damit auch nicht, ob ein Winkel Innen- oder Aussenwinkel ist.
Wie ist denn dann durch Angabe von vier Punkten eindeutig ein Viereck
bestimmt? Aus den vier Punkte A(0, 0), B(1, 0), C(1, 1) und D(0, 1)
können durchaus verschiedene Vierecke gebildet werden: ABCD ist ein
Quadrat, ACBD eine Fliege.
> Kannte ich noch nicht. Kannst Du kurz erlaeutern oder Referenz geben
> (oder beides ;-)
Der Betrag der Determinante ist das Volumen des von den Vektoren
gebildeten Parallelepipeds; ihr Vorzeichen gibt die Orientierung der
Vektoren an. Und das heißt bei der zweireihigen Determinante: Ist
det(a, b) > 0, so ist der Winkel, der a im positiven Sinne (also
entgegen des Uhrzeigersinns) auf b dreht, kleiner als 180 Grad.
Überdies ist das Viereck ABCD konvex, falls alle vier Determinanten
det(B - A, D - A), det(C - B, A - B),
det(D - C, B - C) und det (A - D, C - D)
entweder nicht-negativ oder nicht-positiv sind. Jedenfalls kann so
bestimmt werden, ob die vier Punkte in dieser Reihenfolge ein konvexes
Viereck bilden.
Übrigens ist sind die vier Determinanten genau diejenigen, die Klaus
Nagel in seinem Programm verwendet; so ist etwa Klausens
det = a1*b2 + b1*c2 + c1*a2 - b2*c1 - c2*a1 - a2*b1 = det(C - B, A - B)
und
det3 = a1*b2 + b1*d2 + d1*a2 - b2*d1 - d2*a1 - a2*b1
= det(B - A, D - A).
Wenn das nicht zu denken gibt ...
Rainer Rosenthal
| Hier liegt die andere Ungereimtheit: Dein Programm bezeichnet manche
| Vierecke als entartet, die es nun wirklich nicht sind, etwa das
| Einheitsquadrat
Hallo Klaus,
habe sofort den Unfallbericht abgesendet. Und wie das hier
so bei dem "interaktiven Denken" so ist: Es ist wieder eine
faszinierende Erkenntnis herausgesprungen.
Ich wollte Deinen Reparatur-Vorschlägen nicht gerne folgen,
(Programmierer-Starrsinn. Trotzdem Dank für dafür.) und
bin bei meinen Reparatur-Versuchen auf die Nase gefallen.
Dann plötzlich die Einsicht, dass dieser "Entartungsfall",
ich kurzerhand als "konvex" behandelt hatte auch anders
interpretiert werden kann: Nämlich als "Trapez". Und witziger-
weise ist man dann ebenfalls fein raus, weil das Trapez
immer konvex ist.
Eine aus Faul- und Sturheit gewonnene Erkenntnis mit
dem netten Nebeneffekt, dass der Code einfach bleiben kann.
Hier noch mein Unfallbericht:
*********************************
Hallo Malte,
hier kommt ein "Unfall-Bericht" !
Dank eingehender Tests hat Klaus Nagel noch einen bösen
Fehler entdeckt.
Und zwar beim Untersuchen der ersten Determinante in
Schneidet-Funktion. Es war ja eigentlich schon eine logische
Ungereimtheit, dass die Funktion Schneidet() sich anmasst,
sich zum Thema Konvexität zu äussern. Sie hat gefälligst nur
auf die Frage "Scheidet ?" zu antworten.
Jetzt kommt aber die nächste - jetzt positive -. Überraschung:
Der Programmier-Fehler (eindeutig ! So hatte ich das nicht
gewollt.) erweist sich als HARMLOS !
Zumindest habe ich mir durch Zeichnungen klargemacht, dass
in dem Fall, dass zwei Seiten parallel sind,
entweder das Viereck zusammenklapt zu einer Strecke
und das ist der entartete Fall, der von mir mit
gutem Grund zu den konvexen zählt,
oder das Viereck tatsächlich konvex ist,
nämlich ein Trapez.
Es ist schon närrisch, was da alles zu sehen ist (und auch
zu über-sehen !).
Also doch wieder ENTWARNUNG: Das Programm tut,
der Warnungstext muss nur lauten: "Entartet oder Trapez".
Wegen der nunmehr erlaubten Frechheit der Funktion
Schneidet(), habe ich sie umgetauft in SchTest().
Gruss, Rainer
----------------------------------------------
P.S. Diese mail geht an Dich direkt, aber wegen der Dinge,
die ich beim Schreiben entdeckt habe, poste ich alles
gleich noch in die NG zum Klaus.
Thomas Haunhorst
>Malte Lance <ma...@axon.yi.org> wrote:
>
>> Ja. Allerdings brauchst Du fuer eine Reihenfolge den Begriff der
>> Orientierung und den wollte ich gerade nicht verwenden.
>> Ansonsten kannst Du nicht wissen, welche Punkte benachbart sind und
>> damit auch nicht, ob ein Winkel Innen- oder Aussenwinkel ist.
>
>Wie ist denn dann durch Angabe von vier Punkten eindeutig ein Viereck
>bestimmt? Aus den vier Punkte A(0, 0), B(1, 0), C(1, 1) und D(0, 1)
>können durchaus verschiedene Vierecke gebildet werden: ABCD ist ein
>Quadrat, ACBD eine Fliege.
Die Frage lautete:
>> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
Das heisst insbesondere, ob es ein konvexes Viereck aus diesen 4 Punkten
gibt. Oder anderes geschrieben: ob kon(p1,p2,p3,p4) ein Viereck bildet,
also p1,p2,p3,p4 Ecken sind.
Dass man aus den vorgegebenen Punkten auch andere Figuren (Fliege) basteln
kann, ist dabei ohne Belang. Tatsaechlich kann man aus den obigen Punkten
A,B,C,D ein konvexes Viereck bilden und das reicht fuer die Frage, ob es
zu diesen Punkten ein konvexes Viereck gibt. Mit Florians Loesung kann
man dann auch auf die Orientierung verzichten bzw. sie ergibt sich daraus
(klarerweise).
Gruss
Thomas.
--
Thomas Haunhorst
>
>> Ja. Allerdings brauchst Du fuer eine Reihenfolge den Begriff der
>> Orientierung und den wollte ich gerade nicht verwenden.
>> Ansonsten kannst Du nicht wissen, welche Punkte benachbart sind und
>> damit auch nicht, ob ein Winkel Innen- oder Aussenwinkel ist.
>
>Wie ist denn dann durch Angabe von vier Punkten eindeutig ein Viereck
>bestimmt? Aus den vier Punkte A(0, 0), B(1, 0), C(1, 1) und D(0, 1)
>können durchaus verschiedene Vierecke gebildet werden: ABCD ist ein
>Quadrat, ACBD eine Fliege.
Die Frage lautete:
>> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
Das heisst insbesondere, ob es ein konvexes Viereck aus diesen 4 Punkten
gibt. Oder anderes geschrieben: ob kon(p1,p2,p3,p4) ein Viereck bildet,
also p1,p2,p3,p4 vier voneinander verschiedene Ecken sind.
Malte Lance
Florian Wessels <no.spam.flo...@math.uni-muenster.de> writes:
> On Sun, 3 Sep 2000 14:07:47 +0200, ma...@axon.yi.org (Malte Lance)
> wrote:
>
>>> Wenn es zwei Punktepaare (p1,p2), (p3,p4) gibt, so dass
>>> sich L(p1,p2), L(p3,p4) im Innern schneiden. (L(x,y) Strecke
>>> zwischen x,y)
>>Hast Du vieleicht einen Ansatz fuer eine Herleitung oder eine
>>Beweisidee, wie man die Richtigkeit Deiner Behauptung zeigen
>>koennte ?
>
> Wenn du ein konvexes Viereck hast, dann nimm die Diagonalen.
Wie bestimmt man die Diagonalen ohne den Begriff der Orientierung ?
> Wenn sich zwei Segmente im Innern schneiden, dann nimm
> die Segmente als Diagonale des 4ecks, dass es geben soll.
Malte
--
Malte Lance.
Malte Lance
m...@michael-hoppe.de (Michael Hoppe) writes:
> Malte Lance <ma...@axon.yi.org> wrote:
>> Ja. Allerdings brauchst Du fuer eine Reihenfolge den Begriff der
>> Orientierung und den wollte ich gerade nicht verwenden.
>> Ansonsten kannst Du nicht wissen, welche Punkte benachbart sind und
>> damit auch nicht, ob ein Winkel Innen- oder Aussenwinkel ist.
>
> Wie ist denn dann durch Angabe von vier Punkten eindeutig ein Viereck
> bestimmt? Aus den vier Punkte A(0, 0), B(1, 0), C(1, 1) und D(0, 1)
> können durchaus verschiedene Vierecke gebildet werden: ABCD ist ein
> Quadrat, ACBD eine Fliege.
Seien die Punkte A,B,C,D (wie in Deiner Aufzählung) gegeben.
Ein Viereck ist konvex, wenn conv({A,B,C,D}) genau die Punkte
A,B,C,D als Extrempunkte hat.
Damit lässt sich natürlich nicht vernünftig arbeiten, aber genau
das hatte ich im Sinn, als ich in meinem ersten posting
"konvexes Viereck" schrieb.
Sorry nochmal, dass ich so unspezifisch war. Ich ärgere mich selbst
masslos darüber.
>> Kannte ich noch nicht. Kannst Du kurz erlaeutern oder Referenz geben
>> (oder beides ;-)
>
> Der Betrag der Determinante ist das Volumen des von den Vektoren
> gebildeten Parallelepipeds; ihr Vorzeichen gibt die Orientierung der
> Vektoren an. Und das heißt bei der zweireihigen Determinante: Ist
> det(a, b) > 0, so ist der Winkel, der a im positiven Sinne (also
> entgegen des Uhrzeigersinns) auf b dreht, kleiner als 180 Grad.
Alles klar.
Danke für die Auffrischung :-)
> Überdies ist das Viereck ABCD konvex, falls alle vier Determinanten
>
> det(B - A, D - A), det(C - B, A - B),
> det(D - C, B - C) und det (A - D, C - D)
>
> entweder nicht-negativ oder nicht-positiv sind.
Daran bastel ich gerade rum.
Leider ist die Sache doch nicht so trivial wie man oft versucht ist
zu glauben.
Kann man formal zeigen, dass für konvexe Vierecke in dem Sinne wie
ich sie oben definiert habe, stets gilt:
det(B-A,D-A)*det(C-B,A-B)*det(D-C,B-C)*det(A-D,C-D) > 0
ohne auf den Begriff der Orientierung zurückzugreifen ?
Es ist mir intuitiv klar, dass für konvexe Vierecke gilt:
det(B-A,D-A)*det(C-B,A-B)*det(D-C,B-C)*det(A-D,C-D) > 0
Hat jemand einen Ansatz oder eine Beweisidee.
Das schöne an der Formel ist ja, dass sie für jede Orientierung im
|R^2 richtig funktioniert, d.h. sie kommt völlig ohne eine
Orientierung aus (die Punkte müssen nicht in einer bstimmten Reihen-
folge sortiert sein und es wird nicht explitzit nach inneren/äusseren
Winkeln gefragt).
> Jedenfalls kann so
> bestimmt werden, ob die vier Punkte in dieser Reihenfolge ein konvexes
> Viereck bilden.
Wie gesagt, so wie ich das sehe, funktioniert es für jede Reihenfolge
von 4 Punkten richtig.
> Übrigens ist sind die vier Determinanten genau diejenigen, die Klaus
> Nagel in seinem Programm verwendet; so ist etwa Klausens
> det = a1*b2 + b1*c2 + c1*a2 - b2*c1 - c2*a1 - a2*b1 = det(C - B, A - B)
> und
> det3 = a1*b2 + b1*d2 + d1*a2 - b2*d1 - d2*a1 - a2*b1
> = det(B - A, D - A).
Durch die Vorzeichen wird die Sache doch wieder orientierungsabhängig,
oder ? Sehe ich hier etwas nicht richtig ?
> Wenn das nicht zu denken gibt ...
Wie meinst Du das ?
Erklär bitte ...
Malte
--
Malte Lance.
Malte Lance
"Rainer Rosenthal" <r.ros...@ngi.de> writes:
> Rainer Rosenthal <r.ros...@ngi.de> wrote in message
> news:8otv22$pa6$1...@news.online.de...
>| Satz K:
>| Vier Punkte in der Ebene können genau dann ein konvexes
>| Viereck bilden, wenn alle Verbindungsstrecken ohne gemein-
>| same Endpunkte auch sonst keine gemeinsamen Punkte haben.
> dass Du in Deinem Drang, alles richtig abzusichern, derart verquer
> formuliert hast, dass keiner diesen Satz als Müll bemängelt hat.
> Es kann ja sein, dass da bloss ein "nicht konvex" stehen müsste
> statt "konvex". Aber das ist nicht meine Aufgabe, das zu korrigieren,
> sondern Deine.
Jeder hat wohl gewusst, dass es bloss ein Flüchtigkeitsfehler sein
konnte.
;-)
Malte
--
Malte Lance.
Malte Lance
"Rainer Rosenthal" <r.ros...@ngi.de> writes:
>
> Klaus Nagel München <nagel...@t-online.de> wrote in message
> news:39B4BB68...@t-online.de...
> Sonderfälle reagieren könnte. (Ich kenne sie immer noch nicht,
> diese Applikation. Schade.)
Ich hab es in einem meiner Postings kurz erklärt (1 Satz), leider
finde ich das posting nicht mehr ... egal.
Meine Applikation ist ein Compressor/Dekompressor, der bivariate
diskrete Funktionen (Bilddaten) "geeignet" trianguliert und dann
auf dieser Unterteilung approximiert und danach vektorquantisiert.
Das ist zumindest bisher die Idee.
> Bezüglich "konvex" und "entartet" nehme ich eine total konservative
> Haltung ein: Ich halte mich strikt an die Definition, dass ein Gebilde
> als konvex zu bezeichnen ist, wenn mit je zwei Punkten des Gebildes
> die gesamte Verbindungsstrecke darin enthalten ist. Und das ist
> nun mal der Fall, wenn alles zusammenklatscht.
Passt.
> Die "Abweichung" beim Erkennen entarteter Vierecke muss erst
> noch durch die Applikation gerechtfertigt werden.
Deine Behandlung von entarteten Vierecken ist vollkommen in Ordnung.
Malte
--
Malte Lance.
Malte Lance
Klaus Nagel München <nagel...@t-online.de> writes:
> Klaus Nagel München wrote:Klaus Nagel
>> Die baryzentrischen Koordinaten klingen wohl zu gewaltig und schrecken
>> deswegen ab.
Keineswegs.
> Das Programm enthält einen Fehler,im Kommentar sind die Bedeutungen von
> 1 und 2 vertauscht. Unten steht das Programm verbessert, zusammen mit
> einem Testrahmen für Druckergraphik:Übersetzen mit "cc -o viereck
> viereck.c" und "viereck" aufrufen.
Erst mal vielen herzlichen Dank für Deine Mühe, die Idee gleich in Code
zu giessen.
Der schwierige Part allerdings steht noch aus:
4 paarw. versch. Punkte p1,p2,p3,p4 einer Ebene heissen Ecken eines
konvexen Vierecks, wenn sie Extrempunkte von conv({p1,p2,p3,p4}) sind,
wobei conv() die Konvexe Hülle einer Punktmenge ist.
Z.z. ist, dass fuer die Ecken aller konvexen Vierecke stets gilt:
wählt man drei Punkte (der vier) bel. aber fest, so gilt für die
baryzentrischen Koordinaten des vierten Punktes bzgl. der ersten
drei Punkte, dass zwei der drei Koordinaten > 0 sind, und die dritte
Koordinate < 0 ist (bzw. <= 0 falls man 3 kollineare Punkte für
konvexe Vierecke zulässt, was mit meiner obigen Definition kollidiert;
was mich aber nicht allzusehr stört, da ich solche Vierecke eigentlich
auch als konvex betrachte).
> Ändert man die Routine so, daß sie statt 0,0,0,0 die Werte 0,3,4,5
> liefert, dann lassen sich in der Druckergraphik auch die verschiedenen
> Fälle der Kollinearitäten unterscheiden.
Was ist eigentlich "Druckergraphik" ?
Sorry meine Ignoranz.
Malte
--
Malte Lance.
Klaus Nagel
Rainer Rosenthal schrieb:
>
> Ich wollte Deinen Reparatur-Vorschlägen nicht gerne folgen,
> (Programmierer-Starrsinn. Trotzdem Dank für dafür.) und
> bin bei meinen Reparatur-Versuchen auf die Nase gefallen
>
> Dann plötzlich die Einsicht, dass dieser "Entartungsfall",
> ich kurzerhand als "konvex" behandelt hatte auch anders
> interpretiert werden kann: Nämlich als "Trapez". Und witziger-
> weise ist man dann ebenfalls fein raus, weil das Trapez
> immer konvex ist.
>
> Eine aus Faul- und Sturheit gewonnene Erkenntnis mit
> dem netten Nebeneffekt, dass der Code einfach bleiben kann.
Ich halte meinen Code für einfacher. Vielleicht überzeugt Dich der zweite
Baryzentriker (Horst Kraemer), der heute zu uns gestoßen ist.
> Und zwar beim Untersuchen der ersten Determinante in
> Schneidet-Funktion. Es war ja eigentlich schon eine logische
> Ungereimtheit, dass die Funktion Schneidet() sich anmasst,
> sich zum Thema Konvexität zu äussern. Sie hat gefälligst nur
> auf die Frage "Scheidet ?" zu antworten.
Am Namen "Schneidet" hätte ich es erkennen müssen! Ich hatte Dein Programm
nicht abgetippt, sondern Dein Hauptprogramm durch meinen Testrahmen
ersetzt. Dabei hatte ich nicht beachtet, daß ein Teil der
Entscheidungslogik bei Dir im Rahmen untergebracht ist.
> Jetzt kommt aber die nächste - jetzt positive -. Überraschung:
> Der Programmier-Fehler (eindeutig ! So hatte ich das nicht
> gewollt.) erweist sich als HARMLOS !
>
> Zumindest habe ich mir durch Zeichnungen klargemacht, dass
> in dem Fall, dass zwei Seiten parallel sind,
>
> entweder das Viereck zusammenklapt zu einer Strecke
> und das ist der entartete Fall, der von mir mit
> gutem Grund zu den konvexen zählt,
>
> oder das Viereck tatsächlich konvex ist,
> nämlich ein Trapez.
>
> Es ist schon närrisch, was da alles zu sehen ist (und auch
> zu über-sehen !).
> Also doch wieder ENTWARNUNG: Das Programm tut,
> der Warnungstext muss nur lauten: "Entartet oder Trapez".
>
> Wegen der nunmehr erlaubten Frechheit der Funktion
> Schneidet(), habe ich sie umgetauft in SchTest().
Es bleibt zumindest ein Schönheitsfehler und nur ein Kurieren an den
Symptonen, denn die Abfrage nach Parallelität (erste Determinante wird
Null) ist überflüssig, Du wolltest an der Stelle doch auf Kollinearität
prüfen und die ist dadurch gekennzeichnet, daß - mit den Bezeichnungen aus
Deiner Routine - t oder u zu Null oder Eins wird; in meiner Korrektur wird
das geprüft. Wegen der falschen Prüfung, erkennt Deine Routine die
wirklichen Kollinearitäten nicht. Wenn das auch für Maltes Problem keine
Rolle spielt, so sollte man zumindest die Fehlermeldung unterdrücken,
damit nicht bei jedem Rechteck "Entartet oder Trapez" erscheint.
Nochmal zur Klärung von "entartet": Ich verstehe darunter die Sätze von
vier Punkten, bei denen drei oder alle Punkte auf einer Geraden liegen.
Die konvexen Hüllen sind in diesem Fall ein Dreieck, eine Strecke oder ein
Punkt und an deren Konvexität zweifelt niemand. Die Frage ist vielmehr, ob
das auch Vierecke sind, also ob etwa ein Viereck mit einem Innenwinkel von
180° als Dreieck oder Viereck zu bezeichnen ist, und die Antwort auf diese
Frage hängt vom Kontext ab:
Beispiel 1: Man will den Umfang eines Vierecks ermitteln, indem man die
vier Abstände zwischen den Eckpunkten addiert. Das geht auch, wenn alle
vier Punkte zusammenfallen, also bei schlimmster Entartung.
Beispiel 2: Man will durch jeden Eckpunkt eine Gerade legen, die mit der
konvexen Hülle nur diesen Eckpunkt gemeinsam hat. Hier scheitert man
schon, wenn ein Punkt auf der Verbindungsgeraden zweier anderer liegt.
Laß Dir das Bier trotzdem schmecken,
Klaus
Klaus Nagel
Michael Hoppe schrieb:
> Übrigens ist sind die vier Determinanten genau diejenigen, die Klaus
> Nagel in seinem Programm verwendet; so ist etwa Klausens
>
> det = a1*b2 + b1*c2 + c1*a2 - b2*c1 - c2*a1 - a2*b1 = det(C - B, A - B)
>
> und
>
> det3 = a1*b2 + b1*d2 + d1*a2 - b2*d1 - d2*a1 - a2*b1
> = det(B - A, D - A).
>
> Wenn das nicht zu denken gibt ...
>
> Michael
>
>
Die Idee des Flächenvergleichsverfahren finde ich sehr schön. Ich überlegte
auch gerade, ob das Verfahren mit den baryzentrischen Koordinaten und das
Flächenvergleichsverfahren identisch sind, weil mir die Gleichheit der
Ausdrücke aufgefallen war.
Bei der Flächenberechnung kommt man auf positive oder negative Werte, hier
geht die Orientierung ein. Ich vermute, daß man Michael Hoppes Aussage über
die die vier positiven oder vier negativen Werte verallgemeinern kann:
Die Punkte bilden genau dann ein konvexes Viereck, wenn eine gerade Anzahl
der vier Determinanten
positiv ist. Über den Beweis denke ich nach.
Klaus Nagel
Thomas Haunhorst
>In article <bqg4rsknmdajpk7gb...@4ax.com>,
> Florian Wessels <no.spam.flo...@math.uni-muenster.de> writes:
>> Wenn du ein konvexes Viereck hast, dann nimm die Diagonalen.
>
>Wie bestimmt man die Diagonalen ohne den Begriff der Orientierung ?
Im R^2 gibt es zu jedem konvexen 4-Eck genau 4 Kanten. Andererseits kannst
Du die Ecken p_1,...p_4 auf 4!/2!/2!=6 verschiedene Weisen durch Strecken
verbinden. Also sind zwei Verbindungsstrecken von gewissen Eckpunkten keine
Kanten.
Gruss
Thomas.
--
Thomas Haunhorst
> Florian Wessels <no.spam.flo...@math.uni-muenster.de> writes:
>> Wenn du ein konvexes Viereck hast, dann nimm die Diagonalen.
>
>Wie bestimmt man die Diagonalen ohne den Begriff der Orientierung ?
Im R^2 gibt es zu jedem konvexen 4-Eck genau 4 Kanten. Andererseits kannst
Du die Ecken p_1,...p_4 auf 4!/2!/2!=6 verschiedene Weisen durch Strecken
verbinden. Also sind zwei Verbindungsstrecken von gewissen Eckpunkten keine
Kanten.
Dabei heisst eine Verbindungsstrecke [a,b] Kante eines konvexen n-Ecks,
wenn K\setminus [a,b] konvex ist.
Gruss
Thomas.
--
Thomas Haunhorst
> Florian Wessels <no.spam.flo...@math.uni-muenster.de> writes:
>> Wenn du ein konvexes Viereck hast, dann nimm die Diagonalen.
>
>Wie bestimmt man die Diagonalen ohne den Begriff der Orientierung ?
Im R^2 gibt es zu jedem konvexen 4-Eck genau 4 Kanten. Andererseits kannst
Du die Ecken p_1,...p_4 auf 4!/2!/2!=6 verschiedene Weisen durch Strecken
verbinden. Also sind zwei Verbindungsstrecken von gewissen Eckpunkten keine
Kanten.
Dabei heisst eine Verbindungsstrecke [a,b] Kante eines konvexen n-Ecks K,
Malte Lance
"Rainer Rosenthal" <r.ros...@ngi.de> writes:
> Malte Lance <malte...@gmx.net> wrote in message
> news:8oqe25$f46$18$1...@news.t-online.com...
>| Hi,
>|
>| hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>| Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>| der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>|
> geholt, seinen Tipp hier allgemein zu machen:
Gute Massnahme.
> ------------------
> I responded by private email to the "4 points" person. The fastest answer
> I have seen before is: simply check whether any of the four points is
> in the convex hull of the other three, and to do that (four times), simply
> compute the areas of the triangles and see if the one which is supposed
> to be the outer triangle has an area equal to the sum of the three
> inner triangles.
Annahme: Zuweisungen und Inkrement gibt es geschenkt.
Rechenaufwand:
Methode des Flächenvergleichs:
(4 über 3) Translationsvektoren berechnen = 8 Add.
(4 über 3) mal eine 2x2 Determinante berechnen = 4 * (2 Mul. + 1 Add.)
Einmal Maximum ermitteln = 3 Vergleiche
Die verbleibenden Determinanten Werte mit abs() addieren = 4 Add.
(Fl.1 + ... + Fl.4 - max-Fl.)
Gesamtaufwand: 8 Mul., 14 Add., 3 Vergl.
Der von Dir benutzte Ansatz (Prüfen, ob sich die Liniensegmente
zweier verschiedener Punktpaare schneiden) (Bezug ist
Message-ID: <8ou0on$3l2$15$1...@news.t-online.com>):
(4 über 2) / 2 = 3 mal Schnitttest:
2 Translationsvektoren berechnen = 4 Add.
Je drei (worst case) 2x2 Determinanten (t,u,d in Deinem code)
= 3 * (2 Mul. + 1 Add.)
Je 5 Vergleiche zur Ermittlung der Ausgabe = 5 Vergl.
Gesamtaufwand: 3 * 3 * 2 Mul., 3 * (3 + 4) Add., 5 Vergl.
Das klingt auf den ersten Blick böse; es bezieht sich aber alles auf
"worst case".
Methode über Berechnung der baryzentrischen Koordinaten:
Die baryzentrischen Koordinaten eines bel. Punktes bzgl. der
drei anderen berechnen:
4 mal eine 3x3 Determinante berechnen, wobei eine Zeile der
Determinante je eine 1-Zeile ist = Je 6 Mul. + 5 Add.
Zählen der Vorzeichen der baryz. Koordinaten: 4 Vergl.
Gesamtaufwand: 4 * 4 * 6 Mul., 4 * 4 * 5 Add, 4 Vergl.
Für eine vollständige Klassifikation (konvexes, konkaves, entartetes
Viereck) mit Hilfe der baryzentrischen Koordinaten, müsste man
die baryz. Koordinaten jedes der vier Punkte bzgl. der drei
verbleibenden berechnen, d.h. (4 über 3) mal der obige Aufwand
wäre fällig.
Vom Rechenaufwand ist also die "Methode des Flächenvergleichs" die
billigste.
Die bevorzugte Mehtode ist aber auf jeden Fall die, die sich als
korrekt beweisen lässt. Dass sie alle korrekt sind behaupte ich einfach
mal.
> Numerically, this makes for a fairly robust algorithm because there is
> no division at all and we don't have to worry about degenerate cases
> (e.g. 3 collinear points). The nearest thing to a numerical problem is
> deciding whether or not (area1)=(area2)+(area3)+(area4), but in some
> sense that's not a problem: if the two numbers are so close that you
> cannot tell whether they are truly equal, then one of your points is
> very close to the triangle joining the other three. It makes perfect
> sense to flag those as being configurations of "indeterminate convexity"
> or whatever.
Ich nehme an er geht hier von reellen (bzw. float/double)
Punktkoordinaten aus.
> dave
> ---------------------
> Ich stelle es hier einfach mal ins Netz. Komischerweise hat sich in
> sci.math bisher keiner zum Thema gemeldet. Diese Reaktion kam,
> nachdem ich Dave in einer privaten mail auf das Thema aufmerksam
> gemacht hatte.
Malte
--
Malte Lance.
Malte Lance
horst....@gmx.de (Horst Kraemer) writes:
> On Sat, 2 Sep 2000 10:34:13 +0200, malte...@gmx.net (Malte Lance)
> wrote:
>> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
>> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
>> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>>
>> Ich bin fuer jede Idee und jeden Hinweis dankbar.
>
> Sorry, wenn ich so einfach hineinplatze, ohne alle 49 Antworten
Hm, ... immer wenn ich solche Kommentare lese, fühle ich mich irgendwie
schlecht ... als hätte ich etwas Triviales übersehen. Hm ...
(...snip...)
> det(Q1Q2Q3)*P4 = det(Q4Q2Q3)*P1 + det(Q1Q4Q3)*P2 +det(Q1Q2Q4)*P3
> = det(Q4Q2Q3)*P1 + det(Q4Q3Q1)*P2 +det(Q4Q1Q2)*P3
(...snip...)
> d=det (Q1Q2Q3) = (x2-x1)(y3-y1)-(y2-y1)(x3-x1)
> a=det (Q4Q2Q3) = (x2-x4)(y3-y4)-(y2-y4)(x3-x4)
> b=det (Q4Q3Q1) = (x3-x4)(y1-y4)-(y3-y4)(x1-x4)
> c=det (Q4Q1Q2) = (x1-x4)(y2-y4)-(y1-y4)(x2-x4)
(...snip...)
Eine exzellente Herleitung, aus der sich sowohl die Methode mit den
baryzentrischen Koordinaten als auch die Methode des Flachenvergleichs
ableiten lässt und die obendrein wahrscheinlich zum gewünschten Beweis
gereicht.
Auch Dir gebührt meine herzliche Anerkennung.
Vielen Dank für Deine Mühe.
Malte
> MfG
> Horst
--
Malte Lance.
Klaus Nagel
>
> Der schwierige Part allerdings steht noch aus:
> 4 paarw. versch. Punkte p1,p2,p3,p4 einer Ebene heissen Ecken eines
> konvexen Vierecks, wenn sie Extrempunkte von conv({p1,p2,p3,p4}) sind,
> wobei conv() die Konvexe Hülle einer Punktmenge ist.
> Z.z. ist, dass fuer die Ecken aller konvexen Vierecke stets gilt:
> wählt man drei Punkte (der vier) bel. aber fest, so gilt für die
> baryzentrischen Koordinaten des vierten Punktes bzgl. der ersten
> drei Punkte, dass zwei der drei Koordinaten > 0 sind, und die dritte
> Koordinate < 0 ist (bzw. <= 0 falls man 3 kollineare Punkte für
> konvexe Vierecke zulässt, was mit meiner obigen Definition kollidiert;
> was mich aber nicht allzusehr stört, da ich solche Vierecke eigentlich
> auch als konvex betrachte).
Zum Verständnis sollte man die kollinearen Fälle erst einmal außer acht
lassen, die ergeben sich später ganz von selbst. Es seien also alle
Koeffizienten ungleich Null. Wenn ich Dich richtig verstehe, fehlt Dir der
Beweis, daß die Aussage unabhängig davon ist, welchen der vier Punkte ich
auswähle. Das ist leicht zu zeigen:
Sei D=a*A+b*B +c*C mit a+b+c=1.
Löse ich diese Gleichung nach A auf, so erhalte ich:
A=(1/a)*D -(b/a)*B-(c/a)*C
Die Summe der Gewichte ist 1/a + (- b/a) + ( -(1-a-b)/a ) = (1-b-1+a+b)/a =
1, also ist A durch baryzentrische Koordinaten des Dreiecks BCD dargestellt.
Falls a<0 ,b>0 und c > 0 gilt, dann folgt 1/a < 0, -(b/a) > 0 und -(c/a) >0,
also wieder 2 positive Koordinaten.
Falls a >0, b<0 und c > 0 gilt, dann folgt 1/a >0, -(b/a) > 0 und -(c/a)< 0,
also wieder 2 positive Koordinaten; entsprechend für a>0,b>0 und c < 0;
Aus Symmetriegründen gilt das Gleiche bei der Auflösung nach B oder C.
> Was ist eigentlich "Druckergraphik" ?
Ich weiß nicht, ob Druckergraphik ein gängiger Begriff ist. Im Gegensatz zur
Bildschirmgraphik läßt sie sich auf dem Drucker ausgeben, einem Pixel
entspricht ein Druckzeichen. Wenn Du mein Programm zum Laufen bringst, siehst
Du die Druckergraphik auf dem............ Bildschirm :-). Ich werde Dir die
Ergebnisdatei mit der Druckergraphik per E-Mail schicken, sobald ich wieder
in Linux bin.
Mit besten Grüßen,
Klaus Nagel
Klaus Nagel
>
> Methode über Berechnung der baryzentrischen Koordinaten:
> Die baryzentrischen Koordinaten eines bel. Punktes bzgl. der
> drei anderen berechnen:
> 4 mal eine 3x3 Determinante berechnen, wobei eine Zeile der
> Determinante je eine 1-Zeile ist = Je 6 Mul. + 5 Add.
> Zählen der Vorzeichen der baryz. Koordinaten: 4 Vergl.
> Gesamtaufwand: 4 * 4 * 6 Mul., 4 * 4 * 5 Add, 4 Vergl.
> Für eine vollständige Klassifikation (konvexes, konkaves, entartetes
> Viereck) mit Hilfe der baryzentrischen Koordinaten, müsste man
> die baryz. Koordinaten jedes der vier Punkte bzgl. der drei
> verbleibenden berechnen, d.h. (4 über 3) mal der obige Aufwand
> wäre fällig.
>
Nein.
Die Berechnung wird nur für einen Punkt ausgeführt, es spielt keine Rolle,
welchen man auswählt!
Klaus Nagel
Malte Lance
Ja sorry, es müsste heissen:
Gesamtaufwand: 4 * 6 Mul., 4 * 5 Add, 4 Vergl.
Und ja stimmt, es reicht einmal den Test für einen Punkt bzgl. der
drei verbleibenden durchzuführen, um zu entscheiden, ob ein Punkt in
der konvexen Hülle der drei anderen enthalten ist.
Malte
> Klaus Nagel
--
Malte Lance.
Malte Lance
Ja, ich meinte:"wie bestimmt man konkret die Diagonalen?".
Dass diese Diagonalen existieren ist unbestritten (in einem konvexen 4-Eck).
Bei der konkreten Bestimmung nützt Dir Dein Existenzquantor dann auch
wieder nichts.
Und beim Beweisen nützt es mir nicht viel, wenn ich schreibe:
Gegeben 4 Punkte p1,p2,p3,p4 in der Ebene.
Wähle aus den (4 über 2) Kanten diejenigen 2 Kanten ki, kj aus, für die
gilt:
ki \cap \inner{\conv{p1,p2,p3,p4}} \neq \emptyset und
kj \cap \inner{\conv{p1,p2,p3,p4}} \neq \emptyset
ki \neq kj
(mit \inner und \conv als "das Innere einer Menge" und "die konvexe
Hülle einer Menge".)
Das wars dann; viel mehr gibt dieser Formalismus nicht her (in diesem Fall),
ausser zu behaupten, dass sich die beiden Kanten wohl schneiden müssten. Den
Beweis bleibt man mit dem Formalismus erst mal schuldig.
Malte
> Gruss
> Thomas.
--
Malte Lance.
Klaus Nagel München
>
> > Nein.
> > Die Berechnung wird nur für einen Punkt ausgeführt, es spielt keine Rolle,
> > welchen man auswählt!
>
> Ja sorry, es müsste heissen:
> Gesamtaufwand: 4 * 6 Mul., 4 * 5 Add, 4 Vergl.
Es wird noch besser, wenn man die Determinantenberechnung ändert (vgl. Michael
Hoppe, 6.9 11:36 und Horst Kraemer 6.9 8:35):
a1*b2+b1*c2+c1*a2-b2*c1-c2*a1-a2*b1 = (a1-b1)*(b2-c2)-(a2-b2)*(b1-c1)
Dann ist der
Gesamtaufwand: 4 * 2 Mul., 4 * 5 Add, 4 Vergl.
MfG
Klaus Nagel
Thomas Haunhorst
Ich moechte den Raum zum Selberdenken auch nicht leeren. (Der Beweis ist
nun wirklich ganz einfach.)
Gruss
Thomas.
--
Thomas Haunhorst
>> I responded by private email to the "4 points" person. The fastest answer
>> I have seen before is: simply check whether any of the four points is
>> in the convex hull of the other three, and to do that (four times), simply
>> compute the areas of the triangles and see if the one which is supposed
>> to be the outer triangle has an area equal to the sum of the three
>> inner triangles.
>
>Annahme: Zuweisungen und Inkrement gibt es geschenkt.
>
>Rechenaufwand:
>Methode des Flächenvergleichs:
> (4 über 3) Translationsvektoren berechnen = 8 Add.
> (4 über 3) mal eine 2x2 Determinante berechnen = 4 * (2 Mul. + 1 Add.)
> Einmal Maximum ermitteln = 3 Vergleiche
> Die verbleibenden Determinanten Werte mit abs() addieren = 4 Add.
> (Fl.1 + ... + Fl.4 - max-Fl.)
> Gesamtaufwand: 8 Mul., 14 Add., 3 Vergl.
Tatsaechlich ist es so, dass, wenn man die Flaeche eines Dreiecks ueber seine
Eckpunkte berechnet, man sich des Gaussschen
Integralsatz der Ebene bedient. Man erhaelt die Flaeche, wenn der Rand
orientiert "durchlaufen" wird. Dabei spielt es fuer den absoluten Betrag
der Flaeche keine Rolle, ob positiv oder negativ orientiert, aber die
Punkte werden nunmal nach einer gewissen Reihenfolge durchlaufen. Dieses
drueckt sich in den Determinanten aus und deshalb wird hier implizit die
Orientierung benutzt.
--
Klaus Nagel München
Ich skizziere den Beweis der Vermutung:
Die Punkte bilden genau dann ein konvexes Viereck, wenn eine gerade Anzahl
der vier Determinanten positiv ist.
Ich setze voraus, daß keine Kollinearitäten vorliegen, also sämtliche
Determinanten (und Flächen) von Null verschieden sind.
Die Aussage ist gleichwertig damit, daß eine gerade Anzahl der vier
Teildreiecke positiv orientiert ist, wenn die Dreiecksecken in der durch das
Viereck festgelegten Richtung durchlaufen werden. Ich zeige zunächst, daß für
eine spezielle Anordnung der Eckpunkte bei einem konvexen Viereck die Anzahl
der positiv orientierten Teildreiecke gerade ist, für ein spezielles
nichtkonvexes Viereck ungerade. Dann zeige ich, daß sich bei einer
Vertauschung zweier Punkte, eine gerade Anzahl von Orientierungen ändert, daß
also die behauptete Eigenschaft bei Permutationen erhalten bleibt.
1. Konvexes Viereck.
Bei der speziellen Anordnung seien die Ecken in der Reihenfolge ABCD positiv
orientiert. Dann sind alle vier Teildreiecke ABC, BCD, CDA,DAB positiv
orientiert.
2. Nichtkonvexes Viereck.
D liege im Inneren des von ABC aufgespannten Dreieck, die Reihenfolg ABC sei
positiv orientiert. Dann gilt für die Orientierung der Teildreiecke:
ABC +
BCD +
CDA -
DAB +
Also drei positiv orientierte Teildreiecke.
Vertausche ich die Punkte A und B, dann ändert sich die Orientierung in den
beiden Dreiecken, die die Seite AB enthalten. Die beiden anderen Dreiecke
enthalten die Seite CD und es gilt: Liegen A und B auf der gleichen Seite der
Geraden durch C und D, dann ändern die Dreiecke BCD und CDA ihre Orientierung
nicht, liegen A und B auf entgegengesetzten Seiten, so ändern beide ihre
Orientierung. In jedem Fall ändert sich die Orientierung bei einer geraden
Anzahl von Teildreiecken.
Wegen der Symmetrie gilt dies alles für alle vertauschten Punktpaare.
Damit ist die Behauptung bewiesen.
Das Zählen der positiven Orientierungen (modulo 2) ist gleichwertig mit dem
Zählen der positiven baryzentrischen Koordinaten. Weil beim Zählen der
Orientierung kein Punkt ausgezeichnet ist - im Gegensatz zum baryzentrischen
Verfahren-, habe ich aus ästhetischen Gründen meine Subroutine geändert , die
Abfrage der vier Determinanten ist jetzt voll symmetrisch ist; dadurch wird
es klarer, daß diese Prüfung nur einmal auferufen werden muß.
Außerdem habe ich die Determinantenberechnung nach den Vorschlägen von Michael
Hoppe und Horst Kraemer verschnellert. Eine neue Version des Programms steht
unten.
Klaus Nagel
#include <stdio.h>
/* ----------------- Konvex 07.09.2000 K. Nagel -------------------- */
/* */
/* Konvex prüft, ob die vier Punkte (a1,a1) ... (d1,d2) ein konvexes */
/* Viereck aufspannen. */
/* Ergebnis: */
/* 0 bedeutet mindestens 3 Punkte kollinear. */
/* 1 bedeutet nicht konvex. */
/* 2 bedeutet konvex. */
/* */
/* ----------------------------------------------------------------- */
int konvex(int a1,int a2,int b1,int b2,int c1,int c2,int d1,int d2)
{
int det0,det1,det2,det3,anzahl ;
det0 = (b1-c1)*(c2-d2)-(b2-c2)*(c1-d1) ;
if(det0==0) return(0); /* D B C kollinear */
det1 = (c1-d1)*(d2-a2)-(c2-d2)*(d1-a1) ;
if(det1==0) return(0); /* A D C kollinear */
det2 = (d1-a1)*(a2-b2)-(d2-a2)*(a1-b1) ;
if(det2==0) return(0); /* A B D kollinear */
det3 = (a1-b1)*(b2-c2)-(a2-b2)*(b1-c1) ;
if(det3==0) return(0); /* A B C kollinear */
anzahl = 0 ;
if ( det0 > 0) anzahl++ ;
if ( det1 > 0) anzahl++ ;
if ( det2 > 0) anzahl++ ;
if ( det3 > 0) anzahl++ ;
if ((anzahl & 1) == 0 ) return(2); /* Bei gerader Anzahl konvex */
return(1) ;
}
/* ------------------ Testrahmen mit Druckergraphik ------------------ */
void main()
{
int a1,a2,b1,b2,c1,c2,d1,d2,ergebnis;
a1 = 20 ; a2 = 20 ;
b1 = 20 ; b2 = 40 ;
c1 = 40 ; c2 = 40 ;
for ( d2 = 0 ; d2 < 60 ; d2++)
{
printf("\n %2d : ",d2);
for ( d1 = 0 ; d1 < 60 ; d1++)
{
ergebnis=konvex(a1,a2,b1,b2,c1,c2,d1,d2);
printf("%1d",ergebnis);
}
}
printf("\n");
}
Thomas Haunhorst
>> I responded by private email to the "4 points" person. The fastest answer
>> I have seen before is: simply check whether any of the four points is
>> in the convex hull of the other three, and to do that (four times), simply
>> compute the areas of the triangles and see if the one which is supposed
>> to be the outer triangle has an area equal to the sum of the three
>> inner triangles.
>
>Annahme: Zuweisungen und Inkrement gibt es geschenkt.
>
>Rechenaufwand:
>Methode des Flächenvergleichs:
> (4 über 3) Translationsvektoren berechnen = 8 Add.
> (4 über 3) mal eine 2x2 Determinante berechnen = 4 * (2 Mul. + 1 Add.)
> Einmal Maximum ermitteln = 3 Vergleiche
> Die verbleibenden Determinanten Werte mit abs() addieren = 4 Add.
> (Fl.1 + ... + Fl.4 - max-Fl.)
> Gesamtaufwand: 8 Mul., 14 Add., 3 Vergl.
Tatsaechlich ist es so, dass, wenn man die Flaeche eines Dreiecks ueber seine
Eckpunkte berechnet, man sich des Gaussschen
Integralsatz der Ebene bedient. Man erhaelt die Flaeche, wenn der Rand
orientiert "durchlaufen" wird. Dabei spielt es fuer den absoluten Betrag
der Flaeche keine Rolle, ob positiv oder negativ orientiert, aber die
Punkte werden nunmal nach einer gewissen Reihenfolge durchlaufen. Dieses
drueckt sich in den Determinanten aus und deshalb wird hier implizit die
Orientierung benutzt.
Gruss
Thomas.
--
Thomas Haunhorst
>> I responded by private email to the "4 points" person. The fastest answer
>> I have seen before is: simply check whether any of the four points is
>> in the convex hull of the other three, and to do that (four times), simply
>> compute the areas of the triangles and see if the one which is supposed
>> to be the outer triangle has an area equal to the sum of the three
>> inner triangles.
>
>Annahme: Zuweisungen und Inkrement gibt es geschenkt.
>
>Rechenaufwand:
>Methode des Flächenvergleichs:
> (4 über 3) Translationsvektoren berechnen = 8 Add.
> (4 über 3) mal eine 2x2 Determinante berechnen = 4 * (2 Mul. + 1 Add.)
> Einmal Maximum ermitteln = 3 Vergleiche
> Die verbleibenden Determinanten Werte mit abs() addieren = 4 Add.
> (Fl.1 + ... + Fl.4 - max-Fl.)
> Gesamtaufwand: 8 Mul., 14 Add., 3 Vergl.
Tatsaechlich ist es so, dass, wenn man die Flaeche eines Dreiecks in dieser
Weise ueber seine Eckpunkte berechnet, man sich des Gaussschen
Klaus Nagel München
> Hi,
>
> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Ich bin fuer jede Idee und jeden Hinweis dankbar.
>
> Malte.
>
> --
> Malte Lance.
Hallo ,
wenn ich richtig gezählt habe, ist dieses der achtzigste Beitrag. Da
verliert man den Überblick. Darum hier eine Zusammenfassung wesentlicher
Ergebnisse:
Bei vier Punkten in der Ebene soll zwischen folgenden Anordnungen
unterschieden werden:
1. Konvex: Die konvexe Hülle ist ein Viereck, alle
Innenwinkel sind kleiner als 180°.
2. Nicht konvex: Die konvexe Hülle ist ein Dreieck, einer der Punkte
liegt im Inneren dieses Dreiecks.
3. Entartet: Mindestens drei Punkte liegen auf einer Geraden.
Die konvexe Hülle ist entweder ein Dreieck, eine Strecke oder ein Punkt.
Drei Verfahren wurden vorgeschlagen:
1. Das Diagonalenverfahren benutzt folgende Eigenschaft:
Bei einem konvexen Viereck schneiden die Diagonalen einander im Inneren.
Es wird geprüft, ob eines der drei Streckenpaare (AB,CD) , (AC,BD) oder
(AD,BC) diese Bedingung erfüllt. Kollinearität liegt vor, wenn solch ein
Schnittpunkt auf einen Endpunkt der Strecke fällt.
2. Das Flächenverfahren benutzt die Eigenschaft, daß im Fall 2 (nicht
konvex) ein Punkt im Inneren des Dreiecks liegt, das von den drei
anderen aufgespannt wird, und das die Fläche dieses Dreiecks der Summe
der drei anderen gleicht.
Diese Eigenschaft wird geprüft, bei Kollinearität ist mindestens eine
Dreiecksfläche gleich Null.
3. Das baryzentrische Verfahren stellt einen der vier Punkte durch die
anderen dar: D=a*A+b*B+c*C, mit a+b+c=1.
Im Fall 1 (konvex) gilt genau, wenn zwei der baryzentrischen
Koordinaten positiv, die dritte negativ. Bei Kollinearität wird
mindestens eine Koordinate Null.
Ich habe die Verfahren 2 und 3 in C programmiert (Verfahren 1 stammt von
Rainer Rosenthal), und Laufzeiten gemessen für Festkomma- und
Gleitkommarechnung. Programmcodes und Meßergebnisse stehen unten.
Die Verfahren 2 und 3 sind sehr ähnlich, beide berechnen die gleichen
vier Determinanten, nur mit unterschiedlicher Begründung. Im 3.
Verfahren werden die positiven Vorzeichen dieser Determinanten gezählt,
im zweiten Verfahren werden die Beträge der Determinanten gebildet, um
zu prüfen, ob das größte Dreieck so groß ist wie die drei anderen
zusammen. Die Laufzeiten von 2 und 3 unterscheiden sich nur geringfügig.
Beim Flächenverfahren kommt die Berechnung der Absolutbeträge hinzu,
außerdem erfordert ind der Gleitkommaversion der Vergleich der Flächen
eine Genauigkeitschranke, da wegen der Darstellungsungenauigkeiten nicht
auf Gleichheit geprüft weden kann. Genau genommen müßte die relative
Abweichung benutzt werden.
Programmcode für die drei Verfahren (Festkommavariante):
/*------------------ Baryzentrisches Verfahren ------------------ */
/* --------------- baryverf 04.09.2000 K. Nagel -------------------- */
/* */
/* baryverf prüft, ob die vier Punkte (a1,a2) ... (d1,d2) ein */
/* konvexes Viereck aufspannen. */
/* Ergebnis: */
/* 0 bedeutet mindestens 3 Punkte kollinear. */
/* 1 bedeutet nicht konvex. */
/* 2 bedeutet konvex. */
/* */
/* ----------------------------------------------------------------- */
int
baryverf (int a1, int a2, int b1, int b2, int c1, int c2, int d1, int
d2)
{
int det0, det1, det2, det3, anzahl;
det0 = (b1 - c1) * (c2 - d2) - (b2 - c2) * (c1 - d1);
if (det0 == 0)
return (0); /* D B C kollinear */
det1 = (c1 - d1) * (d2 - a2) - (c2 - d2) * (d1 - a1);
if (det1 == 0)
return (0); /* A D C kollinear */
det2 = (d1 - a1) * (a2 - b2) - (d2 - a2) * (a1 - b1);
if (det2 == 0)
return (0); /* A B D kollinear */
det3 = (a1 - b1) * (b2 - c2) - (a2 - b2) * (b1 - c1);
if (det3 == 0)
return (0); /* A B C kollinear */
anzahl = 0;
if (det0 > 0)
anzahl++;
if (det1 > 0)
anzahl++;
if (det2 > 0)
anzahl++;
if (det3 > 0)
anzahl++;
if (anzahl & 1)
return (1);
return (2);
}
/*------------------ Flaechen Verfahren ------------------ */
int
flaeverf (int a1, int a2, int b1, int b2, int c1, int c2, int d1, int
d2)
{
int det0, det1, det2, det3, anzahl, maxi, summe;
det0 = abs ((b1 - c1) * (c2 - d2) - (b2 - c2) * (c1 - d1));
if (det0 == 0)
return (0); /* D B C kollinear */
det1 = abs ((c1 - d1) * (d2 - a2) - (c2 - d2) * (d1 - a1));
if (det1 == 0)
return (0); /* A D C kollinear */
det2 = abs ((d1 - a1) * (a2 - b2) - (d2 - a2) * (a1 - b1));
if (det2 == 0)
return (0); /* A B D kollinear */
det3 = abs ((a1 - b1) * (b2 - c2) - (a2 - b2) * (b1 - c1));
if (det3 == 0)
return (0); /* A B C kollinear */
maxi = (det0 > det1) ? det0 : det1;
if (det2 > maxi)
maxi = det2;
if (det3 > maxi)
maxi = det3;
summe = det0 + det1 + det2 + det3;
if (maxi == summe - maxi)
return (1);
return (2);
}
/*------------------ Diagonalen Verfahren ------------------ */
#define PARALLEL 1
#define KOLLINEAR 2
#define AUSSEN 4
#define INNEN 8
int
Schneidet (int xP, int yP, int xQ, int yQ, int xR, int yR, int xS, int
yS)
{
int d, t, u;
d = (xQ - xP) * (yR - yS) - (xR - xS) * (yQ - yP);
if (d == 0)
return (PARALLEL);
t = (yR - yS) * (xR - xP) - (xR - xS) * (yR - yP);
u = (yR - yP) * (xQ - xP) - (xR - xP) * (yQ - yP);
if (t == 0 || t == d || u == 0 || u == d)
return (KOLLINEAR);
if (d < 0.)
{
d = -d;
t = -t;
u = -u;
}
if (t < 0 || t > d || u < 0 || u > d)
return (AUSSEN);
return (INNEN);
}
int
diagverf (int a1, int a2, int b1, int b2, int c1, int c2, int d1, int
d2)
{
int erg1, erg2, erg3, erg, gesamt;
erg1 = Schneidet (a1, a2, b1, b2, c1, c2, d1, d2);
erg2 = Schneidet (a1, a2, d1, d2, b1, b2, c1, c2);
erg3 = Schneidet (a1, a2, c1, c2, b1, b2, d1, d2);
erg = erg1 | erg2 | erg3;
if (erg & INNEN)
return (2);
if (erg & KOLLINEAR)
return (0);
return (1);
}
/* ------------------------------------------------------ */
Ergebnisse der Laufzeitmessungen.
200 MHz -Pentiumprozessor, Linux, gcc C-Compiler ohne Optimierung.
Zeit im Mikrosekunden für einen Durchlauf.
| Festkomma | Gleitkomma |
| Bary Fläche Diag | Bary Fläche Diag |
|---------------|---------------
| 0.41 0.46 1.42 | 0.81 0.91 2.35 |
------------------------------------------------------
Wenn jemand aus dem Code noch ein paar Nanosekunden herausquetschen
kann, dann bin ich gern bereit, es zu messen.
Klaus Nagel.
Rainer Rosenthal
> Ergebnisse der Laufzeitmessungen.
> 200 MHz -Pentiumprozessor, Linux, gcc C-Compiler ohne Optimierung.
> Zeit im Mikrosekunden für einen Durchlauf.
> | Festkomma | Gleitkomma |
> | Bary Fläche Diag | Bary Fläche Diag |
> |---------------|---------------
> | 0.41 0.46 1.42 | 0.81 0.91 2.35 |
Hallo Klaus,
feine Arbeit ! Und schön dass der Thread die achtzig noch
überschreitet. Ich darf schon mal ganz geheimnisvoll ankündigen,
dass ich aus dem "Trapez-Unfall" gelernt habe und dem
von Malte angemahnten Theorie-Teil näher gerückt bin.
Mein Beitrag wird lauten: "Vierecke: x + y = A + B"
x+y: bedeutet, dass ich eine Klassifikation der Vierpunkt-
Mengen in x-Typen und y-Typen gefunden habe.
A wie Algorithmus zur Konvexitätsbestimmung.
B wie Beweis, dass der Algorithmus wirklich die konvexen
Vierecke kennzeichnet.
Bezüglich der Rechenzeit des neuen Algorithmus bin ich sehr
optimistisch, weil ich nur noch das einzige Streckenpaar
P1-P2, P3-P4 untersuche. Ich habe noch keine einzige Zeile
codiert, biete ihn Dir aber jetzt schon gerne als vierten bzw.
dreieinhalbten Kandidaten für Deine Sammlung an.
Der Beweis wird den Bezug zur wohlbekannten Konvexität
herstellen: Mit je zwei Punkten des Vierecks liegt die gesamte
Verbindungsstrecke darin.
Um nicht wieder zu pfuschen, werde ich zwar noch ein Weilchen
schrauben, aber nur auf meinem Schreibblock. Ich werde mich
sicher beherrschen können, heute nacht noch loszuposten.
Fröhliche Drahtverlängerung. Deine schöne Homepage
http://home.t-online.de/home/nagel.klaus
habe ich in de.sci.astronomie weiterempfohlen. Bei mir
war leider noch wenig los in den bewegten Bildern !?
Rainer
-----------------------------------------------------------
4 4444 4444 4444 4444 4444 4444 4
Gottfried Helms
auch im 82.-Beitrag noch ein paar Ergänzungn
Klaus Nagel schrieb:
(...Zusammenfassung bisher dargestellter Methoden...)
<snip>
1) Flächenmethode
Bei der Flächenmethode finde ich einen Aufwand von (5,2)
5 Subtraktionen, 2 Multiplikationen pro Dreieck
Aus der Verallgemeinerung auf das n-Eck geht hervor, daß es
besser ist zu sagen:
man braucht "maximal N" Flächenberechnungen,
anstatt davon auszugehen, daß man
"alle" Flächensummen miteinander vergleichen
muß.
Man braucht nämlich nur den Umlauf der Dreiecke mit benachbartem
Index i: also nur
F(ABC),F(BCD),F(CDE),F(DEF),...F(XYA),F(YAB)
(gleich N) Dreiecke zu testen und nicht die
Gesamtfläche berechnen.
Darüberhinaus kann man mit der Berechnung abbrechen, wenn der
erste Orientierungswiderspruch auftritt.
Da der Orientierungsvergleich ausreicht, brauche ich noch
nicht einmal die reale Flächengröße, sondern nur den Testwert,
der ihr Vorzeichen angibt (=T(ABC)).
Der Gesamtaufwand beim N-Eck ist also etwa
2 * Aufwand(F_D) <= Gesamtaufwand <= N*Aufwand(T())
Übrigens brauchen wir nur N-2 Tests auf Kollinearität,
um zu wissen, ob das gesamte N-Eck kollinear ist. (aber
so war das betreffende Code-Schnipsel von Klaus sicherlich
auch nicht gemeint)
2) Orientierungsfreies Verfahren?
Malte wollte eigentlich ein "Orientierungfreies" Verfahren.
Das kann ich mir nur so vorstellen, daß man mit den Längen
der Strecken, also mit Distanzen arbeitet, und die Matrix
der Punkt-Distanzen analysiert. Ist das eigentlich richtig
gedacht?
Ich habe hiermit versucht, die Methode: "liegt ein Punkt
im Dreieck der andern?" zu behandeln.
Mit der strengen Behandlung nur der Längen habe aber bisher nur
Ergebnisse, die im Prinzip die Position des 4.Punktes gegen
die Schnittflächen 3 er Kreise testen - und nicht gegen
die geraden Kanten eines 3-Ecks.
Verwende ich die Methode der Bestimmung des __Abstandes eines
Punktes zu einer Geraden__ (also zB. Abstand(D,AB)), muß man
im Endeffekt doch wieder Vorzeichen miteinander vergleichen,
Abs(Abstand(D,AB))<=Abs(Abstand(C,AB))
UND Sign(Abstand(D,AB))=Sign(Abstand(C,AB))
um zu erfahren, ob Punkt D näher an Seite(AB) liegt als Punkt C.
Übrigens kann ich hier dieselbe Berechnungsmethode anwenden
wie für die Fläche, aber anscheinend brauche ich eine
zusätzliche Division, wenn ich die Skalierung des n-Ecks
beibehalten will.
Ich nehme an, daß diese Methode auch _nicht orientierungsfrei_
ist, weil ich einen Vorzeichenvergleich machen muß?
(Hoffe, es ist nicht ALLES redundant respektive der vorigen
81 Artikel...)
Gottfried.
========================================================
Zu dem Aufwand der nötigen Berechnungen:
1) ----------------------------------------------------
Flächenberechnung mit maximaler Aufwandseinsparung:
(Testwert = Fläche*2)
Die Berechnung 1 Dreiecks-Testwertes T_D(ABC) erfordert
Subtrak Multipli
tionen kationen
1 Translation von 4 Koordinaten
C'=C-A, B'=B-A 4
1 2-D-Determinate : 1 2
Cy" = Cy'Bx'-Cx'By'
------------------------------------------------------
Subtraktionen, 5
Multiplikationen 2
Wenn ich nur an der Berechnung
eines Testwertes interessiert
bin, kann ich die Halbierung des
Ergebnisses einsparen :
Fläche des Dreiecks = Cy"/2 ( 1)
Die Y-Koordinate von C ist dann direkt das Doppelte der
Fläche und ihr Vorzeichen der Rückgabewert von T_D(ABC)
Habe ich ganzzahlige Koordinaten, kann ich übrigens komplett
mit Integern arbeiten.
2)---------------------------------------------------------
Ausgedrückt als Problem von n-Ecken:
Hierzu braucht man nicht alle Flächen zu berechnen, sondern nur im
Umlauf die Orientierung der Rand-Dreiecke zu prüfen:
T_D(ABC), T_D(BCD), T_D(CDE)....
Alle diese Testwerte haben entweder das Vorzeichen +, - oder sind 0.
Es reicht zu erkennen, daß sich 2 Flächen im Vorzeichen widersprechen.
Nach dem ersten Widerspruch in der Orientierung kann abgebrochen
werden.
3)-------------------------------------------------------------
Pseudocode :
============
function T_D(ABC) // liefert die Orientierung für 1 Dreieck
Bx=Bx-Ax By=By-Ay
Cx=Cx-Ax Cy=Cy-Ay
Testwert = Cy*Bx-Cx*By
// Fläche = Testwert * 0.5 //
return(sign(Testwert)) // +1,0 oder -1
endfunction
function test_N_eck(ABCDEF...) // testet ein N-eck
vorige_orientierung = T_D(ABC) // liefert +1,0 oder -1
for i=2 to anzahl
akt_Orientierung = T_D(BCD) // liefert +1,0 oder -1
if vorige_orientierung*akt_orientierung=-1 then RETURN("konvex")
if akt_orientierung<>0 then vorige_orientierung=akt_orientierung
next i
if vorige_orientierung= 0 then RETURN("komplett kollinear")
RETURN("konkav")
endfunction
===========================
Malte Lance
[...]
> Ich skizziere den Beweis der Vermutung:
[...]
Die Idee ist gut, nur basiert sie absolut auf "Orientierung" :-(
Malte
--
Malte Lance.
Thomas Haunhorst
Jeder konvexe Polyeder ist kompakt.
Gruss
Thomas.
--
Thomas Haunhorst
Jeder konvexe Polyeder ist kompakt. (Vielleicht hilft Dir das bei Deinen
weiteren Ueberlegungen)
Gruss
Thomas.
--
Thomas Haunhorst
Jeder konvexe Polyeder ist kompakt. (Vielleicht hilft Dir das bei Deinen
weiteren Ueberlegungen; im R^n sind alle kompakten Mengen abgeschlossen und
beschraenkt.)
Gruss
Thomas.
--
Thomas Haunhorst
Jeder konvexe Polyeder ist kompakt. (Vielleicht hilft Dir das bei Deinen
weiteren Ueberlegungen; im R^n sind alle kompakten Mengen abgeschlossen und
beschraenkt und umgekehrt.)
Gruss
Thomas.
--
Klaus Nagel
mir ist nicht klar geworden, auf was Du hinaus willst. Der Übergang vom
Viereck zum N-Eck verwirrt mich ganz und gar. Ich habe den Eindruck, Du
prüfst, ob ein N-Eck mit vorgegebener Reihenfolge der Eckpunkte konvex
ist. Das Problem ist, daß bei Maltes Aufgabe die Reihenfolge nicht bekannt
ist.
Gottfried Helms schrieb:
> Aus der Verallgemeinerung auf das n-Eck geht hervor, daß es
> besser ist zu sagen:
> man braucht "maximal N" Flächenberechnungen,
> anstatt davon auszugehen, daß man
> "alle" Flächensummen miteinander vergleichen
> muß.
Wo steht, daß alle Flächensummen verglichen werden müssen? Es wird
geprüft, ob das größte Dreieck so groß ist wie die drei anderen zusammen.
Im Programm habe ich die Summe der drei berechnet als
F1+F2+F3+F4-Fmax, die Abfrage lautet dann: 2*Fmax == F1+F2+F3+F4 ?; geht
es einfacher oder schneller?
> Man braucht nämlich nur den Umlauf der Dreiecke mit benachbartem
> Index i: also nur
>
> F(ABC),F(BCD),F(CDE),F(DEF),...F(XYA),F(YAB)
>
> (gleich N) Dreiecke zu testen und nicht die
> Gesamtfläche berechnen.
Die Orientierung der Randdreiecke ist gleichwertig mit der
Richtungsänderung nach links oder nach rechts. Wenn die Punkte Ecken eines
konvexen Polygons sein sollen, dann muß die Richtungsänderung immer im
gleichen Sinn sein. Das ist aber nicht hinreichend, Gegenbeispiel
Pentagramm, oder bei größerem N Schleifenbahnen nur aus Linkskurven oder
Epizykelbahnen ( zu sehen auf meiner Homepage:
<http://home.t-online.de/home/nagel.klaus> unter Astronomie).
> Übrigens brauchen wir nur N-2 Tests auf Kollinearität,
> um zu wissen, ob das gesamte N-Eck kollinear ist. (aber
> so war das betreffende Code-Schnipsel von Klaus sicherlich
> auch nicht gemeint)
Es ist klar, daß alle vier Punkte auf einer Geraden liegen, wenn zwei
Tripel kollinear sind. Die Berechnung der Determinanten diente nicht dazu,
die Kollinearität festzustellen - das ist nur ein willkommener Nebeneffekt
-, sondern um später die Vorzeichen zu zählen.
> 2) Orientierungsfreies Verfahren
In der symmetrischen Form, in der ich das baryzentrische Verfahren
implementiert habe, kann man es auch so interpretieren: Es prüft, ob 0,2
oder 4 der Teildreiecke positiv orientiert sind; auch das charakterisiert
die konvexen Vierecke (vgl. mein Beitrag vom 7.9 12:11). Es entsteht ein
philosophisches Problem: Wenn Verfahren A orientierungsfrei ist, Verfahren
B nicht, beide aber zum gleichen Programmcode führen, ist dann Verfahren A
wirklich orientierungsfrei? Ich vermute, daß es bei Malte um ein
praktisches Problem geht, und er nicht in diesem Dilemma steckt.
Mit besten Grüßen
Klaus Nagel
Christian Helms
ich schreibe hier unter der Kennung von meinem Bruder, bei
dem ich zu Besuch bin - nicht verwirren lassen...
Gottfried.
"Klaus Nagel" <nagel...@t-online.de> schrieb im Newsbeitrag
news:39BA95F0...@t-online.de...
> Hallo Gottfried,
> mir ist nicht klar geworden, auf was Du hinaus willst. Der Übergang vom
> Viereck zum N-Eck verwirrt mich ganz und gar.
Das war nicht meine Absicht... Geht das ganze übrigens auch analog mit
Tetraedern...;-)
>
Ich habe den Eindruck, Du
> prüfst, ob ein N-Eck mit vorgegebener Reihenfolge der Eckpunkte konvex
> ist. Das Problem ist, daß bei Maltes Aufgabe die Reihenfolge nicht bekannt
> ist.
Ich hatte es so verstanden. Ich bin nicht davon ausgegangen, daß die Frage
ist,
ob "4 vorgegebene Punkte so verbunden werden können, daß..."
In meinen Zettel-Überlegungen war ich noch einen Schritt weiter gegangen und
hatte überlegt, daß man eine Sortierung der Punkte vornehmen könnte, um
einen
konvexen Pfad zu finden, "wenn er denn möglich ist." Dies entspräche dann
eher
der Aufgabe: "Gibt es eine konvexe Hülle für vier Punkte?" - wahrscheinlich
haben
wir die Aufgabe unterschiedlich verstanden.
>
> Gottfried Helms schrieb:
>
> > Aus der Verallgemeinerung auf das n-Eck geht hervor, daß es
> > besser ist zu sagen:
> > man braucht "maximal N" Flächenberechnungen,
> > anstatt davon auszugehen, daß man
> > "alle" Flächensummen miteinander vergleichen
> > muß.
>
> Wo steht, daß alle Flächensummen verglichen werden müssen? Es wird
> geprüft, ob das größte Dreieck so groß ist wie die drei anderen zusammen.
Anscheinend habe ich Deinen Artikel nicht genau genug gelesen. Ich
hatte noch die Überlegungen anderer Autoren (und meine eigenen) im Kopf,
Ansatz (1)
daß man eine Flächensumme aller benachbarten Dreiecke mit der Spitze A,
F(ABC) + F(ACD)
mit der entsprechenden Flächensumme der Dreiecke mit der Spitze B
F(BCD) + F(BDA)
vergleichen muß. Dies sind nur 4 Dreiecke und nicht "alle" - da habe ich
mich mißverständlich ausgedrückt - Sorry. "Alle" tauchte einfach in diesem
Zusammenhang öfters auf - und das fand ich ungünstig und beantwortenswert.
> Im Programm habe ich die Summe der drei berechnet als
> F1+F2+F3+F4-Fmax, die Abfrage lautet dann: 2*Fmax == F1+F2+F3+F4 ?; geht
> es einfacher oder schneller?
-------------------
Im n-Eck-Fall summiert man nach dem obigen Ansatz (1) (mindestens)
2 mal (n-2) Dreiecke, also (mindestens) 2n-4 Dreiecksberechnungen.
Bei meinem Verfahren sind es maximal n.
*** Allerdings hast Du mich auf den Fehler aufmerksam gemacht,
daß mein Verfahren eine spiralige Anordnung der Punkte nicht
berücksichtigt -
*** Also: meine Idee reicht offensichtlich nicht aus. (erst mal auf Eis
legen...).
> Richtungsänderung nach links oder nach rechts. Wenn die Punkte Ecken eines
> konvexen Polygons sein sollen, dann muß die Richtungsänderung immer im
> gleichen Sinn sein. Das ist aber nicht hinreichend, Gegenbeispiel
> Pentagramm, oder bei größerem N Schleifenbahnen nur aus Linkskurven oder
> Epizykelbahnen ( zu sehen auf meiner Homepage:
> <http://home.t-online.de/home/nagel.klaus> unter Astronomie).
Tja, das ist einfach einleuchtend.
> > 2) Orientierungsfreies Verfahren
>
> In der symmetrischen Form, in der ich das baryzentrische Verfahren
> implementiert habe, kann man es auch so interpretieren: Es prüft, ob 0,2
> oder 4 der Teildreiecke positiv orientiert sind; auch das charakterisiert
> die konvexen Vierecke (vgl. mein Beitrag vom 7.9 12:11). Es entsteht ein
> philosophisches Problem: Wenn Verfahren A orientierungsfrei ist, Verfahren
> B nicht, beide aber zum gleichen Programmcode führen, ist dann Verfahren A
> wirklich orientierungsfrei? <...snip...>
Ich nehme an, NICHT. Ich denke, wir sehen das gleich.
> <.. snip...> Ich vermute, daß es bei Malte um ein
> praktisches Problem geht, und er nicht in diesem Dilemma steckt.
Bezüglich Malte: er hatte mehrfach darauf insistiert,
und deshalb dachte ich mir, daß es einen wichtigen Grund dafür gibt, und
fand es interessant zu kapieren, was das eigentlich ist...
Tja, trickreich, trickreich....
Gottfried.
Klaus Nagel
> ....... Es wird
> geprüft, ob das größte Dreieck so groß ist wie die drei anderen zusammen.
> Im Programm habe ich die Summe der drei berechnet als
> F1+F2+F3+F4-Fmax, die Abfrage lautet dann: 2*Fmax == F1+F2+F3+F4 ?; geht
> es einfacher oder schneller?
Ja, es geht einfacher, aber das ist nur als Spielerei zu betrachten: Man
sucht Fmax nicht explizit, sondern prüft stattdessen, ob eine der
Dreiecksflächen F1,F2,F3 oder F4 der halben Gesamtsumme gleicht. Beim ersten
Übereinstimmen ist man fertig. Den C-Code füge ich an.
Dies ist zwar eleganter, aber nicht schneller, in der Festkommaversion sogar
erheblich langsamer, wenn man die Summe durch 2 teilt, also
Halbsumme = (F1+F2+F3+F4)/2 ; schreibt. Mit einer Verschiebung um ein Bit
nach rechts, also
Halbsumme = (F1+F2+F3+F4)>>1; erreicht man wieder die alte Geschwindigkeit
Ein optimierender Compiler könnte das selbst finden, doch habe ich für diese
Messungen mit der Optimierung schlechte Erfahrungen gemacht:Teilweise war die
optimierte Version langsamer oder sogar falsch (Flächenverfahren mit
Gleitkommarechnung und Stufe O3 bei der Optimierung) .
Klaus Nagel
int flaeverf (int a1, int a2, int b1, int b2, int c1, int c2, int d1, int d2)
{
int det0, det1, det2, det3, summe;
det0 = abs ((b1 - c1) * (c2 - d2) - (b2 - c2) * (c1 - d1));
if (det0 == 0) return (0); /* D B C kollinear */
det1 = abs ((c1 - d1) * (d2 - a2) - (c2 - d2) * (d1 - a1));
if (det1 == 0) return (0); /* A D C kollinear */
det2 = abs ((d1 - a1) * (a2 - b2) - (d2 - a2) * (a1 - b1));
if (det2 == 0) return (0); /* A B D kollinear */
det3 = abs ((a1 - b1) * (b2 - c2) - (a2 - b2) * (b1 - c1));
if (det3 == 0) return (0); /* A B C kollinear */
summe = (det0 + det1 + det2 + det3)>>1; /* immer gerade! */
if(det0==summe || det1==summe || det2==summe || det3==summe )
return (1);
return (2);
}
--
Klaus Nagel
> Hi,
>
> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Ich bin fuer jede Idee und jeden Hinweis dankbar.
>
> Malte.
>
> --
> Malte Lance.
Hallo Malte,
ich habe noch ein weiteres Verfahren programmiert, welches mit dem von
Rainer Rosenthal angekündigtem Verfahren übereinstimmt. Man wählt
willkürlich zwei disjunkte Punktpaare und schneidet die dadurch
definierten Geraden. Liegt der Schnittpunkt auf beiden Geraden zwischen
den Punkten, dann hat man die Diagonalen eines konvexen Vierecks
erwischt. Liegen beide außerhalb oder gibt es keinen Schnittpunkt, dann
sind es gegenüberliegende Seiten eines konvexen Vierecks. Im nicht
konvexen Fall liegt der Schnittpunkt auf der einen Geraden innerhalb des
Intervalls, auf der anderen außerhalb. Für die Entscheidung sind nur
drei (statt vier beim baryzentrischen Verfahren) Determinanten zu
berechnen , dafür sind die Abfragen etwas komplizierter, die
Geschwindigkeit müßte im Eizelfall gemessen werden. Das Programm füge
ich an, den Testrahmen für die vier Verfahren stelle ich auf Wunsch gern
zur Verfügung.
Klaus Nagel
--
Klaus Nagel
> Hi,
>
> hat jemand eine Idee wie man testen kann, ob vier Punkte im R^2
> Ecken eines konvexen Vierecks sind, ohne dabei auf den Begriff
> der 'Orientierung' bzw. 'orientierte Basis' zurueckzugreifen ?
>
> Ich bin fuer jede Idee und jeden Hinweis dankbar.
>
> Malte.
>
> --
> Malte Lance.
Hier ist das vergessene Programm.
Klaus Nagel
int
neuverf (int a1, int a2, int b1, int b2, int c1, int c2, int d1, int d2)
{
int det0, det1, det2, erg;
det0 = (a1 - b1) * (d2 - c2) - (a2 - b2) * (d1 - c1);
det1 = (d1 - b1) * (d2 - c2) - (d2 - b2) * (d1 - c1);
if (det1 == 0 || det1 == det0)
return (0);
det2 = (a1 - b1) * (d2 - b2) - (a2 - b2) * (d1 - b1);
if (det2 == 0 || det2 == det0)
return (0);
if (det0 < 0)
{
det0 = -det0;
det1 = -det1;
det2 = -det2;
}
erg = (det1 > 0 && det1 < det0) ? 1 : 0;
if (det2 > 0 && det2 < det0) erg++ ;
if(erg == 1) return(1);
return (2);
}
--