Wie berechnet man einen Punkt in einem Rechteck?

Neue Frage »

Jane Doe Auf diesen Beitrag antworten »
Wie berechnet man einen Punkt in einem Rechteck?
Hallo allerseits.

Ich habe ein Programmierproblem und weiß gar nicht wie ich es erklären soll, aber ich versuche es einfach mal. smile

Ich habe in einem zweidimensionalen Koordinatensystem zwei Rechtecke mit beliebigen Maßen, deren Mittelpunkt auf den gleichen x/y-Koordinaten liegen. Eines der Rechtecke ist größer als das andere und somit hat man eine Fläche zwischen diesen beiden Rechtecken. Ich weiß nicht ob es einen Namen für diese Form gibt, aber man kann sich das als die Seitenfläche eines 'eckigen Hohlzylinders' vorstellen.

Nun möchte ich eine Programmfunktion schreiben die mir einen Zufallspunkt liefert, der, in einem bestimmten Radiusbereich, auf dieser Fläche liegt und ich weiß nicht so richtig wie.

Ich habe zwar eine Lösung gefunden, aber die ist sehr rechenaufwendig und da im Zweifelsfall hunderte bis tausende Punkte pro Sekunde berechnet werden müssen, könnte mein Ansatz zwar richtig, aber zu kompliziert sein.

Mein Ansatz ist folgender:
Zuerst wähle ich einen Winkel in dem vorgegebenem Winkelbereich und erstelle damit eine Strecke vom Mittelpunkt der Rechtecke bis zu einem Punkt der außerhalb des größeren Rechteckes liegt. Damit ergeben sich zwei Schnittpunkte, die ich danach berechne.
Nun habe ich eine zweite Strecke die von einem Schnittpunkt zum anderen geht und kann einen Punkt auf dieser Strecke zufällig auswählen.

Meine Überlegungen müssten eigentlich zu einem korrekten Ergebnis führen, aber das ist eben recht umständlich. Kennt denn jemand eine leichtere und/oder effektivere Lösung für mein Problem ?


Ich weiß nicht ob der Versuch meiner Erklärung verständlich ist. Falls nicht, dann einfach fragen. smile

Viele Grüße
Dopap Auf diesen Beitrag antworten »

das hört sich plausibel an sofern die Rechtecke "parallel" sind und /oder ein Rechteck eine echte Teilmenge des anderen Rechtecks ist.

Trotzdem ist das nicht einfach. Alle 8 Strecken sind zu parametrisieren. Die Zufallsrichtung ( der Leuchtturmstrahl ) ist eine parametrisierte Halbgerade in Polardarstellung, mit einem Zufallswinkel gleichverteilt in 0 bis 2 Pi. Welche 2 Schnittpunkte mit den 8 Strecken anfallen muss rechentechnisch genau geprüft werden.

Ein ähnliches Problem ist in Windows , ob der Cursor im Rechteck (Klickfeld ) ist.
Das ist aber derart häufig der Fall, dass dafür eine feste Routine gibt.
Jane Doe Auf diesen Beitrag antworten »

Ich hatte vergessen zu erwähnen das die Rechtecke 'gerade' sind. Die Seiten der Dreiecke sind also parallel zur den Koordinatenachsen.

Ob der Cursor in einem klickbaren Bereich liegt ist total einfach zu bestimmen. Eigentlich ist mein Problem ähnlich, wenn man nur das äußere Rechteck betrachten würde. Allerdings darf der berechnete Punkt ja nicht näher am Ursprung sein als es das innere Rechteck zulässt. Und genau daß ist das Schwierige dabei.

Wenn es sich um Ellipsen handeln würde, dann wäre das viel einfacher, aber es sind nunmal leider Rechtecke.

Denkst Du, daß mein Ansatz der einzige ist oder könnte es da noch einen einfacheren Weg geben um zu einem korrekten Ergebnis zu kommen ?
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Jane Doe

Ob der Cursor in einem klickbaren Bereich liegt ist total einfach zu bestimmen.


Das ist mir neu . Wie geht das verwirrt
Jane Doe Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
Zitat:
Original von Jane Doe

Ob der Cursor in einem klickbaren Bereich liegt ist total einfach zu bestimmen.


Das ist mir neu . Wie geht das verwirrt



Stell Dir einen Button vor. Du kennst ja die Position und die Maße dieses Buttons.
Du hast also vier Variablen:
X - Links und Rechts
Y - Links und Rechts

Wenn Du also einen Button mit der Größe 100x20px hast und er auf den Koordinaten 500;200 liegt, dann ist:

X-Min -> 500-50=450
X-Max -> 500+50=550
Y-Min -> 200-10=190
Y-Max -> 200+10=210

Damit brauchst Du nur noch prüfen ob die x/y-Koodinaten des Cursors zum Klickzeitpunkt in diesem Bereich liegen.
Jane Doe Auf diesen Beitrag antworten »

Ich meinte natürlich: Y - Oben und Unten !
 
 
Dopap Auf diesen Beitrag antworten »

ja klar ! unglücklich

Ich dachte wohl an ein gedrehtes Rechteck.

Zur Aufgabe: die konstruktive Lösung mit dem rotierenden Strahl und den beiden Schnittpunkten auf den Kanten und dem Zufallspunkt auf der Verbindungsstrecke hat nur einen Haken:
Die Flächendichte von Zufallspunkten im Rahmenrechteck ist aus mehreren Gründen nicht konstant.
Sollte das vielleicht gewünscht sein verwirrt
Jane Doe Auf diesen Beitrag antworten »

Achso. Ich dachte Du meinst einen normalen Button und die sind ja meistens gerade. Aber bei einem gedrehten Rechteck ist es auch nicht viel schwerer.
Bei einem gedrehten Rechteck hast Du ja trotzdem noch die vier Seiten, was ja nichts anderes als 4 Strecken sind. Damit kannst Du Dir einfach die kürzeste Entfernung zwischen dem Cursor und den Strecken berechnen und schaust dann ob der Cursor innerhalb der 4 Punkte liegt.
Das lässt sich auch problemlos auf jedes x-beliebiges Vieleck anwenden, da man ja jedes davon in Strecken zerlegen kann.
Aber dafür sollte man vielleicht einen eigenen Thread aufmachen, da das Offtopic ist.


Die Flächendichte ist prinzipiell egal. Wichtig ist nur, daß der berechnete Punkt innerhalb der beiden Rechtecke liegt. Aber meine Lösung kommt mir trotzdem noch viel zu aufwendig vor.
riwe Auf diesen Beitrag antworten »

nur eine Frage am Rande:
was genau verstehst du unter "... einem bestimmten Radiusbereich..." verwirrt
Jane Doe Auf diesen Beitrag antworten »

Zitat:
Original von riwe
nur eine Frage am Rande:
was genau verstehst du unter "... einem bestimmten Radiusbereich..." verwirrt


Ich glaube 'Radiusbereich' war falsch formuliert. Ich meine damit einen bestimmten Winkelbereich von der Mitte der Rechtecke ausgehend. Also zum Beispiel einen Winkel zwischen 0° und 90°, oder zwischen 38° und 176°.
Dopap Auf diesen Beitrag antworten »
RE: Wie berechnet man einen Punkt in einem Rechteck ?
deine Beschreibung ist zwar richtig, nur enthält es noch einige Dinge die dem Menschen klar sind, aber nicht dem Programm
Zitat:


Mein Ansatz ist folgender:
Zuerst wähle ich einen Winkel in dem vorgegebenem Winkelbereich und erstelle damit eine Strecke vom Mittelpunkt der Rechtecke bis zu einem Punkt der außerhalb des größeren Rechteckes liegt. Damit ergeben sich zwei Schnittpunkte, die ich danach berechne[...]



Wie berechnest du den Punkt außerhalb ?
Welche 2 Schnittpunkte ? Theoretisch sind 8 verschiedene Schnittpunkte denkbar.
Wie berechnet man den Schnittpunkt zweier Strecken ?
Außerdem müssen die Schnittpunkte nicht auf parallelen Strecken liegen.

Programmtechnisch ist da noch einiges zu tun.
Jane Doe Auf diesen Beitrag antworten »

Programmtechnisch ist das absolut kein Problem, nur meine Methode kommt mir zu uneffektiv vor.

1.
Den Punkt außerhalb kann man einfach durch Breite*Höhe des größeren Rechteckes in Verbindung mit dem Winkel (Sinus/Cosinus) bestimmen.

2.
Man kann ja alle Strecken auf einen Schnittpunkt überprüfen. Das wäre die einfachste Möglichkeit. Allerdings wär das nicht sehr effektiv, so daß man die zu prüfenden Strecken eingrenzen sollte.

3.
Das ist recht einfach mit einem Gleichungssystem. Ich denke da findest Du hier genügend Lösungen.

4.
Das ist ja auch nicht notwendig.
nahörmal Auf diesen Beitrag antworten »

Das ist ein ganz nettes "Problem".

Ich würde es folgendermaßen tun.

Eingabe der Winkel-Unter- & -Ober-Grenze. Sei oBdA a<b
Dann bestimme random r in [a,b]

Nun hast du einen festen Winkel r. Der ist im Intervall [0,2pi) bzw [0,360°)
Das ist also ein Strahl (keine Strecke!) vom Ursprung (= Mittelpunkt der Rechtecke) aus.

Dann oBdA ist der Winkel im 1.Quadranten. Da kannst du dun das innere Rechteck entweder
* von links oder
* von unten oder
* gerade in seiner rechten oberen Ecke

treffen.

Und zwar ist dafür der kritische Winkel gerade der Arkus-Tangens aus halbe Höhe durch halbe Breite. Kannst du dir das vorstellen?

(das ist der Fall wenn man den Winkel wie im üblichen KOOS ggUZS-drehend von der "x"-Achse aus rumfahren lässt)

...

Du hast immer genau zwei Schnittpunkte S1,S2 (eben mit je einem Rechteck einen)
Dann wählst du noch eine Zufallszahl d im Intervall [0, (Abstand S1,S2) ] und dann über Pythagoras in Kombination mit Tangens oder nur sinus und cosinus (2 Fkten braucht man schon ...) auf den Punkt klettern der so ja jetzt eindeutig bestimmt ist.

Viel Erfolg falls was nicht klar ist einfach nachfragen,

Btw: spezielle Programmiersprache oder nur so Idee?
Jane Doe Auf diesen Beitrag antworten »

Hallo nahörmal und Danke für Deinen Post.

Die Umsetzung ist, wie ich bereits mehrfach sagte, absolut kein Problem ! Wie ich meine Methode umsetze weiß ich also ganz genau, denn ich hab sie mir ja so ausgedacht.
Ich zweifel nur an der Effektivität und fragte ob noch jemand eine bessere Lösung für die Aufgabenstellung hat oder ob ich mir schon die einfachste Lösung ausgedacht habe !?
nahörmal Auf diesen Beitrag antworten »

Ist es wichtig, dass die statistische Gleichverteilung über den Winkel erfolgt oder wäre es auch eine Option, eine Gleichverteilung über den Flächeninhalt ?

Nur ein Vorschlag, aber ich denke du hast dir schon was dabei gedacht einen Leuchtturmstrahl zu nutzen, und da bezweifle ich dass es was effizienteres gibt..
Jane Doe Auf diesen Beitrag antworten »

Eine Gleichverteilung spielt keine Rolle. Es geht nur darum einen Zufallspunkt zu ermitteln, der zwischen den zwei Rechtecken liegt. Wenn zweimal hintereinander der gleiche Punkt ermittelt wird, dann ist das also nicht schlimm.
nahörmal Auf diesen Beitrag antworten »

Es geht also nur darum einen "zufälligen" Punkt zu bestimmen, der sich zwischen diesen Rechtecken befindet.

Nun was heißt zufällig? Da war eben die Frage, ob
* jeder Punkt (Pixel) gleich wahrscheinlich sein soll oder
* ob jeder Winkel (Azimut) gleich wahrscheinlich sein soll...

Dass der selbe Punkt beim nächsten mal wieder "gewählt" wird, das kann in jedem Fall passieren.

Nun könnte das Programm auch so aussehen:
* Zerlege diese Form (die keinen Namen hat ;) ), die du im Eingangsposting beschrieben hast in vier Rechtecke, wobei je zwei die selbe Größe haben. Am einfachsten einmal den oberen und unteren Streifen und dann links und rechts die Rechtecke mit den Maßen Höhe= Höhe des inneren Rechtecks, Breite = Delta Breite_Rechtecke / 2

Dann kannst du entweder
* jedem Rechteck erstmal die Wahrscheinlichkeit 1/4 geben
* oder eine gewichtete Wahrscheinlichkeit je nach Flächeninhalt = Breite mal Höhe geben wobei das ja einfach zu berechnen ist und es auch nur zwei Flächeninhalte A1 , A2 gibt. Dann nochmal per Warhscheinlichkeit p=0,5 eines der beiden gleich großen auswählen.


Dann hast du also ein festes Rechteck mit festen Koordinaten (werden im Programmablauf sicherlich bis jetzt schon in Variablen festgeschrieben sein). Da eben noch einen x_r = rand(width), y_r= rand(height) und dann x_final = x_rechteck + x_r

Sollte klar sein, oder?

Viel Erfolg und Spaß :)
Jane Doe Auf diesen Beitrag antworten »

Hallo nahörmal.

Zufällig bedeutet in meinem Fall die Nutzung der Random-Funktion des Computers. Das ist zwar kein 'richtiger Zufall', aber für meine Zwecke völlig ausreichend.

Die Idee, die auf Deiner Vorgehensweise beruht, hatte ich auch schon, aber sie löst leider nicht mein Problem, denn sonst hätte ich es schon längst so gemacht. Wenn es nur darum gehen würde einen Punkt innerhalb der zwei Rechtecke zu finden, dann würde das so funktionieren, aber ich habe ja einen vorgegebenen Winkelbereich und deswegen passt diese Lösung leider nicht zu meinem Problem.

So wie es momentan aussieht gibt es wohl keine einfachere Lösung als die, die ich mir ausgedacht habe. Also werde ich sie mal umsetzen und testen wie schnell das ist. Vielleicht stelle ich mir die ganzen Berechnungen ja auch nur zu langsam vor.
URL Auf diesen Beitrag antworten »

du könntest auch einen Punkt innerhalb des äußeren Rechtecks wählen und dann nachprüfen, ob er die beiden anderen Bedingungen erfüllen. Falls nicht, verwirfst du den Punkt.
Oder du nimmst den Vorschlag von nahörmal und prüfst für den generierten Punkt nur die Sektorbedingung und verwirfst ihn ggf.
Wenn ich es recht verstanden habe, sind "Fehlschüsse" nicht teuer, weil du keine Ansprüche an die Zufallsquelle hast.
Jane Doe Auf diesen Beitrag antworten »

Die Überlegung hatte ich auch schon, aber dagegen sprechen gleich mehrere Sachen:

1. Die Überprüfung ob es im gegebenen Winkelbereich liegt ist genauso rechenaufwendig. Also kann ich es ja gleichrichtig machen.
2. Wenn es ganz blöd kommt, hat er vielleicht pro Punkt mehrere tausend Fehlschüsse und generell ist jeder Fehlschuss eine Berechnung zu viel. Es wäre also sehr kontraproduktiv.
URL Auf diesen Beitrag antworten »

1.Die Prüfung erscheint mir nicht sehr aufwändig.
2.Wie kontraproduktiv das ist, hängt sehr von der Geometrie ab.

ObdA ist das äußere Rechteck das Einheitsquadrat und das innere Rechteck ist flach.
Im Fall haben die in Frage kommenden Punkte genau die Form

Die übrigen Fälle kann man genauso ex ante bestimmen. Viel zu berechnen gibt es da doch nicht mehr geschockt
Jane Doe Auf diesen Beitrag antworten »

ObdA ?

Insgesamt hast Du zwar recht, aber wie gesagt kann es im ungünstigsten Fall zu vielen Fehlschüssen kommen und somit ist das uneffektiver als meine Methode, da es bei meiner Methode keine Fehlschüsse geben kann.
URL Auf diesen Beitrag antworten »

ObdA=Ohne Beschränkung der Allgemeinheit

Was spricht gegen den letzten von mir genannten Weg?
Jane Doe Auf diesen Beitrag antworten »

Zitat:
Original von URL
ObdA=Ohne Beschränkung der Allgemeinheit

Was spricht gegen den letzten von mir genannten Weg?


Wenn Du es nochmal so erklärst, ohne das man dafür Mathe studiert haben muss, dann kann ich Dir die Frage auch beantworten. Augenzwinkern
URL Auf diesen Beitrag antworten »

Mach dir eine Skizze. Der rechte obere Eckpunkt des inneren Rechtecks hat die Koordinaten (a,b) und es ist (das meine ich mit flachem Rechteck).
Wenn für deinen zufällig gewählten Winkel gilt, dann schneidet der vom Ursprung unter diesem Winkel ausgehende Strahl das innere Rechteck unterhalb seiner rechte oberen Ecke. Der Schnittpunkt hat also die Koordinaten .
Der Schnittpunkt mit dem äußeren Rechteck (OBdA das Einheitsquadrad) hat die Koordinaten .
Die Punkte dazwischen kann man als Konvexkombination dieser beiden Punkte schreiben, also in der Form
mit Paramter .
Wählst du jetzt in diesem Bereich zufällig aus, hast du einen passenden Punkt gefunden.
Jane Doe Auf diesen Beitrag antworten »

Es ist aber nicht gegeben, daß das Rechteck breiter als hoch ist. Auch kann es sein, daß das eine Rechteck zum Beispiel im Hoch- und das andere im Querformat oder quadratisch ist.
URL Auf diesen Beitrag antworten »

Skaliere die Achsen so, dass außen das Einheitsquadrat ist. Bei Bedarf noch die Achsen vertauschen, dann hast du innen ein flaches Rechteck.
Sie Skalierungsfaktoren kannst du auch in die von mir genannte Konvexkombination wieder einrechnen. Das war mir nur zu mühsam.
Jane Doe Auf diesen Beitrag antworten »

Ich glaube ich verstehe nicht so richtig was Du meinst. verwirrt
URL Auf diesen Beitrag antworten »

Das äußere Rechteck hat die rechte obere Ecke bei den Koordinaten
Jetzt wird skaliert: . Dann hat das Rechteck die Koordinaten .
Die rechte obere Ecke des inneren Rechtecks hat dann die skalierten Koordinaten . Ist , das innere Rechteck also hoch, dann wird noch vertauscht:
Jane Doe Auf diesen Beitrag antworten »

Zitat:
Original von Jane Doe
Ich glaube ich verstehe nicht so richtig was Du meinst. verwirrt

Deine ganzen Formeln erleichtern das Verständnis nicht. Vor allem verstehe ich nicht was daran besser sein soll.
Aber ist auch nicht so schlimm, denn ich hab es jetzt nach meiner Idee umgesetzt und das ist gar nicht mal so langsam. smile
URL Auf diesen Beitrag antworten »

Du fragtest, ob es effizient wäre, jedesmal die Schnittpunkte zu berechnen.
Ich habe dir gezeigt, wie man in einem speziellen Fall diese Berechnung vorab durchführen und sich auf Einsetzen und ein wenig Buchhaltung beschränken kann. Dann habe ich dir gezeigt, wie man deine allgemeine Situation durch Dehnen/Stauchen (=Skalierung) und ggf. Spiegelung an einer Winkelhalbierenden (=Koordinatenvertauschung) auf den speziellen Fall zurückführen kann. (programmiertechnisch beides eher Buchhaltung als Berechnung)
Du hast dich für Berechnung der Schnittpunkte statt Einsetzen+Buchhaltung entschieden.
Du bist zufrieden, weil deine Implementierung schnell genug ist. Ich bin zufrieden, weil ich dein Problem auf ein einfachers zurückgeführt habe. Also viel Freude an deiner Implementierung Wink
HAL 9000 Auf diesen Beitrag antworten »

Ich hab mal den Thread quergelesen, und verstehe eigentlich nicht so richtig, wo überhaupt ein Effizienzproblem liegen soll: Nach der urprünglich von Jane Doe vorgeschlagenen Methode wird

1) ein Winkelwert in einem vorgegebenen Intervall gleichmäßig verteilt ausgewürfelt,

2) ein Strahl vom Mittelpunkt in diese ausgewürfelte Richtung geschickt und die beiden Schnittpunkte mit dem "Rechteckring" (in Analogie zum Kreisring) berechnet.

3) ein Punkt gleichmäßig verteilt auf der Schnittstrecke ausgewürfelt.


Soweit ich erkenne benötigt man im ganzen Verfahren zwei Zufallswerte, sowie eine Tangensbestimmung, der Rest ein bisschen Grundrechenarten. Primär für den Rechenaufwand sind also die beiden Zufallszahlerzeugungen sowie die eine Tangensbestimmung - Vereinfachungen und Optimierungen des Restverfahrens scheinen mir im Vergleich dazu nicht sonderlich viel zu bringen. Ich weiß nicht, auf welcher Hardware du das implementieren willst, aber z.B. auf einem normalen PC und kompiliert sollte mehrere 100000 bzw. gar Millionen solche Punktauswürfelungen pro Sekunde kein Problem sein. Vermutlich bringt es deutlich mehr Effizienzgewinn, die Tangensberechnung nur mit float (6 Stellen Genauigkeit) statt mit double (15 Stellen Genauigkeit) auszuführen, als alle anderen denkbaren Optimierungsbemühungen dieses Verfahrens zusammen. smile
URL Auf diesen Beitrag antworten »

Ich habe die Frage nach der Effizienz auch nicht gestellt smile
HAL 9000 Auf diesen Beitrag antworten »

Es war auch eher eine Frage an die Threaderstellerin.
Jane Doe Auf diesen Beitrag antworten »

Es ist richtig, denn es ist schnell genug, aber das wusste ich vor meiner Umsetzung noch nicht. smile
Ich hatte ja einen Lösungsweg für die Aufgabenstellung, aber da man sehr viele Berechnungen ausführen muss, dachte ich das es zu rechenaufwändig wäre. Deswegen hatte ich hier gefragt ob jemand einen einfacheren Weg als den meinen kennt, damit ich meinen nicht sinnlos umsetze, wenn es doch auch einfacher gehen würde. Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »

Eins fällt mir noch ein, aber das hast du ja vielleicht schon so ähnlich umgesetzt:

Der vom Mittelpunkt ausgehende Leitstrahl schneidet ja - je nach Richtung - nur genau eine der vier Seiten jedes Rechtecks. Es lässt sich anhand der Rechteckeckpunkte vorab berechnen, welche Seite zu welchem Winkelintervall gehört - das reduziert ein wenig den Berechnungsaufwand zur Berechnung des eigentlichen Schnittpunkts.
Jane Doe Auf diesen Beitrag antworten »

Darüber habe ich mir auch schon Gedanken gemacht, aber bin noch zu keiner akzeptablen Lösung gekommen. Da die Rechtecke ja in ihren Ausmaßen variieren, kann ich keinen festen Winkelbereich bestimmen.
Wenn der Strahl beispielsweise in einem Winkel zwischen 1° und 179° liegt, dann brauche ich die linken Strecken nicht überprüfen, aber viel weiter bin ich mit meinen Überlegungen noch nicht.
Ich könnte auch den Winkel zwischen dem Mittelpunkt der Rechtecke und deren Endpunkten berechnen und dann schauen ob das zu meinem Winkelbereich passt, aber ich bin mir nicht sicher ob das effizienter wäre.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Jane Doe
Darüber habe ich mir auch schon Gedanken gemacht, aber bin noch zu keiner akzeptablen Lösung gekommen. Da die Rechtecke ja in ihren Ausmaßen variieren, kann ich keinen festen Winkelbereich bestimmen.

Ich hatte das so verstanden, dass du für ein- und dasselbe Rechteck viele (wenn nicht Tausende) solche Punkte auswürfelst - in dem Fall lohnt sich eine solche Vorabberechnung.
Jane Doe Auf diesen Beitrag antworten »

Ja, das stimmt. Es können sehr viele zu berechnende Punkte werden.
Aber wie meintest Du die Umsetzung ? Mit der Winkelbestimmung zwischen Mittelpunkt und Eckpunkten ?
riwe Auf diesen Beitrag antworten »

so in etwa Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »