2d-separating-axis-theorem

This repository contains a simple C++ implementation of a 2D separating axis algorithm. The algorithm does not compute the Minimum Translation Vector (MTV) as it is not within my use case. For more information, read here.

Warning: The comparing polygons must have an equal number of vertices. This does not necessarily have to be the case but I didn't have time to write that feature.

:param bounds_a:            (vector<x, y>) vertices of polygon A
:param bounds_b:            (vector<x, y>) vertices of polygon B

:return isIntersecting:     (bool) true if the two polygons are intersecting

Test

g++ main.cpp
./a.out

Example

The following snippet is an example used in actual production.

for (size_t j = 0; j < static_obstacles_set.size(); j++) {
    const std::vector<Vector2> static_obstacle = {
        static_obstacles_set[j].points[0],
        static_obstacles_set[j].points[1],
        static_obstacles_set[j].points[2],
        static_obstacles_set[j].points[3]
    };

    const bool isIntersecting = separating_axis_intersect(vehicle_bounds, static_obstacle);

    if (intersects) {
        path.is_blocked = true;
        path.is_static_obstacle = true;
    }
}