تیر
۱۱
۱۳۹۱

پیدا کردن نقطه تلاقی دو پاره خط در ‏OpenGL

برخوردها از مسائل مهم و جالب در برنامه های گرافیکی هستند. یکی از پایه ای ترین نوع برخوردها برخورد بین دو خط در صفحه است.

 در این نوشته قصد دارم در مورد پیاده سازی کد تشخیص این نوع برخورد در OpenGL صحبت کنم.

برای پیاده سازی دقیق و کامل تشخیص این نوع برخورد در شرایط مختلف ابتدا نیاز داریم که تمام وضعیت های ممکن رو بررسی کنیم.

در صورتی که دو خط دارای شیب یکسان نباشند به طور قطع در نقطه ای از صفحه همدیگر رو قطع میکنند:

برای یافتن مختصات نقطه تلاقی دو خط ابتدا فرمول هر خط رو به دست آورده و با مساوی قرار دادن طول (x) دو معادله، عرض نقطه تلاقی و با مساوی قرار دادن عرض (Y) دو معادله، طول نقطه تلاقی رو به دست میاریم.

مثلا فرض کنید معادله خطوط ما به صورت زیر هستند:

۱) Y1 = 3X1 + 10

۲) Y2 = 2X2 – 6

 برابر قرار دادن عرض ها برای پیدا کردن طول نقطه تلاقی :

    Y1 = Y2    =>   ۳X + 10 = 2X – ۶   =>    -۱۶ = Xنقطه تلاقی

 برابر قرار دادن طول ها برای پیدا کردن عرض نقطه تلاقی :

   X1 = X2  =>  (Y – ۱۰) / ۳ = (Y + 6) / 2  =>   -۳۸ =  Yنقطه تلاقی

 

به این صورت مختصات نقطه تلاقی به دست خواهد آمد.

برای پیاده سازی این مسئله در OpenGL ابتدا باید معادله دو خط را از روی نقاط ابتدایی و انتهایی آن به دست آورده و سپس با انجام مراحل بالا نقطه تلاقی را به دست آوریم.

به طور مثال ابتدا فرض کنید که در زبان سی ساختمان داده زیر را برای تعریف مختصات یک نقطه در OpenGL تعریف کردیم:

 

و نیز از ساختمان داده زیر برای تعریف خطوط در OpenGL استفاده میکنیم:

حالا میخواهیم دو خط دلخواه خود را در برنامه تعریف کنیم و معادله دو خط و نقطه تلاقی احتمالی آنها را نیز به دست بیاوریم. برای به دست آوردن معادله دو خط ابتدا با استفاده از خطوط زیر شیب هر دو خط را محاسبه میکنیم:

 

سپس با استفاده از معادلات زیر مختصات نقطه تلاقی به دست خواهد آمد:

 

این دو معادله حالت کلی مساوی قرار دادن طول و عرض معادلات خط در صفحه را نشان میدهد.

البته مسئله تا اینجا تنها برای حالتی حل شده که شیب هر دو خط مخالف بینهایت باشد. و در صورتی که شیب یکی از خطوط بینهایت باشد برنامه با خطای مهلک تقسیم بر صفر مواجه خواهد شد. برای حل این مشکل باید حالت های دیگر رو هم در برنامه لحاظ کنیم.

همانطور که میدانید وقتی خطی دارای شیب بینهایت باشد معادله خط آن به صورت زیر خواهد بود:

X = عددی ثابت

در این صورت برای یافتن نقطه تلاقی، کافیه مقدارعددی این معادله را درون معادله دوم جاگذاری کنیم. در این صورت عرض نقطه تلاقی به دست خواهد آمد.

در ادامه تکه کدی را براتون آماده کردم که در این کد تابعی را مشاهده خواهید کرد که دو خط را از ورودی دریافت میکند  سپس با در نظر گرفتن حالت های مختلف در صورتی که برخوردی بین دو خط وجود داشت مختصات نقطه تلاقی را به دست آورده و برمیگرداند:

 

در انتها برنامه کاملی را که با استفاده از الگوریتم بالا برخورد بین خطوط مختلف را نشان میدهد براتون برای دانلود و تست قرار میدم. در این برنامه شما با کلیک کردن بر روی صفحه خطوط دلخواه خود را رسم میکنیم. رئوس اصلی با رنگ سبز و نقاط تلاقی بین خطوط با رنگ قرمز مشخص میشوند.

دموی برنامه

دانلود کامل برنامه

تصاویری از اجرای برنامه بالا:

//

//

مرور کد فایل LinesCollision.cpp از برنامه بالا:

 

اشتراک گذاری این مطلب:

نوشته‌های مرتبط

درباره نویسنده

برنامه‌نویس ++‏C/C‏ - برنامه‌نویس سیستم‌های گرافیکی با استفاده از کتابخانه ‏OpenGL - برنامه‌نویس #‏C و ..‏



۳ دیدگاه افزودن دیدگاه +

  • خیلی خوب بود من استفاده کردم

  • عالی. یه خورده تغییرش دادم توی سی شارپ ازش استفاده کردم.

  • آقا بسیار جالب بود – ممنون ، ادامه بدید

فرستادن دیدگاه