Check if two polygons overlap: Difference between revisions
New post.
(New post.) |
(New post.) |
||
Line 266:
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>
| |||