Laden...

Überschneiden sich zwei Kreissegmente?

Erstellt von Golo Roden vor 17 Jahren Letzter Beitrag vor 17 Jahren 5.762 Views
Golo Roden Themenstarter:in
4.207 Beiträge seit 2003
vor 17 Jahren
Überschneiden sich zwei Kreissegmente?

Hallo,

folgendes Szenario: Gegeben sind vier Winkel, A, B, C und D. Die Winkel A und B definieren ein Kreissegment, ebenso wie die Winkel C und D. Gefragt ist, ob sich das Kreissegment AB mit dem von BC überschneidet - wobei es egal ist, ob die beiden sich nur an einer Kante berühren, ob sie teilweise oder sogar gänzlich ineinander liegen. Sobald sie mindestens einen Berührungspunkt haben, schneiden sie sich.

Wäre das ganze eine diskrete Struktur, wäre es kein Problem - einfach prüfen, ob A oder B zwischen C und D liegt, und umgekehrt.

Durch die Winkel gibt es aber Probleme, da 15 und 375 das gleiche sind, und 15 > 359 durchaus wahr sein kann, ebenso können auch negative Werte vorkommen ... wie löst man dieses Problem am elegantesten und möglichst generisch?

Viele Grüße,

Golo

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

T
327 Beiträge seit 2006
vor 17 Jahren

Rechne doch einfach die Winkel in einen Sinus- oder Cosinuswert um...

Dann sollte es kein Problem mehr sein zu überprüfen ob sich die Segmente überschneiden oder berühren. Du jeden beliebigen Winkel hast du ja dann einen Wert zwischen -1 und 1....

139 Beiträge seit 2006
vor 17 Jahren

[NEUGIER]
Wie kann man ein Kreissegment mit 2 Winkeln Definieren?

Pictrue by Wikipedia

Nur der Kreismittelpunkt hat einen Winkel...
Sry wenn das nicht hier hin passt und ne dumme Frage ist ^^*
[/NEUGIER]

Aber wofür soll das gut sein? – Advanced Computing Systems Division von IBM, 1968, zum Microchip

Golo Roden Themenstarter:in
4.207 Beiträge seit 2003
vor 17 Jahren

Original von Nordwald
Wie kann man ein Kreissegment mit 2 Winkeln Definieren?

Kreissektor ... sorry.

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

F
97 Beiträge seit 2006
vor 17 Jahren

wie wärs wenn du die winkel im ring 360 errechnest?

d.h. 375 = [15] mod 360
so hast du alle winkel immer zwischen 0 und 359, leider kannst du so nur mit ganzzahlige winkel rechnen

als funktion



private int modulo(int winkel)
{
      return winkel % 360;
}


eine möglichkeit für float zahlen als winkel



private double modulo(double winkel)
{
      while(winkel >= 360)
      {
             winkel = winkel - 360;
      }

     return winkel;
}


To Infinity and Beyond

Golo Roden Themenstarter:in
4.207 Beiträge seit 2003
vor 17 Jahren

Original von felix_schmidt
wie wärs wenn du die winkel im ring 360 errechnest?

d.h. 375 = [15] mod 360

Genau DAS ist ja das Problem, weil 375 > 360, 15 aber eben nicht > 360 ...

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

T
327 Beiträge seit 2006
vor 17 Jahren

Ganz einfach.... du zeichnest den Kreis ja in ein 2-dimensionales Koordinatensystem (setzte ich mal voraus) mit dem Mittelpunkt M(0;0). Dann hast du automatisch die positive X-Achse als 0° definiert, die pos Y-Achse sind 90°, die neg. X-Achse 180° etc.

Ok.. auch auf den Begriff reingefallen 🙂

Golo Roden Themenstarter:in
4.207 Beiträge seit 2003
vor 17 Jahren

Original von telnet
Ganz einfach.... du zeichnest den Kreis ja in ein 2-dimensionales Koordinatensystem (setzte ich mal voraus) mit dem Mittelpunkt M(0;0). Dann hast du automatisch die positive X-Achse als 0° definiert, die pos Y-Achse sind 90°, die neg. X-Achse 180° etc.

Ich zeichne es nicht, ich rechne nur damit ... aber abgesehen davon verstehe ich nicht, wie mich Deine Erklärung weiterbringt? Dass dem so ist, ist mir klar, nur sehe ich nicht, inwieweit das etwas mit der Frage zu tun hat. Kannst Du mich da aufklären?

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Golo,

der erste Schritt ist, wie schon beschrieben, den modulo von alen Winkeln zu berechnen. Im zweiten Schritt, muss man den möglichen Wrap-Around berücksichtigen. Das Ganze läuft aber - soweit ich das überblicke - auf nicht mehr als ein paar || in der if-Abfrage hinaus (Stichwort: Vollständige Fallunterscheidung).

herbivore

4.506 Beiträge seit 2004
vor 17 Jahren

Hallo Golo,

ist schon ne Weile her bei mir, aber kann man nicht vom Winkelmaß ins Polarmaß rechnen.

Ich denke im Polarmaß sind solche Überprüfungen einfacher durchzuführen. Ich kann allerdings Dir da keine fertige Lösung aus dem Ärmel schütteln, und meine Behauptung beruht nur auf wage Vermutungen 😉

Gruß
Norman-Timo

A: “Wie ist denn das Wetter bei euch?”
B: “Caps Lock.”
A: “Hä?”
B: “Na ja, Shift ohne Ende!”

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo norman_timo,

verstehe ich nicht. Polarkoordinaten haben als eine Komponente genau den Winkel, um den es hier geht und und als andere Komponente die Entfernung vom Ursprung, die hier nicht interessiert oder sogar unbekannt ist. Also ist man genau bei den Winkeln, bei den man ohnehin schon ist.

Oder meinst du Bogenmaß? Ob man die Überprüfung in Grad oder im Bogenmaß durchführt ändert nichts gundsätzliches, weil sich Grad und Bogenmaß nur durch einen konstanten Faktor unterscheiden.

herbivore

4.506 Beiträge seit 2004
vor 17 Jahren

Hallo Herbivore,

ich vermute mal ganz stark, dass Du Recht hast 😉

Ich hatte nur dunkle Erinnerungen, dass irgendwelche Berechnungen im Polarmaß deutlich einfacher zu machen waren, als im "Normalen" Maß. Ich habe das aber nur einmal im Studium gehört, und hatte noch nie (leider) einen Anwendungsfall. Daher ist das mir zu lange her, dass ich hier fundierte Kenntnisse widergeben könnte.

Also Polarmaß vergessen, meinen Beitrag ignorieren (sorry).

Bogenmaß meinte ich nicht, das kenne ich dann wieder genauer 😉

Gruß
Norman-Timo

A: “Wie ist denn das Wetter bei euch?”
B: “Caps Lock.”
A: “Hä?”
B: “Na ja, Shift ohne Ende!”

B
1.529 Beiträge seit 2006
vor 17 Jahren

Ich vermute mal, du meinst dass so, dass der Winkel A den Beginn des ersten Kreissektors, Winkel B dessen Ende angeben. Entsprechend C und D für den zweiten.
Jetzt rechnest du alle Grad einfach per modulo in das Intervall [0;360] (bzw. [0;2Pi]) um. Ist ein Wert negativ, addierst du anschließend 360 bzw. 2Pi.
Die Kreissegmente schneiden sich jetzt, wenn C oder D zwischen A und B liegt.
Das ist aber ein relativ simples mathematisches Problemchen...

Golo Roden Themenstarter:in
4.207 Beiträge seit 2003
vor 17 Jahren

Hallo Borg,

Du hast recht - so geht's. Danke für den Tipp.

Und ja, eigentlich ist es auch ein relativ einfaches Problemchen ... ich fürchte, ich habe da den Wald vor lauter Bäumen nicht gesehen und zu kompliziert gedacht: Meine ersten beiden Ansätze gingen in Richtung Restklassenringe und Rotationsmatrizen ... (blödes Mathestudium 😉).

Na ja, jetzt klappt's aber.

Nochmals danke,

Golo

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Borg, hallo Golo,

Die Kreissegmente schneiden sich jetzt, wenn C oder D zwischen A und B liegt.

ist natürlich eine Frage der Definition von zwischen, aber wenn ich mal von A ≤ C ≤ B ausgehe (analog für D), dann reicht das noch nicht, denn B könnte ja auch echt kleiner A sein (nach der Moduloberechnung).
In diesem Fall schneiden sich die Kreissegmente, wenn C und D nicht beide echt zwischen B und A liegen (also A < C < B), es sei denn, dass D < C. Das meinte ich mit vollständiger Falluntrscheidung oben.

herbivore

T
512 Beiträge seit 2006
vor 17 Jahren

Naja wenn man es so betrachtet, ob ein Punkt vom kleineren Bogen im größeren Bogen liegt, dann klappt das auch.

Also man muss eventuell die Eingabe umtauschen, so dass A und B immer den größeren Bogen repräsentieren.

Außerdem wäre es vieleicht leichter, nicht A und B zu betrachten, sondern A und Distanz zu B. Dann muss man nur die Distanz von A zu C und D berechnen, und schauen, ob die kleiner als die Distanz zu B ist.
Man muss die Punkte dann nur im gleichen Drehsinn betrachten d.h. wenn die Distanz negativ wird, nochmal 360 draufaddieren.
Dadurch sollte man aber die Probleme loswerden die entstehen, wenn die Bögen den Winkel 0 überschneiden. Man betrachtet dann quasi alle Winkel von A aus, und dort ist B immer größer als A.

e.f.q.

Aus Falschem folgt Beliebiges