• bird
  • Восстановленный участник
  • На форуме с 30 ноября 2005г.
  • Сообщений: 30
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

> explicit
Я тестировал на "крестике"
(50,0)
(50,50)
(0,50)
(0,100)
(50,100)
(50,150)
(100,150)
(100,100)
(150,100)
(150,50)
(100,50)
(100,0)

  • bird
  • Восстановленный участник
  • На форуме с 30 ноября 2005г.
  • Сообщений: 30
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Ой, забыл добавить, эти точки опрделяют многоугольник - наследнике полилинии,
Определял "впуклость" вершин, для этого брал весь контур, кроме проверяемой вершины и запускал в вашу функцию, ну и все это в цикле:

AcGePoint3d pw;
AcGePoint3dArray rtte;
for (int i=0;i<this->numVerts();i++)
{
rtte.setPhysicalLength(0);
for (int w=0;w<this->numVerts();w++)
{
  if (w!=i)
     {
         this->getPointAt(w,pw);rtte.append(pw);      }
}
this->getPointAt(i,pw);
if (IsPointInPolygon2(pw,rtte)) acutPrintf("%d\n",i);
...

  • Откуда: Украина / Киев
  • На форуме с 15 апреля 2005г.
  • Сообщений: 8,666
  • Спасибо: 158

Re: Как определить принадлежность точки многоугольнику?

> explicit
В алгоритме не учтен вариант, когда первые три точки полигона находятся на одной прямой.

> bird
Этот алгоритм работает для многоугольника направленного против часовой стрелки, как написал Евгений Елпанов, а этот - по часовой. Так что ничего удивительного.

  • teolog
  • Восстановленный участник
  • На форуме с 27 апреля 2006г.
  • Сообщений: 1
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Смотреть сюда
http://forums.realcoding.net/index.php? … entry55123

  • Sandrick
  • Восстановленный участник
  • На форуме с 13 января 2006г.
  • Сообщений: 96
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Есть в стандартной библиотеке ObjectARX класс AcBrBrep. С помощью этого класса проверяется принадлежность точки к любой форме РЕГИОНА при помощи функции AcBrEntity::getPointContainment

  • supremum
  • Восстановленный участник
  • На форуме с 27 ноября 2006г.
  • Сообщений: 53
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

А у меня была идея от точки на каждую вершину опустить по лучу, и если сумма площадей образованных "треугольников" равна площади замкнутой полилинии - то значит точка лежит внутри. Это для выпуклого.
Для не выпуклого:
делим на выпуклые, и рекурсивно проверяем, лежит ли точка внутри какого либо из не выпуклых !

  • supremum
  • Восстановленный участник
  • На форуме с 27 ноября 2006г.
  • Сообщений: 53
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Жесть какая-то с этим AcBrBrep.
Во-первых brbrep.h лежит отдельно в C:\ObjectARX2006\utils\brep\inc
Во-вторых после подключения brbrep.h и внесения lib- и inc- папок в настройках проджекта остается следующая проблема:
по описанию AcBr::ErrorStatus set(const AcDbEntity& entity); , где entity - это AcDb3dSolid, AcDbRegion or AcDbBody. Но обе конструкции выдают одну и тоже ошибку:

AcDbRegion *reg;
//или AcDbEntity *reg;
........
AcBrBrep *tp = new AcBrBrep;
tp->set(reg);

acrxEntryPoint.cpp(222) : error C2664: 'AcBr::ErrorStatus AcBrEntity::set(AcBrBrepData *)' : cannot convert parameter 1 from 'AcDbRegion *' to 'AcBrBrepData *'
        Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast
AcBrBrepData вообще не описано

  • supremum
  • Восстановленный участник
  • На форуме с 27 ноября 2006г.
  • Сообщений: 53
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Нашел в StdAfx.h строку
//#define _BREP_SUPPORT_            //- Support for the BRep API
Раскоментил - эффекта нет.

  • supremum
  • Восстановленный участник
  • На форуме с 27 ноября 2006г.
  • Сообщений: 53
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Просмотрел...надо делать так

        ads_name name;
        ads_point pt;
        AcDbObjectId eId;
        AcDbVoidPtrArray ar, regions;
        AcDbRegion reg;
        AcGe::PointContainment ppp;
        AcBrEntity *be;
        acedEntSel("Укажите полигон\n", name, pt);
        acdbGetObjectId(eId,name);
        AcDbObjectPointer<AcDbCurve> pline(eId,AcDb::kForRead) ;
        ar.setLogicalLength(1);
        ar[0] = pline.object();
        reg.createFromCurves(ar,regions);
        AcBrBrep *tp = new AcBrBrep;
        tp->set(reg);
        acedGetPoint(NULL,"Укажи точку", pt);
        AcGePoint3d pt3= AcGePoint3d(pt[0],pt[1],0);
        AcBr::ErrorStatus err = tp->getPointContainment(pt3,ppp,be);
        switch(ppp)
        {
        case AcGe::kOutside: acedAlert("Out"); break;
        case AcGe::kInside: acedAlert("In"); break;
        case AcGe::kOnBoundary: acedAlert("On"); break;
        default:
            switch(err)
            {
            case AcBr::eInvalidObject: acedAlert("eInvalidObject"); break;
            case AcBr::eBrepChanged: acedAlert("eBrepChanged"); break;
            case AcBr::eAmbiguousOutput: acedAlert("eAmbiguousOutput"); break;
            case AcBr::eOutOfMemory: acedAlert("eOutOfMemory"); break;
            default: acedAlert("Other err");
            }
        }

Но при этом getPointContainment выдает какую-то неопознанную ошибку - постоянно вылетает "Other err" sad

  • Откуда: Украина / Киев
  • На форуме с 15 апреля 2005г.
  • Сообщений: 8,666
  • Спасибо: 158

Re: Как определить принадлежность точки многоугольнику?

> supremum
Кто сказал, что делать нужно так? :)

  • supremum
  • Восстановленный участник
  • На форуме с 27 ноября 2006г.
  • Сообщений: 53
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

Ну я сам решил разобраться с AcBrEntity::getPointContainment, и наваял ))
А как надо ? )))

  • Откуда: Украина / Киев
  • На форуме с 15 апреля 2005г.
  • Сообщений: 8,666
  • Спасибо: 158

Re: Как определить принадлежность точки многоугольнику?

Выглядеть это должно где-то так:

static void BrepPointCheckPoint(void)
{
  Acad::ErrorStatus es;
  AcBr::ErrorStatus ebr;
  ads_name en;
  ads_point pt;
  if (acedEntSel("\nУкажите контур: ", en, pt) != RTNORM)
    return;
  AcDbObjectId eId; acdbGetObjectId(eId,en);
  AcDbObjectPointer<AcDbCurve> pline(eId,AcDb::kForRead) ;
  if ((es = pline.openStatus()) != Acad::eOk) {
    acutPrintf("\npline.openStatus()=%s",acadErrorStatusText(es));
    return;
  }
  if (acedGetPoint(pt,"\nУкажите точку: ", pt) != RTNORM)
    return;
  AcDbVoidPtrArray ar, regions;
  ar.append(pline.object());
  if ((es = AcDbRegion::createFromCurves(ar,regions)) != Acad::eOk)  {
    acutPrintf("\nAcDbRegion::createFromCurves(ar,regions)=%s",acadErrorStatusText(es));
    return;
  }
  AcDbRegion reg; reg.copyFrom((AcDbRegion *)regions[0]);
  for (int i=0; i<regions.length();i++) delete regions[i];
  AcBrBrep brEnt;  ebr = brEnt.set(reg);
  if (ebr != AcBr::eOk) {
    acutPrintf("\nbrEnt.set(sol)=%s",acadErrorStatusText((Acad::ErrorStatus)(Adesk::UInt32)ebr));
    return;
  }
  AcGe::PointContainment pDesc;
  AcBrEntity *pCont = NULL;
  AcBrBrepFaceTraverser brepFaceTrav; brepFaceTrav.setBrep(brEnt);
  AcBr::ErrorStatus err = AcBr::eInvalidInput;
  while (!brepFaceTrav.done()) {
   AcBrFace brFace; brepFaceTrav.getFace(brFace);
   err = brFace.getPointContainment(asPnt3d(pt),pDesc,pCont);
   if (err == Acad::eOk && pDesc == AcGe::kInside) {
     acedAlert("In"); return;
   } else if (err == Acad::eOk && pDesc == AcGe::kOnBoundary) {
     acedAlert("On"); return;
   }
   brepFaceTrav.next();
  }
  if (err == Acad::eOk) {
    acedAlert("Out");
  } else {
    acedAlert("Unknown error");
  }
  return;
}

Ответ от Barmaleus (изменено: Сергей Гнусарев, 20 декабря 2015г. 10:15:25)

  • На форуме с 20 декабря 2015г.
  • Сообщений: 1
  • Спасибо: 0

Re: Как определить принадлежность точки многоугольнику?

bool point_in_polygon(const AcGePoint3d &test,const AcGePoint3dArray &polygon)
{    const double tol=0.001;//Погрешность
    long i,n;
    static const int q_patt[2][2]= { {0,1}, {3,2} };
    n=polygon.length();
    if (n<3){
        return false;
    }
   
    //Проверка лежит ли точка на контуре   
    AcGePoint3d cur_pt;
    AcGePoint3d pred_pt=polygon[n-1];
    double s0,s1,s2;
    for (i=0;i<n;i++){
        cur_pt=polygon[i];
        s0=pred_pt.distanceTo(cur_pt);
        s1=pred_pt.distanceTo(test);
        s2=cur_pt.distanceTo(test);
        if (fabs(s0-s1-s2)<tol){
            return true;//точка на контуре
        }
        pred_pt = cur_pt;
    }

        //Проверка лежит ли точка внутри контура
    pred_pt.x-=test.x;
    pred_pt.y-=test.y;
    int pred_q=q_patt[pred_pt.y<0][pred_pt.x<0];
    int w=0;
    pred_pt=polygon[n-1];
    for (i=0;i<n;i++){   
        cur_pt=polygon[i];
        cur_pt.x-=test.x;
        cur_pt.y-=test.y;
        int q=q_patt[cur_pt.y<0][cur_pt.x<0];
        switch (q-pred_q){
            case -3:++w;break;
            case 3:--w;break;
            case -2:if(pred_pt.x*cur_pt.y>=pred_pt.y*cur_pt.x) ++w;break;
            case 2:if(!(pred_pt.x*cur_pt.y>=pred_pt.y*cur_pt.x)) --w;break;
        }
        pred_pt = cur_pt;
        pred_q = q;
    }
    return w!=0;
}