Community
static void Mhelper(vector<AcGePoint2d> pts, AcGePoint2d A, AcGePoint2d B, bool up, vector<AcGePoint2d>& res) {
if (pts.size() == 0) return;
vector<AcGePoint2d> LeftPts;
vector<AcGePoint2d> RightPts;
AcGePoint2d AB(B.x - A.x, B.y - A.y);
int maxArea = 0;
AcGePoint2d Pmax;
bool flag = false;
if (up) {
// 找到使得APmaxB面积最大的点
for (auto p : pts) {
int Area = abs(A.x * p.y + B.x * A.y + p.x * B.y - B.x * p.y - p.x * A.y - A.x * B.y) / 2;
if (Area > maxArea) {
Pmax = p;
maxArea = Area;
flag = true;
}
}
AcGePoint2d APmax (Pmax.x - A.x, Pmax.y - A.y);
AcGePoint2d PmaxB (B.x - Pmax.x, B.y - Pmax.y);
for (auto p : pts) {
AcGePoint2d AP (p.x - A.x, p.y - A.y);
AcGePoint2d PmaxP (p.x - Pmax.x, p.y - Pmax.y);
// 找出APmax左边的点
if ((APmax.x * AP.y - AP.x * APmax.y) > 0) {
LeftPts.push_back(p);
}
// 找出PmaxB右边的点
else if (PmaxB.x * PmaxP.y - PmaxP.x * PmaxB.y > 0) {
RightPts.push_back(p);
}
}
}
else {
// 找到使得APmaxB面积最大的点
for (auto p : pts) {
int Area = abs(A.x * p.y + B.x * A.y + p.x * B.y - B.x * p.y - p.x * A.y - A.x * B.y) / 2;
if (Area > maxArea) {
Pmax = p;
maxArea = Area;
flag = true;
}
}
AcGePoint2d APmax (Pmax.x - A.x, Pmax.y - A.y);
AcGePoint2d PmaxB (B.x - Pmax.x, B.y - Pmax.y);
for (auto p : pts) {
AcGePoint2d AP (p.x - A.x, p.y - A.y);
AcGePoint2d PmaxP (p.x - Pmax.x, p.y - Pmax.y);
// 找出APmax左边的点
if ((APmax.x * AP.y - AP.x * APmax.y) < 0) {
LeftPts.push_back(p);
}
// 找出PmaxB右边的点
else if (PmaxB.x * PmaxP.y - PmaxP.x * PmaxB.y < 0) {
RightPts.push_back(p);
}
}
}
if (flag) {
res.push_back(Pmax);
Mhelper(LeftPts, A, Pmax, up, res);
Mhelper(RightPts, Pmax, B, up, res);
}
}
static void MquickHull(vector<AcGePoint2d> pts, vector<AcGePoint2d>& res) {
// 少于三点直接返回点集合
if (pts.size() <= 3) {
res = pts;
}
// 点按x坐标排序
sort(pts.begin(), pts.end() ,sortby);
// 最左边的点和最右边的点就是凸包的顶点
AcGePoint2d A = pts.front();
AcGePoint2d B = pts.back();
res.push_back(A);
vector<AcGePoint2d> UpPts;
vector<AcGePoint2d> DownPts;
AcGePoint2d AB (B.x - A.x, B.y - A.y);
for (auto p : pts) {
AcGePoint2d AP (p.x - A.x, p.y - A.y);
// 找出上凸包的里面的点
if ((AB.x * AP.y - AP.x * AB.y) > 0) {
UpPts.push_back(p);
}
// 找出下凸包的里面的点
else {
DownPts.push_back(p);
}
}
// 找出上凸包的顶点
Mhelper(UpPts, A, B, true, res);
// 找出下凸包的顶点
Mhelper(DownPts, A, B, false, res);
res.push_back(B);
}
Solved! Go to Solution.
Solved by tbrammer. Go to Solution.
You could use boost::geometry::convex_hull.
Here is sample code that calculates and draws the convex hull around POINTs:
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/multi/geometries/multi_point.hpp>
using boost::geometry::model::d2::point_xy;
using boost::geometry::append;
using boost::geometry::make;
using multiPoint = boost::geometry::model::multi_point<point_xy<double> >;
void cmdConvexHull() {
ads_name sset = { 0,0 };
AcDbObjectIdArray objIdArr; // ID-Array
acutPrintf(L"\nSelect POINT entities: ");
if (acedSSGet(NULL, NULL, NULL, NULL, sset) == RTNORM) {
Selset2ObjIdArray(sset, objIdArr); //imos Funktion
acedSSFree(sset);
}
multiPoint my_multipoint;
AcDbPoint *pointEnt;
Acad::ErrorStatus es;
for (const AcDbObjectId& id : objIdArr) {
AcGePoint3d pos;
if ((es = acdbOpenObject(pointEnt, id, AcDb::kForRead)) == Acad::eOk) {
pos = pointEnt->position();
append(my_multipoint, make<point_xy<double> >(pos.x, pos.y));
pointEnt->close();
}
}
boost::geometry::model::polygon<point_xy<double> > hull;
boost::geometry::convex_hull(my_multipoint, hull);
AcDbDatabase *pDB = acdbHostApplicationServices()->workingDatabase();
AcDbPolyline *pline = new AcDbPolyline();
pline->setDatabaseDefaults(pDB);
using ring = boost::geometry::model::ring<point_xy<double> >;
const ring &rng = hull.outer();
unsigned int ix=0;
for (auto it = rng.begin(); it != rng.end(); ++it)
pline->addVertexAt(ix++, AcGePoint2d(it->x(), it->y()));
postToDb(pline, pDB);
}
Can't find what you're looking for? Ask the community or share your knowledge.