یافتن بیرونی ترین نقاط(فوری)

[delphiamator]

تعدادی نقطه داریم در صفحه.می خواهیم بیرونی ترین نقاط را پیدا کنیم.help plz

[Sepidar]

یه تعریف از نقاط بیرونی: (تعریف 1)
از یه مجموعه نقاط دلخواه، نقاطی رو بیرونی میگیم، اگه بشه یه چند ضلعی به رئوس اون نقطه ها رسم کنیم که 2 شرط زیر رو بر آورده کنه:
1. چند ضلعی مذکور محدب باشه؛
2. تمام نقاط دیگه فقط داخل (نه خارج و نه روی اضلاع) اون واقع بشن.

لم 1: برای هر مجموعه متناهی از نقاط با تعداد بیشتر از 3 نقطه، یک مجموعه نقاط بیرونی وجود داره.
لم 2: مجموعه نقاط بیرونی یه مجموعه نقطه، درصورت وجود یکتاست.

تعریف 2: 2 نقطه از مجموعه نقاط بیرونی رو مجاور میگیم اگه در چند ضلعی تعریف 1 روی یک ضلع باشند.

لم 3: همه نقاط هر مجموعه نقطه، در یک طرف خط مار بر 2 نقطه مجاور قرار دارن.
لم 4: مجموعه نقاط بیرونی دارای نقاطی است که دارای طول بیشینه، طول کمینه، عرض بیشینه و عرض کمینه نسبت به همه نقاط دیگر هستند.
لم 5: نقاطی که دارای طول بیشینه، طول کمینه، عرض بیشینه و عرض کمینه نسبت به همه نقاط دیگر هستند، نقاط بیرونی می باشند.

[delphiamator]

مرسی از راهنماییتون.اگه ممکنه در موردالگوریتمشم یه راهنمایی بکنید.من الگوریتمشو می خواهم.بازم ممنون

[seyedof]

سلام
این یک الگوریتم مشهور در هندسه محاسباتی است. چیزی که شما میخواهید بهش میگن پوسته محدب یا به انگلیسی Convex Hull الگوریتم مشهورش هم اسمش الگوریتم گراهام است، الگوریتم نسبتا ساده ای هم است ولی پیچیدگی زمانیش یادم نیست فکر کنم زمان خطی بود.
ممنون علی

[delphiamator]

بازم مرسی به خاطر کمکتون.ولی چرا من این الگوریتم گراهام رو جایی پیدا نمی کنم؟هر چی search می کنم جوابی پیدا نمی کنم.

[Sepidar]

فرض کن مجموعه نقاط ورودی S باشه و مجموعه نقاط بیرونی O. خوب در ابتدای الگوریتم، بدیهیه که O={}
اول باید چک کنی که n(S)>3
یه نقطه از S که عرضش بزرگتر مساوی همه نقاط دیگه S هست رو انتخاب کن. اسم این نقطه رو میذاریم a
O=O+{a}
top:
توی S-O دنبال یه نقطه مثل x بگرد که همه نقاط S یه طرف خط ax واقع بشن.
اگه x=nil برو به end
a=x
O=O+{a}
برو به top
end:

[Sepidar]

برای اینکه چک کنی یه نقطه مثل (x0,y0) کدوم طرف یه خط مثل y=ax+d هست کافیه y0-m*x0-d رو تشکیل بدی. اگه حاصل مثبت شد، این نقطه بالای خط مذکوره. اگه منفی شد ثایینشه. اگه صفر شد هم روشه.
البته برای خطوط قائم این روش جواب نمیده و باید مستقیما طول نقاط چک بشن.
در ضمن الگوریتم بالا یه ایراد کوچیک داره. گذاشتم خودت پیداش کنی

[seyedof]

سلام
غیر ممکنه. حتما روی اینترنت هست. Convex Hull Algorithm رو جستجو کنید. اگر هم دنبال سورس کد آماده هستید شرمنده. اینجا فقط برای راهنمایی است.
ممنون علی

[delphiamator]

مرسی از راهنماییتون خیلی کمکم کردین

[pakzad_64]

سلام به همه دوستان

[pakzad_64]

خواهشمندم در نوشتن برنامه حرکت اسب کمکم کنید