Check if a polygon overlaps with a rectangle: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Julia}}: specify return types)
m (→‎{{header|Wren}}: Changed to Wren S/H)
Line 738: Line 738:
{{libheader|Wren-dynamic}}
{{libheader|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.
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.
<syntaxhighlight lang="ecmascript">import "./vector" for Vector2
<syntaxhighlight lang="wren">import "./vector" for Vector2
import "./dynamic" for Tuple
import "./dynamic" for Tuple


Revision as of 10:43, 17 November 2023

Task
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





ALGOL 68

Basically the same as the Algol 68 sample for the Check if two polygons overlap task, with added rectangle handling (as in the Go, Wren, etc. samples) and using the same test cases as the Wren and other samples. The Algol 68 Check if two polygons overlap sample was based on that task's Go sample. 

BEGIN # test whether a 2D polygon overlaps a rectangle                       #
      # - based on a translation Go which is a translation of Wren           #

    # In the following a polygon is represented as a row of vertices         #
    # and a vertex ( POINT ) by a pair of x, y coordinates in the plane      #

    # most of this is verbatim from the check if two polygons overlap task   #

    MODE POINT      = STRUCT( REAL x,   y   );
    MODE PROJECTION = STRUCT( REAL min, max );
    MODE POLYGON    = FLEX[ 1 : 0 ]POINT;

    PRIO DOT = 3;
    OP   DOT = ( POINT v, other )REAL:
         ( x OF v * x OF other ) + ( y OF v * y OF other );

    # returns the axes of the polygon defined by poly                        #
    OP  AXES = ( POLYGON poly )[]POINT:
        BEGIN
            [ LWB poly : UPB poly ]POINT result;
            FOR i FROM LWB poly TO UPB poly DO
                INT j = IF i = UPB poly THEN LWB poly ELSE i + 1 FI;
                POINT vertex1 = poly[ i ];
                POINT vertex2 = poly[ j ];
                POINT edge    = ( x OF vertex1 - x OF vertex2, y OF vertex1 - y OF vertex2 );
                result[ i ]  := ( - y OF edge, x OF edge )
            OD;
            result
         END # AXES # ;

    # returns the projection of poly onto axis                               #
    PRIO PROJECTONTO = 3;
    OP   PROJECTONTO = ( POLYGON poly, POINT axis )PROJECTION:
         BEGIN
             REAL min := axis DOT poly[ LWB poly ];
             REAL max := min;
             FOR i FROM LWB poly + 1 TO UPB poly DO
                 REAL p = axis DOT poly[ i ];
                 IF   p < min THEN
                     min := p
                 ELIF p > max THEN
                     max := p
                 FI
             OD;
             PROJECTION( min, max )
         END # PROJECTONTO # ;

    PRIO OVERLAPS = 5;
    # returns TRUE if the projections proj1 and proj2 overlap,               #
    #         FALSE otherrwise                                               #
    OP   OVERLAPS = ( PROJECTION proj1, proj2 )BOOL:
         IF   max OF proj1 < min OF proj2 THEN FALSE
         ELIF max OF proj2 < min OF proj1 THEN FALSE
         ELSE                                  TRUE
         FI # OVERLAPS # ;

    # returns TRUE if the polygons poly1 and poly2 overlap,                  #
    #         FALSE otherrwise                                               #
    OP   OVERLAPS = ( POLYGON poly1, poly2 )BOOL:
         BEGIN
            []POINT axes1 = AXES poly1, axes2 = AXES poly2;
            BOOL does overlap := TRUE;
            FOR a FROM LWB axes1 TO UPB axes1 WHILE does overlap DO
                does overlap := ( poly1 PROJECTONTO axes1[ a ] )
                       OVERLAPS ( poly2 PROJECTONTO axes1[ a ] )
            OD;
            FOR a FROM LWB axes2 TO UPB axes2 WHILE does overlap DO
                does overlap := ( poly1 PROJECTONTO axes2[ a ] )
                       OVERLAPS ( poly2 PROJECTONTO axes2[ a ] )
            OD;
            does overlap
         END # OVERLAPS # ;

    # returns x as a string without trailing 0 decoimals                     #
    OP TOSTRING = ( REAL x )STRING:
         BEGIN
            STRING v       := fixed( x, -14, 11 );
            INT    end pos := UPB v;
            WHILE IF end pos < LWB v THEN FALSE ELSE v[ end pos ] = "0" FI DO
                end pos -:= 1
            OD;
            IF end pos >= LWB v THEN
                IF v[ end pos ] = "." THEN end pos -:= 1 FI
            FI;
            INT start pos := LWB v;
            WHILE IF start pos > end pos THEN FALSE ELSE v[ start pos ] = " " FI DO
                start pos +:= 1
            OD;
            IF end pos < start pos THEN "0" ELSE v[ start pos : end pos ] FI
         END # TOSTRING # ;

    # returns a string representation of the POINT p                         #
    OP   TOSTRING = ( POINT p )STRING: "( " + TOSTRING x OF p + ", " + TOSTRING y OF p + " )";

    # returns a string representation of the points of p                     #
    OP   TOSTRING = ( POLYGON p )STRING:
         BEGIN
            STRING result    := "(", separator := "";
            FOR i FROM LWB p TO UPB p DO
                result   +:= separator + " " + TOSTRING p[ i ];
                separator := ","
            OD;
            result + " )"
         END # TOSTRING # ;

    # begin additional code for this task                                    #

    # a rectangle is represented by its lower left corner, width and height  #
    MODE RECTANGLE  = STRUCT( POINT corner, REAL width, height );

    # returns a POLYGON equivalent to the RECTANGLE r                        #
    OP   TOPOLYGON = ( RECTANGLE r )POLYGON:
         ( corner OF r
         , ( x OF corner OF r,               y OF corner OF r + height OF r )
         , ( x OF corner OF r + width  OF r, y OF corner OF r + height OF r )
         , ( x OF corner OF r + width  OF r, y OF corner OF r               )
         );

    # returns TRUE if the POLYGON poly and RECTANGLE rect overlap,           #
    #         FALSE otherrwise                                               #
    OP   OVERLAPS = ( POLYGON poly, RECTANGLE rect )BOOL: poly OVERLAPS TOPOLYGON rect;

    # returns a string representation of the rectangle r                     #
    OP TOSTRING = ( RECTANGLE r )STRING:
        "( " + TOSTRING corner OF r + ", " + TOSTRING width OF r + ", " + TOSTRING height OF r + " )";

    # end  additional code for this task                                     #

    # test cases                                                             #
    POLYGON   poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) );
    RECTANGLE rect1 = ( ( 4, 0 ), 2, 2), rect2 = ( ( 1, 0 ), 8, 2);

    print( ( "poly1 = ", TOSTRING poly1, newline ) );
    print( ( "rect1 = ", TOSTRING rect1, " => ", TOSTRING TOPOLYGON rect1, newline ) );
    print( ( "rect2 = ", TOSTRING rect2, " => ", TOSTRING TOPOLYGON rect2, newline ) );
    print( ( newline ) );
    print( ( "poly1 and rect1 overlap? ", IF poly1 OVERLAPS rect1 THEN "yes" ELSE "no" FI, newline ) );
    print( ( "poly1 and rect2 overlap? ", IF poly1 OVERLAPS rect2 THEN "yes" ELSE "no" FI, newline ) )
END
Output:
poly1 = ( ( 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 ) )

poly1 and rect1 overlap? no
poly1 and rect2 overlap? yes

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

Julia

Translation of: Nim
import LinearAlgebra: dot

const Vector2 = Tuple{Float64, Float64}
const Projection = NamedTuple{(:min, :max), NTuple{2, Float64}}
const Polygon = Vector{Vector2}
const Rectangle = NamedTuple{(:x, :y, :w, :h), NTuple{4, Float64}}

function axes(poly::Polygon)::Polygon
	result = [(0.0, 0.0) for _ in eachindex(poly)]
	for (i, vertex1) in enumerate(poly)
		vertex2 = i == lastindex(poly) ? first(poly) : poly[i+1] # wraps around
		edge = (first(vertex1) - first(vertex2), last(vertex1) - last(vertex2))
		result[i] = (-last(edge), first(edge))
	end
	return result
end

function projectiononaxis(poly::Polygon, axis::Vector2)::Projection
	resultmin, resultmax = Inf, -Inf
	for vertex in poly
		p = dot(axis, vertex)
		p < resultmin && (resultmin = p)
		p > resultmax && (resultmax = p)
	end
	return Projection((resultmin, resultmax))
end

projectionoverlaps(p1::Projection, p2::Projection) = p1[2] <= p2[1] && p2[2] >= p1[1]

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

function polygonoverlapsrect(p1::Polygon, rect::Rectangle)::Bool
	p2 = Polygon(rect)
	return !any(projectionoverlaps(projectiononaxis(p1, axis), projectiononaxis(p2, axis))
				for a in [axes(p1), axes(p2)] for axis in a)
end

const poly = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
const rect1 = Rectangle((4.0, 0.0, 2.0, 2.0))
const rect2 = Rectangle((1.0, 0.0, 8.0, 2.0))
println("poly = a polygon with vertices: ", poly)
println("rect1 = Rectangle with ", rect1)
println("rect2 = Rectangle with ", rect2)
println("\npoly and rect1 overlap? ", polygonoverlapsrect(poly, rect1))
println("poly and rect2 overlap? ", polygonoverlapsrect(poly, rect2))
Output:
poly = a polygon with vertices: [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
rect1 = Rectangle with (x = 4.0, y = 0.0, w = 2.0, h = 2.0)
rect2 = Rectangle with (x = 1.0, y = 0.0, w = 8.0, h = 2.0)

poly and rect1 overlap? false
poly and rect2 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

Raku

Translation of: Go
# 20230810 Raku programming solution

class Vector2 { has ( $.x, $.y );
   method dot ( \other ) { self.x * other.x + self.y * other.y }
}; 

class Rectangle { has ( $.x, $.y, $.w, $.h ) }

class Projection { has ( $.min, $.max ) };

sub getAxes(\poly) {
   return poly.append(poly[0]).rotor(2=>-1).map: -> (\vertex1,\vertex2) {
      my \vector1 = Vector2.new: x => vertex1[0], y => vertex1[1];
      my \vector2 = Vector2.new: x => vertex2[0], y => vertex2[1];
      my \edge    = Vector2.new: x => vector1.x - vector2.x, 
                                 y => vector1.y - vector2.y;
      $_ = Vector2.new: x => -edge.y, y => edge.x
   }
}

sub projectOntoAxis(\poly, \axis) {
   my \vertex0 = poly[0];
   my \vector0 = Vector2.new: x => vertex0[0], y => vertex0[1];
   my $max     = my $min = axis.dot: vector0;
   for poly -> \vertex {
      my \vector = Vector2.new: x => vertex[0], y => vertex[1];
      given axis.dot: vector { when $_ < $min { $min = $_ } 
                               when $_ > $max { $max = $_ } }
   }
   return Projection.new: min => $min, max => $max
}

sub projectionsOverlap(\proj1, \proj2) {
   return ! ( proj1.max < proj2.min or proj2.max < proj1.min )
}

sub rectToPolygon( \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)]
}

sub polygonOverlapsRect(\poly1, \rect) {
   my \poly2 = rectToPolygon rect;
   my (\axes1,\axes2) := (poly1,poly2).map: { getAxes $_ };
   for (axes1, axes2) -> \axes {
     for axes -> \axis {
         my (\proj1,\proj2) := (poly1,poly2).map: { projectOntoAxis $_, axis }
         return False unless projectionsOverlap(proj1, proj2) 
      }
   }
   return True
}

my \poly = [ <0 0>, <0 2>, <1 4>, <2 2>, <2 0> ]; 
my \rect1 = Rectangle.new: :4x, :0y, :2h, :2w;
my \rect2 = Rectangle.new: :1x, :0y, :8h, :2w;
say "poly  = ", poly;
say "rect1 = ", rectToPolygon(rect1);
say "rect2 = ", rectToPolygon(rect2);
say();
say "poly and rect1 overlap? ", polygonOverlapsRect(poly, rect1);
say "poly and rect2 overlap? ", polygonOverlapsRect(poly, rect2);

You may Attempt This Online!

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
Retrieved from "https://rosettacode.org/wiki/Check_if_a_polygon_overlaps_with_a_rectangle?oldid=358926"