نقطة داخل مثلث؟

السلام عليكم,

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

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

والله اعلم

السلام عليكم

لدي طريقة لكن غير متاكد (غير متاكد منها طبعا لست خبير لكن مشاركة):

لتكن نقاط المثلث (أ ب ج) والنقطة تحت البحث د.

نوجد |أ ب| و |أ ج| و | ب ج| وناخذ اطولها ل1= أكبر{|أ ب| , |أ ج| , | ب ج|}

نوجد الان |دأ| و |دب| و |دج| وناخذ اطولها ل2=أكبر{|دأ| , |دب| , |دج|}

أذا كان ل2< ل1 فإن د تقع في المثلث.

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

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

romanof كتب:

لنفترض ان لدينا رؤوس مثلث معطاة  بواسطة  احداثياتها (x,y ) 

ولدينا نقطة رابعة ؟ كيف نحدد ان نقطة الاخيرةا تقع داخل هذا المثلث ؟

ممنوع مشاركة احمد غريب وايكوسان  :P

←

لماذا يا أخي romanof هذا المنع :huh: ...من حقي أن أدلي بمحاولتي, وأظن أنها لن تكون الأفضل, وسيأتي الأخوة بأمثلة جد قوية و بسيطة.

ليكن المثلث (A,B,C) والنقطة P.

النقطة P توجد داخل المثلث إذا وفقط إذا حققت الثلاث شروط التالية:

- النقطة P توجد في نفس الجهة التي توجد فيها النقطة C بالنسبة للمستقيم (AB).

- النقطة P توجد في نفس الجهة التي توجد فيها النقطة B بالنسبة للمستقيم (AC).

- النقطة P توجد في نفس الجهة التي توجد فيها النقطة A بالنسبة للمستقيم (BC).

يعني أرى أن نحسب معادلة كل المستقيمات التلاث y=ax+b و نتحقق أن الجداء التالي موجب: (a . Px - Py + b )(a . TrdPx - TrdPy + c )

حيث Px و Py هما إحداثياث النقطة P و TrdPx وTrdPy هما إحداثياث النقطة الثالثة للمثلث.

والله أعلم

انا منعتك فقط لاني اعرف انك تحرق كل الاسئلة

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

وهذا ما اهرب انا منه الان

السلام عليكم،

أعجبني حل أخونا ikossan ،

ما شاء الله، فعلاً الأخ عادل لم يخطئ عندما منعك :D

لاستيفاء الدالة برمجياً راجعوا المقال التالي :

http://www.ddj.com/184404201

romanof كتب:

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

وهذا ما اهرب انا منه الان

←

الأستاذ romanof, حضرتك لو كنت قريت حلى كنت عرفت إن دى مش مشكلة!

الأستاذ ikossan, تسمحلى أعدل جزء صغير :^), إن ناتج التعويض مش لازم يبقى موجب المهم إنه يكون نفس الإشارة فى التعويضين.

نفرض ان المثلث له ثلاث نقط

A ( Ax,Ay,Az) 
B ( Bx,By,Bz)
C ( Cx,Cy,Cz) 
F ( Fx,Fy,Fz)  هي النقطة المراد الكشف هنا إذا كانت داخل مستوي المثلث ام لا

من الهندسة التحليلة نعلم ان اي ثلاث متجهات يكونوا في مستوي واحد إذا كان حاصل المحدد لهم بصفر

و لوقوع النقطة داخل المثلث يجب ان يكون الثلاث متجهات واقعين في مستوي واحد و هم المتجهات
FA , FB,FC
|Fx-Ax     Fy-Ay      Fz-Az|
|Fx-Bx     Fy-By     Fz-Bz| = 0
|Fx-Cx     Fy-Cy     Fz-Cz|

يعني تكشف إن كان المحدد بصفر أي الثلاث متجهات في مستوي واحد "  وهو المثلث " هذه الطريق مفيدة جداً بحيث لاتوجد دوال مثلثية تستهلك دورات كثيرة للمعالج في الحساب

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

الأخوة الكرام احبتى فى الله

رغم اقتناعى الكامل بان هذا المنتدى ( منتدى الرياضيات ) اكبر بكثير من ذلك , ولم يتم افتتاح هذا المنتدى لغرض الالغاز والترفيه , ورغم اقتناعى ايضا ان مثل هذا الاتجاه سيؤدى لقتل الهدف الرئيسى لهذا المنتدى.

الا انى سأشارك برأيى والذى اعلم انه سيغضب معظم المشاركين

اولا : بالنسبة للسؤال المقدم من الاخ romanof فالحل الوحيد الصحيح حتى مشاركتى هذه هو حل الاخ الكريم Blueteeth , وحل الأخ الكريم ikossan هو نفس الحل بالضبط.

الأخ الكريم Abo-Omer

خذ الثلاث نقاط هم بكل بساطه (0, 0) و (0,2) و (2,0)

فهى تمثل مثلث قائم الزاوية ورأسه القائمة عند نقطة الأصل واكبر ضلع به هو الوتر ويساوى جذر(8)

وخذ النقطه ( 1.5 , 1.5 ) اكبر بعد بينها وبين رؤوس المثلث اقل من جذر(8) ورغم ذلك فهى خارج المثلث.

الأخ الكريم احمد صالح

نفس المثال السابق بالضبط خذ الثلاث نقاط للمثلث هى (0 , 0 ,0 ) و ( 0 ,2 , 0 ) و (2 , 0 , 0 ) , وخذ النقطه محل الدراسه هى ( 1.5 , 1.5 , 0 ) (الإحداثيات من اليمين للشمال).

اعتقد الاربع نقاط فى مستوى واحد ( المستوى XY او المستوى Z=0 ) , واحسب اى محدد يعجبك هتلاقى قيمته صفرا , ورغم ذلك النقطة خارج المثلث.

ثانيا : رغم وجود حل اخونا Blueteeth وهو اول حل صحيح معطى , الا ان الاخوة الكرام بارك الله فيهم لم يعطوه حتى اى تعليق , ولكن عندما وضع الاخ الكريم ikossan نفس الحل بالضبط , حدث التفاعل وحدث الاهتمام , سبحان الله العظيم حتى المجاملات اصبحت فى العلم.

ثالثا : وهو الأهم احب ان ابرئ ذمتى من الله وان اعلن وبصفتى متخصص فى الرياضيات , ان هذا المنتدى ملئ بالاخطاء العلمية الرهيبه , ولقد ارسلت بذلك لبعض المشرفين الافاضل ممن اعرفهم معرفه شخصية , ولكنهم لم يستطيعوا ان يفعلوا اى شئ حيال هذا الأمر , ولو استمر الحال على ما هو عليه سيصبح هذا المنتدى بدلا من منتدى علمى لنشر العلم , سيتحول الى ساحة الغاز وترفيه , ومواضيع مليئة بالأخطاء والسموم .

هذا والله على ما اقول شهيد,,,

الاخ الكريم عماد ،

هذه الطريقة فرضتها بحيث ان المثلث مستوي Triangle Plane لكن بوضع الZ=0 يعني في بعدين سيكون المحدد بصفر مهما كان ،

هناك طريق اخري موضحة في الرسم

احمد صالح كتب:

الاخ الكريم عماد ،

هذه الطريقة فرضتها بحيث ان المثلث مستوي Triangle Plane لكن بوضع الZ=0 يعني في بعدين سيكون المحدد بصفر مهما كان  ،

هناك طريق اخري  موضحة في الرسم

←

يا أستاذ أحمد صالح, حتى لو كان المثلث 3D, فإن شرط وقوع ال 4 نقاط فى نفس المستوى ضرورى و لكن ليس كافى لإثبات أن النقطة تقع داخل المثلث.

الأخ عماد,

أنا يا أخى كنت إبتديت أشك إن الناس مش شايفة البوست بتاعى :D و جالى إحباط فعلا!!, لكن الحمد لله لقيت حد شايفنى :) جزاك الله خيرا.

اعجبتني ردود الجماعة جدا واسف يا اخ Blueteeth لم افهم حلك

هناك طريقة اخرى وهي ناخذا النقطة الرابعة ونوصلها برؤوس المثلث فان ونقوم بحساب فتنتج 3 مثلثاث جديدة فاذا كانت مجموع مساحاتها

تساوي مساحة المثلث الاصلي فهي داخ المثلث والا فلا

يا اخ عماد عندا هذا ليس لغزا الجماعة وضعوا خوارزمية لحل هكذا مسائل وهذه السؤال من كتاب

computational geometry

bye Franco Preprata

واعتقد ان الاخ احمد صالح يؤكد كلامي ايضا

Blueteeth كتب:

السلام عليكم,

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

حل صحيح ما شاء الله , والله لم أنتبه له عندما كتبت مشاركتي حتى أني كتبتها وانصرفت بسرعة لم أقرأ المشاركات التي سبقتني.

romanof كتب:

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

وهذا ما اهرب انا منه الان

عندما ستتعامل مع المستقيم بمعادلات تحليلية فلا يهم إن كانت النقطة يمين أم يسار, فوق أم تحت, المهم أن تكون النقطتين من نفس الجهة.

(أنظر المرفقات ملف تنفيذي, وسأدرج الكود بلغة الديلفي).

Blueteeth كتب:

الأستاذ ikossan, تسمحلى أعدل جزء صغير :^), إن ناتج التعويض مش لازم يبقى موجب المهم إنه يكون نفس الإشارة فى التعويضين.

إذا قلنا أن عددين A و B لهما نفس الإشارة فهذا يعني أن a.b>=0.

لهذا استعملت الجداء ( عملية الضرب).

عماد حمدي احمد كتب:

رغم اقتناعى الكامل بان هذا المنتدى ( منتدى الرياضيات ) اكبر بكثير من ذلك , ولم يتم افتتاح هذا المنتدى لغرض الالغاز والترفيه , ورغم اقتناعى ايضا ان مثل هذا الاتجاه سيؤدى لقتل الهدف الرئيسى لهذا المنتدى.

أظن أن المنتدى منتدى خاص لعلوم الرياضيات والخواريزميات.

هذا السؤال أصنفه من الخواريزميات الرياضية, يعني فيها فيها. :P .

****************************************************************

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

type
  TPoint = record
    X,Y: Extended;
  end;

  TLine = record  // ax + by + c = 0
    a,b,c: real;
  end;

var
  Pnt,A,B,C: TPoint;

//*****************************************************************************
// Equation Line (AB) :
// ax + by + c = 0
// ( By-Ay) X + (Ax-Bx) Y + Bx.Ay - Ax.By = 0
function Line( Pa,Pb: TPoint) : TLine;
begin
  result.a := pb.Y - pa.Y;
  result.b := pa.X - pb.X;
  result.c := pb.X*pa.Y - pA.X*pb.Y;
end;


//*****************************************************************************
// P and W is in the same side from the line (UV)?
function IsOnSameSide(P,W: Tpoint; UV: TLine): Boolean;
begin
  result:= ((P.X * UV.a + P.Y * UV.b + UV.c) * (W.X * UV.a + W.Y * UV.b + UV.c)) >= 0;
end;


//*****************************************************************************
// The point P is in the triangle (ABC)?
function IsInTriangle(P: Tpoint; Pa,Pb,Pc: Tpoint): boolean;
begin
  if
    IsOnSameSide(P,C,Line(A,B)) and
    IsOnSameSide(P,B,Line(A,C)) and
    IsOnSameSide(P,A,Line(C,B))
  then
    Result:= true
  else
    Result:= false;
end;

Triangle__Executable.rar

romanof نعم اخي ، و هذه الطريقة التي ذكرتها استخدمها في برمجة الرسومات حيث ان المجسمات كلها نعتبرها مثلثات لان المثلث يُمثل مستوي باي ثلاث نقط ليست علي استقامة واحدة و لانه سهل في تطبيقات بعض خوارزميات الرسومات مثل الClipping..إلخ

و هناك مجموعة كتب قديمة تُسمي Graphics Gems بها خوارزميات في Computational Geometry .

اقتباس

إذا قلنا أن عددين A و B لهما نفس الإشارة فهذا يعني أن a.b>=0.

لهذا استعملت الجداء ( عملية الضرب).

أيوة صح أنا مخدتش بالى أنا أسف (معلش معرفش يعنى إيه "الجداء" دى أول مرة أشوفها بصراحة :( ).

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

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

الاخ الكريم احمد صالح

فعلا اخى الكريم كما اشار اخونا Blueteeth فان شرط وقوع النقاط الأربع فى مستوى واحد هو شرط ضرورى وليس كافى , وبعدين حضرتك بتتكلم عن مثلث فى مستوى فى الفراغ , اليس المستوى Z=0 هو احدى ملايين المستويات الموجوده فى الفراغ مثل X=0 او Y=0 او حتى X+Y+Z=5 , كل هذه اخى الكريم مستويات والمفروض تكون بتحقق كلام حضرتك.

طبعا الحل الثانى الخاص بحساب الزوايا صحيح بالتأكيد , مع مراعاة الدقة والحذر عند حساب الزوايا .

الأخ الكريم romanof

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

الأخ الكريم ikossan

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

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

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

على الرغم من ان ما كنت اقصده من الصورة ان تكون جميع النقطة واقعة باتجاه واحد بالنسبة للرأس والضلع الذي يرسم منه الشعاع الا اني لم استطع التفكير بخوارزمية رياضية مباشرة للاثبات. لكن خوارزمية الاخ ikossan واضحة وبينت لي امر خفي عني في البداية.

الزوايا يا بشر الزوايا

لوكانت النقطة داخل المثلث فان لايمكن ان تكون اي زاوية يصنعها ضلعين من الراس اليها اكبر من 180

الطريقة بسيطة نأخذ مناط اسناد لكل ضلع و من ثم اذا كانت النقطة المطلوبة موجبة ام سالبة

اذا كانت كل النقط موجبة عند كل حالة اذا فالنقطة داخل المثلث و اذا لم يكن فالنقطة بالخارج

اقتباس

, بس معلش فرق كبير قوى قوى بين الخوارزمية والبرنامج ,

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

ياأستاذ/عماد

وما هى البرمجة الا خوارزمية كبيييييرة داخلها عدة خوارزميات أخرى

وعلى المبرمج حل هذه الخوارزمية الكبيييييرة وما بداخلها من خوارزميات

ثم ترجمة الحل بعد ذلك بأى لغة من لغات البرمجه أيآ كانت

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