凸包

static int ccw(const AcGePoint3d &p1,const AcGePoint3d &p2, const AcGePoint3d &p3)
  {
    double or = (p2.x - p1.x)*(p3.y - p1.y)-(p2.y - p1.y)*(p3.x - p1.x);
    if(or  0.0)
      return 1;
    else return 0;
  }
  static bool PointSortByX(const AcGePoint3d &a, const AcGePoint3d &b)
  {
    if(a.x == b.x)
      return a.y isA() == AcDbPoint::desc())
        {
          AcDbPoint *pPoint = AcDbPoint::cast(pEnt);
          if(pPoint)
          {
           vec.push_back(pPoint->position());
          }
        }
        else if(pEnt->isA() == AcDbLine::desc())
        {
          AcDbLine *pLine = AcDbLine::cast(pEnt);
          if(pLine)
          {
            vec.push_back(pLine->startPoint());
            vec.push_back(pLine->endPoint());
          }
        }
        else if(pEnt->isA() == AcDbPolyline::desc())
        {
          AcDbPolyline *pLine = AcDbPolyline::cast(pEnt);
          if(pLine)
          {
            for(int i = 0 ; i numVerts() ; i++)
            {
              AcGePoint3d pt;
              pLine->getPointAt(i,pt);
              vec.push_back(pt);
            }
          }
        }
      }
    }
  }
  static void sortPoints(PointVector &points, PointVector &ptsout)
  {
    PointVector upper;
    PointVector lower;
    AcGePoint3d left, right;
    PointVector::const_iterator iter;
    PointVector::const_reverse_iterator riter;
    std::sort(points.begin(), points.end(), PointSortByX);
    if(points.size() > 3)
    {
      left = points.front();
      right = points.back();
      for ( size_t i = 0 ; i  1)
      {
        if (ccw(pntQue[1],pntQue[0],points[i]) == 1)
          pntQue.push_front(points[i++]);
        else
          pntQue.pop_front();
      }
      else
        pntQue.push_front(points[i++]);
    }
    for(iter = pntQue.begin(); iter != pntQue.end(); ++iter)
      ptsout.push_back(AcGePoint3d((*iter).x, (*iter).y , (*iter).z));
    
  }
  // - ArxConvexHull._doit command (do not rename)
  static void ArxConvexHull_doit(void)
  {
    PointVector::const_iterator iter;
    PointVector basepoints,sortedPoints;
    getPoints(basepoints);
    sortPoints(basepoints,sortedPoints);
    basepoints.clear();
    grahamScan(sortedPoints,basepoints);
    AcDbPolyline *pline = new AcDbPolyline(basepoints.size());
    for(size_t i = 0 ; i addVertexAt(i,AcGePoint2d(basepoints[i].x,basepoints[i].y));
    pline->setClosed(Adesk::kTrue);
    AddEntityToDataBase(pline);
  }
  static void AddEntityToDataBase(AcDbEntity *pEnt) 
  {
    AcDbDatabase* pDb = acdbHostApplicationServices()->workingDatabase();
    AcDbBlockTableRecordPointer pBTR(pDb->currentSpaceId(), AcDb::kForWrite); 
    if (pEnt && Acad::eOk == pBTR.openStatus())
    {
      pBTR->appendAcDbEntity(pEnt);
      pEnt->close();
    }
  }

kgbfhr5nks5.PNG