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

Подскажите пожалуста как определить лежит ли точка внутри треугольника. Хотелось бы использовать встроеные средства ACad'а а не какую-то собственную математику

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

Тема уже обсуждалась: https://www.caduser.ru/forum/topic14506.html
Похоже без применения "какой-то собственной математики" тебе не обойтись...

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

В стандартной графической библиотеке ObjectARX нет средств, которые бы напрямую позволили определить факт нахождения точки внутри треугольника. Могу тебе предложить такое решение, которое легко обобщается на произвольный замкнутый многоугольник:

static void PointInTriangle(void)
{
  ads_point p1, p2, p3, p;
  if (acedGetPoint(0L,"\nУкажите первую точку треугольника: ",p1) == RTNORM &&
      acedGetPoint(p1,"\nУкажите вторую точку треугольника: ",p2) == RTNORM &&
      acedGetPoint(p2,"\nУкажите третью точку треугольника: ",p3) == RTNORM &&
      acedGetPoint(p3,"\nУкажите точку для проверки: ",       p ) == RTNORM) {
    bool bIn = IsPointInTriangle(asPnt3d(p),asPnt3d(p1),asPnt3d(p2),asPnt3d(p3));
    acutPrintf("\nТочка %sвнутри треугольника!",bIn?"":"не ");
  }
}
static bool IsPointInTriangle(AcGePoint3d p,AcGePoint3d p1,AcGePoint3d p2,AcGePoint3d p3)
{
  const double PI = 3.14159265358979323846;
  AcGeVector3d v1 = p1-p, v2 = p2-p, v3 = p3-p;
  if (v1.length() <= AcGeContext::gTol.equalVector() ||
      v2.length() <= AcGeContext::gTol.equalVector() ||
      v3.length() <= AcGeContext::gTol.equalVector()) {
    // Точка совпадает с одной из вершин
    return true;
  }
  AcGeLineSeg3d s1(p1,p2),s2(p2,p3),s3(p3,p1);
  if (s1.distanceTo(p) <= AcGeContext::gTol.equalPoint() ||
      s2.distanceTo(p) <= AcGeContext::gTol.equalPoint() ||
      s3.distanceTo(p) <= AcGeContext::gTol.equalPoint()) {
    // Точка на одной из сторон треугольника
    return true;
  }
  double ang = v1.angleTo(v2) + v2.angleTo(v3) + v3.angleTo(v1);
  // Если точка внутри треугольника, то сумма углов равна 2*PI
  return fabs(ang - 2*PI) <= 1e-6;
}

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

Опс! Это решение обобщается только на произвольный выпуклый многоугольник.

static void PointInConvexPolygon(void)
{
  AcGePoint3d p,p1;
  AcGePoint3dArray pArr;
  int i=0,rc;
  if (acedGetPoint(0, "\nУкажите точку для проверки: ",asDblArray(p)) == RTNORM) {
    char buf[256]; sprintf(buf,"\nУкажите %d-ую точку полигона: ",++i);
    acedInitGet(1,NULL);
    while (acedGetPoint(asDblArray(p), buf ,asDblArray(p1)) == RTNORM) {
      pArr.append(p1);
      if (i < 3) {
        sprintf(buf,"\nУкажите %d-ую точку полигона: ",++i);
        acedInitGet(1,NULL);
      } else {
        sprintf(buf,"\nУкажите %d-ую точку полигона (ENTER-завершение): ",++i);
      }
    }
  }
  bool bIn = IsPointInConvexPolygon(p,pArr);
  acutPrintf("\nТочка %sвнутри многоугольника!",bIn?"":"не ");
}
static bool IsPointInConvexPolygon(AcGePoint3d p, AcGePoint3dArray pArr)
{
  const double PI = 3.14159265358979323846;
  AcGeVector3dArray vArr;
  int nVert = pArr.length();
  for (int i=0; i < nVert; i++) {
    AcGeLineSeg3d s(pArr[i],pArr[(i+1)%nVert]);
    // Точка на одной из сторон многоугольника
    if (s.distanceTo(p) <= AcGeContext::gTol.equalPoint())
      return true;
  }
  for (int i=0; i < nVert; i++) {
    AcGeVector3d v = pArr[i]-p;
    // Точка совпадает с одной из вершин многоугольника
    if (v.length() <= AcGeContext::gTol.equalVector())
      return true;
    vArr.append(v);
  }
  double ang = 0;
  for (int i=0; i < nVert; i++) {
    ang += vArr[i].angleTo(vArr[(i+1)%nVert]);
  }
  // Если точка внутри выпуклого многоугольника, то сумма углов равна 2*PI
  return fabs(ang - 2*PI) <= 1e-6;
}

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

Раз речь пошла о многоугольниках, то проще наверно так, хотя это на любителя :)

/*
      Входные данные:
        P = точка,
                  V[] = массив точек(узлов) полигона, где общее количество узлов V[n+1]
              и V[n]=V[0]
      Возврат:  0 = снаружи, 1 = внутри
*/
int cn_PnPoly( Point P, Point* V, int n )
{
  int cn = 0;    // количество пересечений
  for (int i=0; i<n; i++)
  {
    if
      (
      ((V[i].y <= P.y) && (V[i+1].y > P.y))
        ||
      ((V[i].y > P.y) && (V[i+1].y <= P.y))
      )
      {
        float vt = (float)(P.y - V[i].y) / (V[i+1].y - V[i].y);
        if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) ++cn;
      }
  }
  return (cn&1);    // 0 если "снаружи", and 1 если "внутри"
}

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

Вот еще один алгоритм (ObjectARX не владею, если интересно могу написать на лиспе)...
Подходит для любого многоугольника.
Находим ближайшее ребро к тестируемой точке, находим угол между ребром и точкой, для многоугольника построенного против часовой стрелки для внутренней точки угол должен быть 0<angle< Pi, если угол angle=0 то точка на ребре...

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

Большое спасибо всем, кто отозвался, я воспользовался следующим методом

bool isPointInTriangle(const AcGePoint3d &a, const AcGePoint3d &b, const AcGePoint3d &c, const AcGePoint3d &p)
{
    AcGePoint3d tmp;
    AcDbDatabase *pDb = acdbHostApplicationServices()->workingDatabase();    
    AcGePoint3d p1 (p.x, p.y, pDb->extmin().z);
    AcGePoint3d p2 (p.x, p.y, pDb->extmax().z);
    AcGeLine3d line (p1, p2);
    AcGeBoundedPlane plane(a, b, c);
    return Adesk::kTrue == plane.intersectWith(line, tmp);
}//CPlnSurfDbAcad::isPointInTriangle

Я хотел метод именно без "какой-то собственной математики" ибо до этого использовал методику которую выше описал Евгений Елпанов.... замучался искать ошибки, решил переложить всё на стндартные методы.

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

> Александр Ривилис
Есть проблема.
Предложенный вами метод сбоит для треугольника
(37156.62, 27717.24),(37139.51, 27723.33), (37137.44, 27711.73) и точки (37144.6671, 27716.9674) IsPointInTriangle возвращает false

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

> Alex9817
Что-то у Вас не так. Возможно разные координаты Z у точек. Я проверил с Вашими данными:

Command: id Specify point:  X = 37137.4400     Y = 27711.7300     Z = 0.0000
Command: id Specify point:  X = 37139.5100     Y = 27723.3300     Z = 0.0000
Command: id Specify point:  X = 37156.6200     Y = 27717.2400     Z = 0.0000
Command: id Specify point: _nod of  X = 37144.6671     Y = 27716.9674     Z = 0.0000
Command: PointInTriangle
Укажите первую точку треугольника:
Укажите вторую точку треугольника:
Укажите третью точку треугольника:
Укажите точку для проверки: _nod of
[b]Точка внутри треугольника![/b]

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

> Александр Ривилис
Вы правы, ещё раз спасибо.
P.S. Приведённый мной метод проверку не прошел

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

> Александр Ривилис
Ещё один вопрос. В вашем коде фигурирует число 1e-6, почему именно такое, почему не 1e-10?

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

> Alex9817

> Alex9817
По поводу Вашего метода - я не хотел Вас огорчать раньше времени - лучше самому разобраться. :)
Я немного модифицировал свой алгоритм. Теперь можно задать направление вектора проекции (в данном примере я использовал VIEWDIR, хотя можно использовать и (0,0,1) и любой другой.

static void PointInTriangle(void)
{
  ads_point p1, p2, p3, p;
  if (acedGetPoint(0, "\nУкажите первую точку треугольника: ",p1) == RTNORM &&
      acedGetPoint(p1,"\nУкажите вторую точку треугольника: ",p2) == RTNORM &&
      acedGetPoint(p2,"\nУкажите третью точку треугольника: ",p3) == RTNORM &&
      acedGetPoint(p3,"\nУкажите точку для проверки: ",p) == RTNORM) {
    // Проверяем попадает ли точка внутрь треугольника в данной точке зрения
    resbuf rb; acedGetVar("VIEWDIR",&rb);
    bool bIn = IsPointInTriangle(asPnt3d(p),asPnt3d(p1),asPnt3d(p2),asPnt3d(p3),asVec3d(rb.resval.rpoint));
    acutPrintf("\nТочка %sвнутри треугольника!",bIn?"":"не ");
  }
}
#define PI  3.14159265358979323846
static bool IsPointInTriangle(AcGePoint3d p,AcGePoint3d p1,AcGePoint3d p2,AcGePoint3d p3,AcGeVector3d norm)
{
  AcGePlane plan(p,norm);
  p  = p.orthoProject(plan);  p1 = p1.orthoProject(plan);
  p2 = p2.orthoProject(plan); p3 = p3.orthoProject(plan);
  AcGeVector3d v1 = p1-p, v2 = p2-p, v3 = p3-p;
  if (v1.length() <= AcGeContext::gTol.equalVector() ||
      v2.length() <= AcGeContext::gTol.equalVector() ||
      v3.length() <= AcGeContext::gTol.equalVector()) {
    // Точка совпадает с одной из вершин
    return true;
  }
  AcGeLineSeg3d s1(p1,p2),s2(p2,p3),s3(p3,p1);
  if (s1.distanceTo(p) <= AcGeContext::gTol.equalPoint() ||
      s2.distanceTo(p) <= AcGeContext::gTol.equalPoint() ||
      s3.distanceTo(p) <= AcGeContext::gTol.equalPoint()) {
    // Точка на одной из сторон треугольника
    return true;
  }
  double ang = v1.angleTo(v2) + v2.angleTo(v3) + v3.angleTo(v1);
  // Если точка внутри треугольника, то сумма углов равна 2*PI
  return fabs(ang - 2*PI) <= 1e-6;
}

Что касается 1e-6, то с учетом погрешностей при вычислениях AutoCAD брать меньшее значение рисковано. А с учетом того, что угол не может превысить 2*PI это достаточно точная оценка. В ряде случаев при 1e-8 я получал ошибочные результаты.

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

Реализация алгоритма предложенного Евгением Елпановым.
Работает для любых многоугольников, кроме самопересекающихся.
bool IsPointInPolygon(const AcGePoint3d &point, const AcGePoint3dArray &polygon)
{
    const AcGePlane plane(polygon[1],polygon[0],polygon[2]);
    /* Проверяем, лежит ли точка в плоскости многоугольника */
    if(plane.isOn(point) == Adesk::kFalse)
    {
        return false;
    }
    const int vert_count = polygon.length();
    double min_dist = -1.0;
    int needed_vert_id = -1;
    /* Находим ближайшую к тестируемой точке сторону многоугольника */
    for(int i = 0; i < vert_count; ++i)
    {
        const AcGePoint3d curr_vert = polygon[i], next_vert = polygon[(i + 1) % vert_count];
        const AcGeLineSeg3d edge(curr_vert,next_vert);
        const AcGePoint3d closest_point = edge.closestPointTo(point);
        const double dist = (point - closest_point).length();
       
        if((dist < min_dist) || (i == 0))
        {
            min_dist = dist;
            needed_vert_id = i;
        }
    }
    const AcGePoint3d start_vert = polygon[needed_vert_id], end_vert = polygon[(needed_vert_id + 1) % vert_count];
    const AcGeVector3d a = end_vert - start_vert, b = point - start_vert, normal = plane.normal();
    /* Определяем угол между ближайшей стороной, и вектором, соединяющим
       начальную вершину ближайшей стороны с тестируемой точкой */
    const double angle = a.angleTo(b,normal);
    const double Pi = 3.1415926535897932384626433832795;
    /* Если угол больше, либо равен Pi - тестируемая точка не лежит в многоугольнике */
    if(angle >= Pi)
    {
        return false;
    }
    return true;
}

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

> explicit
Есть еще функция AcDbMPolygon::isPointInsideMPolygon

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

> Александр Ривилис
А как быть с впуклыми многоугольниками?
Последний приведенный здесь метод в ряде случаев дает неверный рузультат... к сожалению...

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

> bird
Какой именно метод? И почему бы не воспользоваться советом Николая Николаевича с AcDbMPolygon::isPointInsideMPolygon
? Прекрасно работает.

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

> Александр Ривилис
А для его использования AcDbMPolygon должен быть в базе сохранен?

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

> bird
Нет. Совершенно необязательно. Сейчас нет времени, а попозже выложу пример использования.

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

> Александр Ривилис
Пытаюсь использовать
AcDbMPolygon *pol = new AcDbMPolygon();
в одном из методов своего объекта, ругается
"unresolved external symbol LNK2019"
на AcDbMPolygon()...

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

1) Для анализа нахождения точки внутри контура можно создавать объект в стеке, т.е.:
AcDbMPolygon pol;
2) Линкеру укажи использовать AcDbMPolygon16.lib

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

enum PointContourStatus {
  OutsideContour  = -1, // Точка вне контура
  OnContour       =  0, // Точка на контуре
  InsideContour   =  1, // Точка внутри контура
  InternalError   = -99  // Ошибка
};
PointContourStatus is_point_in_curve(AcGePoint3d p, AcGePoint2dArray &pts, AcGeDoubleArray &blgs)
{
  AcDbMPolygon mpol;
  if (mpol.appendMPolygonLoop(pts,blgs) != Acad::eOk) return InternalError;
  AcGeIntArray ar;
  if (mpol.isPointOnLoopBoundary(p,0)) return OnContour;
  if (mpol.isPointInsideMPolygon(p,ar) > 0) return InsideContour;
  else return OutsideContour;
}
PointContourStatus is_point_in_curve(AcGePoint3d p, AcDbCurve *pCurv)
{
  double fuzz = AcGeContext::gTol.equalPoint();
  AcGePoint3d pointOnCurve;
  pCurv->getClosestPointTo(p,pointOnCurve);
  if (p.distanceTo(pointOnCurve) <= fuzz) return OnContour;
  AcDbPolyline   *pPoly   = AcDbPolyline::cast(pCurv);
  AcDb2dPolyline *p2Poly  = AcDb2dPolyline::cast(pCurv);
  AcDbCircle     *pCircle = AcDbCircle::cast(pCurv);
  AcDbMPolygon mpol;
  if (pPoly) {
    if (mpol.appendLoopFromBoundary(pPoly)   != Acad::eOk) return InternalError;
  } else if (p2Poly) {
    if (mpol.appendLoopFromBoundary(p2Poly)  != Acad::eOk) return InternalError;
  } else if (pCircle) {
    if (mpol.appendLoopFromBoundary(pCircle) != Acad::eOk) return InternalError;
  } else return InternalError;
  AcGeIntArray ar;
  if (mpol.isPointInsideMPolygon(p,ar) > 0) return InsideContour;
  else return OutsideContour;
}

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

> Александр Ривилис
Спасибо большое :)

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

> bird
:) Тогда еще одна функция, которая позволяет определить взаимное расположение двух контуров. Я не стал ее переделывать для массива точек и кривизны, так что она работает только с примитивами AcDbPolyline, AcDb2dPolyline, AcDbCircle:

//
// Варианты взаимного расположения контуров
//
enum Contour2ContourStatus {
  ContourInsideContour1  =  1,  // Контур 1 внутри контура 2
  ContourInsideContour2  =  2,  // Контур 2 внутри контура 1
  ContourEqualContour    =  3,  // Контуры совпадают
  ContourOutsideContour  =  4,  // Контуры вне друг друга
  ContourIntersect       =  0,  // Контуры пересекаются
  ContourSelfIntersect1  = -1,  // Первый контур самопересекающийся
  ContourSelfIntersect2  = -2,  // Второй контур самопересекающийся
  ContourInternalError   = -99  // Ошибка
};
// Функция для получения взаимного расположения контуров
Contour2ContourStatus is_curve_in_curve(AcDbCurve *pCurv1, AcDbCurve *pCurv2, double fuzz = AcDbMPolygonCrossingFuzz);
Contour2ContourStatus is_curve_in_curve(AcDbCurve *pCurv1, AcDbCurve *pCurv2, double fuzz)
{
  AcDbPolyline   *pPoly1   = AcDbPolyline::cast(pCurv1);
  AcDb2dPolyline *p2Poly1  = AcDb2dPolyline::cast(pCurv1);
  AcDbCircle     *pCircle1 = AcDbCircle::cast(pCurv1);
  AcDbPolyline   *pPoly2   = AcDbPolyline::cast(pCurv2);
  AcDb2dPolyline *p2Poly2  = AcDb2dPolyline::cast(pCurv2);
  AcDbCircle     *pCircle2 = AcDbCircle::cast(pCurv2);
  AcGePoint2dArray pts;
  AcGeDoubleArray  blg;
  // Проверяем корректность переданных данных
  if (!pPoly1 && !p2Poly1 && !pCircle1) return ContourInternalError;
  if (!pPoly2 && !p2Poly2 && !pCircle2) return ContourInternalError;
  // Проверяем первый контур на самопересечение
  AcDbMPolygon mpol1;
  if (pPoly1) {
    if (mpol1.appendLoopFromBoundary(pPoly1,true,fuzz)   != Acad::eOk) return ContourSelfIntersect1;
  } else if (p2Poly1) {
    if (mpol1.appendLoopFromBoundary(p2Poly1,true,fuzz)  != Acad::eOk) return ContourSelfIntersect1;
  } else if (pCircle1) {
    if (mpol1.appendLoopFromBoundary(pCircle1,true,fuzz) != Acad::eOk) return ContourSelfIntersect1;
  }
  mpol1.getMPolygonLoopAt(0,pts,blg);
  // Проверяем второй контур на самопересечение
  AcDbMPolygon mpol2;
  if (pPoly2) {
    if (mpol2.appendLoopFromBoundary(pPoly2,true,fuzz)   != Acad::eOk) return ContourSelfIntersect2;
    if (mpol1.appendLoopFromBoundary(pPoly2,true,fuzz)   != Acad::eOk) return ContourIntersect;
  } else if (p2Poly2) {
    if (mpol2.appendLoopFromBoundary(p2Poly2,true,fuzz)  != Acad::eOk) return ContourSelfIntersect2;
    if (mpol1.appendLoopFromBoundary(p2Poly2,true,fuzz)  != Acad::eOk) return ContourIntersect;
  } else if (pCircle2) {
    if (mpol2.appendLoopFromBoundary(pCircle2,true,fuzz) != Acad::eOk) return ContourSelfIntersect2;
    if (mpol1.appendLoopFromBoundary(pCircle2,true,fuzz) != Acad::eOk) return ContourIntersect;
  }
  mpol2.appendMPolygonLoop(pts,blg,true,fuzz);
  // Проверяем контуры на нахождение друг в друге
  AcGeIntArray aIdx10,aIdx11,aIdx20,aIdx21;
  mpol1.getChildLoops(0,aIdx10); mpol1.getChildLoops(1,aIdx11);
  mpol2.getChildLoops(0,aIdx20); mpol2.getChildLoops(1,aIdx21);
  if (aIdx10.length()>0 && aIdx20.length()>0) return ContourEqualContour;
  if (aIdx10.length()>0) return ContourInsideContour2;
  if (aIdx11.length()>0) return ContourInsideContour1;
  return ContourOutsideContour;
}

Если найдете ошибки - буду благодарен.

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

> Александр Ривилис
Маленькое примечание: контур должен быть замкнутым, т.е. последняя точка массива должна совпадать с первой, иначе
mpol.appendMPolygonLoop(pts,blgs) будет возвращать ошибку.

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

> bird

А как быть с впуклыми многоугольниками?
Последний приведенный здесь метод в ряде случаев дает неверный рузультат... к сожалению...

bool IsPointInPolygon(const AcGePoint3d &point, const AcGePoint3dArray &polygon) {...}

Это мой код. Хотелось бы знать случаи где он не работает.