منحنی هیلبرت

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

هیلبرت منحنی (همچنین به عنوان شناخته شده منحنی فضای پر کردن هیلبرت ) است مستمر فراکتال منحنی فضای پر کردن برای اولین بار توسط آلمان ریاضیدان توصیف دیوید هیلبرت در سال 1891، [1] به عنوان یک نوع از فضای پر کردن منحنی های پیانو کشف شده توسط جوزپه پینو در سال 1890. [2]

از آنجا که فضای پر است ، بعد هاسدورف آن 2 است (دقیقاً ، تصویر آن مربع واحد است که در هر تعریف بعد 2 برابر است ؛ نمودار آن یک مجموعه هومومورفیک فشرده تا فاصله واحد بسته با بعد هاسد ورف2 است) .

منحنی هیلبرت به عنوان محدوده ای از منحنی های قطعه ای جداگانه ساخته شده است . طول $n$ منحنی هفتم است پ $\ textstyle 2 ^ n - {1 \ over 2 ^ n}$ ، به عنوان مثال ، طول به طور نمایی با رشد می کند $n$ ، حتی اگر هر منحنی در یک مربع با مساحت باشد $1$ .

فهرست

تصاویر [ ویرایش ]

منحنی هیلبرت ، سفارش اول
منحنی های هیلبرت ، سفارشات اول و دوم
منحنی های هیلبرت ، سفارشات اول تا سوم
قوانین تولید
منحنی هیلبرت ، ساختاری کدگذاری شده است
یک منحنی 3-D Hilbert با رنگی که پیشرفت را نشان می دهد
نوع ، سه تکرار اول [3]
عکس دیوید هیلبرت که بر منحنی مرتبه هفتم هیلبرت تحمیل شده است

کاربردها و الگوریتم های نقشه برداری [ ویرایش ]

هم منحنی واقعی هیلبرت و هم تقریب های گسسته آن مفید هستند زیرا آنها نقشه ای را بین فضای 1D و 2D ارائه می دهند که محل را به خوبی حفظ می کند. [4] این بدان معناست که دو نقطه داده که در فضای یک بعدی نزدیک به یکدیگر هستند نیز پس از جمع شدن به یکدیگر نزدیک هستند. گفتگو همیشه نمی تواند درست باشد.

به دلیل این خاصیت محلی ، منحنی Hilbert به طور گسترده ای در علوم کامپیوتر استفاده می شود. به عنوان مثال ، دامنه آدرسهای IP مورد استفاده رایانه ها را می توان با استفاده از منحنی Hilbert به یک تصویر ترسیم کرد. کد برای تولید تصویر برای پیدا کردن رنگ هر پیکسل از 2D به 1D است و از منحنی Hilbert گاهی اوقات استفاده می شود زیرا آدرس های IP نزدیک را در تصویر نزدیک به یکدیگر نگه می دارد. [5]

در یک الگوریتم به نام Diversing Riemersma ، عکس مقیاس خاکستری را می توان با استفاده از آستانه به یک تصویر سیاه و سفید متلاشی شده تبدیل کرد ، در حالی که مقدار باقی مانده از هر پیکسل به پیکسل بعدی در امتداد منحنی هیلبرت اضافه می شود. کد برای این کار از 1D به 2D ترسیم می شود و از منحنی Hilbert گاهی اوقات استفاده می شود زیرا الگوهای منحرف کننده ای را ایجاد نمی کند که برای چشم قابل مشاهده باشد در صورتی که ترتیب در هر ردیف پیکسل به سمت راست قرار داشته باشد. [6] منحنی های هیلبرت در ابعاد بالاتر نمونه ای از تعمیم کدهای خاکستری است و گاهی اوقات به دلایل مشابه برای اهداف مشابه استفاده می شود. برای پایگاه داده های چند بعدی ، سفارش Hilbert پیشنهاد شده است که به جای سفارش Z استفاده شودزیرا رفتار بهتری برای حفظ مکان دارد. به عنوان مثال ، از منحنی های Hilbert برای فشرده سازی و تسریع شاخص های R-tree استفاده شده است [7] (نگاه کنید به Hilbert R-tree ). آنها همچنین برای کمک به فشرده سازی انبارهای داده استفاده شده اند. [8] [9]

با توجه به برنامه های متنوع ، داشتن الگوریتم هایی برای نقشه برداری در هر دو جهت مفید است. در بسیاری از زبانها ، این موارد بهتر است اگر با تکرار اجرا شوند و نه بازگشتی. کد C زیر نگاشت ها را در هر دو جهت با استفاده از عملیات تکرار و بیت به جای بازگشت ، انجام می دهد. این یک مربع را به n توسط n سلول تقسیم می کند ، برای n دارای قدرت 2 ، با مختصات عدد صحیح ، با (0/0) در گوشه پایین سمت چپ ، ( n - 1 ، n - 1) در گوشه بالا سمت راست ، و فاصله d که از 0 در گوشه پایین سمت چپ شروع می شود و به آن می رود $n ^ 2-1$ در گوشه پایین سمت راست این متفاوت از انیمیشن نشان داده شده در بالا است که در آن منحنی از گوشه بالا سمت چپ شروع می شود و در گوشه سمت راست بالا خاتمه می یابد.

//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
    }
    return d;
}

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s

اینها از قراردادهای C استفاده می کنند: نماد & bit بطور AND و ، نماد ^ bitwise XOR است ، عملگر + = به یک متغیر اضافه می شود و عملگر / = یک متغیر را تقسیم می کند. از دست زدن به Booleans می در معنای C که در xy2d، متغیر RX به 0 یا 1 مجموعه ای برای مطابقت کمی بازدید کنندگان از X ، و به همین ترتیب برای RY .

تابع xy2d از پایین به پایین کار می کند ، با مهمترین بیت های x و y شروع می شود و در ابتدا مهمترین بیت های d را ایجاد می کند. تابع d2xy به ترتیب مخالف کار می کند ، با کمترین بیت d شروع می شود ، و x و y را با کمترین بیت شروع می کند. هر دو عملکرد از چرخش برای چرخش و چرخش مناسب سیستم مختصات ( x ، y ) استفاده می کنند.

این دو الگوریتم نقشه برداری به روش های مشابهی کار می کنند. كل مربع از 4 ناحیه تشكیل شده است كه 2 در 2 مرتب شده است. هر منطقه از 4 منطقه كوچكتر و غیره برای تعدادی سطح تركیب شده است. در سطح بازدید کنندگان ، در هر منطقه است بازدید کنندگان توسط بازدید کنندگان سلول. یک حلقه FOR وجود دارد که از طریق سطوح تکرار می شود. در هر تکرار ، مقدار به d یا به x و y اضافه می شود ، مشخص می شود که در کدام یک از 4 منطقه در سطح فعلی باشد. منطقه فعلی از 4 ( rx ، ry ) است ، جایی که rx و ry هر کدام 0 یا 1 هستند. بنابراین 2 بیت ورودی مصرف می کند (یا 2 بیت از dیا هر کدام از x و y ) ، و دو بیت خروجی تولید می کند. همچنین تابع چرخش را فراخوانی می کند تا ( x ، y ) برای تکرار بعدی برای سطح بعدی مناسب باشد. برای xy2d ، از سطح بالایی کل مربع شروع می شود و تا پایین ترین سطح سلولهای جداگانه کار می کند. برای d2xy ، از پایین با سلول شروع می شود و کار می کند تا کل مربع را شامل شود.

پیاده سازی منحنی های Hilbert به طور کارآمد حتی زمانی که فضای داده مربع تشکیل ندهد ، امکان پذیر است. [10] علاوه بر این ، چندین تعمیم منحنی هیلبرت به ابعاد بالاتر وجود دارد. [11] [12]

نمایندگی به عنوان سیستم Lindenmayer [ ویرایش ]

منحنی هیلبرت را می توان با یک سیستم بازنویسی ( سیستم L ) بیان کرد.

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

حروف الفبا : A ، B

ثابت ها : F + -

بدیهیات : الف

قوانین تولید :

A → + BF − AFA − FB +

B −AF + BFB + FA−

در اینجا ، "F" به معنی "جلو کشیدن" است ، "+" به معنی "چرخش 90 درجه به چپ" ، "-" به معنی "چرخش 90 درجه راست" (نگاه کنید به گرافیک لاک پشت ) ، و "A" و "B" در هنگام طراحی نادیده گرفته می شوند .

سایر پیاده سازی ها [ ویرایش ]

Graphics Gems II [13] در مورد انسجام منحنی هیلبرت بحث کرده و پیاده سازی را ارائه می دهد.

منحنی Hilbert معمولاً در میان ارائه تصاویر یا فیلم ها استفاده می شود. برنامه های رایج مانند Blender و Cinema 4D از منحنی Hilbert برای ردیابی اشیا و رندر صحنه استفاده می کنند. [ نیاز به منبع ]

همچنین به [ ویرایش ] مراجعه کنید

Wikimedia Commons دارای رسانه های مربوط به منحنی هیلبرت است .

منبع:https://en.wikipedia.org/wiki/Hilbert_curve

+ نوشته شده در جمعه یکم مرداد ۱۴۰۰ ساعت 17:56 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی