Determine if the point is inside closed curve

[majklha]

I have AcGeCurve2d or AcDbCurve2d and AcGePoint2d. They are closed. How I determine, if the point is inside the curve?

I know mathematical methods for it, but, do Autocad classes have some easier build-in function?

[tbrammer]

As far as I know there is no such function that you can use directly.

But it is easy to write a function that uses the "Ray casting algorithm" with class AcGeCurveCurveInt2d. 

1. Construct an AcGeRay2d ray(pt,v); with the point pt you want to test. The direction  v is arbitrary.
2. Construct an AcGeCurveCurveInt2d sect(ray, curve); object with your AcGeCurve2d and the ray.
3. int count = sect.numIntPoints(); is the number of intersection points.
4. Determine the number n of intersections on which the ray's path does not change from one side of curve to the other side. See below.
5. If (count-n) it is odd pt is inside curve. If it is even the point is outside curve.

For step 4 you can use

AcGeCurveCurveInt2d::getIntConfigs(
	int intNum, 
	AcGe::AcGeXConfig& config1wrt2, 
	AcGe::AcGeXConfig& config2wrt1
) const;

to analyze whether the ray's path changes from one side of the curve to the other side at each section point.

If you happen to find an AcGeXConfig of kind kOverlapXXX or kXXXOverlap you could either retry with a different ray direction vector v or check the previous/next sectionpoint.

I think you can even get a direct result if you add the results of the function below using the xcfg values of the ray:

int CountLR(AcGe::AcGeXConfig xcfg)
{
	switch (xcfg)
	{
		case AcGe::kLeftRight:     return  2;
		case AcGe::kRightLeft:     return -2;
		case AcGe::kLeftLeft:      return  0;
		case AcGe::kRightRight:    return  0;
		case AcGe::kLeftOverlap:   return  1;
		case AcGe::kOverlapLeft:   return -1;
		case AcGe::kRightOverlap:  return -1;
		case AcGe::kOverlapRight:  return  1;
		case AcGe::kOverlapOverlap:return  0;
											
		// not sure about these:            
		case AcGe::kOverlapStart:  return  0;
		case AcGe::kOverlapEnd:    return  0;
		case AcGe::kPointLeft:     return -1;
		case AcGe::kPointRight:    return  1;
		case AcGe::kNotDefined:    return  0; 
		case AcGe::kUnknown:       return  0;
	}
}

The sum could be

• -2  => pt is inside. curve runs clockwise.
• -1 => pt is on curve. curve runs clockwise.
• 0 => pt is outside curve. curve may be cw or ccw.
• 1 => pt is on curve. curve runs counter clockwise.
• 2  => pt is inside. curve runs counter clockwise.
• Other values: Something went wrong or curve is self-intersecting and winds multiple times around pt.

I didn't try this myself yet and would be interested if someone uses this method. Please comment!

[majklha]

Thanks, I seems usable, I an going to try it. But I got stuck immediately on start - I am not able to transfer polyline or spline to AcGeCurve2d.

I select in drawing eg. polyline - AcDbPolyline, the child of the AcDCurve. But AcDbCurve has method only to transfer to AcGeCurve3d.... And AcGeCurve3d is virtual, we must use AcGeSpline3d.....and I dont know hoe to trasfer AcGeSpline3d to AcGeSpline2d....

And with Ray (I wanted to check it first with user-defined ray) is the same problem: AcDbRay-AcDbCurve->AcGeCurve3d...

Maybe it is the basic knowlege, I am sorry for that easy question.

[majklha]

Problem with ray I solved 

	AcGePoint3d ptRay;
	pRay->getStartPoint(ptRay);
	AcGeRay2d geRay(asPnt2d(ptRay), asVec2d(pRay->unitDir()));

[Alexander.Rivilis · Accepted solution]

Other method with using AcDbMPolygon class:

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

P 

[majklha]

It seems to be easier, but not applicable for spline and other "strange" curves.

Maybe it will be quicker.

For me it is sufficient. I need it for cadastral plots.

I am going to test both. Thanks.

[Alexander.Rivilis]

---

@majklha wrote:

It seems to be easier, but not applicable for spline and other "strange" curves.

Maybe it will be quicker.

For me it is sufficient. I need it for cadastral plots.

I am going to test both. Thanks.

---

For any other type of AcDbCurve you can:

1) use AcDbCurve::getAcGeCurve method to get AcGeCurve3d

2) use AcGeCurve3d::getSamplePoints  to get points for curve approximation

3) convert AcGePoint3dArray to AcGePoint2dArray 

4) use is_point_in_curve(AcGePoint3d p, AcGePoint2dArray &pts, AcGeDoubleArray &blgs) method

[tbrammer · Accepted solution]

---

@Alexander.Rivilis wrote:

1) use AcDbCurve::getAcGeCurve method to get AcGeCurve3d

2) use AcGeCurve3d::getSamplePoints  to get points for curve approximation

3) convert AcGePoint3dArray to AcGePoint2dArray 

4) use is_point_in_curve(AcGePoint3d p, AcGePoint2dArray &pts, AcGeDoubleArray &blgs) method

---

If you are using a polygon build of sample points instead of "real curves" I would advice to use the "Winding number algorithm" and calculate subtended angles which is very easy and effective to implement for polygons.

To create an AcGeCurve from a polyline:

In case of an AcDbPolyline that consists of lines and arcs only you can construct an AcGeCompositeCurve2d that consists of AcGeCircArc2d and AcGeLine2d elements.

For an exact spline curve you can try this:
1) AcDbCurve::getSpline(AcDbSpline*& spline) const;

2) AcDbSpline::getNurbsData(int& degree, Adesk::Boolean& rational,
  Adesk::Boolean& closed, Adesk::Boolean& periodic,
  AcGePoint3dArray& controlPoints, AcGeDoubleArray& knots,
  AcGeDoubleArray& weights, double& controlPtTol, double& knotTol
);

3) Convert AcGePoint3dArray controlPoints to AcGePointdArray cntrlPnts

4) construct a AcGeNurbCurve2d with
AcGeNurbCurve2d nurb(int degree,
const AcGeKnotVector& knots, const AcGePoint2dArray& cntrlPnts,
const AcGeDoubleArray& weights, Adesk::Boolean isPeriodic
);

5) Set open/closed/rational:
if (closed)
   nurb.makeClosed();
else
  nurb.makeOpen();
if (rational)
  nurb.makeRational();

[majklha]

You must include "dbMPolygon.h" and link "AcMPolygonObj.lib"

[Alexander.Rivilis]

Yes of course.

[majklha]

And bulges is diametr of circle part of polygon? And for lines it expected "0"?

[Alexander.Rivilis · Accepted solution]

 For straight segment bulge equal 0 (if bulge < 1e-6 segment is straight)