عجائب المتجهات : ( هل النقطة Q داخل المضلّع P ؟ )

يبدو أن السؤال صعب شيئا ما, ولكني حصلت على الحل :)

نقوم بإطلاق خطين من النقطة , بإتجاهين متعاكسين (خط للأعلى و خط للأسفل مثلا) ونقوم بعد الأضلاع التي تتقاطع مع الخط الأول (للأعلى) و كذلك نقوم بعد الأضلاع التي تتقاطع مع الخط الآخر (السفلي) . في حال كانت عدد التقاطعات مع الخط الأول فرديه و عدد التقاطعات مع الخط الثاني فرديه تكون النقطة في داخل المضلع , و إلا تكون خارجه :):)

سؤال البونص إذا فضيت بحله :)

تمت الإجابة بمشاورة الدكتور B) :P

شكرا على الحل يا خلدون . ما دريت انه رح يكون بهذه بالبساطة

اقتباس

في حال كانت عدد التقاطعات مع الخط الأول فرديه و عدد التقاطعات مع الخط الثاني فرديه تكون النقطة في داخل المضلع , و إلا تكون خارجه

على اي اساس؟ هل تستطيع البرهنة على ذلك؟

خلدون خالد2 كتب:

يبدو أن السؤال صعب شيئا ما, ولكني حصلت على الحل :)

نقوم بإطلاق خطين من النقطة , بإتجاهين متعاكسين (خط للأعلى و خط للأسفل مثلا) ونقوم بعد الأضلاع التي تتقاطع مع الخط الأول (للأعلى) و كذلك نقوم بعد الأضلاع التي تتقاطع مع الخط الآخر (السفلي) . في حال كانت عدد التقاطعات مع الخط الأول فرديه و عدد التقاطعات مع الخط الثاني فرديه تكون النقطة في داخل المضلع , و إلا تكون خارجه :):)

سؤال البونص إذا فضيت بحله :)

تمت الإجابة بمشاورة الدكتور B) :P

قصدك نقوم باطلاق شعاعين :) وليس خطين , والمفروض تعد عدد تقاطعات الشعاعين مع محيط المضلع وليس اضلاع المضلع. لانه لو قطع شعاع راس من رؤوس المضلع , فستعتبر عندها هذه الراس كتقاطعين حسب كلامك , لان الشعاع عندها يقطع ضلعين فى نفس الوقت (عند نقطة تقاطعهما). وهذا بالتأكيد سيعطى نتائج خاطئة :)

وعن نفسى , اعتقد انه يكفى ان تطلق شعاع واحد فى اى اتجاه , وتقوم بحساب عدد التقاطعات مع محيط المضلع (وليس اضلاعه) ولو كان عدد التقاطعات فردى فان النقطة داخل المضلع , طالما نضمن ان المضلع مغلق :P وان النقطة محل الدراسة لا تقع على محيط المضلع.

لكن المشكلة الفعليه هى ان تكون النقطه واقعة على محيط المضلع , عندها تفشل الطريقتين فشلا ذريعا :):):)

والاهم من كل هذا , هو كيف ستحسب نقاط التقاطع اصلا؟ وكيف ستعرف اى ضلع قد يقطعه الشعاع وايها لن يقطعه؟

السلام عليكم

اعتقد انه كما قال الأخ خلدون خالد2 ولكن اذا تقاطع الخط الى اعلى بأى عدد وايضا الخط الى اسفل باى عدد تكون النقطه داخل المضلع

ولكن ان تقطع خط واحد فتكون النقطه خارج المضلع

sayedf1 كتب:

السلام عليكم

اعتقد انه كما قال الأخ خلدون خالد2 ولكن اذا تقاطع الخط الى اعلى بأى عدد وايضا الخط الى اسفل باى عدد تكون النقطه داخل المضلع

ولكن ان تقطع خط واحد فتكون النقطه خارج المضلع

ما رايك فى هذه الحالات؟

الموضوع اخى الفاضل مش مجرد اعتقاد ,,,

عفوا .. يبدو أن الشجاعة فقط لاتكفي للحديث عن الرياضيات ..

المضلع يجب أن يكون Convex ( وليس أي مضلع ) ( انظر للمشاركة رقم 1 ) .. حتى تنطبق عليه فكرة الحل بالمتجهات ( التي أعرفها باستخدام dot product ) .. طبقتها مرة ثانية واكتشفت الخطأ الفادح ...اسف جدا على تضييع وقتكم في مضلع ليس Convex :blush:

وبسبب هذا الغلط .. سأعطي درجات الـ Bonus للجميع :) .. وليعذرني الجميع ( عماد - حسن - سيد - خلدون - virtual )

وفي الانتظار .

الشمري كتب:

المضلع يجب أن يكون Convex ( وليس أي مضلع )

وكأحد الحلول بالضرب القياسى كما تطلب.

نفرض ان الرؤوس هى v1 , v2 , ... , vn , وان النقطة هى q

نبدأ بالرأسين v1, v2 ونقوم بحساب المتجه بين v1 و َq وكذلك المتجه بين v2 و q. ومن ثم نقوم بحساب الزاوية بينهما باستخدام الضرب القياسى. وبالمثل مع الرأسين v2, v3 , وهكذا حتى ننتهى بالرأسين vn, v1.

وبجمع هذه الزوايا جميعا , فان كان المجموع 360 درجة , كانت النقطة داخل المضلع. وان كانت اقل من 360 درجة , كانت النقطة خارج المضلع.

هذا والله اعلى واعلم ,,,

السلام عليكم و رحمة الله

اولا اسف على التأخر في الرد و ذلك بسبب الإنشغال

اقتباس

قصدك نقوم باطلاق شعاعين وليس خطين , والمفروض تعد عدد تقاطعات الشعاعين مع محيط المضلع وليس اضلاع المضلع. لانه لو قطع شعاع راس من رؤوس المضلع , فستعتبر عندها هذه الراس كتقاطعين حسب كلامك , لان الشعاع عندها يقطع ضلعين فى نفس الوقت (عند نقطة تقاطعهما). وهذا بالتأكيد سيعطى نتائج خاطئة

وعن نفسى , اعتقد انه يكفى ان تطلق شعاع واحد فى اى اتجاه , وتقوم بحساب عدد التقاطعات مع محيط المضلع (وليس اضلاعه) ولو كان عدد التقاطعات فردى فان النقطة داخل المضلع , طالما نضمن ان المضلع مغلق وان النقطة محل الدراسة لا تقع على محيط المضلع.

لكن المشكلة الفعليه هى ان تكون النقطه واقعة على محيط المضلع , عندها تفشل الطريقتين فشلا ذريعا

أولا: نعم أنا اقصد نطلق شعاعين بإتجاهين متعاكسين إنطلاقا من النقطة المحدده.

ثانيا: بالنسبة لمشكلة النقاط يمكننا أولا أن نعمل فحص بين النقطة المطلوبة مع نقاط المضلع جميعها إذا كانت تقع على إحدا رؤوس هذا المضلع تكون النقطة واقعه على المضلع نفسه !!

اقتباس

وعن نفسى , اعتقد انه يكفى ان تطلق شعاع واحد فى اى اتجاه

يبدو أن هذا صحيح

اقتباس

والاهم من كل هذا , هو كيف ستحسب نقاط التقاطع اصلا؟ وكيف ستعرف اى ضلع قد يقطعه الشعاع وايها لن يقطعه؟

ببساطه نقوم بعمل مصفوفة تحتوي على معادلات (الميل و ال.. m ,b ) كل ضلع من أضلاع المضلع

طبعا لدينا معادلة الشعاعين المنطلقين من النقطة , الآن بإمكاننا معرفة نقاط التقاطع (من خلال مساواة كل معادلة لكل ضلع مع معادلة كل من الشعاعين)

اقتباس

اعتقد انه كما قال الأخ خلدون خالد2 ولكن اذا تقاطع الخط الى اعلى بأى عدد وايضا الخط الى اسفل باى عدد تكون النقطه داخل المضلع

ولكن ان تقطع خط واحد فتكون النقطه خارج المضلع

بالأغلب لا و الدليل في الصورة التي وضعها الأستاذ عماد (الصورة الثالثة)

اقتباس

الموضوع اخى الفاضل مش مجرد اعتقاد ,,,

هذه GIS وليست مجرد إعتقاد :happy:

اقتباس

عفوا .. يبدو أن الشجاعة فقط لاتكفي للحديث عن الرياضيات ..

المضلع يجب أن يكون Convex ( وليس أي مضلع ) ( انظر للمشاركة رقم 1 ) .. حتى تنطبق عليه فكرة الحل بالمتجهات ( التي أعرفها باستخدام dot product ) .. طبقتها مرة ثانية واكتشفت الخطأ الفادح ...اسف جدا على تضييع وقتكم في مضلع ليس Convex

وبسبب هذا الغلط .. سأعطي درجات الـ Bonus للجميع .. وليعذرني الجميع ( عماد - حسن - سيد - خلدون - virtual )

وفي الانتظار .

صراحة لم أفهم ماذا تقصد ب Convex ! :lol: :lol:

تقبلو إحترامي جميعا :)

خلدون خالد2 كتب:

ثانيا: بالنسبة لمشكلة النقاط يمكننا أولا أن نعمل فحص بين النقطة المطلوبة مع نقاط المضلع جميعها إذا كانت تقع على إحدا رؤوس هذا المضلع تكون النقطة واقعه على المضلع نفسه !!

وماذا لو كانت النقطه تقع على ضلع من الاضلاع وليست رأس؟ اى تقع على القطعة المستقيمة بين رأسين!

خلدون خالد2 كتب:

ببساطه نقوم بعمل مصفوفة تحتوي على معادلات (الميل و ال.. m ,b ) كل ضلع من أضلاع المضلع

طبعا لدينا معادلة الشعاعين المنطلقين من النقطة , الآن بإمكاننا معرفة نقاط التقاطع (من خلال مساواة كل معادلة لكل ضلع مع معادلة كل من الشعاعين)

:):):)

الامور ليست بهذه البساطة اخى الكريم. لانه ممكن الشعاع الذى سترسمه , يتقاطع مع احد الخطوط المستقيمة (التى تحمل احد الاضلاع) فى نقطة خارج المضلع. طريقة حل المعادلتين معا ستعطيك نقطة التقاطع بين الشعاع والخط المستقيم فعليا , ولكنه لن يقول لك احذر نقطة التقاطع خارج الضلع محل الدراسة :)

مثلا فى الشكل التالى , تخيل انه معك معادلة الخط المستقيم الذى يحمل الضلع AB ومعك معادلة الشعاع QC. بحل معادلتهما سويا , ستحصل على نقطة التقاطع D وبالتالى هتتحسب عليك تقاطع. فى حين انه اصلا الضلع AB لا يتقاطع مع الخط QC.

ولا تقل لى سنقوم بتحديد الاضلاع التى ستتقاطع مع الخط QC فى البداية , ارجع واقول لك , ماهو ده كان سؤالى اصلا. المفروض ان كل معطياتك هى احداثيات الرؤوس فقط. فكيف لك ان تعرف اى الاضلاع التى تصل بين هذه الرؤوس سيقطع الشعاع المقترح؟ وايها المفروض الا يقطعه؟

اخى الكريم الكلام على بالرسوم الهندسية سهل جدا , لكن المشكله فى كيفية تطبيق هذا الكلام جبريا وحسابيا.

خلدون خالد2 كتب:

صراحة لم أفهم ماذا تقصد ب Convex ! :lol: :lol:

علشان كده طلبت من الاخ الشمرى شرح معناها اولا. وعامة ببحث سريع على النت ستجد التعريف موجود.

بالله التوفيق,,,

بالنسبة لتعريف الـ Convex فهو عكس الـ Concave ..أعتقد التعريف هو ببساطة.. كل زاوية من الزوايا الداخلية أصغر من 180 درجة

( انظر الرابط أحسن :) )

http://www.mathopenref.com/polygonconvex.html

http://www.mathopenref.com/polygonconcave.html

بالنسبة لحل الاخ خلدون ( حقيقة ليس لدي الخلفية الكافية للنقاش .. لذلك يمكن اثبات الحل بكود برمجي قاطع :D .. مع أن المطلوب هو الحل بالمتجهات . )

أما حل الاخ عماد :

اقتباس

وكأحد الحلول بالضرب القياسى كما تطلب.

نفرض ان الرؤوس هى v1 , v2 , ... , vn , وان النقطة هى q

نبدأ بالرأسين v1, v2 ونقوم بحساب المتجه بين v1 و َq وكذلك المتجه بين v2 و q. ومن ثم نقوم بحساب الزاوية بينهما باستخدام الضرب القياسى. وبالمثل مع الرأسين v2, v3 , وهكذا حتى ننتهى بالرأسين vn, v1.

وبجمع هذه الزوايا جميعا , فان كان المجموع 360 درجة , كانت النقطة داخل المضلع. وان كانت اقل من 360 درجة , كانت النقطة خارج المضلع.

فهو حل الصحيح ( ما شاء الله ) .. وقمت بتطبيقه برمجيا ونفّذ بشكل مبهر ..

/*
Method 1 :
The algorithm is written by : Emad Hamdi Ahmad
q :  the point to be tested .
*v : an array of points of a convex polygon.
n :  number of points ( vertices ) .
*/
bool isPointInsidePolygon_1(const Vector2f& q,const Vector2f *v,unsigned short n )
{
		Vector2f u1 ,u2;
		float angle = 0.0;
		for(int i=0;i<n-1;i++)
		{
			u1 = q - v;
			u2 = q - v[i+1];
			angle += Vector2f::angle(u1,u2);
		}
		u1 = q - v[0];
		u2 = q - v[n-1];
		angle += Vector2f::angle(u1,u2);
//		std::cout << angle << std::endl;
		return ((int)angle >= 359 && (int) angle <361);
}

وهناك حل آخر ( لا أعرف اذا كان له علاقة وثيقة بحل الاخ عماد ) وهو كالاتي :

هذا الكتاب .. بسم الله .. دعوني أبحث عن صفحة الحل .. أين هي .. أين هي .. اهه .. صفحة 200 :

1- انظر الى هذه الصورة :

2- الفكرة هي بأن نقوم بعملية الضرب القياسي dot product بين متجهين :

1 - المتجه الأول هو : Q - P1 حيث Q هي النقطة .. و P1 هو أحد رؤوس المصلع .

2 - المتجه الثاني هو : n1 .. حيث n1 هو العمودي على المتجه الأول .

3- الحصول على المتجه الأول سهل ( طرح نقطتين ينتج متجه يبدأ من أحد النقطتين ويتجه للأخرى ) , أما الحصول على المتجه الاخر فنحتاج لايجاد ما يسمّى بالـ Perpendicular أو العمودي بالنسبة للمتجه الأول .. وهو يخضع لهذا التعريف :

وكما قلنا .. ميزة prep أنه عمودي على المتجه الاصلي الذي نتج منه ( ناتج الضرب القياسي = 0 ) ..

4- اذا كان ناتج الضرب بين المتجهين ( في الفقرة 2 ) .. أكبر من صفر ( الزاوية بينهما أقل من 90 ) .. فهذا يعني ان النقطة خارج المضلع .. اما اذا كان ناتج الضرب القياسي اصغر من الصفر فهذا يعني أنه من الممكن ان تكون داخل المضلع .. فننتقل الى بقية المتجهات :

/*
Method 2:
The algorithm is written by : the author of "Computer Graphics Using OpenGL (2nd Edition)"
q :  the point to be tested .
*v : an array of points of a convex polygon.
n :  number of points ( vertices ) .
*/

bool isPointInsidePolygon_2(const Vector2f& q ,const Vector2f *v,unsigned short n)
{
	Vector2f u1;
	Vector2f u2;// prependicular to u1
	bool result = true;
		for(int i=0;i<n-1;i++)
		{
			u1 = v - v[i+1];
			u2 = u1.perp();

			drawArrow(v.x  ,v.y ,v.x + u2.x, v.y + u2.y);

			if( ((q-v)*u2)>0)
				result =  false; // TODO: optimize this by return false directly.
		}
			u1 = v[n-1] - v[0];
			u2 = u1.perp();

			drawArrow(v[n-1].x  ,v[n-1].y ,v[n-1].x + u2.x, v[n-1].y + u2.y);
			if(  ( q - v[n-1]) * u2 > 0)
				result = false;
		return result;

}

الخوارزمية مأخوذة من كتاب Computer Graphics Using OpenGL - الطبعة الثانية - صفحة 200 .

في المرفقات تطبيقان على خوارزمية الاخ عماد والخوارزمية السابقة , مكتوبة بلغة السي بلس و OpenGL ( يكفي ان تنظر الى الملف main.cpp ) .. مع الملف التنفيذي .. حرك الفأرة .. والبرنامج سيخبرك ناتج الخوارزمية ( inside - outside )

----------------------

نأتي للسؤال :

في الصورة التالية .. عند محاولتي حساب perpendicular لكل متجه .. مثلا P0 .. أقوم بهذه العملية :

v = p[0] - p[1];
n2 = v.perp();

ولكن في هذا الحالة .. كيف سيكون اتجاه المتجه v ؟ .. هل سيكون كما في اتجاه السهم الأحمر ؟

أعتقد ذلك .. ولكن سيظهر وكأنه مع عقارب الساعة .. وسيظهر العمودي الى خارج المضلع ..

بينما لو غيرنا الكود السابق الى :

v = p[1] - p[0];
n2 = v.perp();

فان اتجاه المتجه سيكون مع عقارب الساعة .. ولكن سيكون العمودي الى داخل المضلّع .. وستفشل المهمة .

السؤال .. على أي أساس نكتب :

p0 - p1

ولم نكتب

p1 - p0

هل الامر له علاقة بالحركة مع عقارب الساعة أو عكسها ؟

isPointInsideConvexPolygon.zip