Robotics Square Grid Schnittpunkt

Question

Ich versuche den Punkt zu bestimmen, an dem mein Roboter eine Wand schneiden wird, wenn man seine Position in einer Karte und einen Winkel im Bogenmaß angibt. Um also das Problem zu summieren, wird bei einem quadratischen Raster beliebiger Größe [1-unendlich], einem Objekt innerhalb dieses Rasters und dem Winkel, in dem das Objekt (Radianten) liegt, der Schnittpunkt mit dem Rand des Rasters gefunden . Zum Beispiel haben Sie ein 10 x 10 Gitter, Ihr Objekt befindet sich an der Position (5,5) und es steht in einem Winkel von pi/8 Radiant (Nordosten). Wenn dieses Objekt sich in einer geraden Linie bewegen würde, wo würde es sich mit der Wand kreuzen? Gibt es eine verallgemeinerte Lösung, die für jede Position und jeden Winkel funktioniert? Was ich bisher mache ist, einen Punkt außerhalb des Gitters auf der gleichen Flugbahn zu berechnen und alle Punkte zu betrachten, bis ich eine Wand finde, aber ich habe das Gefühl, dass es wahrscheinlich eine elegantere Lösung gibt. Danke für die Hilfe!

Answer 1

Sie einfach den Schnittpunkt zweier Liniensegmente finden.

Erstes Segment: Das Segment von der Roboterposition im Zielwinkel. Machen Sie dieses Segment größer als die Diagonale Ihres Rasters, um sicherzustellen, dass es die Grenze schneidet, wenn es das Ziel erreicht. Zweites Segment: Das Liniensegment, aus dem die betreffende Wand besteht.

Siehe Abschnitt http://www.faqs.org/faqs/graphics/algorithms-faq/ Abschnitt 1.03 für Algorithmus, um zwei Liniensegmente zu schneiden.

Die FAQ zu comp.graphics.algorithmen ist eine nützliche Ressource für allgemeine Geometrieprobleme in der Robotik.

Answer 2

Pseudocode für ray mit Startpunkten innerhalb Rechteck:
Startpunkt (X0, Y0)
Ray Winkel Theta, c = Cos(Theta), s = Sin(Theta);
Rechteck-Koordinaten: bottom left (X1,Y1), top right (X2,Y2)

if c >= 0 then //up 
    XX = X2 
else 
    XX = X1 

if s >= 0 then //right 
    YY = Y2 
else 
    YY = Y1 

if c = 0 then //vertical ray 
    return Intersection = (X0, YY) 

if s = 0 then //horizontal ray 
    return Intersection = (XX, Y0) 

tx = (XX - X0)/c //parameter when vertical edge is met 
ty = (YY - Y0)/s //parameter when horizontal edge is met 

if tx <= ty then //vertical first 
    return Intersection = (XX, Y0 + tx * s) 
else   //horizontal first 
    return Intersection = (X0 + ty * c, YY)