View source for Check if two polygons overlap

{{task}}Self-explanatory: given two polygons (as a list of their vertices), check whether they overlap.

;Related tasks
* [[Determine_if_two_triangles_overlap|Determine if two triangles overlap]]
* [[Check_if_a_polygon_overlaps_with_a_rectangle|Check if a polygon overlaps with a rectangle]]
<br><br>







=={{header|ALGOL 68}}==
{{Trans|Go|but using operators instead of functions and representing a polygon as a row of points instead of a [][]REAL}}
<syntaxhighlight lang="algol68">
BEGIN # test for overlapping 2D polygons                                     #
      # - 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      #

    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 ppolygons 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 # ;


    # test cases                                                             #
    POLYGON poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) )
          , poly2 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )
          , poly3 = ( ( 1, 0 ), ( 1, 2 ), ( 5, 4 ), ( 9, 2 ), ( 9, 0 ) )
          ;
    print( ( "poly1 = ", TOSTRING poly1, newline ) );
    print( ( "poly2 = ", TOSTRING poly2, newline ) );
    print( ( "poly3 = ", TOSTRING poly3, newline ) );
    print( ( newline ) );
    print( ( "poly1 and poly2 overlap? ", IF poly1 OVERLAPS poly2 THEN "yes" ELSE "no" FI, newline ) );
    print( ( "poly1 and poly3 overlap? ", IF poly1 OVERLAPS poly3 THEN "yes" ELSE "no" FI, newline ) );
    print( ( "poly2 and poly3 overlap? ", IF poly2 OVERLAPS poly3 THEN "yes" ELSE "no" FI, newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) )
poly2 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )
poly3 = ( ( 1, 0 ), ( 1, 2 ), ( 5, 4 ), ( 9, 2 ), ( 9, 0 ) )

poly1 and poly2 overlap? no
poly1 and poly3 overlap? yes
poly2 and poly3 overlap? yes
</pre>

=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>

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

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

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;
}

bool polygonsOverlap(double poly1[][2], double poly2[][2], size_t len1, size_t len2) {
    int i;
    Vector2 axis, axes1[len1], axes2[len2];
    Projection proj1, proj2;
    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 poly1[][2] = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} };
    double poly2[][2] = { {4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0} };
    double poly3[][2] = { {1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0} };
    printf("poly1 = ");
    printPoly(poly1, 5);
    printf("poly2 = ");
    printPoly(poly2, 5);
    printf("poly3 = ");
    printPoly(poly3, 5);
    printf("\n");
    printf("poly1 and poly2 overlap? %s\n", polygonsOverlap(poly1, poly2, 5, 5) ? "true" : "false");
    printf("poly1 and poly3 overlap? %s\n", polygonsOverlap(poly1, poly3, 5, 5) ? "true" : "false");
    printf("poly2 and poly3 overlap? %s\n", polygonsOverlap(poly2, poly3, 5, 5) ? "true" : "false");
    return 0;
}</syntaxhighlight>

{{out}}
<pre>
poly1 = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} }
poly2 = { {4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0} }
poly3 = { {1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0} }

poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>

=={{header|C++}}==
An implementation of the Separating Axis Theorem algorithm for convex polygons.
<syntaxhighlight lang="c++">
#include <iostream>
#include <limits>
#include <string>
#include <vector>

class Point {
public:
	float x;
	float y;
};

class Projection {
public:
	float min;
	float max;

	const bool overlaps(const Projection& other) {
		return ! ( max < other.min || other.max < min );
	}
};

class Vector {
public:
	float x;
	float y;

	const float scalarProduct(const Vector& other) {
		return x * other.x + y * other.y;
	}

	const Vector edgeWith(const Vector& other) {
		return Vector(x - other.x, y - other.y);
	}

	const Vector perpendicular() {
		return Vector(-y, x);
	}

	const std::string to_string() {
		return "(" + std::to_string(x) + ", " + std::to_string(y) + ") ";
	}
};

class Polygon {
public:
	Polygon(const std::vector<Point>& points) {
		computeVertices(points);
		computeAxes();
	}

	const bool overlaps(Polygon& other) {
		std::vector<Vector> allAxes = axes;
		allAxes.insert(allAxes.end(), other.axes.begin(), other.axes.end());

		for ( Vector& axis : allAxes ) {
			Projection projection1 = projectionOnAxis(axis);
			Projection projection2 = other.projectionOnAxis(axis);
			if ( ! projection1.overlaps(projection2) ) {
				return false;
			}
		}

		return true;
	}

	const Projection projectionOnAxis(Vector& axis) {
		float min = std::numeric_limits<float>::infinity();
		float max = -std::numeric_limits<float>::infinity();

		for ( const Vector& vertex : vertices ) {
			double p = axis.scalarProduct(vertex);
			if ( p < min ) {
				min = p;
			}
			if ( p > max ) {
			  max = p;
			}
		}

		return Projection(min, max);
	}

	const std::string to_string() {
		std::string result = "[ ";
		for ( Vector& vertex : vertices ) {
			result += vertex.to_string();
		}

		result += "]";
		return result;
	}

private:
	void computeVertices(const std::vector<Point>& points) {
		for ( const Point& point : points ) {
			vertices.emplace_back(Vector(point.x, point.y));
		}
	}

	void computeAxes() {
		for ( size_t i = 0; i < vertices.size(); i++ ) {
			Vector vertex1 = vertices[i];
			Vector vertex2 = vertices[( i + 1 ) % vertices.size()];
			Vector edge = vertex1.edgeWith(vertex2);
			axes.emplace_back(edge.perpendicular());
		}
	}

	std::vector<Vector> vertices;
	std::vector<Vector> axes;
};

int main() {
	Polygon polygon1(std::vector<Point> { Point(0.0, 0.0), Point(0.0, 2.0), Point(1.0, 4.0),
										  Point(2.0, 2.0), Point(2.0, 0.0) } );

	Polygon polygon2(std::vector<Point> { Point(4.0, 0.0), Point(4.0, 2.0), Point(5.0, 4.0),
					                      Point(6.0, 2.0), Point(6.0, 0.0) } );

	Polygon polygon3(std::vector<Point> { Point(1.0, 0.0), Point(1.0, 2.0), Point(5.0, 4.0),
					                      Point(9.0, 2.0), Point(9.0, 0.0) } );

	std::cout << "polygon1: " << polygon1.to_string() << std::endl;
	std::cout << "polygon2: " << polygon2.to_string() << std::endl;
	std::cout << "polygon3: " << polygon3.to_string() << std::endl;
	std::cout << std::boolalpha << std::endl;
	std::cout << "polygon1 and polygon2 overlap? " << polygon1.overlaps(polygon2) << std::endl;
	std::cout << "polygon1 and polygon3 overlap? " << polygon1.overlaps(polygon3) << std::endl;
	std::cout << "polygon2 and polygon3 overlap? " << polygon2.overlaps(polygon3) << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
polygon1 = [ (0.000000, 0.000000) (0.000000, 2.000000) (1.000000, 4.000000) (2.000000, 2.000000) (2.000000, 0.000000) ]
polygon2 = [ (4.000000, 0.000000) (4.000000, 2.000000) (5.000000, 4.000000) (6.000000, 2.000000) (6.000000, 0.000000) ]
polygon3 = [ (1.000000, 0.000000) (1.000000, 2.000000) (5.000000, 4.000000) (9.000000, 2.000000) (9.000000, 0.000000) ]

polygon1 and polygon2 overlap? false
polygon1 and polygon3 overlap? true
polygon2 and polygon3 overlap? true
</pre>

=={{header|Go}}==
{{trans|Wren}}
<syntaxhighlight lang="go">package main

import "fmt"

type Vector2 struct {
    x, y float64
}

type Projection struct {
    min, max 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 polygonsOverlap(poly1, poly2 [][2]float64) bool {
    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() {
    poly1 := [][2]float64{{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}
    poly2 := [][2]float64{{4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0}}
    poly3 := [][2]float64{{1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0}}
    fmt.Println("poly1 = ", poly1)
    fmt.Println("poly2 = ", poly2)
    fmt.Println("poly3 = ", poly3)
    fmt.Println()
    fmt.Println("poly1 and poly2 overlap?", polygonsOverlap(poly1, poly2))
    fmt.Println("poly1 and poly3 overlap?", polygonsOverlap(poly1, poly3))
    fmt.Println("poly2 and poly3 overlap?", polygonsOverlap(poly2, poly3))
}</syntaxhighlight>

{{out}}
<pre>
poly1 =  [[0 0] [0 2] [1 4] [2 2] [2 0]]
poly2 =  [[4 0] [4 2] [5 4] [6 2] [6 0]]
poly3 =  [[1 0] [1 2] [5 4] [9 2] [9 0]]

poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>

=={{header|Java}}==
 An implementation of the Separating Axis Theorem algorithm for convex polygons.
<syntaxhighlight lang="java">

import java.util.ArrayList;
import java.util.List;

public final class CheckIfTwoPolygonsOverlap {

	public static void main(String[] args) {
		Polygon polygon1 = new Polygon(List.of( new Point(0.0, 0.0), new Point(0.0, 2.0), new Point(1.0, 4.0),
				                                new Point(2.0, 2.0), new Point(2.0, 0.0) ));
				
		Polygon polygon2 = new Polygon(List.of( new Point(4.0, 0.0), new Point(4.0, 2.0), new Point(5.0, 4.0),
				                                new Point(6.0, 2.0), new Point(6.0, 0.0) ));
		
		Polygon polygon3 = new Polygon(List.of( new Point(1.0, 0.0), new Point(1.0, 2.0), new Point(5.0, 4.0),
				                                new Point(9.0, 2.0), new Point(9.0, 0.0) ));
		
		System.out.println("polygon1 = " + polygon1);
		System.out.println("polygon2 = " + polygon2);
		System.out.println("polygon3 = " + polygon3);
		System.out.println();
		System.out.println("polygon1 and polygon2 overlap? " + polygon1.overlaps(polygon2));
		System.out.println("polygon1 and polygon3 overlap? " + polygon1.overlaps(polygon3));
		System.out.println("polygon2 and polygon3 overlap? " + polygon2.overlaps(polygon3));
	}
	
	private static class Polygon {
		
		public Polygon(List<Point> points) {
			vertices = points.stream().map( point -> new Vector(point.x, point.y) ).toList();
			axes = computeAxes();
		}
		
		public boolean overlaps(Polygon other) {
			List<Vector> allAxes = new ArrayList<Vector>(axes);
			allAxes.addAll(other.axes);
	
			for ( Vector axis : allAxes ) {
		        Projection projection1 = projectionOnAxis(axis);
		        Projection projection2 = other.projectionOnAxis(axis);
		        if ( ! projection1.overlaps(projection2) ) {
		        	return false;
		        }
			}
			
			return true;
	    }
		
		public Projection projectionOnAxis(Vector axis) {
			double min = Double.POSITIVE_INFINITY;
			double max = Double.NEGATIVE_INFINITY;
		
			for ( Vector vertex : vertices ) {
			    double p = axis.scalarProduct(vertex);
			    if ( p < min ) {
			        min = p;
			    }
			    if ( p > max ) {
			      max = p;
			    }
			}
			
			return new Projection(min, max);
	    }
		
		public String toString() {
			StringBuilder result = new StringBuilder("[ ");
			for ( Vector vertex : vertices ) {
				result.append(vertex);
			}
			
			result.append("]");
			return result.toString();			
		}
		
		private List<Vector> computeAxes() {
	        List<Vector> axes = new ArrayList<Vector>();
            for ( int i = 0; i < vertices.size(); i++ ) {
                Vector vertex1 = vertices.get(i);
                Vector vertex2 = vertices.get(( i + 1 ) % vertices.size());
                Vector edge = vertex1.edgeWith(vertex2);
                axes.addLast(edge.perpendicular());
            }

            return axes;
        }
		
		private List<Vector> vertices;
	    private List<Vector> axes;
		
	}
	
	final record Vector(double x, double y) {			
		
	    public double scalarProduct(Vector other) {
	    	return x * other.x + y * other.y;
	    }
	    
	    public Vector edgeWith(Vector other) {
	    	return new Vector(x - other.x, y - other.y);
	    }
	    
	    public Vector perpendicular() {
	    	return new Vector(-y, x);
	    }
	    
	    public String toString() {
			return "(" + x + ", " + y + ") ";
		}
	    		
	}

	final record Projection(double min, double max) {
		
		public boolean overlaps(Projection other) {
			return ! ( max < other.min || other.max < min );
		}

	}

	final record Point(double x, double y) { }

}
</syntaxhighlight>
{{ out }}
<pre>
polygon1 = [ (0.0, 0.0) (0.0, 2.0) (1.0, 4.0) (2.0, 2.0) (2.0, 0.0) ]
polygon2 = [ (4.0, 0.0) (4.0, 2.0) (5.0, 4.0) (6.0, 2.0) (6.0, 0.0) ]
polygon3 = [ (1.0, 0.0) (1.0, 2.0) (5.0, 4.0) (9.0, 2.0) (9.0, 0.0) ]

polygon1 and polygon2 overlap? false
polygon1 and polygon3 overlap? true
polygon2 and polygon3 overlap? true
</pre>

=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]''' (2D convex polygons)
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''

In the following:
* a vertex is represented by a pair of x, y coordinates in the plane;
* a polygon is represented as a list of vertices;
* a projection is represented by a JSON object {min, max}
<syntaxhighlight lang="jq">
# Input: [$A, $B] where $A and $B are points
# Output: the vector $B - $A
def AB:
  . as [$A, $B]
  | [ $B[0] - $A[0],  $B[1] - $A[1]];

# Input: a vector
# Output: perpendicular
def perp: [- .[1], .[0]];

# dot product of this and $v, assumed to be of the same dimension
def dot($v):
  . as $this
  | reduce range(0; $this|length) as $i (0; . + ($this[$i] * $v[$i] ));
  
def getAxes:
  . as $poly
  | reduce range(0; $poly|length) as $i ([];
      $poly[$i] as $vertex1
      | $poly[if $i+1 == ($poly|length) then 0 else $i+1 end] as $vertex2
      | . + [ [$vertex1, $vertex2] | AB | perp] );

# emit {min, max}
def projectOntoAxis($axis):
  . as $poly
  | { max: - infinite, min: infinite }
  | reduce range(0; $poly|length) as $i (.;
       ($axis | dot( $poly[$i] )) as $p
       | if $p < .min then .min = $p else . end
       | if $p > .max then .max = $p else . end ) ;

def projectionsOverlap($proj1; $proj2):
  if   $proj1.max < $proj2.min then false
  elif $proj2.max < $proj1.min then false
  else true
  end;

# If there's an axis for which the projections do not overlap, then false; else true
def polygonsOverlap($poly1; $poly2):
  any( $poly1, $poly2 | getAxes[];
    . as $axis
    | ($poly1 | projectOntoAxis($axis)) as $proj1
    | ($poly2 | projectOntoAxis($axis)) as $proj2
    | projectionsOverlap($proj1; $proj2) | not)
  | not;    

def poly1: [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]];
def poly2: [[4, 0], [4, 2], [5, 4], [6, 2], [6, 0]];
def poly3: [[1, 0], [1, 2], [5, 4], [9, 2], [9, 0]];

def task:
  "poly1 = \(poly1)",
  "poly2 = \(poly2)",
  "poly3 = \(poly3)",
  "",
  "poly1 and poly2 overlap? \(polygonsOverlap(poly1; poly2))",
  "poly1 and poly3 overlap? \(polygonsOverlap(poly1; poly3))",
  "poly2 and poly3 overlap? \(polygonsOverlap(poly2; poly3))"
  ;

task
</syntaxhighlight>
{{output}}
As for [[#Wren]]

=={{header|Julia}}==
<syntaxhighlight lang="julia">using Plots
using Polyhedra
using GLPK

lib = DefaultLibrary{Float64}(GLPK.Optimizer)

const poly1 = polyhedron(vrep([
    0 0
    0 2
    1 4
    2 2
    2 0
]), lib)

const poly2 = polyhedron(vrep([
    4 0
    4 2
    5 4
    6 2
    6 0
]), lib)

const poly3 = polyhedron(vrep([
    1 0
    1 2
    5 4
    9 2
    9 0
]), lib)

println("Polygons poly1 and poly2 intersect at ", npoints(intersect(poly1, poly2)), " points.")
println("Polygons poly1 and poly3 intersect at ", npoints(intersect(poly1, poly3)), " points.")
println("Polygons poly2 and poly3 intersect at ", npoints(intersect(poly2, poly3)), " points.")
const P1 = polyhedron(vrep([
    -1.9 -1.7
    -1.8  0.5
     1.7  0.7
     1.9 -0.3
     0.9 -1.1
]), lib)

const P2 = polyhedron(vrep([
   -2.5 -1.1
   -0.8  0.8
    0.1  0.9
    1.8 -1.2
    1.3  0.1
]), lib)

Pint = intersect(P1, P2)
println("Polygons P1 and P2 intersect at ", npoints(Pint), " points.")

plot(P1, color="blue", alpha=0.2)      
plot!(P2, color="red", alpha=0.2)      
plot!(Pint, color="yellow", alpha=0.6) 
</syntaxhighlight>{{out}}
<pre>
Polygons poly1 and poly2 intersect at 0 points.
Polygons poly1 and poly3 intersect at 5 points.
Polygons poly2 and poly3 intersect at 5 points.
Polygons P1 and P2 intersect at 8 points.
</pre>

[[File:Poly intersect.svg|thumb|center]]




=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="Kotlin">
import kotlin.math.*

data class Vector2(val x: Double, val y: Double) {
    fun dot(other: Vector2): Double = this.x * other.x + this.y * other.y
}

class Projection(var min: Double = Double.POSITIVE_INFINITY, var max: Double = Double.NEGATIVE_INFINITY) {
    fun overlaps(proj2: Projection): Boolean = !(this.max < proj2.min || proj2.max < this.min)
}

class Polygon(vertices: List<Pair<Double, Double>>) {
    private val vertices: List<Vector2> = vertices.map { Vector2(it.first, it.second) }
    private val axes: List<Vector2> = getAxes()

    public fun getVertices(): List<Vector2> { return vertices}
    

    private fun getAxes(): List<Vector2> {
        val axes = mutableListOf<Vector2>()
        for (i in vertices.indices) {
            val vertex1 = vertices[i]
            val vertex2 = if (i + 1 == vertices.size) vertices[0] else vertices[i + 1]
            val edge = Vector2(vertex1.x - vertex2.x, vertex1.y - vertex2.y)
            axes.add(Vector2(-edge.y, edge.x))
        }
        return axes
    }

    fun projectionOnAxis(axis: Vector2): Projection {
        return Projection().apply {
            vertices.forEach { vertex ->
                val p = axis.dot(vertex)
                if (p < min) min = p
                if (p > max) max = p
            }
        }
    }

    fun overlaps(other: Polygon): Boolean {
        (this.axes + other.axes).forEach { axis ->
            val proj1 = this.projectionOnAxis(axis)
            val proj2 = other.projectionOnAxis(axis)
            if (!proj1.overlaps(proj2)) return false
        }
        return true
    }
}

fun main() {
    val poly1 = Polygon(listOf(0.0 to 0.0, 0.0 to 2.0, 1.0 to 4.0, 2.0 to 2.0, 2.0 to 0.0))
    val poly2 = Polygon(listOf(4.0 to 0.0, 4.0 to 2.0, 5.0 to 4.0, 6.0 to 2.0, 6.0 to 0.0))
    val poly3 = Polygon(listOf(1.0 to 0.0, 1.0 to 2.0, 5.0 to 4.0, 9.0 to 2.0, 9.0 to 0.0))
    val polygons = listOf(poly1, poly2, poly3)

    polygons.forEachIndexed { index, polygon ->
        println("poly${index + 1} = ${polygon.getVertices()}")
    }
    println("poly1 and poly2 overlap? ${polygons[0].overlaps(polygons[1])}")
    println("poly1 and poly3 overlap? ${polygons[0].overlaps(polygons[2])}")
    println("poly2 and poly3 overlap? ${polygons[1].overlaps(polygons[2])}")
}
</syntaxhighlight>
{{out}}
<pre>
poly1 = [Vector2(x=0.0, y=0.0), Vector2(x=0.0, y=2.0), Vector2(x=1.0, y=4.0), Vector2(x=2.0, y=2.0), Vector2(x=2.0, y=0.0)]
poly2 = [Vector2(x=4.0, y=0.0), Vector2(x=4.0, y=2.0), Vector2(x=5.0, y=4.0), Vector2(x=6.0, y=2.0), Vector2(x=6.0, y=0.0)]
poly3 = [Vector2(x=1.0, y=0.0), Vector2(x=1.0, y=2.0), Vector2(x=5.0, y=4.0), Vector2(x=9.0, y=2.0), Vector2(x=9.0, y=0.0)]
poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true

</pre>

=={{header|Nim}}==
{{trans|Wren}}
{{trans|Go}}
<syntaxhighlight lang="Nim">type
  Vector2 = (float, float)
  Projection = tuple[min, max: float]
  Polygon = seq[Vector2]

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 polygonsOverlap(poly1, poly2: Polygon): bool =
  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 poly1 = @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
let poly2 = @[(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)]
let poly3 = @[(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)]

echo "poly1 = ", poly1
echo "poly2 = ", poly2
echo "poly3 = ", poly3
echo()
echo "poly1 and poly2 overlap? ", polygonsOverlap(poly1, poly2)
echo "poly1 and poly3 overlap? ", polygonsOverlap(poly1, poly3)
echo "poly2 and poly3 overlap? ", polygonsOverlap(poly2, poly3)
</syntaxhighlight>

{{out}}
<pre>poly1 = @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
poly2 = @[(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)]
poly3 = @[(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)]

poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>

=={{header|Phix}}==
{{trans|Wren}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
 <span style="color: #000080;font-style:italic;">-- demo\rosetta\Polygons_overlap.exw</span>
 <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 <span style="color: #008080;">function</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">axes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)]</span>
         <span style="color: #000000;">axes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span> <span style="color: #000080;font-style:italic;">-- ie {-y,x}</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">axes</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
 <span style="color: #008080;">function</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">axis</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ay</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">axis</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">))</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pi</span> <span style="color: #008080;">in</span> <span style="color: #000000;">poly</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">px</span><span style="color: #0000FF;">,</span><span style="color: #000000;">py</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span>
         <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ax</span><span style="color: #0000FF;">*</span><span style="color: #000000;">px</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ay</span><span style="color: #0000FF;">*</span><span style="color: #000000;">py</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)}</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
 <span style="color: #008080;">function</span> <span style="color: #000000;">projectionsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">min1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">max1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> 
          <span style="color: #0000FF;">{</span><span style="color: #000000;">min2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">max2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">proj2</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">max1</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">min2</span> <span style="color: #008080;">and</span> <span style="color: #000000;">max2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">min1</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
 <span style="color: #008080;">function</span> <span style="color: #000000;">polygonsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">poly2</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">axes1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">),</span>
              <span style="color: #000000;">axes2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">axes</span> <span style="color: #008080;">in</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">axes1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axes2</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">axis</span> <span style="color: #008080;">in</span> <span style="color: #000000;">axes</span> <span style="color: #008080;">do</span>
             <span style="color: #004080;">sequence</span> <span style="color: #000000;">proj1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">),</span>
                      <span style="color: #000000;">proj2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">)</span>
             <span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">projectionsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
 <span style="color: #008080;">constant</span> <span style="color: #000000;">poly1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
          <span style="color: #000000;">poly2</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
          <span style="color: #000000;">poly3</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
 <span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
 poly1 = %v
 poly2 = %v
 poly3 = %v
 
 poly1 and poly2 overlap? %t
 poly1 and poly3 overlap? %t
 poly2 and poly3 overlap? %t
 """</span>
 <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">polygonsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">poly2</span><span style="color: #0000FF;">),</span>
                                 <span style="color: #000000;">polygonsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">poly3</span><span style="color: #0000FF;">),</span>
                                 <span style="color: #000000;">polygonsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">poly3</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
poly1 = {{0,0},{0,2},{1,4},{2,2},{2,0}}
poly2 = {{4,0},{4,2},{5,4},{6,2},{6,0}}
poly3 = {{1,0},{1,2},{5,4},{9,2},{9,0}}

poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>
=={{header|Python}}==
{{trans|Nim}}
<syntaxhighlight lang="python3">
# overlaying_polygons.py by xing216
from math import inf
class Vector2:
    def __init__(self, x: float, y: float) -> None:
        self.x = x
        self.y = y
    def dot(self, other: 'Vector2') -> float:
        return self.x * other.x + self.y * other.y
    def __repr__(self) -> str:
        return f'({self.x}, {self.y})'
class Projection:
    min: float
    max: float
    def overlaps(self, proj2: 'Projection') -> bool:
        if self.max < proj2.min or proj2.max < self.min: return False
        return True
class Polygon:
    def __init__(self, vertices: list[tuple[float, float]]) -> None:
        self.vertices = [Vector2(*vertex) for vertex in vertices]
        self.axes = self.get_axes()
    def get_axes(self) -> list[Vector2]:
        axes = []
        for i, vertex1 in enumerate(self.vertices):
            if i + 1 == len(self.vertices): vertex2 = self.vertices[0]
            else: vertex2 = self.vertices[i + 1]
            edge = (vertex1.x - vertex2.x, vertex1.y - vertex2.y)
            axes.append(Vector2(-edge[1], edge[0]))
        return axes
    def projection_on_axis(self, axis: Vector2) -> Projection:
        projection = Projection()
        projection.min = inf
        projection.max = -inf
        for vertex in self.vertices:
            p = axis.dot(vertex)
            if p < projection.min:
                projection.min = p
            if p > projection.max:
                projection.max = p
        return projection
    def overlaps(self, other: 'Polygon') -> bool:
        for axes in [self.axes, other.axes]:
            for axis in axes:
                proj1 = self.projection_on_axis(axis)
                proj2 = other.projection_on_axis(axis)
                if not proj1.overlaps(proj2): return False
        return True
    
poly1 = Polygon([(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)])
poly2 = Polygon([(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)])
poly3 = Polygon([(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)])
polygons = (poly1, poly2, poly3)
for i, polygon in enumerate(polygons):
    print(f'poly{i+1} = {polygon.vertices}')
print(f'poly1 and poly2 overlap? {polygons[0].overlaps(polygons[1])}')
print(f'poly1 and poly3 overlap? {polygons[0].overlaps(polygons[2])}')
print(f'poly2 and poly3 overlap? {polygons[1].overlaps(polygons[2])}')
</syntaxhighlight>
{{out}}
<pre>
poly1 = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
poly2 = [(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)]
poly3 = [(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)]
poly1 and poly2 overlap? False
poly1 and poly3 overlap? True
poly2 and poly3 overlap? True
</pre>

=={{header|Raku}}==
{{trans|Go}}
<syntaxhighlight lang="raku" line># 20230810 Raku programming solution

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

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 polygonsOverlap( \poly1, \poly2 ) {
   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 \poly1 = [ <0 0>, <0 2>, <1 4>, <2 2>, <2 0> ];
my \poly2 = [ <4 0>, <4 2>, <5 4>, <6 2>, <6 0> ];
my \poly3 = [ <1 0>, <1 2>, <5 4>, <9 2>, <9 0> ];

say "poly1 = ", poly1;
say "poly2 = ", poly2;
say "poly3 = ", poly3;
say();
say "poly1 and poly2 overlap? ", polygonsOverlap(poly1, poly2);
say "poly1 and poly3 overlap? ", polygonsOverlap(poly1, poly3);
say "poly2 and poly3 overlap? ", polygonsOverlap(poly2, poly3);</syntaxhighlight>
You may [https://ato.pxeger.com/run?1=jVXNbtpAED5W8lNMIw52ayx7oVGDwVUuvVXpoeolRJEbFnBLbOSfxBbiSXrJoX2pPk1ndtY_MZSGA7s7O998M_PNws9fafijeHr6XeTL4fs_rz7dbcIsg6_yLk9SATtYhxmYMHBKG78qsHwDAO5lvk4WsEhyvJsn-VqmYKFzJjdLp4Q3oEy4e8umqjFVsDf2PhgG83xOk-9IFSVxh-o-ionsPiwx6N43jKz4BiuZX5aSHObbZFMRHWWSyrxIYyCTE263Ml6YtL92bywnTbAGU8yCoWdhtO0EhgGY8weZ5rL0bL0ROhKVVQEaqXIPZnUPnFg-TqCEWQAaicFtqLoG78Y_CCFOhBD9EKIXQi5WkvbHQ6gMsbtDvRekjkaf-FRddNVBVzX14PYo45DScSqdsTqUhEApWZwty3gV58llGTUi2TAP6ag7zL2hcl2k0TL57Q3Ruie65va75tZdQ_yAxoVbpk5RjDtid3BKJ7pUV3kvk1Sx0zjohI6MwIlE-nl0xFtFDzI-4MXhflyjHfs75dx2dYpo2v9XuxoccJk7XjR4z1K0j6F9VJy5IgoUoQ0KyHF66qF_doUFbcKtEhCtns2r6D231-ig7tUjnaq9oHcL1Fo-NBeeurAaNuz8qqXSo6KYcBWdYTFxemSGD5UWfKaTGZjsqzz1m941Pw3UjUZgk7GgsSQ1bWuhyUWd-SJqLqDm5vq5_H9z9yd_cGsr9VkQ_uimfQw3mYQi3kj84Tvsuakbrgk1_EDcL2khqZU0qCohHINrmLrgBjYtghYPxrQIPgm8A5zQGiIYMmbImJ3eMeScT-c9yIghHkO8Z5ALPl1oiJGFFZzVqZ3ZSnDPb82iNYuOedSaR8psWn43VhgvGAMJN-xD7d6dJj1LLNJR_Oil-JH1LOmX40WD539V_eda_8n-BQ Attempt This Online!]

=={{header|Wren}}==
{{libheader|Wren-vector}}
{{libheader|Wren-dynamic}}
The task description doesn't say whether the polygons are 2D or 3D and whether they're convex or not. So for now, I've assumed the simplest case of 2D convex polygons though a non-convex polygon can always be decomposed into a combination of convex polygons.

The approach here is based on the Separating Axis theorem ("SAT"). See [https://dyn4j.org/2010/01/sat/ here] for a simple explanation of this with pseudo-code.
<syntaxhighlight lang="wren">import "./vector" for Vector2
import "./dynamic" for Tuple

var Projection = Tuple.create("Projection", ["min", "max"])

/* 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 polygonsOverlap = Fn.new { |poly1, poly2|
    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 poly1 = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]]
var poly2 = [[4, 0], [4, 2], [5, 4], [6, 2], [6, 0]]
var poly3 = [[1, 0], [1, 2], [5, 4], [9, 2], [9, 0]]
System.print("poly1 = %(poly1)")
System.print("poly2 = %(poly2)")
System.print("poly3 = %(poly3)")
System.print()
System.print("poly1 and poly2 overlap? %(polygonsOverlap.call(poly1, poly2))") 
System.print("poly1 and poly3 overlap? %(polygonsOverlap.call(poly1, poly3))")
System.print("poly2 and poly3 overlap? %(polygonsOverlap.call(poly2, poly3))") </syntaxhighlight>

{{out}}
<pre>
poly1 = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]]
poly2 = [[4, 0], [4, 2], [5, 4], [6, 2], [6, 0]]
poly3 = [[1, 0], [1, 2], [5, 4], [9, 2], [9, 0]]

poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>