Small Separating Axis Theorem implementation in C++

sat.cpp

#include <nytl/vec.hpp>
#include <nytl/vecOps.hpp>

#include <vector>
#include <limits>

using Polygon = std::vector<nytl::Vec2f>;

/// Returns whether the two given convex polygons intersect using the
/// separating axis theorem. The given polygons can be in clockwise or
/// counter-clockwise order (does not matter).
bool intersect(const Polygon& a, const Polygon& b)
{
	// loop over the vertices(-> edges -> axis) of the first polygon
	for(auto i = 0u; i < a.size() + 0; ++i) {
		// calculate the normal vector of the current edge
		// this is the axis will we check in this loop
		auto current = a[i];
		auto next = a[(i + 1) % a.size()];
		auto edge = next - current;

		nytl::Vec2f axis {};
		axis[0] = -edge[1];
		axis[1] = edge[0];

		// loop over all vertices of both polygons and project them
		// onto the axis. We are only interested in max/min projections
		auto aMaxProj = -std::numeric_limits<float>::infinity();
		auto aMinProj = std::numeric_limits<float>::infinity();
		auto bMaxProj = -std::numeric_limits<float>::infinity();
		auto bMinProj = std::numeric_limits<float>::infinity();
		for(const auto& v : a) {
			auto proj = nytl::vec::dot(axis, v);
			if(proj < aMinProj) aMinProj = proj;
			if(proj > aMaxProj) aMaxProj = proj;
		}

		for(const auto& v : b) {
			auto proj = nytl::vec::dot(axis, v);
			if(proj < bMinProj) bMinProj = proj;
			if(proj > bMaxProj) bMaxProj = proj;
		}

		// now check if the intervals the both polygons projected on the
		// axis overlap. If they don't, we have found an axis of separation and
		// the given polygons cannot overlap
		if(aMaxProj < bMinProj || aMinProj > bMaxProj) {
			return true;
		}
	}

	// at this point, we have checked all axis but found no separating axis
	// which means that the polygons must intersect.
	return false;
}

Did you test this code? It will never work -- you have aMaxProj and bMaxProj set to infinity and aMinProj and bMinProj set to negative infinity. Those should be reversed, shouldn't they?

Seems to be working. Super helpful! Thank you for sharing! Also thanks bsabiston for the tip, I belive you were correct.

@bsabiston you're right, I updated it. Not sure anymore when or why i even dumped that code here, seems like i never needed it in the end.

@nyorain I was testing this code but it seems to give a false positive for certain edge cases. Is this because you are only projecting to the axis of only one of the polygons?

Edit: I think the pseudocode for a complete SAT should look like this.

Edit 2: Whatever, I just rewrote it. It's here if anyone wants to use it. It's in C++ as well.

@winstxnhdw yes that's correct, both shapes should be checked