SAT java implementation

Question

J'ai essayé d'obtenir cette implémentation du Théorème de l'Axe de Séparation pour fonctionner mais une collision est détectée lorsque les polygones sont seulement proches les uns des autres ... sur certains côtés. Qu'est-ce que je me suis trompé? Mis à part le fait que le code est ... l'optimisation est la prochaine étape, ce n'est pas le problème ici. Mais il devrait être assez facile à lire.

import javax.swing.JPanel; 
import javax.swing.JFrame; 

import java.awt.Color; 
import java.awt.Graphics; 
import java.awt.event.MouseEvent; 
import java.awt.event.MouseMotionListener; 

import java.util.ArrayList; 

public class SAT 
{ 
    public static boolean SAT(Polygon p1, Polygon p2) 
    { 
     ArrayList<Vector> normals = new ArrayList<Vector>(); 

     //recover normal vectors for p1 and p2 

     for (int i = 0; i < p1.getPointCount(); i++) 
     { 
      if (i < p1.getPointCount() - 1) 
      { 
       float x = p1.getPoint(i + 1).x + p1.getPosition().x - p1.getPoint(i).x + p1.getPosition().x; 
       float y = p1.getPoint(i + 1).y + p1.getPosition().y - p1.getPoint(i).y + p1.getPosition().y; 
       normals.add(new Vector(x, y).getNormalVectorLeft()); 
      } 
      else 
      { 
       float x = p1.getPoint(0).x + p1.getPosition().x - p1.getPoint(i).x + p1.getPosition().x; 
       float y = p1.getPoint(0).y + p1.getPosition().y - p1.getPoint(i).y + p1.getPosition().y; 
       normals.add(new Vector(x, y).getNormalVectorLeft()); 
      } 
     } 

     for (int i = 0; i < p2.getPointCount(); i++) 
     { 
      if (i < p2.getPointCount() - 1) 
      { 
       float x = p2.getPoint(i + 1).x + p2.getPosition().x - p2.getPoint(i).x + p2.getPosition().x; 
       float y = p2.getPoint(i + 1).y + p2.getPosition().y - p2.getPoint(i).y + p2.getPosition().y; 
       normals.add(new Vector(x, y).getNormalVectorLeft()); 
      } 
      else 
      { 
       float x = p2.getPoint(0).x + p2.getPosition().x - p2.getPoint(i).x + p2.getPosition().x; 
       float y = p2.getPoint(0).y + p2.getPosition().y - p2.getPoint(i).y + p2.getPosition().y; 
       normals.add(new Vector(x, y).getNormalVectorLeft()); 
      } 
     } 

     //project points of p1 and p2 on each normal vector until a gap is found 

     for (int n = 0; n < normals.size(); n++) 
     { 
      ArrayList<Float> projectedPoints1 = new ArrayList<Float>(); 
      ArrayList<Float> projectedPoints2 = new ArrayList<Float>(); 

      for (int i = 0; i < p1.getPointCount(); i++) 
       projectedPoints1.add(new Vector(p1.getPoint(i).x + p1.getPosition().x, p1.getPoint(i).y + p1.getPosition().y).dot(normals.get(n))); 

      for (int i = 0; i < p2.getPointCount(); i++) 
       projectedPoints2.add(new Vector(p2.getPoint(i).x + p2.getPosition().x, p2.getPoint(i).y + p2.getPosition().y).dot(normals.get(n))); 

      float min1 = getMin(projectedPoints1); 
      float max1 = getMax(projectedPoints1); 

      float min2 = getMin(projectedPoints2); 
      float max2 = getMax(projectedPoints2); 

      if (max1 < min2 || max2 < min1) 
       return false; 
     } 

     return true; 
    } 

    public static float getMin(ArrayList<Float> list) 
    { 
     float min = list.get(0); 

     for (float f : list) 
      if (f < min) 
       min = f; 

     return min; 
    } 

    public static float getMax(ArrayList<Float> list) 
    { 
     float max = list.get(0); 

     for (float f : list) 
      if (f > max) 
       max = f; 

     return max; 
    } 

    public static void main(String[] args) 
    { 
     JFrame frame = new JFrame(); 
     frame.setTitle("SAT"); 
     frame.setLocation(128, 32); 
     frame.setSize(800, 512); 
     frame.setContentPane(new Panel()); 
     frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 

     frame.setVisible(true); 
    } 

    private static class Panel extends JPanel implements MouseMotionListener 
    { 
     Polygon p1; 
     Polygon p2; 

     public Panel() 
     { 
      this.p1 = new Polygon(); 
      this.p2 = new Polygon(); 

      this.p1.setPointCount(3); 
      this.p1.setPoint(0, new Vector(0 * 32, 0 * 32)); 
      this.p1.setPoint(1, new Vector(2 * 32, 3 * 32)); 
      this.p1.setPoint(2, new Vector(0 * 32, 2 * 32)); 
      this.p1.setPosition(128, 128); 

      this.p2.setPointCount(3); 
      this.p2.setPoint(0, new Vector(0 * 32, 0 * 32)); 
      this.p2.setPoint(1, new Vector(1 * 32, 2 * 32)); 
      this.p2.setPoint(2, new Vector(0 * 32, 2 * 32)); 
      this.p2.setPosition(128, 128); 

      this.addMouseMotionListener(this); 
     } 

     public void paintComponent(Graphics g) 
     { 
      super.paintComponent(g); 

      if (SAT(p1, p2)) 
       g.setColor(Color.RED); 
      else 
       g.setColor(Color.BLACK); 

      java.awt.Polygon p; 

      p = new java.awt.Polygon(); 

      for (int i = 0; i < p1.getPointCount(); i++) 
       p.addPoint((int) (p1.getPoint(i).x + p1.getPosition().x), (int) (p1.getPoint(i).y + p1.getPosition().y)); 

      g.drawPolygon(p); 

      p = new java.awt.Polygon(); 

      for (int i = 0; i < p2.getPointCount(); i++) 
       p.addPoint((int) (p2.getPoint(i).x + p2.getPosition().x), (int) (p2.getPoint(i).y + p2.getPosition().y)); 

      g.drawPolygon(p); 
     } 

     public void mouseDragged(MouseEvent e) 
     { 
      return; 
     } 

     public void mouseMoved(MouseEvent e) 
     { 
      p2.setPosition(e.getX(), e.getY()); 
      repaint(); 
     } 
    } 

    private static class Polygon 
    { 
     private Vector[] points; 
     private Vector position; 

     public Polygon() 
     { 
      this.points = new Vector[0]; 
     } 

     public void setPointCount(int n) 
     { 
      points = new Vector[n]; 
     } 

     public void setPoint(int i, Vector v) 
     { 
      points[i] = v; 
     } 

     public void setPosition(float x, float y) 
     { 
      position = new Vector(x, y); 
     } 

     public Vector getPoint(int i) 
     { 
      return points[i]; 
     } 

     public Vector getPosition() 
     { 
      return position; 
     } 

     public int getPointCount() 
     { 
      return points.length; 
     } 
    } 

    private static class Vector 
    { 
     public final float x; 
     public final float y; 

     public Vector(float x, float y) 
     { 
      this.x = x; 
      this.y = y; 
     } 

     public float dot(Vector v) 
     { 
      return x * v.x + y * v.y; 
     } 

     public float length() 
     { 
      return (float) Math.sqrt(x * x + y * y); 
     } 

     public Vector normalize() 
     { 
      float l = length(); 
      return new Vector(x/l, y/l); 
     } 

     public Vector getNormalVectorLeft() 
     { 
      return new Vector(-y, x); 
     } 

     public Vector getNormalVectorRight() 
     { 
      return new Vector(y, -x); 
     } 
    } 
} 

Answer 1

Ok, j'ai trouvé quel était le problème ... Je vais juste afficher le code fixe pour la partie problématique si cette question contiendra une mise en œuvre valable, totalement non optimisé de SAT (il est utilisé pour détecter les collisions entre les polygones convexes si vous ne faites que passer):

//recover normal vectors for p1 and p2 

    for (int i = 0; i < p1.getPointCount(); i++) 
    { 
     if (i < p1.getPointCount() - 1) 
     { 
      float x = p1.getPoint(i + 1).x - p1.getPoint(i).x; 
      float y = p1.getPoint(i + 1).y - p1.getPoint(i).y; 
      normals.add(new Vector(x, y).getNormalVectorLeft()); 
     } 
     else 
     { 
      float x = p1.getPoint(0).x - p1.getPoint(i).x; 
      float y = p1.getPoint(0).y - p1.getPoint(i).y; 
      normals.add(new Vector(x, y).getNormalVectorLeft()); 
     } 
    } 

    for (int i = 0; i < p2.getPointCount(); i++) 
    { 
     if (i < p2.getPointCount() - 1) 
     { 
      float x = p2.getPoint(i + 1).x - p2.getPoint(i).x; 
      float y = p2.getPoint(i + 1).y - p2.getPoint(i).y; 
      normals.add(new Vector(x, y).getNormalVectorLeft()); 
     } 
     else 
     { 
      float x = p2.getPoint(0).x - p2.getPoint(i).x; 
      float y = p2.getPoint(0).y - p2.getPoint(i).y; 
      normals.add(new Vector(x, y).getNormalVectorLeft()); 
     }