Prüfen ob Viereck konvex ist |
| 09.06.2009, 10:38 | marodeur | Auf diesen Beitrag antworten » | ||
| Prüfen ob Viereck konvex ist seien A,B,C,D die (geordneten) Eckpunkte eines Vierecks. Gibt es einen einfacheren Weg zum Prüfen auf Konvexität eines Vierecks, als zu schauen, ob die Eckpunkte A und C auf der gleichen Seite der Diagonalen BD sind? (Also Geradengleichung von BD aufstellen und A und C einsetzen und Vorzeichen vergleichen) Das ganze soll numerisch nicht zu aufwendig sein, da es in ein Programm integriert wird. Dank und Gruß maro |
||||
| 09.06.2009, 13:20 | mYthos | Auf diesen Beitrag antworten » | ||
Alle Innenwinkel des Viereckes müssen kleiner als 180° sein. mY+ |
||||
| 09.06.2009, 13:57 | marodeur | Auf diesen Beitrag antworten » | ||
Ok, das wäre auch eine Möglichkeit. Aber ich glaube, da ist der Rechenaufwand zu groß. Das wären insgesamt 4 Normen, 4 Skalarprodukte und 4 mal arccos. Bei dem was ich sagte sind es: Aufstellen der Geraden: 2mal eine Dvision Berechnung der Funktionswerte der anderen Ecken: je eine Multiplikation (macht dann 4) Vergleich der Vorzeichen: kostet? achja: es ist alles in 2D. |
||||
| 09.06.2009, 14:12 | mYthos | Auf diesen Beitrag antworten » | ||
Du wolltest eine andere Möglichkeit. Wie dein Programm damit umgeht, ist ja eine andere Geschichte ... mY+ |
||||
| 09.06.2009, 14:16 | WebFritzi | Auf diesen Beitrag antworten » | ||
RE: Prüfen ob Viereck konvex ist
Das Verfahren wird kläglich scheitern. Was machst du denn, wenn der Innenwinkel bei B größer als 180 Grad ist? |
||||
| 09.06.2009, 14:39 | marodeur | Auf diesen Beitrag antworten » | ||
@mYthos: nein, einen einfacheren. Ok einfach in Bezug auf programmierungstechnisch. @WebFritzi: Mein Fehler, statt Diagonela BD, Gerade durch B und D. Dann erhalte ich ja daraus ist , so ist (x,y) ein Punkt der Geraden, sonst nicht. gibt an, auf welcher Seite der Punkte (x,y) liegt. Ich frage ja hier, ob es was einfacheres ist, was die Zahl der Multiplikationen minimiert. Kann ja sein, dass es was gibt, dass nur durch Summen auskommt, oder so. Man kann ja nicht immer alles wissen. 
|
||||
| Anzeige | ||||
|
|
||||
| 09.06.2009, 14:53 | AD | Auf diesen Beitrag antworten » | ||
Das war es nicht, was Webfritzi gemeint hat. 
[attach]10734[/attach] Du musst auch den Test mit der anderen Diagonalen AC machen, erst dann kannst du dir sicher sein. |
||||
| 09.06.2009, 17:22 | marodeur | Auf diesen Beitrag antworten » | ||
ja, das ist klar, man muss beide Geraden erstellen und in denen jeweils die beiden anderen Punkte einsetzen. (bei meiner aufwandsberechnung habe ich das ja berücksichtigt) |
||||
| 09.06.2009, 17:27 | AD | Auf diesen Beitrag antworten » | ||
Nur Additionen/Subtraktionen wird sicher nichts - Multiplikationen musst du schon hinzunehmen. Aber zumindest auf Divisionen oder gar Wurzelziehen kannst du mit nur wenigen Umformungen verzichten. Es hat den Anschein, dass du Millionen, wenn nicht Milliarden solche Vergleiche vorhast, ansonsten würde sich ja ein Feilschen um jede kleine Operation gar nicht so lohnen.
|
||||
| 09.06.2009, 17:44 | marodeur | Auf diesen Beitrag antworten » | ||
Millionen nicht gleich, aber einige Tausend bis Zehntausend. Das wird nicht für so viele "Stellen" benötigt. Es ist ja nicht nur das, es kommen ja noch andere Berechnungen dazu und das dann immer gleich noch in ca. 100.000-facher ausführung. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
