Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Perfect Circle - Rectangle Collision Resolution

By: ClickerMonkey on Sep 13th, 2013  |  syntax: Java  |  size: 15.51 KB  |  views: 466  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.  
  2. import java.awt.Color;
  3. import java.awt.Font;
  4. import java.awt.Graphics;
  5. import java.awt.Graphics2D;
  6. import java.awt.RenderingHints;
  7. import java.awt.event.MouseEvent;
  8. import java.awt.geom.Ellipse2D;
  9. import java.awt.geom.Line2D;
  10. import java.awt.geom.Rectangle2D;
  11.  
  12. import javax.swing.JFrame;
  13. import javax.swing.JPanel;
  14. import javax.swing.event.MouseInputListener;
  15.  
  16. public class CircleRectangle extends JPanel implements MouseInputListener
  17. {
  18.    private static final long serialVersionUID = 1L;
  19.  
  20.    public static void main( String[] args )
  21.     {
  22.         JFrame window = new JFrame();
  23.         window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  24.         window.setTitle("Circle Rectangle");
  25.         window.setLocationRelativeTo(null);
  26.  
  27.         CircleRectangle space = new CircleRectangle();
  28.         window.add(space);
  29.         window.setSize(640, 480);
  30.         window.setResizable(false);
  31.  
  32.         window.setVisible(true);
  33.  
  34.         space.start();
  35.     }
  36.  
  37.     public CircleRectangle()
  38.     {
  39.         setBackground(Color.BLACK);
  40.         addMouseListener(this);
  41.         addMouseMotionListener(this);
  42.     }
  43.  
  44.     public static final Font FONT = new Font( "Monospaced" , Font.PLAIN, 12 );
  45.  
  46.     private enum DraggingState
  47.     {
  48.         START, END, RADIUS, NONE;
  49.     }
  50.  
  51.     private class Intersection
  52.     {
  53.         public float cx, cy, time, nx, ny, ix, iy;
  54.         public Intersection(float x, float y, float time, float nx, float ny, float ix, float iy)
  55.         {
  56.             this.cx = x;
  57.             this.cy = y;
  58.             this.time = time;
  59.             this.nx = nx;
  60.             this.ny = ny;
  61.             this.ix = ix;
  62.             this.iy = iy;
  63.         }
  64.     }
  65.  
  66.     private float pointRadius = 8.0f;
  67.     private Vector2 start;
  68.     private Vector2 end;
  69.     private Vector2 radiusPoint;
  70.     private float radius;
  71.     private Bounds bounds;
  72.     private DraggingState dragging;
  73.  
  74.     public void start()
  75.     {
  76.         bounds = new Bounds( 150, 150, 490, 330 );
  77.         start = new Vector2( 50, 400 );
  78.         end = new Vector2( 320, 240 );
  79.         radius = 40.0f;
  80.         radiusPoint = new Vector2( start.x, start.y - radius );
  81.         dragging = DraggingState.NONE;
  82.     }
  83.  
  84.     public void paint( Graphics g )
  85.     {
  86.         Graphics2D g2d = (Graphics2D)g;
  87.        
  88.         g2d.setRenderingHint( RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON );
  89.  
  90.         g2d.setColor(getBackground());
  91.         g2d.fillRect(0, 0, getWidth(), getHeight());
  92.  
  93.         g2d.setColor( Color.BLUE );
  94.         g2d.draw( new Rectangle2D.Float( bounds.left, bounds.top, bounds.getWidth(), bounds.getHeight() ) );
  95.  
  96.         g2d.setColor( Color.WHITE );
  97.         g2d.draw( new Line2D.Float( start.x, start.y, end.x, end.y ) );
  98.  
  99.         g2d.setColor( Color.GREEN );
  100.         g2d.draw( new Ellipse2D.Float( start.x - pointRadius, start.y - pointRadius, pointRadius * 2, pointRadius * 2 ) );
  101.  
  102.         g2d.setColor( Color.RED );
  103.         g2d.draw( new Ellipse2D.Float( end.x - pointRadius, end.y - pointRadius, pointRadius * 2, pointRadius * 2 ) );
  104.  
  105.         g2d.setColor( Color.YELLOW );
  106.         g2d.draw( new Ellipse2D.Float( radiusPoint.x - pointRadius, radiusPoint.y - pointRadius, pointRadius * 2, pointRadius * 2 ) );
  107.         g2d.draw( new Ellipse2D.Float( start.x - radius, start.y - radius, radius * 2, radius * 2 ) );
  108.         g2d.draw( new Ellipse2D.Float( end.x - radius, end.y - radius, radius * 2, radius * 2 ) );
  109.  
  110.         // Check for intersection
  111.  
  112.         g2d.setColor( Color.LIGHT_GRAY );
  113.         g2d.setFont( FONT );
  114.  
  115.         Intersection inter = handleIntersection( bounds, start, end, radius );
  116.  
  117.         if (inter != null)
  118.         {
  119.             g2d.setColor( Color.LIGHT_GRAY );
  120.             g2d.drawString( "time: " + inter.time, 10, 20 );
  121.  
  122.             g2d.setColor( Color.GRAY );
  123.             g2d.draw( new Ellipse2D.Float( inter.cx - radius, inter.cy - radius, radius * 2, radius * 2 ) );
  124.             g2d.draw( new Line2D.Float( inter.cx, inter.cy, inter.cx + inter.nx * 20, inter.cy + inter.ny * 20 ) );
  125.          
  126.             g2d.setColor( Color.RED );
  127.             g2d.draw( new Ellipse2D.Float( inter.ix - 2, inter.iy - 2, 4, 4 ) );
  128.          
  129.             // Project Future Position
  130.             float remainingTime = 1.0f - inter.time;
  131.             float dx = end.x - start.x;
  132.             float dy = end.y - start.y;
  133.             float dot = dx * inter.nx + dy * inter.ny;
  134.             float ndx = dx - 2 * dot * inter.nx;
  135.             float ndy = dy - 2 * dot * inter.ny;
  136.             float newx = inter.cx + ndx * remainingTime;
  137.             float newy = inter.cy + ndy * remainingTime;
  138.  
  139.             g2d.setColor( Color.darkGray );
  140.             g2d.draw( new Ellipse2D.Float( newx - radius, newy - radius, radius * 2, radius * 2 ) );
  141.             g2d.draw( new Line2D.Float( inter.cx, inter.cy, newx, newy ) );
  142.         }
  143.     }
  144.  
  145.     private Intersection handleIntersection(Bounds bounds, Vector2 start, Vector2 end, float radius)
  146.     {
  147.         final float L = bounds.left;
  148.         final float T = bounds.top;
  149.         final float R = bounds.right;
  150.         final float B = bounds.bottom;
  151.  
  152.         // If the bounding box around the start and end points (+radius on all
  153.         // sides) does not intersect with the rectangle, definitely not an
  154.         // intersection
  155.         if ((Math.max( start.x, end.x ) + radius < L) ||
  156.             (Math.min( start.x, end.x ) - radius > R) ||
  157.             (Math.max( start.y, end.y ) + radius < T) ||
  158.             (Math.min( start.y, end.y ) - radius > B) )
  159.         {
  160.             return null;
  161.         }
  162.  
  163.         final float dx = end.x - start.x;
  164.         final float dy = end.y - start.y;
  165.         final float invdx = (dx == 0.0f ? 0.0f : 1.0f / dx);
  166.         final float invdy = (dy == 0.0f ? 0.0f : 1.0f / dy);
  167.         float cornerX = Float.MAX_VALUE;
  168.         float cornerY = Float.MAX_VALUE;
  169.  
  170.         // Calculate intersection times with each side's plane
  171.         // Check each side's quadrant for single-side intersection
  172.         // Calculate Corner
  173.      
  174.         /** Left Side **/
  175.         // Does the circle go from the left side to the right side of the rectangle's left?
  176.         if ( start.x - radius < L && end.x + radius > L )
  177.         {
  178.             float ltime = ((L - radius) - start.x) * invdx;
  179.             if (ltime >= 0.0f && ltime <= 1.0f)
  180.             {
  181.                 float ly = dy * ltime + start.y;
  182.                 // Does the collisions point lie on the left side?
  183.                 if (ly >= T && ly <= B)
  184.                 {
  185.                     return new Intersection( dx * ltime + start.x, ly, ltime, -1, 0, L, ly );
  186.                 }
  187.             }
  188.             cornerX = L;
  189.         }
  190.  
  191.         /** Right Side **/
  192.         // Does the circle go from the right side to the left side of the rectangle's right?
  193.         if ( start.x + radius > R && end.x - radius < R )
  194.         {
  195.             float rtime = (start.x - (R + radius)) * -invdx;
  196.             if (rtime >= 0.0f && rtime <= 1.0f)
  197.             {
  198.                 float ry = dy * rtime + start.y;
  199.                 // Does the collisions point lie on the right side?
  200.                 if (ry >= T && ry <= B)
  201.                 {
  202.                     return new Intersection( dx * rtime + start.x, ry, rtime, 1, 0, R, ry );
  203.                 }
  204.             }
  205.             cornerX = R;
  206.         }
  207.  
  208.         /** Top Side **/
  209.         // Does the circle go from the top side to the bottom side of the rectangle's top?
  210.         if (start.y - radius < T && end.y + radius > T)
  211.         {
  212.             float ttime = ((T - radius) - start.y) * invdy;
  213.             if (ttime >= 0.0f && ttime <= 1.0f)
  214.             {
  215.                 float tx = dx * ttime + start.x;
  216.                 // Does the collisions point lie on the top side?
  217.                 if (tx >= L && tx <= R)
  218.                 {
  219.                     return new Intersection( tx, dy * ttime + start.y, ttime, 0, -1, tx, T );
  220.                 }
  221.             }
  222.             cornerY = T;
  223.         }
  224.  
  225.         /** Bottom Side **/
  226.         // Does the circle go from the bottom side to the top side of the rectangle's bottom?
  227.         if (start.y + radius > B && end.y - radius < B)
  228.         {
  229.             float btime = (start.y - (B + radius)) * -invdy;
  230.             if (btime >= 0.0f && btime <= 1.0f) {
  231.                 float bx = dx * btime + start.x;
  232.                 // Does the collisions point lie on the bottom side?
  233.                 if (bx >= L && bx <= R)
  234.                 {
  235.                     return new Intersection( bx, dy * btime + start.y, btime, 0, 1, bx, B );
  236.                 }
  237.             }
  238.             cornerY = B;
  239.         }
  240.  
  241.         // No intersection at all!
  242.         if (cornerX == Float.MAX_VALUE && cornerY == Float.MAX_VALUE)
  243.         {
  244.             return null;
  245.         }
  246.  
  247.         // Account for the times where we don't pass over a side but we do hit it's corner
  248.         if (cornerX != Float.MAX_VALUE && cornerY == Float.MAX_VALUE)
  249.         {
  250.             cornerY = (dy > 0.0f ? B : T);
  251.         }
  252.         if (cornerY != Float.MAX_VALUE && cornerX == Float.MAX_VALUE)
  253.         {
  254.             cornerX = (dx > 0.0f ? R : L);
  255.         }
  256.  
  257.         /* Solve the triangle between the start, corner, and intersection point.
  258.          *                    
  259.          *           +-----------T-----------+
  260.          *           |                       |
  261.          *          L|                       |R
  262.          *           |                       |
  263.          *           C-----------B-----------+
  264.          *          / \      
  265.          *         /   \r     _.-E
  266.          *        /     \ _.-'
  267.          *       /    _.-I
  268.          *      / _.-'
  269.          *     S-'
  270.          *
  271.          * S = start of circle's path
  272.          * E = end of circle's path
  273.          * LTRB = sides of the rectangle
  274.          * I = {ix, iY} = point at which the circle intersects with the rectangle
  275.          * C = corner of intersection (and collision point)
  276.          * C=>I (r) = {nx, ny} = radius and intersection normal
  277.          * S=>C = cornerdist
  278.          * S=>I = intersectionDistance
  279.          * S=>E = lineLength
  280.          * <S = innerAngle
  281.          * <I = angle1
  282.          * <C = angle2
  283.          */
  284.  
  285.         double inverseRadius = 1.0 / radius;
  286.         double lineLength = Math.sqrt( dx * dx + dy * dy );
  287.         double cornerdx = cornerX - start.x;
  288.         double cornerdy = cornerY - start.y;
  289.         double cornerDistance = Math.sqrt( cornerdx * cornerdx + cornerdy * cornerdy );
  290.         double innerAngle = Math.acos( (cornerdx * dx + cornerdy * dy) / (lineLength * cornerDistance) );
  291.        
  292.         // If the circle is too close, no intersection.
  293.         if (cornerDistance < radius)
  294.         {
  295.            return null;
  296.         }
  297.        
  298.         // If inner angle is zero, it's going to hit the corner straight on.
  299.         if (innerAngle == 0.0f)
  300.         {
  301.            float time = (float)((cornerDistance - radius) / lineLength);
  302.            
  303.            // If time is outside the boundaries, return null. This algorithm can
  304.            // return a negative time which indicates a previous intersection, and
  305.            // can also return a time > 1.0f which can predict a corner intersection.
  306.            if (time > 1.0f || time < 0.0f)
  307.            {
  308.                return null;
  309.            }
  310.            
  311.            float ix = time * dx + start.x;
  312.            float iy = time * dy + start.y;
  313.            float nx = (float)(cornerdx / cornerDistance);
  314.            float ny = (float)(cornerdy / cornerDistance);
  315.            
  316.            return new Intersection( ix, iy, time, nx, ny, cornerX, cornerY );
  317.         }
  318.        
  319.         double innerAngleSin = Math.sin( innerAngle );
  320.         double angle1Sin = innerAngleSin * cornerDistance * inverseRadius;
  321.  
  322.         // The angle is too large, there cannot be an intersection
  323.         if (Math.abs( angle1Sin ) > 1.0f)
  324.         {
  325.             return null;
  326.         }
  327.  
  328.         double angle1 = Math.PI - Math.asin( angle1Sin );
  329.         double angle2 = Math.PI - innerAngle - angle1;
  330.         double intersectionDistance = radius * Math.sin( angle2 ) / innerAngleSin;
  331.  
  332.         // Solve for time
  333.         float time = (float)(intersectionDistance / lineLength);
  334.  
  335.         // If time is outside the boundaries, return null. This algorithm can
  336.         // return a negative time which indicates a previous intersection, and
  337.         // can also return a time > 1.0f which can predict a corner intersection.
  338.         if (time > 1.0f || time < 0.0f)
  339.         {
  340.             return null;
  341.         }
  342.  
  343.         // Solve the intersection and normal
  344.         float ix = time * dx + start.x;
  345.         float iy = time * dy + start.y;
  346.         float nx = (float)((ix - cornerX) * inverseRadius);
  347.         float ny = (float)((iy - cornerY) * inverseRadius);
  348.  
  349.         return new Intersection( ix, iy, time, nx, ny, cornerX, cornerY );
  350.     }
  351.  
  352.     public void mousePressed( MouseEvent e )
  353.     {
  354.        Vector2 mouse = new Vector2(e.getX(), e.getY());
  355.        
  356.         if (mouse.distance( start ) <= pointRadius)
  357.         {
  358.             dragging = DraggingState.START;
  359.         }
  360.         else if (mouse.distance( end ) <= pointRadius)
  361.         {
  362.             dragging = DraggingState.END;
  363.         }
  364.         else if (mouse.distance( radiusPoint ) <= pointRadius)
  365.         {
  366.             dragging = DraggingState.RADIUS;
  367.         }
  368.         else
  369.         {
  370.            dragging = DraggingState.NONE;
  371.         }
  372.     }
  373.  
  374.     public void mouseReleased( MouseEvent e )
  375.     {
  376.        dragging = DraggingState.NONE;
  377.     }
  378.  
  379.     public void mouseDragged( MouseEvent e )
  380.     {
  381.         Vector2 mouse = new Vector2(e.getX(), e.getY());
  382.  
  383.         switch (dragging)
  384.         {
  385.             case END:
  386.                 end.set( mouse );
  387.                 break;
  388.             case RADIUS:
  389.                 radiusPoint.set( mouse );
  390.                 radius = radiusPoint.distance( start );
  391.                 break;
  392.             case START:
  393.                 start.set( mouse );
  394.                 radiusPoint.set( mouse );
  395.                 radiusPoint.y -= radius;
  396.                 break;
  397.             case NONE:
  398.                 break;
  399.         }
  400.  
  401.         repaint();
  402.     }
  403.  
  404.     // Unused Mouse Listener Methods
  405.     public void mouseMoved( MouseEvent e ) {}
  406.     public void mouseClicked( MouseEvent e ) {}
  407.     public void mouseEntered( MouseEvent e ) {}
  408.     public void mouseExited( MouseEvent e ) {}
  409.  
  410.     public class Vector2
  411.     {
  412.         public float x;
  413.         public float y;
  414.         public Vector2()
  415.         {
  416.             this(0, 0);
  417.         }
  418.         public Vector2(float x, float y)
  419.         {
  420.             this.x = (int)x;
  421.             this.y = (int)y;
  422.         }
  423.         public float distance(Vector2 other)
  424.         {
  425.            float dx = other.x - x;
  426.            float dy = other.y - y;
  427.            
  428.             return (float)Math.sqrt(dx * dx + dy * dy);
  429.         }
  430.         public void set(Vector2 other)
  431.         {
  432.             this.x = other.x;
  433.             this.y = other.y;
  434.         }
  435.     }
  436.  
  437.     public class Bounds
  438.     {
  439.         public float left;
  440.         public float top;
  441.         public float right;
  442.         public float bottom;
  443.         public Bounds()
  444.         {
  445.             this(0, 0, 0, 0);
  446.         }
  447.         public Bounds(float left, float top, float right, float bottom)
  448.         {
  449.             this.left = left;
  450.             this.top = top;
  451.             this.right = right;
  452.             this.bottom = bottom;
  453.         }
  454.         public float getWidth()
  455.         {
  456.             return right - left;
  457.         }
  458.         public float getHeight()
  459.         {
  460.             return bottom - top;
  461.         }
  462.     }
  463.  
  464. }