انجمن کامپیوتر ایران

تولید چندضلعی‌های تصادفی از مسائل مهم هندسه محاسباتی است که در تحقیقات روان‌شناختی، گرافیک کامپیوتری و از همه مهمتر برای بررسی درستی الگوریتم‌ها به کار می‌رود. نوع خاصی از چندضلعی‌های تصادفی، چندضلعی‌های متعامد می‌باشند که در آن‌ها هر دوضلع مجاور بر هم عمود می‌باشند و اضلاع پشت سر هم به صورت متناوب افقی و عمودی هستند. در این مقاله ابتدا مفهوم جدیدی به نام ضربه تعریف می‌گردد و سپس الگوریتمی از مرتبه و با استفاده از تکنیک ضربه‌ای ارائه می‌شود که در آن تعداد ضربات و تعداد اضلاع چندضلعی است، یعنی ورودی مسئله یک چندضلعی ساده مربع یا مستطیل شکل، در قالب چهار نقطه در فضای دوبعدی و نیز تعداد ضربات وارده به این چندضلعی توسط یک چکش مجازی است و خروجی مسئله یک چندضلعی ساده متعامد تصادفی می‌باشد. این الگوریتم روشی جدید در تولید چندضلعی محسوب می‌شود و می‌تواند مبنای کار روشهای دیگری محسوب شود.