Game OverGlocke hat geschrieben:Naja für die 3. Phase (vom Kontext her beziehe ich mich erstmal auf 2D) würde ich konvexe Boost-Polygone verwenden.
So wie ich das sehe, kann ich mit boost::polygon nur prüfen, ob ein PUNKT in einem Polygon liegt. Eben habe ich nochmal die alte Geradengleichungsgeschichte aufgegriffen und nochmal umgestellt. Unter der Voraussetzung, dass für beide Skalare gilt 0<=r,s<=1 habe ich dann folgenden Python-Code (als Test des Algorithmus) geschrieben:Code: Alles auswählen
class Vector:
def __init__(self, x, y):
self.x = x
self.y = y
def getCut(a, b, c, d):
tmp1 = c.x - a.x
tmp2 = d.x - c.x
tmp3 = (b.x - a.x)
q1 = (c.y - a.y) * (b.x - a.x) - tmp1 * (b.y - a.y)
q2 = tmp2 * (b.y - a.y) - (d.y - c.y) * tmp3
q = float(q1) / float(q2)
if (q < 0 or q > 1):
return False
p = (tmp1 + q * tmp2) / float(tmp3)
if (p < 0 or p > 1):
return False
return True
A = Vector(1, 1)
B = Vector(13, 8)
C = Vector(2, 7)
D = Vector(10, 2)
print getCut(A, B, C, D)Code: Alles auswählen
bool Polygon::doesIntersect(Polygon* other)
Als Approximation des Kollisionspolygons habe ich mich für einen Kreis entschieden. D.h. ich werde - bevor polygonbasiert getestet wird - einen Kreisschnitt als approximative Kollisionserkennung durchführen (oben hatte ich glaube von einem Rechteck gesprochen). Der Kreis hat aus meiner Sicht zwei Vorteile:
- Ich gebe Polygon-Ecken relativ zum lokalen Koordinatensystem der Figur an. Das Koord.-System liegt in der Weltposition der Figur, so dass ich nicht nur bequem die absoluten Polygon-Eckpunkt-Koordinaten ermitteln kann, sondern auch jenen Punkt ermitteln, der vom lokalen Ursprung am weiteste entfernt liegt (auf Basis des Euklidischen Abstandes). Dieser Abstand bildet den Radius des Approximationskreises; sein Mittelpunkt ist die Weltposition der Figur. Bei einer Bewegung muss ich also nur die Weltposition und die Polygon-Ecken verschieben, der Kreis geht automatisch mit.
- Der Schnitt zweier Kreise lässt sich imho schneller Berechnen als der zweier Rechtecke: Abstand beider Kreismittelpunkte bestimmen und gucken, ob der Abstand kleiner als die Summe der Radien ist.
LG Glocke
- mal direkt mit Quadtrees beschäftigen. Aus mehreren Quellen wurde mir gesagt, dass man die für die Kollisionserkennung mit verwenden kann, um die Objekte so zu strukturieren, dass man i.d.R. schneller alle verdächtigen Objekte hat.