SAT java实现

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