SAT java implementation

Question

Я пытаюсь получить эту реализацию теоремы о разделительной оси для работы, но обнаружение столкновения обнаруживается, когда многоугольники находятся близко друг к другу ... с некоторых сторон. Что я сделал не так? Помимо того, что код ... оптимизация - это следующий шаг, здесь проблема не проблема. Но это должно быть достаточно легко читать.

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

Хорошо, я нашел то, что была проблема ... Я просто разместить фиксированный код для проблемной части так что этот вопрос будет содержать корректную, полностью не оптимизированную реализацию SAT (используются для обнаружения столкновений между выпуклыми многоугольниками, если вы просто проходите мимо):

//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()); 
     }