A demo app showing how to compute tightest possible oriented bounding box of a 2D polygon

poly_obb.odin

// A demo app showing how to compute tightest possible oriented bounding box/rectangle of a convex polygon.
// The order of edges matters, so the points should be in order. In case of convex polygons you can just radially sort them.
//
// By Jakub Tomšů
package poly_obb_demo

import "core:fmt"
import "core:math/linalg"
import rl "vendor:raylib"

// Note: it's easily possible for the user to add points that don't make a convex polygon, are in wrong order etc.
points: [dynamic][2]f32
dragged_offset: [2]f32
dragged_index: int = -1
draw_step_basis: bool
draw_step_obb: bool

COLOR_BG :: rl.Color{10, 12, 20, 255}
COLOR_POLY :: rl.Color{35, 45, 60, 255}

OBB2 :: struct {
    min:    [2]f32,
    max:    [2]f32,
    mat:    matrix[2, 2]f32, // must be orthonormalized
}

obb_area :: proc(obb: OBB2) -> f32 {
    return (obb.max.x - obb.min.x) * (obb.max.y - obb.min.y) // can be computed in local space
}

obb_draw :: proc(obb: OBB2, color: rl.Color) {
    corners := [4][2]f32 {
        obb.mat * [2]f32{obb.min.x, obb.min.y},
        obb.mat * [2]f32{obb.max.x, obb.max.y},
        obb.mat * [2]f32{obb.min.x, obb.max.y},
        obb.mat * [2]f32{obb.max.x, obb.min.y},
    }

    for corner in corners {
        rl.DrawCircleV(corner, 3, color)
    }

    rl.DrawLineEx(corners[0], corners[2], 2, color)
    rl.DrawLineEx(corners[0], corners[3], 2, color)
    rl.DrawLineEx(corners[1], corners[2], 2, color)
    rl.DrawLineEx(corners[1], corners[3], 2, color)
}

poly_find_best_obb :: proc(points: [][2]f32) -> (result: OBB2) {
    if len(points) <= 1 {
        return {}
    }

    min_area: f32 = max(f32)

    // brute force all edge vectors as the basis. This is reasonable in 2D
    p0 := points[len(points) - 1]
    for p1 in points[:] {
        defer p0 = p1

        basis: matrix[2, 2]f32
        dir := linalg.normalize0(p1 - p0)
        basis[0] = dir
        basis[1] = {-dir.y, dir.x} // rotate 90 degrees

        if draw_step_basis {
            rl.DrawLineEx(p0, p0 + basis[0] * 30, 4, rl.RED)
            rl.DrawLineEx(p0, p0 + basis[1] * 30, 4, rl.GREEN)
        }

        obb := poly_obb_from_basis(points, basis)

        if draw_step_obb {
            obb_draw(obb, {50, 200, 150, 50})
        }

        area := obb_area(obb)
        if area < min_area {
            min_area = area
            result = obb
        }
    }

    return result
}

poly_obb_from_basis :: proc(points: [][2]f32, basis: matrix[2, 2]f32) -> (result: OBB2) {
    result.mat = basis

    result.min = max(f32)
    result.max = min(f32)

    for p in points {
        local_p := [2]f32{
            linalg.dot(result.mat[0], p),
            linalg.dot(result.mat[1], p),
        }

        result.min = linalg.min(result.min, local_p)
        result.max = linalg.max(result.max, local_p)
    }

    return result
}


//
// App
//

main :: proc() {
    rl.SetConfigFlags({.MSAA_4X_HINT, .VSYNC_HINT})
    rl.InitWindow(1400, 900, "Rect OBB")
    defer rl.CloseWindow()

    for !rl.WindowShouldClose() {
        rl.BeginDrawing()
        defer rl.EndDrawing()

        rl.ClearBackground(COLOR_BG)

        mouse := rl.GetMousePosition()

        if rl.IsMouseButtonPressed(.RIGHT) {
            append(&points, mouse)
        }

        closest_index := -1
        closest_dist: f32 = 100
        if dragged_index == -1 {
            for p, i in points {
                d := linalg.distance(p, mouse)
                if d < closest_dist {
                    closest_dist = d
                    closest_index = i
                }
            }
        }

        if closest_index != -1 && rl.IsMouseButtonPressed(.LEFT) {
            dragged_index = closest_index
            dragged_offset = points[dragged_index] - mouse
            closest_index = -1
        }

        if rl.IsKeyPressed(.TAB) {
            clear(&points)
        }

        if rl.IsKeyPressed(.B) do draw_step_basis = !draw_step_basis
        if rl.IsKeyPressed(.N) do draw_step_obb = !draw_step_obb

        if rl.IsMouseButtonReleased(.LEFT) {
            dragged_index = -1
        }

        if dragged_index != -1 {
            points[dragged_index] = dragged_offset + mouse
        }

        // HACK lmao
        for p0, i0 in points[:] {
            for p1, i1 in points[:] {
                if i1 == i0 do continue
                for p2, i2 in points[:] {
                    if i0 == i2 do continue
                    if i1 == i2 do continue
                    rl.DrawTriangle(p0, p1, p2, COLOR_POLY)
                }
            }
        }

        if len(points) > 1 {
            p0 := points[len(points) - 1]
            for p1, i in points {
                rl.DrawLineEx(p0, p1, 1.5, {45, 60, 90, 255})
                p0 = p1
            }
        }

        for p, i in points {
            color := rl.Color{100, 110, 150, 255}
            rad: f32 = 7

            if i == closest_index {
                rad += 2
                color = {150, 180, 240, 255}
            }

            if i == dragged_index {
                rad += 4
                color = {200, 200, 255, 255}
            }

            rl.DrawCircleV(p, 16, COLOR_BG)
            rl.DrawCircleV(p, rad, color)
            rl.DrawTextEx(rl.GetFontDefault(), fmt.ctprint(i), p - {2, 4}, 10, 0, rl.BLACK)
        }

        obb := poly_find_best_obb(points[:])

        corners := [4][2]f32 {
            obb.mat * [2]f32{obb.min.x, obb.min.y},
            obb.mat * [2]f32{obb.max.x, obb.max.y},
            obb.mat * [2]f32{obb.min.x, obb.max.y},
            obb.mat * [2]f32{obb.max.x, obb.min.y},
        }

        obb_draw(obb, {180, 255, 220, 200})

        mid: [2]f32
        for p in corners {
            mid += p * 0.25
        }

        rl.DrawLineEx(mid, mid + obb.mat[0] * 50, 3, rl.RED)
        rl.DrawLineEx(mid, mid + obb.mat[1] * 50, 3, rl.GREEN)
        rl.DrawCircleV(mid, 4, rl.BLUE)

        rl.DrawText(fmt.ctprintf("Area: %.0f", obb_area(obb) * 0.01), 4, 4, 20, rl.WHITE)
    }
}