计算两个凸多边形的交集(重叠区域): OpenCV、Boost、GEOS
计算两个凸多边形的交集可以用OpenCV、Boost、GEOS三个开源库实现:
1: OpenCV
cv::intersectConvexConvex(a, b, intersectionPolygon, true)); true表示支持嵌套，即完全包含
2: Boost
boost::geometry::intersection(A_polygon, B_polygon, output))
Boost的这个函数不支持嵌套，即一个凸多边形完全被另一个凸多边形包含，返回的交集面积为0.0.
3: GEOS(开源计算几何库)
GEOSIntersection(pA, pB); // C_API
#############################################################
\#include
\#include
\#include
\#include
\#include
\#include
\#include
typedef boost::geometry::model::polygon > polygon;
double Boost_Intersection_Of_Convex_Polygon(const std::vector &A, const std::vector &B,\
std::vector &intersectionPolygon)
{
/*
polygon green, blue;
boost::geometry::read_wkt(
"POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)"
"(4.0 2.0, 4.2 1.4, 4.8 1.9, 4.4 2.2, 4.0 2.0))", green);
boost::geometry::read_wkt(
"POLYGON((4.0 -0.5 , 3.5 1.0 , 2.0 1.5 , 3.5 2.0 , 4.0 3.5 , 4.5 2.0 , 6.0 1.5 , 4.5 1.0 , 4.0 -0.5))", blue);
std::deque output;
*/
if(A.size()<3 || B.size()<3)
return 0.0;
double area = 0.0;
polygon A_polygon, B_polygon;
for(const auto &pt:A){
boost::geometry::model::d2::point_xy point(pt.x, pt.y);
boost::geometry::append(A_polygon, point);
}
for(const auto &pt:B){
boost::geometry::model::d2::point_xy point(pt.x, pt.y);
boost::geometry::append(B_polygon, point);
}
std::deque output;
if(!boost::geometry::intersection(A_polygon, B_polygon, output)){
//printf("Warning: boost::geometry::intersection was failed!\n");
return 0.0; // there no intersection.
}
double max_area = 0.0;
polygon max_polggon;
BOOST_FOREACH(polygon const& p, output){
area = boost::geometry::area(p);
if(area>max_area){
max_area = area;
max_polggon = p;
}
}
intersectionPolygon.clear();
for(const auto &pt: max_polggon.outer()){
intersectionPolygon.push_back(cv::Point2f(static_cast(pt.x()), static_cast(pt.y())));
}
printf("Boost A area:%f, B area:%f, intersection area:%f\n", boost::geometry::area(A_polygon), boost::geometry::area(B_polygon), max_area);
bool is_overlap = boost::geometry::overlaps(A_polygon, B_polygon);
printf("Boost overlap:%s\n", is_overlap?"Yes":"No");
boost::geometry::model::d2::point_xy pt;
boost::geometry::centroid(A_polygon, pt);
bool is_within = boost::geometry::within(B_polygon, A_polygon);
printf("Boost %f,%f within A:%s\n", pt.x(), pt.y(), is_within?"Yes":"No");
boost::geometry::centroid(B_polygon, pt);
is_within = boost::geometry::within(A_polygon, B_polygon);
printf("Boost %f,%f within B:%s\n", pt.x(), pt.y(), is_within?"Yes":"No");
bool is_inside = boost::geometry::covered_by(A_polygon, B_polygon);
std::cout<<"???:"< /* for printf */
\#include /* for va_list */
\#include
\#include
\#include
\#include
static void geos_msg_handler(const char* fmt, ...)
{
va_list ap;
va_start(ap, fmt);
vprintf (fmt, ap);
va_end(ap);
}
double Geos_Intersection_Of_Convex_Polygon(const std::vector &A, const std::vector &B,\
std::vector &intersectionPolygon)
{
if(A.size()<3 || B.size()<3)
return 0.0;
initGEOS(geos_msg_handler, geos_msg_handler);
std::vector Abuf, Bbuf;
Abuf.assign(A.begin(), A.end());
Bbuf.assign(B.begin(), B.end());
//for close, the last point must same with the first point for GEOS lib.
Abuf.push_back(A[0]);
Bbuf.push_back(B[0]);
double area = 0.0;
GEOSCoordSequence* s1 = GEOSCoordSeq_copyFromBuffer((double *)Abuf.data(), Abuf.size(), 0, 0);
GEOSCoordSequence* s2 = GEOSCoordSeq_copyFromBuffer((double *)Bbuf.data(), Bbuf.size(), 0, 0);
if(nullptr==s1 || nullptr==s2)
return 0.0;
GEOSGeometry *p1 = GEOSGeom_createLinearRing(s1);
GEOSGeometry *p2 = GEOSGeom_createLinearRing(s2);
if(nullptr==p1 || nullptr==p2)
return 0.0;
GEOSGeometry *pA = GEOSGeom_createPolygon(p1, nullptr, 0);
GEOSGeometry *pB = GEOSGeom_createPolygon(p2, nullptr, 0);
if(nullptr==pA || nullptr==pB)
return 0.0;
double area_1 = 0.0, area_2 = 0.0;
GEOSArea(pA, &area_1);
GEOSArea(pB, &area_2);
printf("PA area:%f, PB area:%f\n", area_1, area_2);
GEOSGeometry *poverlay = GEOSIntersection(pA, pB);
if(nullptr==poverlay){
std::cout<<"Err: GEOSIntersection return null!"<
\#include
\#include
double OpenCV_Intersection_Of_Convex_Polygon(const std::vector &A, const std::vector &B,\
std::vector &intersectionPolygon)
{
if(A.size()<3 || B.size()<3)
return 0.0;
intersectionPolygon.clear();
std::vector a;
std::vector b;
a.resize(A.size());
b.resize(B.size());
for(int j=0; j(A[j].x), static_cast(A[j].y));
}
for(int j=0; j(B[j].x), static_cast(B[j].y));
}
for(const auto &pt:b){
std::cout<(cv::intersectConvexConvex(a, b, intersectionPolygon, true)); // opencv don't support double type.
}
![intersection.png][1]
[1]: /usr/uploads/2024/01/1445291094.png