Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Algorithmus: Wird ein Punkt von einem Winkel eingeschlossen

  • 1
  • 2

Werbeanzeige

Oromis_32

Frischling

  • »Oromis_32« ist der Autor dieses Themas

Beiträge: 28

  • Private Nachricht senden

1

06.07.2010, 18:10

Algorithmus: Wird ein Punkt von einem Winkel eingeschlossen

Hi @all,

ich habe folgendes Problem: Für die KI eines 2D-Actionspiels müsste ich herausfinden, ob sich ein Punkt in dem Schussradius befindet. Dazu folgende Illustration:


Mich interessiert jetzt, wie ich herausfinde, ob der Punkt P innerhalb des aufgespannten Kegels liegt - In dem Beispiel ist es ja nicht der Fall. "Gegeben" sind:

Pos - ein Ortsvektor
a - Repräsentiert einen Schenkel; Richtungsvektor
b - Repräsentiert den anderen Schenkel; Richtungsvektor
P - Zu prüfender Ortsvektor

Zu bedenken ist:
- Der zu prüfende Winkel ist immer im Uhrzeigersinn zwischen a und b
- Es ist nicht gewährleistet, dass der Winkel kleiner 180° ist

Danke für alle Lösungsansätze

Oromis_32

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

2

06.07.2010, 18:14

berechne den winkel zwischen dem ziel und dem startpunkt und kontrollier ob er zwischen den beiden winkeln des schussradius liegt.
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

the[V]oid

Alter Hase

Beiträge: 775

Wohnort: Aachen

  • Private Nachricht senden

3

06.07.2010, 18:16

Ich habe die Fragestellung nicht verstanden ^_^

In Bezug auf den Titel:
Wie kann ein Punkt von einem Winkel eingeschlossen werden?

In Bezug auf "ob der Punkt P innerhalb des aufgespannten Kegels liegt - In dem Beispiel ist es ja nicht der Fall":
Hä? Von was wird der Kreis denn "aufgespannt" - Dieses Verb ist mir im Zusammenhang mit Kreisen sowieso fremd...
Aber falls ich es so verstehe, wie du das meinst, dann ist der Punkt IMO doch von dem Kreis eingeschlossen??
Sieht jedenfalls so aus, als wäre §|Pos-P|\leq|a|§.
<< an dieser Stelle ist eine Signatur verstorben >>

Oromis_32

Frischling

  • »Oromis_32« ist der Autor dieses Themas

Beiträge: 28

  • Private Nachricht senden

4

06.07.2010, 18:50

Danke schonmal für die Antworten.

OK, ich werde es nochmal versuchen zu erklären:

Ich habe einen Schusskegel (im Effekt einen Winkel). Jetzt will ich prüfen, ob ein Objekt (hier P) in diesem Winkel liegt. Die Fragestellung ist ganz einfach, wenn man sie sich anhand folgender Zeichnung vorstellt:

Der Punkt P liegt hier klar innerhalb des Winkels.

@the[V]oid: Ich habe auch nicht von einem Kreis, sondern von einem Kegel geredet.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

5

06.07.2010, 18:58

Ganz spontan würd ichs mal so machen: Nimm den Richtungsvektor r von Pos nach P. Dann berechne die beiden Kreuzprodukte r x a und r x b. Wenn das Punktprodukt von r x a mit r x b negativ ist dann liegt P dazwischen, sonst nicht. Da das ganze 2D ist lassen sich die Formeln auch noch stark vereinfachen...
m4studios

Oromis_32

Frischling

  • »Oromis_32« ist der Autor dieses Themas

Beiträge: 28

  • Private Nachricht senden

6

06.07.2010, 19:15

Danke, das werde ich probieren!

Oromis_32

Frischling

  • »Oromis_32« ist der Autor dieses Themas

Beiträge: 28

  • Private Nachricht senden

7

06.07.2010, 19:25

OK, das ist doof... Mir ist gerade aufgefallen, dass das Kreuzprodukt bei 2D - Vektoren keinen Sinn macht... Damit kann ich die Lösung leider nicht testen. Wie könnte ich das umgehen?

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

8

06.07.2010, 19:26

Was meine spontane geometrische Interpretation des Bildes war: finde die Linearkombination Pos + k1*a + k2*b = P, wenn k1 und k2 positiv sind, dann liegt es in dem Winkel.

Zitat von »dot«

Ganz spontan würd ichs mal so machen: Nimm den Richtungsvektor r von Pos nach P. Dann berechne die beiden Kreuzprodukte r x a und r x b. Wenn das Punktprodukt von r x a mit r x b negativ ist dann liegt P dazwischen, sonst nicht. Da das ganze 2D ist lassen sich die Formeln auch noch stark vereinfachen...
Hier hab ich den Eindruck, das Punktprodukt ist auch negativ, wenn man -r ist die Formel gibt. f'`8k


Gruß, TGGC (der kostenlose DMC Download)
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Oromis_32

Frischling

  • »Oromis_32« ist der Autor dieses Themas

Beiträge: 28

  • Private Nachricht senden

9

06.07.2010, 19:30

Zitat von »TGGC«

Was meine spontane geometrische Interpretation des Bildes war: finde die Linearkombination Pos + k1*a + k2*b = P, wenn k1 und k2 positiv sind, dann liegt es in dem Winkel.


Sry für die blöde Frage, aber was in aller Welt ist eine Linearkombination? Hat das was mit nem linearen Gleichungssystem zu tun?

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

10

06.07.2010, 21:03

Zitat von »Oromis_32«

OK, das ist doof... Mir ist gerade aufgefallen, dass das Kreuzprodukt bei 2D - Vektoren keinen Sinn macht... Damit kann ich die Lösung leider nicht testen. Wie könnte ich das umgehen?

Wo liegt das Problem, setz z einfach auf 0. Wie gesagt vereinfachen sich die Gleichungen dann und das ganze läuft im Prinzip auf einen Vorzeichenvergleich der z Koordinaten der beiden Kreuzprodukte raus.

Zitat von »TGGC«

Was meine spontane geometrische Interpretation des Bildes war: finde die Linearkombination Pos + k1*a + k2*b = P, wenn k1 und k2 positiv sind, dann liegt es in dem Winkel.

Das ist hinreichend aber nicht notwendig. Stell dir vor P liegt außerhalb von a und b aber in der Richtung in die a und b zeigen und schon hast du einen Fall wo k1 und k2 positiv sind aber P nicht zwischen a und b liegt.

Zitat von »TGGC«

Zitat von »dot«

Ganz spontan würd ichs mal so machen: Nimm den Richtungsvektor r von Pos nach P. Dann berechne die beiden Kreuzprodukte r x a und r x b. Wenn das Punktprodukt von r x a mit r x b negativ ist dann liegt P dazwischen, sonst nicht. Da das ganze 2D ist lassen sich die Formeln auch noch stark vereinfachen...
Hier hab ich den Eindruck, das Punktprodukt ist auch negativ, wenn man -r ist die Formel gibt.

Punktprodukt negativ bedeutet dass die beiden Kreuzprodukte in entgegengesetzte Richtungen zeigen, was eine notwendig Bedingung dafür ist dass P zwischen a und b liegt.
m4studios

Werbeanzeige

  • 1
  • 2

Ähnliche Themen