رسم بياني خطي مستوٍ

في الهندسة الحسابية ونظرية المخططات الهندسية ، يُعرف المخطط الخطي المستوي ( PSLG )، والذي يُسمى أيضًا المخطط الخطي المستوي أو المخطط الخطي المستوي ، بأنه تمثيل لمخطط مستوٍ في المستوى بحيث تُحوّل حوافه إلى قطع مستقيمة. ^{[ 1 ]} تنص نظرية فاري (1948) على أن كل مخطط مستوٍ له هذا النوع من التمثيل.

في الهندسة الحسابية، غالباً ما يطلق على PSLGs اسم التقسيمات المستوية ، مع افتراض أو تأكيد أن التقسيمات مضلعة بدلاً من أن تكون لها حدود منحنية.

قد تُستخدم نماذج PSLG كتمثيلات لخرائط متنوعة ، على سبيل المثال، الخرائط الجغرافية في نظم المعلومات الجغرافية . ^{[ 2 ]}

تُعدّ التثليثات ( تثليث المضلعات ، وتثليث مجموعات النقاط ) حالات خاصة من مخططات PSLG. وتُعتبر تثليثات مجموعات النقاط مخططات PSLG قصوى، إذ يستحيل إضافة حواف مستقيمة إليها مع الحفاظ على استواء الرسم البياني. وللتثليثات تطبيقات عديدة في مجالات متنوعة.

يمكن اعتبار مخططات PSLG نوعًا خاصًا من المخططات الإقليدية . مع ذلك، في المناقشات المتعلقة بالمخططات الإقليدية، ينصب الاهتمام الأساسي على خصائصها المترية، أي المسافات بين الرؤوس، بينما في مخططات PSLG، ينصب الاهتمام الأساسي على خصائصها الطوبولوجية. بالنسبة لبعض المخططات، مثل تثليثات ديلاوناي ، تُعدّ كل من الخصائص المترية والطوبولوجية مهمة.

توجد ثلاث هياكل بيانات معروفة لتمثيل مخططات التقسيم المستوي (PSLGs)، وهي: هيكل بيانات الحافة المجنحة ، وهيكل بيانات نصف الحافة ، وهيكل بيانات الحافة الرباعية . يُعد هيكل بيانات الحافة المجنحة الأقدم بينها، ولكن التعامل معه يتطلب غالبًا تمييزًا معقدًا بين الحالات. ويعود ذلك إلى أن مراجع الحواف لا تخزن اتجاه الحافة، كما أن اتجاهات الحواف حول الوجه الواحد قد لا تكون متسقة. أما هيكل بيانات نصف الحافة، فيخزن كلا اتجاهي الحافة ويربطهما بشكل صحيح، مما يبسط العمليات ونظام التخزين. بينما يخزن هيكل بيانات الحافة الرباعية كلاً من التقسيم المستوي ونظيره في آنٍ واحد. وتتكون سجلاته صراحةً من سجلات الحواف فقط، أربعة لكل حافة، وهو مناسب في شكله المبسط لتخزين مخططات التقسيم المستوي. ^{[ 3 ]}

• تحديد موقع النقطة . بالنسبة لنقطة استعلام، حدد الوجه الذي تنتمي إليه من PSLG.
• تراكب الخرائط . أوجد تراكب خريطتين (PSLGs)، وهو تقسيم المستوى بواسطة هاتين الخريطتين المضمنتين في آن واحد. في نظم المعلومات الجغرافية، تُعرف هذه المسألة باسم " تراكب الخرائط الموضوعية ".

• قائمة الحواف المتصلة ثنائياً ، وهي بنية بيانات لتمثيل PSLG
• حجم الميزة المحلية