السلام عليكم...
لا أدري إن كان هناك من يذكر بعض الخوارزميات الأساسية في الهندسة الفراغية بحيث يمكنه مساعدتي في هذه المسألة البسيطة...
لدينا class برمجي يعبر عن قوس (Arc) في الفراغ ثنائي البعد (2D) من خلال نقطة مركز القوس، نقطة بداية القوس ونقطة النهاية. و class آخر يعبر عن قطعة مستقيمة (Line) من خلال نقطتين (بداية ونهاية) وأيضاً 2D.
سؤالي هنا هو أني أريد كتابة method لتحدد علاقة هذه القطعة المستقيمة مع القوس بحيث تحدد هل القطعة المستقيمة تقطع القوس، أو لا تتقاطع معه، أو تشكل مماس مع القوس...

شكراً...

تعقيباً على السؤال السابق... كنت أحاول كتابة method لحساب الزاوية المركزية للقوس فأشار علي أحد الأصدقاء بالتالي...
Vector A = Center,StartPoint
Vector B = Center,EndPoint
dotProduct Vector A . Vector B
حساب aCos للقيمة الناتجة لتكون هي قيمة الزاوية...
المشكلة هنا أن الزاوية الناتجة هي دائماً الزاوية الصغيرة أي حتى ولو كانت زاوية القوس أكبر من 180 فسيحسب الزاوية الأصغر.
أعلم انه قد تكون هناك methods جاهزة لحساب قيمة الزاوية بشكل صحيح ولكني أود الحصول على المبدأ الرياضي لها...

شكراً...

هذه المشكلة اللعينة معروفة في الرياضيات الجيومترية وتسبب الكثير من الصداع لمن يحاولون إيجاد الزوايا بين المتجهات. السبب منطقي جداً وهو أن cosine زاوية يأخذ البعد الأفقي x بعين الاعتبار فقط. لتفادي المشكلة، نحتاج إلى تابع رياضي يأخذ كل من x و y المتجه المشكل للزاوية بعين الاعتبار. atan قد يفي بالغرض، لكنه سيسبب لك المزيد من الصداع بسبب أرباع الدائرة. في C، هناك الإجراء atan2 وهو الوحيد القادر على التمييز وإعطاء نتيجة مرضية لمثل هذه الزوايا (وهو يأخذ كل من x و y المتجه طبعاً). مجال atan2 يبدأ من 0 وحتى 360.

في الكود التالي ستجد برنامج ++C يقوم بحساب نقطة التقاطع. نقطة ضعفه هي نفس المشكلة التي ذكرتها أنت (يستخدم الـ dot والـ acos لإيجاد زاوية القوس). عدلها وستحصل على إجراء جاهز...

#include  // for printf
#include 

const double kEpsilon = 0.00001;

struct VECTOR2D { double x,y; };

enum IntersectionType
{
	Intersection_None,
	Intersection_Tangent,
	Intersection_OnePoint,
	Intersection_TwoPoints
};

IntersectionType LineCircle(const VECTOR2D& vec2CircleCenter,double dRadius,
							const VECTOR2D& vec2LineStart,const VECTOR2D& vec2LineEnd,
							VECTOR2D& vec2OutPoint1,VECTOR2D& vec2OutPoint2)
{
	// Simplify calculations by moving the circle to 0,0 and bringing the line along with it
	VECTOR2D vec2LS = { vec2LineStart.x-vec2CircleCenter.x, vec2LineStart.y-vec2CircleCenter.y };
	VECTOR2D vec2LE = { vec2LineEnd.x-vec2CircleCenter.x, vec2LineEnd.y-vec2CircleCenter.y };

	// Difference between line start and end
	double dDX = vec2LE.x - vec2LS.x;
	double dDY = vec2LE.y - vec2LS.y;

	double a = dDX*dDX + dDY*dDY;
	double b = 2.0 * (dDX*vec2LineStart.x + dDY*vec2LineStart.y);
	double c = vec2LineStart.x*vec2LineStart.x + vec2LineStart.y*vec2LineStart.y - dRadius*dRadius;
	double dDiscriminant = b*b - 4*a*c;

	// It's a tangent line if the discriminant is 0. Note that due to number
	// imprecisions, the value could be near 0, but not absolutely 0...
	if ((dDiscriminant > -kEpsilon) && (dDiscriminant < kEpsilon))
	{
		double dU = -b/(2.0*a);
		vec2OutPoint1.x = vec2LineStart.x + dU * (vec2LineEnd.x-vec2LineStart.x);
		vec2OutPoint1.y = vec2LineStart.y + dU * (vec2LineEnd.y-vec2LineStart.y);

		vec2OutPoint2 = vec2OutPoint1;
		return Intersection_Tangent;
	}

	// No intersection if discriminant is less than 0
	if (dDiscriminant < 0.0)
		return Intersection_None;

	// So this is a secant line (has two intersection points with the circle)

	// First point
	double dU1 = (-b + sqrt(dDiscriminant)) / (2.0*a);
	vec2OutPoint1.x = vec2LineStart.x + dU1 * (vec2LineEnd.x-vec2LineStart.x);
	vec2OutPoint1.y = vec2LineStart.y + dU1 * (vec2LineEnd.y-vec2LineStart.y);

	// Second point
	double dU2 = (-b - sqrt(dDiscriminant)) / (2.0*a);
	vec2OutPoint2.x = vec2LineStart.x + dU2 * (vec2LineEnd.x-vec2LineStart.x);
	vec2OutPoint2.y = vec2LineStart.y + dU2 * (vec2LineEnd.y-vec2LineStart.y);

	return Intersection_TwoPoints;
}

bool IsPointInLine(const VECTOR2D& vec2Point,const VECTOR2D& vec2LineStart,const VECTOR2D& vec2LineEnd)
{
	// Line length
	double dDX = vec2LineEnd.x-vec2LineStart.x;
	double dDY = vec2LineEnd.y-vec2LineStart.y;
	double dLineLength = sqrt(dDX*dDX+dDY*dDY);

	// Distance between point and line start
	double dDX1 = vec2Point.x-vec2LineStart.x;
	double dDY1 = vec2Point.y-vec2LineStart.y;
	double dPtToStartDistance = sqrt(dDX1*dDX1+dDY1*dDY1);

	// Distance between point and line end
	double dDX2 = vec2Point.x-vec2LineEnd.x;
	double dDY2 = vec2Point.y-vec2LineEnd.y;
	double dPtToEndDistance = sqrt(dDX2*dDX2+dDY2*dDY2);

	// It's outside the line if the sum of the distance to the two line
	// points doesn't equal the line length
	if (dPtToStartDistance+dPtToEndDistance > dLineLength)
		return false;

	// It's on the line
	return true;
}

bool IsPointInArc(const VECTOR2D& vec2Point,const VECTOR2D& vec2ArcCenter,
				  const VECTOR2D& vec2ArcStart,const VECTOR2D& vec2ArcEnd)
{
	// Point position in relation to arc center
	VECTOR2D vec2Pt = {vec2Point.x-vec2ArcCenter.x, vec2Point.y-vec2ArcCenter.y};
	double dPointToArcCenterDistance = sqrt(vec2Pt.x*vec2Pt.x+vec2Pt.y*vec2Pt.y);

	// Normalize into a direction
	vec2Pt.x /= dPointToArcCenterDistance;
	vec2Pt.y /= dPointToArcCenterDistance;

	double dDX = vec2ArcStart.x-vec2ArcCenter.x;
	double dDY = vec2ArcStart.y-vec2ArcCenter.y;
	double dCircleRadius = sqrt(dDX*dDX+dDY*dDY);

	if (fabs(dPointToArcCenterDistance-dCircleRadius) > kEpsilon)
		return false; // The point is not even on the circle!

	double dDX1 = (vec2ArcStart.x-vec2ArcCenter.x)/dCircleRadius;
	double dDY1 = (vec2ArcStart.y-vec2ArcCenter.y)/dCircleRadius;
	double dDX2 = (vec2ArcEnd.x-vec2ArcCenter.x)/dCircleRadius;
	double dDY2 = (vec2ArcEnd.y-vec2ArcCenter.y)/dCircleRadius;
	double dArcAngle = acos(dDX1*dDX2+dDY1*dDY2);

	double dPtToArcStartAngle = acos(vec2Pt.x*dDX1+vec2Pt.y*dDY1);
	double dPtToArcEndAngle = acos(vec2Pt.x*dDX2+vec2Pt.y*dDY2);

	// It's outside the arc if the sum of the angles between it
	// and the arc end points doesn't equal the arc's angle
	if (dPtToArcStartAngle+dPtToArcEndAngle > dArcAngle)
		return false;

	// It's on the arc
	return true;
}

IntersectionType LineArcIntersect(const VECTOR2D& vec2LineStart,const VECTOR2D& vec2LineEnd,
								  const VECTOR2D& vec2ArcCenter,const VECTOR2D& vec2ArcStart,
								  const VECTOR2D& vec2ArcEnd,
								  VECTOR2D& vec2OutPt1,VECTOR2D& vec2OutPt2)
{
	double dDX = vec2ArcStart.x-vec2ArcCenter.x;
	double dDY = vec2ArcStart.y-vec2ArcCenter.y;
	double dCircleRadius = sqrt(dDX*dDX+dDY*dDY);

	IntersectionType intersectType = LineCircle(vec2ArcCenter,dCircleRadius,
		vec2LineStart,vec2LineEnd,vec2OutPt1,vec2OutPt2);

	// Check if the line and the circle containing the arc intersect
	if (intersectType == Intersection_None)
		return Intersection_None;

	if (intersectType == Intersection_Tangent)
	{
		if (IsPointInArc(vec2OutPt1,vec2ArcCenter,vec2ArcStart,vec2ArcEnd) &&
			IsPointInLine(vec2OutPt1,vec2LineStart,vec2LineEnd))
			return Intersection_Tangent; // Output tangent point is in vec2OutPt1
		return Intersection_None;
	}

	// We have two intersection points... It's enough if one of them is actually contained
	// in both the line and the arc...

	bool bPoint1Valid = false;
	if ( IsPointInArc(vec2OutPt1,vec2ArcCenter,vec2ArcStart,vec2ArcEnd) &&
		 IsPointInLine(vec2OutPt1,vec2LineStart,vec2LineEnd) )
	{
		bPoint1Valid = true;
	}

	bool bPoint2Valid = false;
	if ( IsPointInArc(vec2OutPt2,vec2ArcCenter,vec2ArcStart,vec2ArcEnd) &&
		 IsPointInLine(vec2OutPt2,vec2LineStart,vec2LineEnd) )
	{
		bPoint2Valid = true;
	}

	if (bPoint1Valid && bPoint2Valid)
		return Intersection_TwoPoints; // Output points are in vec2OutPt1 and vec2OutPt2

	if (bPoint2Valid)
	{
		vec2OutPt1 = vec2OutPt2;
		return Intersection_OnePoint; // Output point is in vec2OutPt1
	}

	if (bPoint1Valid)
		return Intersection_OnePoint; // Output point is in vec2OutPt1

	return Intersection_None; // All intersecting points don't fall on the line piece nor on the arc
}

void main(void)
{
	// Inputs
	VECTOR2D vec2ArcCenter = {0,0};
	VECTOR2D vec2ArcStart = {0,10};
	VECTOR2D vec2ArcEnd = {10,0};
	VECTOR2D vec2LineStart = {-10,5};
	VECTOR2D vec2LineEnd = {10,5};

	// Outputs
	IntersectionType itype;
	VECTOR2D vec2Point1;
	VECTOR2D vec2Point2;

	itype = LineArcIntersect(
		vec2LineStart,vec2LineEnd,
		vec2ArcCenter,vec2ArcStart,vec2ArcEnd,
		vec2Point1,vec2Point2);

	// Show the result
	switch (itype)
	{
	case Intersection_None:
		printf("Line and arc don't intersect\n");
		break;
	case Intersection_Tangent:
		printf("Line is tangent to arc at (%f,%f)\n",vec2Point1.x,vec2Point1.y);
		break;
	case Intersection_OnePoint:
		printf("Line intersects arc once at (%f,%f)\n",vec2Point1.x,vec2Point1.y);
		break;
	case Intersection_TwoPoints:
		printf("Line intersects arc twice at (%f,%f) and (%f,%f)\n",
			vec2Point1.x,vec2Point1.y,vec2Point2.x,vec2Point2.y);
		break;
	}
}

يبدو لي هذا هو الحل الذي يمكن القول عنه على موقع (طبق) من ذهب... شكراً جزيلاً على الكود...أعتقد أن هذا المنتدى يحض أمثالي على التكاسل بالفعل...
بالمناسبة تفاجأت بفكرة أن يكون النموذج الرياضي لحساب تقاطع مستقيم مع دائرة هو معادلة من الدرجة الثانية... طريقة بسيطة ومنطقية... ولكن كنت أحاول أن أقوم بتحليل الإسقاطات الجيومترية لعوامل المعادلة المحسوبة... (a)، (b) و (c).
أتمنى أن توضحها لي إن أمكن أو تدلني على المرجع المناسب لفهم مدلولاتها الهندسية كيفية استنتاجها...
شكراً...

الفكرة ببساطة إيجاد النقاط التي تحقق كل من معادلة الدائرة والمستقيم في نفس الوقت. من هذا المبدأ يمكننا وضع معادلة المستقيم في طرف (aX+bY+c=0) ومعادلة الدائرة في طرف آخر (x*x+y*y-r*r=0) ثم إيجاد الحل لكل من x و y. طبعاً المعادلة من الدرجة الثانية كما نرى بسبب معادلة الدائرة. هكذا ينتج لدينا إما حلان، حل وحيد (مماس)، أو لا حل على الإطلاق...

هذه الصفحة تعطي شرحاً أكثر عن اشتقاق المعادلات إياها:
http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/

طبعاً هناك الخطوة الإضافية بعد إيجاد نقاط التقاطع، وهي التحقق من أن هذه النقاط تقع ضمن قطعة المستقيم المحددة والقوس الذي يقع على محيط الدائرة إياها.