الگوريتم تشخيص نقطه درون چند ضلعي

[fidnah]

سلام
من ميخوام بدونم ايا الگوريتم خاصي براي تشخيص وجود يه نقطه درون چند ضلعي وجود داره؟
مختصات رئوس چند ضلعي رو داريم حالا ميخوام بدونم يه نقطه مثلx,yداخل محدوده شكل وجود داره؟
ممنون ميشم اگه راهنماييم كنيد

[manager]

می تونید یک نقطه درون چند ضلعی انتخاب کنید و یک خط به نقطه مورد نظر ترسیم کنید اگر این خط یکی از رئوس چند ضلعی را قطع کرد یعنی نقطه مورد نظر خارج از چند ضلعیه وگر نه داخل اون هست.(شکل C)

البته اگر مختصات های مربوط به رئوس شما به ترتیب و پشت سر هم باشه(شکل A و C). البته برای پیشنهاد راه حل بهتر باید در مورد داده هایی که در اختیار دارید بیشتر توضیح بدید. مثلا یک وقتی هست شما مجموعه ای از رئوس رو دارید که ترتیب اونها اصلا مشخص نیست (شکل B)! باید در مورد شرایط اولیه مسئله بیشتر توضیح بدید.

[رضا عربلو]

یک قضیه است در ریاضیات توپولوژی که یک همچین چیزی می گوید "نقطه ای داخل یک چند ضلعی است که اگر خطی از ان به خارج بکشیم تعداد فردی ضلع را قطع کند"

[dadvand]

می تونید یک نقطه درون چند ضلعی انتخاب کنید

سلام
فکر میکنم انتخاب نقطه درون چند ضلعی خود مجدد بازگشت به صورت مسئله است .
راه حل پیشنهادی من محدود کردن چند ضلعی به یک 3 یا 4 ضلعی است.
به طریق انتخاب هر بار 3 راس متصل به هم (بدون واسطه) که هر 3 در یک طرف نقطه قرار دارند یعنی طرف چپ یا راست یا پایین یا بالا (v1.left,v2.left,v3.left< point.left ...... و غیره) و سپس حذف نقطه وسط و اتصال 1و3 به هم .
راه حل پیشنهادی برای انتخاب 3 نقطه متصل .
انتخاب یک راس v

• انتخاب راس vi که متصل به v است و یکی از مختصات چپ یا راست یا بالا یا پایین آن هماهنگ با راس v با شرط گفته شده در بالا باشد.
• انتخاب راس vk که متصل به vi یا V با شرط ذکر شده .

در هر بارشکست یک راس دیگر انتخاب میشود
در هر بار موفقیت راس وسط حذف و با همان راس V مجدد ادامه میدهیم .
الگوریتم تا وقتی که فقط 3 راس باقی بماند ادامه پیدا میکند.

[dadvand]

یک قضیه است در ریاضیات توپولوژی که یک همچین چیزی می گوید "نقطه ای داخل یک چند ضلعی است که اگر خطی از ان به خارج بکشیم تعداد فردی ضلع را قطع کند"

آیا شکل زیر یک چند ضلعی است ؟


اگر باشد که این قضیه صدق نمیکند . راه خودم هم مشکل خواهد داشت .

[رضا عربلو]

از صحت قضیه فوق که مطمئنم. (این قضیه را 17 سال پیش تو یک مجله ریاضیات خوندم و هنوز ام مضمونش در ذهنم است.)
اما قضیه فوق برای اشکالي صادق است که هیچ ضلعی همديگر را قطع نکنند. و همچنی خط فوق بر هيچ ضلعی مماس نشود.
شکل زیر را ببينيد:

[atilla snowman]

با سلام
از این که این تاپیک جالب رو ایجاد کردید ممنونم
همون طور که میدونید این مساله مربوطه به حوزه computational geometry که مسایل متنوع و جالبی رو در بر میگیره.
راه حلهایی که دوستان ارایه دادی جالب بود و البته شدنی
من هم راه حل خودمو میگم.
اگه ما چند ضلعی اولیه رو به صورت مجموعه از نقاط در صفحه داشته باشیم که با مختصات دو بعدی توصیف شدند احتمالا مساله از ما میخواد که تعیین کنیم که اگر با این نقاط یک پوش محدب یا همون convex hall داشته باشیم نقطه ی مورد نظر مساله تو این پوش محدب قرار میگیره یا نه؟
ما با الگوریتم(هایی) خاصی میتونیم پوش محدب رو برای مجموعه ای از نقاط در زمانی که از big-oh ی nlogn هستش بدست بیاریم که میشه دنباله ای از نقاط که پشت سر هم پوش رو میسازن و زیر مجموعه ای از مجموعه ی اولیه هستن. حال اگر نقطه مورد نظر رو به مجموعه ی اولیه ی نقاط اضافه کرده و پوش رو برای اون در زمانی از big-oh ی (n+1)log(n+1) بسازیم. حال اگر این نقطه جزو دنباله ی جواب باشه داخل پوش اولیه نخواهد بود و اگر نباشه خواهد بود.
با تشکر

[hserver]

هیچ کس اینجا نمی پرسه این الگوریتم رو کجا می خواین؟
شاید نیازی به اینهمه ایده و نظر نباشه
شما اگه مشخص کنید
1 سکل منظمه یا نه
2 محدب هست کامل یا نه
3 نقاط ساعت گرد هستن یا پاد ساعت گرد یا ...
می شه با هم به یک یا چند نظر خوب برسیم
(البته اگه این یه سوال تئوری نباشه و واقعا میخواین پیاده سازیش کنید)

[bulut-li-savalan]

با سلام
چط.وری میتونم کد این الگوریتم رو بنویسم؟