SAT 자바 구현

Question

나는 이 구현을 얻으려고 애썼다. Axis Theorem을으로 분리했지만 다각형이 서로 가까이있을 때 충돌이 감지된다. 나는 무엇이 잘못 되었는가? 코드가 ... 최적화라는 사실을 제외하면 다음 단계는 문제가 아닙니다. 그러나 읽을만큼 쉬워야합니다.

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