Collision Detection between circle and triangle?

[Composer3]

Hello all,

Is there any (easy) way to implement collision detection between a circle and a triangle in SFML? Or, even better a fast way to implement pixel-perfect collision which could be applied to all sprites/textures?

As a side note, I have seen many different people on many different threads responding to similar questions with some big long code to be copied and pasted in, and my question is, why in the world couldn't these detection algorithms simply be added to SFML, so everyone would not have to re-invent the wheel for every single project? How hard could it be? Rectangle based detection is already a part of SFML, but it is useless in many cases.

[Hapax]

Collision between triangle and circle is quite simple geometry.

First, calculate the lengths between each point on the triangle to the circle's centre.
Second, find which length is shortest.
Third, if this length is greater than the radius of the circle, there is no collision.

[Composer3]

I had thought of this, and I didn't want to do it for a couple of reasons. First, I don't know how to get every point on the triangle. Second, I'm not sure how performant that would be.

I did find a solution that I believe will work. I am currently writing the functions to implement it by checking if each line of the triangle intersects the circle. Obviously, these are line segments, not actual lines, so I also have to check if the bottom of the circle is below the top of the triangle and vise-versa. It's an isosceles triangle with the point facing up. If it were a scalene triangle, I would also have to check if the right side of the circle is to the right of the left side of the triangle and vise-versa.

The formula I found to check this is at this website.


My question now is how do I get the points for the formula? I only need the two diagonal lines b/c of how the game I am making works. So the two points for line one would be the top and bottom right points, and for line two would be the top and bottom left points. I think I would get the top by getting x coordinate of the origin (which should be the top-left corner of the bounding rectangle, right?) and adding half of the width for the x coordinate, and for the y coordinate, it would be just the y coordinate of the origin. Then for the bottom right it would be the x coord of the origin plus the entire width, and the y coord of the origin plus the height. But do I use getGlobalBounds or getLocalBounds, or does it even matter for width and height? Is there a better way to get these points?

Thanks

[Hapax]

How are you representing the triangle if you don't know all three points? The first thing you need to do to check collision with a triangle is know where its points are...

Checking line segments crossing would be the slower way but either way should be fast enough for normal usage.

That said, to be more specific in my previous suggestion:
For each 2D vector from the centre of the circle to a triangle point, square the components and add them (don't need to divide for the length because it's only comparison at this point):

// this is the information you need to know
sf::Vector2f circleCenter; // the position of the centre of the circle
float circleRadius;
sf::Vector2f trianglePoint1;
sf::Vector2f trianglePoint2;
sf::Vector2f trianglePoint3;

// calculate distances
sf::Vector2f offset1 { trianglePoint1 - circleCenter };
sf::Vector2f offset2 { trianglePoint2 - circleCenter };
sf::Vector2f offset3 { trianglePoint3 - circleCenter };
float distanceSquared1 { offset1.x * offset1.x + offset1.y * offset1.y };
float distanceSquared2 { offset2.x * offset2.x + offset2.y * offset2.y };
float distanceSquared3 { offset3.x * offset3.x + offset3.y * offset3.y };
float shortestDistanceSquared { std::min(distanceSquared1, std::min(distanceSquared2, distanceSquared3)) };
float circleRadiusSquared { circleRadius * circleRadius }; // since we are only comparing lengths, we can use their squares. squaring is faster than performing a square root.

// result
bool circleAndTriangleAreColliding { !(shortestDistanceSquared > circleRadiusSquared) };

[Composer3]

Thank you for your reply.

How are you representing the triangle if you don't know all three points? The first thing you need to do to check collision with a triangle is know where its points are...

Checking line segments crossing would be the slower way but either way should be fast enough for normal usage.

I am sorry, I misunderstood your suggestion. I thought you meant every point on the perimiter of the triangle, not the triangle's three points.

The method you are mentioning would work most of the time. However, if the circle was intersecting with one of the triangle's line segments, but not a point, this method would not work. My method checks to see if the line segments intersect the circle. This will always work.

But my question still remains: Do I use getGlobalBounds or getLocalBounds, or does it even matter for width and height?

[Hapax]

However, if the circle was intersecting with one of the triangle's line segments, but not a point, this method would not work.

This is true and if you think this is an expected possibility or problem, you need to use more detailed tests.
One thing to note, though, is you could do the collision test in stages:
test AABB collision (if not colliding, no need for more tests),
the point-radius collision I suggested (if colliding, no need for more tests),
then a more detailed test that tests line segments with a circle.
Since this discounts the most likely scenarios in the simpler tests, it can save a lot on unnecessary, complicated tests and processing time.

I can't quite remember your question about global or local but since you want to compare them at their final positions, global is more likely.
Although, if you want the points of a triangle (or rectangle - I saw your other post) in global space, you can manually transform the local corners using the same transform.

[Composer3]

Thank you for your reply.

test AABB collision (if not colliding, no need for more tests)

What is AABB collision?

One thing to note, though, is you could do the collision test in stages:

I don't think this would be necessary in my case. This would require much more code, and I don't think it would slow my program down enough to be a problem for my program.

[Hapax]

AABB = Axis-Aligned Boundary Box

So, AABB would be just checking their boundary boxes to see if they overlap.
An AABB is what sf::FloatRect represents when returned from getGlobalBounds().
With SFML shapes, you'd basically be doing this:

object1.getGlobalBounds().intersects(object2.getGlobalBounds())

So, the stages I mentioned would be:

bool isObject1CollidingWithObject2{ false };
if (object1.getGlobalBounds().intersects(object2.getGlobalBounds()))
{
    if (testSimpleCollision(object1, object2)) // the method that I suggested above
        isObject1CollidingWithObject2 = true; // definitely colliding. no need for even slower, accurate method
    else
        isObject1CollidingWithObject2 = testAccurateCollision(object1, object2); // the accurate method that tests for crossing lines
}
// if the global bounds don't interset, there could not have been any collision due to their boundary boxes not being anywhere near. this skips both the other - slower - collision steps since they are not needed.

Slot in the code I posted above for "simple collision" - or something similar - and all you need to do is implement the line-crossing method, as you were going to anyway. No more work for you and it skips the slower and more computationally intensive tests unless absolutely necessary.

[Composer3]

Ok, I may use AABB collision too, but not all three (AABB, point-radius, and line segments), as you said before, because point-radius collision, while fairly simple and easy to understand, does not come out of the box with sfml, and therefore would need more code than I would consider worth the performance boost.

[Composer3]

I'm back again. 

I have implemented the AABB and line segments intersection methods. Obviously, the AABB collision is working, but the line segments method is giving me trouble. Here's my code:

Spaceship.h (the spaceship is the triangle):

#include <SFML\Graphics.hpp>
#include <vector>

class Spaceship : public sf::Sprite {
  public:
    Spaceship();
    float getDistanceToCircleOrigin(sf::CircleShape &circle, float x1, float y1, float x2, float y2);
    bool intersectsCircle(sf::CircleShape &circle);

    int speedX = 0;
    int speedY = 0;
  private:
    sf::Texture _texture;
};
 

Spaceship.cpp:

#include "Spaceship.h"

Spaceship::Spaceship() {
        _texture.loadFromFile("images\\spaceship.png");
        _texture.setSmooth(true);
        setTexture(_texture);

        setPosition(720 / 2 + getGlobalBounds().width / 2,
                                680 - getGlobalBounds().height);
}

float Spaceship::getDistanceToCircleOrigin(sf::CircleShape &circle, float x1, float y1, float x2, float y2) {
        float distance = abs((y2 - y1) * circle.getOrigin().x - (x2 - x1) * circle.getOrigin().y + x2 * y1 - y2 * x1) / sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
        return distance;
}

bool Spaceship::intersectsCircle(sf::CircleShape &circle) {
        if (getGlobalBounds().intersects(circle.getGlobalBounds())) {

                float distance = getDistanceToCircleOrigin(
                        circle, getOrigin().x + getGlobalBounds().width / 2, getOrigin().y,
                        getOrigin().x + getGlobalBounds().width,
                        getOrigin().y + getGlobalBounds().height);

                if (distance <= circle.getRadius())
                        return true;
        }
        return false;
}

 

Asteroid.h (the asteroid is the circle):

#include <SFML\Graphics.hpp>

class Asteroid : public sf::Sprite {
  public:
    Asteroid();
        sf::CircleShape circle;

        void move(float x, float y);

  private:
    sf::Texture _texture;
};

 

Asteroid.cpp:

#include "Asteroid.h"
#include <iostream>

Asteroid::Asteroid() {
        _texture.loadFromFile("C:\\Users\\_____\\OneDrive\\Documents\\C++\\SFML_Asteroids\\images\\asteroid2.png");
        setTexture(_texture);
        setOrigin(getGlobalBounds().width / 2, getGlobalBounds().height / 2);
        setPosition(720 / 2, 680 / 2);
        circle.setRadius(150 / 2);
        circle.setOrigin(circle.getRadius(), circle.getRadius());
        circle.setPosition(720 / 2, 680 / 2);
}

void Asteroid::move(float x, float y) {
        circle.move(x, y);
        sf::Sprite::move(x, y);
}
 

main.cpp:

#include "main.h"

using namespace std;

void initialize() {
        window.create(sf::VideoMode(WIDTH, HEIGHT, 32), "Asteroids");
        window.setKeyRepeatEnabled(false);
}

void input(sf::Event &event) {
        while (window.pollEvent(event)) {
                switch (event.type) {

                        case sf::Event::Closed: {
                                window.close();
                                break;
                        }

                        default:
                                break;
                }
        }

        upPressed = sf::Keyboard::isKeyPressed(sf::Keyboard::Up);
        downPressed = sf::Keyboard::isKeyPressed(sf::Keyboard::Down);
        leftPressed = sf::Keyboard::isKeyPressed(sf::Keyboard::Left);
        rightPressed = sf::Keyboard::isKeyPressed(sf::Keyboard::Right);

        bounds = spaceship.getGlobalBounds();

        if (upPressed && bounds.top > 0) {
                spaceship.move(0, -5);
        }

        if (downPressed && bounds.top + bounds.height < HEIGHT) {
                spaceship.move(0, 5);
        }

        if (leftPressed && bounds.left > 0) {
                spaceship.move(-5, 0);
        }

        if (rightPressed && bounds.left + bounds.width < WIDTH) {
                spaceship.move(5, 0);
        }
}

void update() {
        asteroid.move(0, 1);
}

bool checkForCollisions() {
        return spaceship.intersectsCircle(asteroid.circle);
}

void render() {
        window.clear();

        sf::RectangleShape srect(sf::Vector2f(spaceship.getGlobalBounds().width, spaceship.getGlobalBounds().height));
        srect.setPosition(spaceship.getPosition());
        window.draw(srect);
        window.draw(spaceship);
        window.draw(asteroid.circle);
        window.draw(asteroid);

        window.display();
}

int main() {
        initialize();

        sf::Event event;
        while (window.isOpen()) {
                input(event);
                update();
                if (checkForCollisions())
                        cout << "intersects!" << endl;
                render();

                sf::sleep(sf::milliseconds(10));
        }

        return 0;
}

 

Note: I have a white rectangle behind the spaceship and have filled in the asteroid's circle with white so I can visualize the collisions.

The problem is, the line segment method doesn't seem to be working at all. I get the same results if I comment out the if (distance <= circle.getRadius()). Any ideas?

[Composer3]

Never mind, I figured it out. One problem was that I was using getOrigin instead of getPosition. Also, after I changed that I was still getting false positives because it would still sometimes cross one of the lines when just the corners of the bounding rectangles intersected. I fixed that by making sure it only crossed the right line segment when the spaceship was on the left of the circle, and vice-versa. Also, I did have to use the point-radius collision for the top point of the triangle because of this. Here's my changed code for anyone who's interested:

#include "Spaceship.h"
#include <iostream>

Spaceship::Spaceship() {
        _texture.loadFromFile("images\\spaceship.png");
        _texture.setSmooth(true);
        setTexture(_texture);

        setPosition(720 / 2 + getGlobalBounds().width / 2, 680 - getGlobalBounds().height);
}

bool Spaceship::pointRadius(sf::CircleShape &circle, float x1, float y1) {
        float x2 = circle.getPosition().x;
        float y2 = circle.getPosition().y;

        float distance = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

        return distance < circle.getRadius();
}

float Spaceship::getDistanceToCircleOrigin(sf::CircleShape &circle, float x1, float y1, float x2, float y2) {
        float distance = abs((y2 - y1) * (circle.getPosition().x) - (x2 - x1) * (circle.getPosition().y) + x2 * y1 - y2 * x1) / sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
        return distance;
}

bool Spaceship::intersectsCircle(sf::CircleShape &circle) {
        if (getGlobalBounds().intersects(circle.getGlobalBounds())) {

                if (pointRadius(circle, getPosition().x + getGlobalBounds().width / 2, getPosition().y)) {
                        return true;
                }

                float distance = getDistanceToCircleOrigin(
                        circle,
                        getPosition().x + getGlobalBounds().width / 2,
                        getPosition().y,
                        getPosition().x + getGlobalBounds().width,
                        getPosition().y + getGlobalBounds().height
                );

                float distance2 = getDistanceToCircleOrigin(
                        circle, getPosition().x + getGlobalBounds().width / 2,
                        getPosition().y,
                        getPosition().x,
                        getPosition().y + getGlobalBounds().height);

                float radius = circle.getRadius();
                if (distance <= radius && distance2 > radius && getPosition().x < circle.getPosition().x - circle.getGlobalBounds().width / 2) {

                        return true;
                }

                if (distance2 <= radius && distance > radius && getPosition().x + getGlobalBounds().width > circle.getPosition().x + circle.getGlobalBounds().width / 2) {

                        return true;
                }
        }
        return false;
}

 

[Hapax]

Remember that your spaceship is not a sprite so probably shouldn't inherit from it. Your spaceship has a sprite (or should do) so the sprite could be stored inside the sprite class. This also would help with your functions as they can be much clearer since you no longer have to pass the sprite since it knows which sprite to use (the only one it has).

In the other direction, it's usually a bad idea to store textures directly inside entities, such as your spaceship class. Another approach would be to store the textures (large resources) outside individual classes and store them all together in one "resource manager" (or just a single struct/class that doesn't change). Then, when setting up your spaceship's sprite (that's now inside your class), just pass the texture to the class and set the sprite's texture, never having to change it again or referencing the texture!

All that said, this is just stuff that is best to do every time when you get used to it. Not doing this doesn't necessarily stop the game from working so as long as you're having fun, do whatever you need to. It's worth noting, though, that things like this may cause problems down the line that can be difficult to track down, depending on the size of project, this could be all but impossible so starting with a solid and safe base can really help.