Check if a polygon overlaps with a rectangle: Difference between revisions
Content added Content deleted
(Added Go) |
(Added C) |
||
Line 9: | Line 9: | ||
=={{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; |
|||
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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
Revision as of 13:56, 31 July 2023
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.
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
C
#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
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
Phix
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
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