Circle equation question

Mathma · 2009-09-25 01:23:00

I've been trying for a few days now to create a program that does some basic collision detection, more specific a circle vs an axis aligned rectangle. I ran into alot of problems mainly because my math is not very good to say the least.

Anyway, now I ran into a problem I can't seem to overcome and it has to do with the circle equation.

I know the circle equation is (x-a)²+(y-b)² = r² (I found this on various websites including wikipedia). What I dont understand is they all say this is the circle equation but when I try to draw a circle with it I end up with half a circle.

So if (x-a)²+(y-b)² = r² is the equation for half a circle why do they claim it to be the equation of a circle?

Last edited by Mathma (2009-09-25 01:25:03)

luca-deltodesco · 2009-09-25 01:39:12

Let me guess:

you are attempting to render the circle via the rearrangement:

y = b + sqrt(r^2 - (x-a)^2))

?

in which case, remember that there are two roots, so you need to render both

y = b + sqrt(r^2 - (x-a)^2))

AND

y = b - sqrt(r^2 - (x-a)^2))

There are ofcourse, simpler ways of rendering a circle which will give nicer results, using the polar equation for example with a displacement:

centre of circle C, radius r, by iterating over the full circle for θ render curves through the points

P = C + (r.cosθ i + r.sinθ j)

Mathma · 2009-09-25 03:00:27

thx for the reply.

Well im not exactly trying to render a circle with it, im trying to calculate the intersection point between a circle and a line but the problem all boils down to me not understanding this.

yea I was rendering a circle after rearanging the equation so that gives

y = b + sqrt(r^2 - (x-a)^2)) --> (which gives me half a circle)

but where does the other 1 come from?

luca-deltodesco · 2009-09-25 03:45:54

because there are two square roots, a positive AND a negative

think: (-a)*(-a) = a*a

so if a^2 = b, then a = +/-sqrt(b)

-------

I would suggest an alternative solution to your problem, one which is both simpler to implement, and with less problems associated with it:

Assuming a circle centred at C, with radius r again, and a rectangle with centre P and half width,half radius w,h

First consider the following

if C.x + r < P.x-w then the circle cannot intersect the rectangle, the following goes for:
if C.x - r > P.x+w and equivalent on the y-axis.

This is essentially testing for the intersection of the rectangle, and the bounding square of the circle.

After this, the only test left to consider, is dependant on the voronoi region the circle centre is contained in, to test the circle against the relevant vertex of the square, drawing some simply diagrams you should see that this is true.

So this is my suggestion for your intersection method:

bool intersectCircleAARectangle(vec2 C, float r, vec2 P, float w, float h)
{
    //test bounding square
    float dx, dy, adx, ady;
    dx = adx = C.x-P.x; if(adx<0) adx = -adx;
    dy = ady = C.y-P.y; if(ady<0) ady = -ady;
    if(adx < (r+w) || ady < (r+h)) return false;

    //vertex test
    float px, py;
    if(dx<0) px = P.x-w;
    else       px = P.x+w;
    if(dy<0) py = P.y-h;
    else       py = P.y+h;

    dx = C.x-px;
    dy = C.y-py;
    return (dx*dx+dy*dy)<(r*r);
}

Excuse me if there's any errors, i have just done this from the top of my head.

Last edited by luca-deltodesco (2009-09-25 03:46:22)

Mathma · 2009-09-25 06:04:25

thx for the reply again.

I probably should have given some more info on what I'm trying to do exactly. I started with this little game(similar to ping pong) to refresh my math and see if I was able to work it out myself.

Over the past few days I've made the collision detection with both objects work and the collision response versus the sides of the rectangle, probably overcomplicated but it seems to be working.

So what im working on now is the collision response against the rectangle edges.

What (according to me, I'm probably overcomplicating things) has to happen is the following:
1. check for collision with rectangle edge
2. determine the distance from the edge to the circle along the velocity vector (the pentration)
3. move the circle back for that distance along the opposite velocity (moving it out of collision)
4. calculate the new velocity (somekind of bounce effect or whatever)

So to do 2. (calculating the penetration) I'm drawing a line along the velocity going through the rectangle edge which will intersect with the circle, this intersection is the collision point.
Once I have that point I can calculate the amount penetration.

Its calculating that collision point thats proving to be not so easy, I can only calculate it correctly on 1 half of the circle (just like I was able to draw 1 half).

I hacked up a small program in java to display my problem.
This program displays a circle, a line and calculates 2 intersection points, the line can be moved around by dragging the endpoints.

package com.circle.main;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionAdapter;

import javax.swing.JFrame;
import javax.swing.SwingUtilities;

public class Main {

	public static class Vector2f {

		float x, y;

		public static Vector2f sub(Vector2f v1, Vector2f v2) {
			return new Vector2f(v1.x - v2.x, v1.y - v2.y);
		}

		public static float distance(Vector2f v1, Vector2f v2) {
			float x = v1.x - v2.x;
			float y = v1.y - v2.y;
			return (float) Math.sqrt(x * x + y * y);
		}

		public Vector2f(float x, float y) {
			this.x = x;
			this.y = y;
		}
	}

	public static class Circle {

		public Vector2f position;
		public float radius;
		public int drawMode;

		public Circle(float x, float y, float radius) {
			position = new Vector2f(x, y);
			this.radius = radius;
			this.drawMode = 0;
		}

		public boolean isInside(float x, float y) {
			return Vector2f.distance(position, new Vector2f(x, y)) < radius;
		}

		public void draw(Graphics g) {
			if (drawMode == 0) {
				g.drawOval((int) (position.x - radius), (int) (position.y - radius), (int) (radius * 2),(int) (radius * 2));
			} else {
				g.fillOval((int) (position.x - radius),	(int) (position.y - radius), (int) (radius * 2),(int) (radius * 2));
			}
		}
	}

	public static class Result {
		public Vector2f v1, v2;

		public Result(Vector2f v1, Vector2f v2) {
			this.v1 = v1;
			this.v2 = v2;
		}
	}

	public static class MainFrame extends JFrame {

		public Circle cp1, cp2, circle;

		public MainFrame() {
			cp1 = new Circle(100, 100, 10);
			cp2 = new Circle(200, 200, 10);
			circle = new Circle(400, 300, 100);

			cp1.drawMode = cp2.drawMode = 1;

			addMouseMotionListener(new MouseMotionAdapter() {
				public void mouseDragged(MouseEvent evt) {
					int x = evt.getX();
					int y = evt.getY();
					if (cp1.isInside(x, y)) {
						cp1.position.x = x;
						cp1.position.y = y;
						MainFrame.this.repaint();
					}
					if (cp2.isInside(x, y)) {
						cp2.position.x = x;
						cp2.position.y = y;
						MainFrame.this.repaint();
					}
				}
			});
		}

		public Result intersectionTest() {
			Vector2f p1 = cp1.position;
			Vector2f p2 = cp2.position;

			Vector2f p = Vector2f.sub(p1, p2);

			float a = circle.position.x;
			float b = circle.position.y;
			float r = circle.radius;

			float m = p.y / p.x;
			float c = p1.y - m * p1.x;

			float aa = m * m + 1;
			float bb = -2 * a + 2 * m * c - 2 * m * b;
			float cc = a * a + c * c - 2 * b * c + b * b - r * r;

			float d = bb * bb - 4 * aa * cc;

			float x1 = (-bb + (float) Math.sqrt(d)) / (2 * aa);
			float x2 = (-bb - (float) Math.sqrt(d)) / (2 * aa);

			aa = 1;
			bb = -2 * b;
			cc = x1 * x1 - 2 * a * x1 + a * a + b * b - r * r;

			d = bb * bb - 4 * aa * cc;
			float y1 = (-bb + (float) Math.sqrt(d)) / (2 * aa);

			cc = x2 * x2 - 2 * a * x2 + a * a + b * b - r * r;

			d = bb * bb - 4 * aa * cc;
			float y2 = (-bb + (float) Math.sqrt(d)) / (2 * aa);

			return new Result(new Vector2f(x1, y1), new Vector2f(x2, y2));
		}

		public void paint(Graphics g) {
			Graphics2D g2 = (Graphics2D) g;

			super.paint(g2);

			cp1.draw(g2);
			cp2.draw(g2);
			g2.drawLine((int) cp1.position.x, (int) cp1.position.y,	(int) cp2.position.x, (int) cp2.position.y);
			circle.draw(g2);

			Result r = intersectionTest();

			Color c = g2.getColor();
			g2.setColor(Color.RED);
			g2.fillRect((int) r.v1.x - 2, (int) r.v1.y - 2, 4, 4);
			g2.fillRect((int) r.v2.x - 2, (int) r.v2.y - 2, 4, 4);
			g2.setColor(c);
		}
	}

	public static void main(String args[]) {
		final MainFrame frame = new MainFrame();
		frame.setSize(800, 600);
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		SwingUtilities.invokeLater(new Runnable() {
			public void run() {
				frame.setVisible(true);
			}
		});
	}
}

Mathma · 2009-09-25 17:14:33

I found the problem. It forgot to substitute my results into the line equation.

The new code looks like this, I added some comments.

public Result intersectionTest() {

	//p1 and p2 are 2 points on the line
	Vector2f p1 = cp1.position;
	Vector2f p2 = cp2.position;

	Vector2f p = Vector2f.sub(p1, p2);

	float a = circle.position.x;
	float b = circle.position.y;
	float r = circle.radius;

	//the slope of the line
	float m = p.y / p.x; 

	//y-intercept of the line
	float c = p1.y - m * p1.x; 
                
	//subsitute the line equation "y=mx+c" into the circle equation "(x-a)²+(y-b)² = r²" and solve the 3 components of the quadratic equation
	float aa = m*m + 1;
	float bb = -2*a + 2*m*c - 2*m*b;
	float cc = a*a + c*c - 2*b*c + b*b - r*r;

	//calculate the determinant
	float d = bb * bb - 4 * aa * cc;

	//calculate the x values of the 2 intersection points (if they exist)
	float x1 = (-bb + (float) Math.sqrt(d)) / (2*aa);
	float x2 = (-bb - (float) Math.sqrt(d)) / (2*aa);

	//calculate the y values (this is the part I forgot)
	float y1 = m*x1 + c;
	float y2 = m*x2 + c;
			
	return new Result(new Vector2f(x1, y1), new Vector2f(x2, y2));
}

luca-deltodesco · 2009-09-25 22:15:31

Your solution is 'still' very convoluted, with so much unnecessary calculations, There is absolutely no need to test the circle against each 4 edges of the rectangle (Not to mention that your code snippet there will not work for vertical lines, nor is it complete, as it is only intersecting against an infinite line, and not the bounded line segment which a rectangle edge is) And even testing against the 4 edges is not enough if you go down this road, because you then also need to handle the case of the circle being completely within the rectangle.

My solution get's around all of this, to give a very fast, very stable solution, which then also opens the door to calculate the minimum displacement needed to seperate the rectangle and the circle so that they no longer intersect, and also the normal of the collision which would be used to resolve the collision and change the velocities of the circle etc appropriately etc.

Last edited by luca-deltodesco (2009-09-25 22:17:15)

Mathma · 2009-09-26 04:07:37

I wasnt quite awake when I wrote that post explaining the steps apparently, what I meant were rectangle corners not edges.

I already worked out something for edge collision which is working, your solution looks alot more elegant tho so I'll try to implement it.

So what I'm actually having problems with are corner collisions, how would you go about that then?

luca-deltodesco · 2009-09-26 12:40:18

My solution is a complete axis-aligned rectangle, circle intersection method. (It includes corners,edges,containment)

Last edited by luca-deltodesco (2009-09-26 12:40:33)

Math Is Fun Forum

#1 2009-09-25 01:23:00

Circle equation question

#2 2009-09-25 01:39:12

Re: Circle equation question

#3 2009-09-25 03:00:27

Re: Circle equation question

#4 2009-09-25 03:45:54

Re: Circle equation question

#5 2009-09-25 06:04:25

Re: Circle equation question

#6 2009-09-25 17:14:33

Re: Circle equation question

#7 2009-09-25 22:15:31

Re: Circle equation question

#8 2009-09-26 04:07:37

Re: Circle equation question

#9 2009-09-26 12:40:18

Re: Circle equation question

Board footer