ObjectARX
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 

Can the convex hull code be faster and more concise.

1 REPLY 1
SOLVED
Reply
Message 1 of 2
463017170
331 Views, 1 Reply

Can the convex hull code be faster and more concise.

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

 

1 REPLY 1
Message 2 of 2
tbrammer
in reply to: 463017170

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

 


Thomas Brammer ● Software Developer ● imos AGLinkedIn
If an answer solves your problem please [ACCEPT SOLUTION]. Otherwise explain why not.

Can't find what you're looking for? Ask the community or share your knowledge.

Post to forums  

AutoCAD Inside the Factory


Autodesk Design & Make Report