Check if a polygon overlaps with a rectangle

Check if a polygon overlaps with a rectangle
You are encouraged to solve this task according to the task description, using any language you may know.

Self-explanatory: given a polygon (as an array/vector/list of its vertices) and a rectangle (in x, y, width, height format), check if they intersect.

Related tasks

• Determine if two triangles overlap
• Check if two polygons overlap

C

Translation of: Wren

#include <stdio.h>
#include <stdbool.h>

typedef struct {
    double x;
    double y;
} Vector2;

typedef struct {
    double min;
    double max;
} Projection;

typedef struct {
    double x;
    double y;
    double w;
    double h;
} Rectangle;

double dot(Vector2 v1, Vector2 v2) {
    return v1.x * v2.x + v1.y * v2.y;
}

/* In the following a polygon is represented as an array of vertices
   and a vertex by a pair of x, y coordinates in the plane. */

void getAxes(double poly[][2], size_t len, Vector2 axes[len]) {
    int i, j;
    Vector2 vector1, vector2, edge;
    for (i = 0; i < len; ++i) {
        vector1 = (Vector2){poly[i][0], poly[i][1]};
        j = (i + 1 == len) ? 0 : i + 1;
        vector2 = (Vector2){poly[j][0], poly[j][1]};
        edge = (Vector2){vector1.x - vector2.x, vector1.y - vector2.y};
        axes[i].x = -edge.y;
        axes[i].y = edge.x;
    }
}

Projection projectOntoAxis(double poly[][2], size_t len, Vector2 axis) {
    int i;
    Vector2 vector0, vector;
    double min, max, p;
    vector0 = (Vector2){poly[0][0], poly[0][1]};
    min = dot(axis, vector0);
    max = min;
    for (i = 1; i < len; ++i) {
        vector = (Vector2){poly[i][0], poly[i][1]};
        p = dot(axis, vector);
        if (p < min) {
            min = p;
        } else if (p > max) {
            max = p;
        }
    }
    return (Projection){min, max};
}

bool projectionsOverlap(Projection proj1, Projection proj2) {
    if (proj1.max < proj2.min) return false;
    if (proj2.max < proj1.min) return false;
    return true;
}

void rectToPolygon(Rectangle r, double poly[4][2]) {
    poly[0][0] = r.x;       poly[0][1] = r.y;
    poly[1][0] = r.x;       poly[1][1] = r.y + r.h;
    poly[2][0] = r.x + r.w; poly[2][1] = r.y + r.h;
    poly[3][0] = r.x + r.w; poly[3][1] = r.y;
}

bool polygonOverlapsRect(double poly1[][2], size_t len1, Rectangle rect) {
    int i;
    size_t len2 = 4;
    Vector2 axis, axes1[len1], axes2[len2];
    Projection proj1, proj2;
    /* Convert 'rect' struct into polygon form. */
    double poly2[len2][2];
    rectToPolygon(rect, poly2);
    getAxes(poly1, len1, axes1);
    getAxes(poly2, len2, axes2);
    for (i = 0; i < len1; ++i) {
        axis = axes1[i];
        proj1 = projectOntoAxis(poly1, len1, axis);
        proj2 = projectOntoAxis(poly2, len2, axis);
        if (!projectionsOverlap(proj1, proj2)) return false;
    }
    for (i = 0; i < len2; ++i) {
        axis = axes2[i];
        proj1 = projectOntoAxis(poly1, len1, axis);
        proj2 = projectOntoAxis(poly2, len2, axis);
        if (!projectionsOverlap(proj1, proj2)) return false;
    }
    return true;
}

void printPoly(double poly[][2], size_t len) {
    int i, j;
    printf("{ ");
    for (i = 0; i < len; ++i) {
        printf("{");
        for (j = 0; j < 2; ++j) {
            printf("%g", poly[i][j]);
            if (j == 0) printf(", ");
        }
        printf("}");
        if (i < len-1) printf(", ");
    }
    printf(" }\n");
}

int main() {
    double poly[][2] = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} };
    double poly2[4][2];
    Rectangle rect1 = {4, 0, 2, 2};
    Rectangle rect2 = {1, 0, 8, 2};
    printf("poly  = ");
    printPoly(poly, 5);
    printf("rect1 = {%g, %g, %g, %g} => ", rect1.x, rect1.y, rect1.w, rect1.h);
    rectToPolygon(rect1, poly2);
    printPoly(poly2, 4);
    printf("rect2 = {%g, %g, %g, %g} => ", rect2.x, rect2.y, rect2.w, rect2.h);
    rectToPolygon(rect2, poly2);
    printPoly(poly2, 4);
    printf("\n");
    printf("poly and rect1 overlap? %s\n", polygonOverlapsRect(poly, 5, rect1) ? "true" : "false");
    printf("poly and rect2 overlap? %s\n", polygonOverlapsRect(poly, 5, rect2) ? "true" : "false");
    return 0;
}

Output:

poly  = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} }
rect1 = {4, 0, 2, 2} => { {4, 0}, {4, 2}, {6, 2}, {6, 0} }
rect2 = {1, 0, 8, 2} => { {1, 0}, {1, 2}, {9, 2}, {9, 0} }

poly and rect1 overlap? false
poly and rect2 overlap? true

Go

Translation of: Wren

package main

import "fmt"

type Vector2 struct {
    x, y float64
}

type Projection struct {
    min, max float64
}

type Rectangle struct {
    x, y, w, h float64
}

func (v Vector2) dot(other Vector2) float64 {
    return v.x*other.x + v.y*other.y
}

/* In the following a polygon is represented as a slice of vertices
   and a vertex by a pair of x, y coordinates in the plane. */

func getAxes(poly [][2]float64) []Vector2 {
    axes := make([]Vector2, len(poly))
    for i := 0; i < len(poly); i++ {
        vertex1 := poly[i]
        j := i + 1
        if i+1 == len(poly) {
            j = 0
        }
        vertex2 := poly[j]
        vector1 := Vector2{vertex1[0], vertex1[1]}
        vector2 := Vector2{vertex2[0], vertex2[1]}
        edge := Vector2{vector1.x - vector2.x, vector1.y - vector2.y}
        axes[i] = Vector2{-edge.y, edge.x}
    }
    return axes
}

func projectOntoAxis(poly [][2]float64, axis Vector2) Projection {
    vertex0 := poly[0]
    vector0 := Vector2{vertex0[0], vertex0[1]}
    min := axis.dot(vector0)
    max := min
    for i := 1; i < len(poly); i++ {
        vertex := poly[i]
        vector := Vector2{vertex[0], vertex[1]}
        p := axis.dot(vector)
        if p < min {
            min = p
        } else if p > max {
            max = p
        }
    }
    return Projection{min, max}
}

func projectionsOverlap(proj1, proj2 Projection) bool {
    if proj1.max < proj2.min {
        return false
    }
    if proj2.max < proj1.min {
        return false
    }
    return true
}

func rectToPolygon(r Rectangle) [][2]float64 {
    return [][2]float64{{r.x, r.y}, {r.x, r.y + r.h}, {r.x + r.w, r.y + r.h}, {r.x + r.w, r.y}}
}

func polygonOverlapsRect(poly1 [][2]float64, rect Rectangle) bool {
    // Convert 'rect' struct into polygon form.
    poly2 := rectToPolygon(rect)
    axes1 := getAxes(poly1)
    axes2 := getAxes(poly2)
    for _, axes := range [][]Vector2{axes1, axes2} {
        for _, axis := range axes {
            proj1 := projectOntoAxis(poly1, axis)
            proj2 := projectOntoAxis(poly2, axis)
            if !projectionsOverlap(proj1, proj2) {
                return false
            }
        }
    }
    return true
}

func main() {
    poly := [][2]float64{{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}
    rect1 := Rectangle{4, 0, 2, 2}
    rect2 := Rectangle{1, 0, 8, 2}
    fmt.Println("poly  = ", poly)
    fmt.Println("rect1 = ", rect1, " => ", rectToPolygon(rect1))
    fmt.Println("rect2 = ", rect2, " => ", rectToPolygon(rect2))
    fmt.Println()
    fmt.Println("poly and rect1 overlap?", polygonOverlapsRect(poly, rect1))
    fmt.Println("poly and rect2 overlap?", polygonOverlapsRect(poly, rect2))
}

Output:

poly  =  [[0 0] [0 2] [1 4] [2 2] [2 0]]
rect1 =  {4 0 2 2}  =>  [[4 0] [4 2] [6 2] [6 0]]
rect2 =  {1 0 8 2}  =>  [[1 0] [1 2] [9 2] [9 0]]

poly and rect1 overlap? false
poly and rect2 overlap? true

jq

Works with: jq

Also works with gojq, the Go implementation of jq

This entry uses the same strategy and the same functions as in Check_if_two_polygons_overlap#jq, and so the code is not repeated here.

The twist here is that we provide a function that allows rectangles to be specified by three vertices.

def addVector($B): [ .[0] + $B[0], .[1] + $B[1]];

def isPerpTo($other): dot($other) == 0;

# Input should be three points [A,B,C] where AB is perpendicular to BC
def rectangleToPolygon:
  . as [$A, $B, $C]
  # check perpendicularity
  | if ([$A,$B] | AB | isPerpTo( [$B,$C] | AB)) then .
    else "rectangleToPolygon: AB is not perpendicular to BC" | error
    end
  | . + [$A | addVector( [$B,$C]|AB ) ] ;
  
def poly1: [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]];

def rect1: [ [4, 0], [4, 2], [6, 2] ];
def rect2: [ [1, 0], [1, 2], [9, 2] ];

def task:
  ([rect1, rect2] | map(rectangleToPolygon)) as [$r1, $r2]
  | "poly1 = \(poly1)",
    "r1 = \($r1)",
    "r2 = \($r2)",
     "",
    "poly1 and r1 overlap? \(polygonsOverlap(poly1; $r1))",
    "poly1 and r2 overlap? \(polygonsOverlap(poly1; $r2))"
  ;

task

Output:

poly1 = [[0,0],[0,2],[1,4],[2,2],[2,0]]
r1 = [[4,0],[4,2],[6,2],[6,0]]
r2 = [[1,0],[1,2],[9,2],[9,0]]

poly1 and r1 overlap? false
poly1 and r2 overlap? true

Nim

Translation of: Wren

Translation of: Go

type
  Vector2 = (float, float)
  Projection = tuple[min, max: float]
  Polygon = seq[Vector2]
  Rectangle = tuple[x, y, w, h: float]

func dot(v1, v2: Vector2): float =
  v1[0] * v2[0] + v1[1] * v2[1]

func axes(poly: Polygon): seq[Vector2] =
  result.setLen(poly.len)
  for i, vertex1 in poly:
    let vertex2 = poly[if i + 1 == poly.len: 0 else: i + 1]
    let edge = (vertex1[0] - vertex2[0], vertex1[1] - vertex2[1])
    result[i] = (-edge[1], edge[0])

func projectionOnAxis(poly: Polygon; axis: Vector2): Projection =
  result.min = Inf
  result.max = -Inf
  for vertex in poly:
    let p = axis.dot(vertex)
    if p < result.min:
      result.min = p
    if p > result.max:
      result.max = p

func projectionOverlaps(proj1, proj2: Projection): bool =
  if proj1.max < proj2.min: return false
  if proj2.max < proj1.min: return false
  result = true

func toPolygon(r: Rectangle): Polygon =
  @[(r.x, r.y), (r.x, r.y + r.h), (r.x + r.w, r.y + r.h), (r.x + r.w, r.y)]

func polygonOverlapsRect(poly1: Polygon; rect: Rectangle): bool =
  let poly2 = rect.toPolygon
  for axes in [poly1.axes, poly2.axes]:
    for axis in axes:
      let proj1 = poly1.projectionOnAxis(axis)
      let proj2 = poly2.projectionOnAxis(axis)
      if not projectionOverlaps(proj1, proj2):
        return false
  result = true

let poly = @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
let rect1 = (4.0, 0.0, 2.0, 2.0)
let rect2 = (1.0, 0.0, 8.0, 2.0)

echo "poly n= ", poly
echo "rect1 = ", rect1, " → ", rect1.toPolygon
echo "rect2 = ", rect2, " → ", rect2.toPolygon
echo()
echo "poly and rect1 overlap? ", polygonOverlapsRect(poly, rect1)
echo "poly and rect2 overlap? ", polygonOverlapsRect(poly, rect2)

Output:

poly n= @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
rect1 = (4.0, 0.0, 2.0, 2.0) → @[(4.0, 0.0), (4.0, 2.0), (6.0, 2.0), (6.0, 0.0)]
rect2 = (1.0, 0.0, 8.0, 2.0) → @[(1.0, 0.0), (1.0, 2.0), (9.0, 2.0), (9.0, 0.0)]

poly and rect1 overlap? false
poly and rect2 overlap? true

Phix

Translation of: Wren

with javascript_semantics
function getAxes(sequence poly)
    integer l = length(poly)
    sequence axes = repeat(0,l)
    for i=1 to l do
        sequence p = poly[i], n = poly[iff(i=l?1:i+1)]
        axes[i] = {n[2]-p[2],p[1]-n[1]} -- ie {-y,x}
    end for
    return axes
end function

function projectOntoAxis(sequence poly,axis)
    atom {ax,ay} = axis
    sequence p = repeat(0,length(poly))
    for i,pi in poly do
        atom {px,py} = pi
        p[i] = ax*px+ay*py
    end for
    return {min(p),max(p)}
end function

function projectionsOverlap(sequence proj1, proj2)
    atom {min1,max1} = proj1, 
         {min2,max2} = proj2
    return max1>=min2 and max2>=min1
end function

function rectToPolygon(sequence r)
    atom {x,y,w,h} = r
    return {{x, y}, {x, y+h}, {x+w, y+h}, {x+w, y}}
end function

function polygonOverlapsRect(sequence poly1, rect)
    sequence poly2 = rectToPolygon(rect),
             axes1 = getAxes(poly1),
             axes2 = getAxes(poly2)
    for axes in {axes1, axes2} do
        for axis in axes do
            sequence proj1 = projectOntoAxis(poly1, axis),
                     proj2 = projectOntoAxis(poly2, axis)
            if not projectionsOverlap(proj1, proj2) then return false end if
        end for
    end for
    return true
end function

constant poly = {{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}},
         rect1 = {4, 0, 2, 2},
         rect2 = {1, 0, 8, 2},
fmt = """
poly = %v
rect2 = %v => %v
rect3 = %v => %v

poly and rect1 overlap? %t
poly and rect2 overlap? %t
"""
printf(1,fmt,{poly,rect1,rectToPolygon(rect1),
                   rect2,rectToPolygon(rect2),
              polygonOverlapsRect(poly, rect1),
              polygonOverlapsRect(poly, rect2)})

Output:

poly = {{0,0},{0,2},{1,4},{2,2},{2,0}}
rect2 = {4,0,2,2} => {{4,0},{4,2},{6,2},{6,0}}
rect3 = {1,0,8,2} => {{1,0},{1,2},{9,2},{9,0}}

poly and rect1 overlap? false
poly and rect2 overlap? true

Wren

Library: Wren-vector

Library: Wren-dynamic

This is just a special case of the Check if two polygons overlap task where one of the polygons is a rectangle though, for convenience, the common code is repeated here.

import "./vector" for Vector2
import "./dynamic" for Tuple

var Projection = Tuple.create("Projection", ["min", "max"])
var Rectangle = Tuple.create("Rectangle", ["x", "y", "w", "h"])

/* In the following a polygon is represented as a list of vertices
   and a vertex by a pair of x, y coordinates in the plane. */

var getAxes = Fn.new { |poly|
    var axes = List.filled(poly.count, null)
    for (i in 0...poly.count) {
        var vertex1 = poly[i]
        var vertex2 = poly[(i+1 == poly.count) ? 0 : i+1]
        var vector1 = Vector2.new(vertex1[0], vertex1[1])
        var vector2 = Vector2.new(vertex2[0], vertex2[1])
        var edge = vector1 - vector2
        axes[i] = edge.perp
    }
    return axes
}

var projectOntoAxis = Fn.new { |poly, axis|
    var vertex0 = poly[0]
    var vector0 = Vector2.new(vertex0[0], vertex0[1])
    var min = axis.dot(vector0)
    var max = min
    for (i in 1...poly.count) {
        var vertex = poly[i]
        var vector = Vector2.new(vertex[0], vertex[1])
        var p = axis.dot(vector)
        if (p < min) {
            min = p
        } else if (p > max) {
            max = p
        }
    }
    return Projection.new(min, max)
}

var projectionsOverlap = Fn.new { |proj1, proj2|
    if (proj1.max < proj2.min) return false
    if (proj2.max < proj1.min) return false
    return true
}

var rectToPolygon = Fn.new { |r|
    return [[r.x, r.y], [r.x, r.y + r.h], [r.x + r.w, r.y + r.h], [r.x + r.w, r.y]]
}

var polygonOverlapsRect = Fn.new { |poly1, rect|
    // Convert 'rect' object into polygon form.
    var poly2 = rectToPolygon.call(rect)
    var axes1 = getAxes.call(poly1)
    var axes2 = getAxes.call(poly2)
    for (axes in [axes1, axes2]) {
        for (axis in axes) {
            var proj1 = projectOntoAxis.call(poly1, axis)
            var proj2 = projectOntoAxis.call(poly2, axis)
            if (!projectionsOverlap.call(proj1, proj2)) return false
        }
    }
    return true
}

var poly  = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]]
var rect1 = Rectangle.new(4, 0, 2, 2)
var rect2 = Rectangle.new(1, 0, 8, 2)
System.print("poly  = %(poly)")
System.print("rect1 = %(rect1) => %(rectToPolygon.call(rect1))")
System.print("rect2 = %(rect2) => %(rectToPolygon.call(rect2))")
System.print()
System.print("poly and rect1 overlap? %(polygonOverlapsRect.call(poly, rect1))") 
System.print("poly and rect2 overlap? %(polygonOverlapsRect.call(poly, rect2))")

Output:

poly  = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]]
rect1 = (4, 0, 2, 2) => [[4, 0], [4, 2], [6, 2], [6, 0]]
rect2 = (1, 0, 8, 2) => [[1, 0], [1, 2], [9, 2], [9, 0]]

poly and rect1 overlap? false
poly and rect2 overlap? true