Как определить принадлежность точки многоугольнику? (Страница 1 из 2)

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

/*
      Входные данные:
        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 если "внутри"
}

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

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]

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

//
// Варианты взаимного расположения контуров
//
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;
}