我一直在尝试让分离轴定理的这种实现工作，但是当多边形彼此靠近时检测到碰撞......在某些方面。我做错了什么？除了代码是...优化是下一步，这不是这里的问题。但它应该很容易阅读。
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);
}
}
}
好的，我找到了问题所在...我将只发布有问题的部分的固定代码，因此这个问题将包含一个有效的、完全未优化的 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());
}