ساخت داده های مکانی-زمانی

چکیده

در مسیر یک سیستم اطلاعاتی علم زمین مکانی-زمانی، یک مدل داده مناسب برای اجسام جغرافیایی در فضا و زمان ایجاد شده است. در این مدل، ژئواشیاء به صورت دنباله ای از هندسه ها و ویژگی ها با تکامل پیوسته در هر بازه زمانی نمایش داده می شوند. از آنجایی که سیستم‌های نرم‌افزار ژئومدلینگ معمولاً اشیاء را در نمونه‌های زمانی خاص مدل‌سازی می‌کنند، می‌خواهیم هندسه و ویژگی‌های دو مدل از یک شی را تنها با محدودیت‌های هندسی (بدون محدودیت فیزیکی یا مکانیکی) درون یابی کنیم. این فرآیند ساخت داده های مکانی-زمانی یا درونیابی مورفولوژیکی هندسه های میانی نامیده می شود. این مقاله به شدت به شکل‌گیری شکل، تغییر شکل شکل، پارامترهای متقاطع و پوشش مجدد سازگار مربوط می‌شود و تنها به سطوح زمین‌شناسی می‌پردازد. در این مطالعه، دو راه حل فرعی اصلی مش های سازگار را می سازند و مسیرهایی را پیدا می کنند که در آن رئوس مش تکامل می یابد. هدف این تحقیق یافتن الگوریتمی برای ساخت داده‌های مکانی-زمانی با برخی محدودیت‌های علوم زمین، مانند برش سطوح توسط پدیده‌های گسل یا شکست و مرزهای در حال تکامل متصل به سطوح دیگر است. یکی دیگر از اهداف این تحقیق پیاده سازی الگوریتم در یک محصول نرم افزاری، یعنی پلاگین gOcad است. چهار رویه اصلی الگوریتم عبارتند از برش سطوح، تنظیم محدودیت ها، تقسیم بندی و محاسبه پارامترها و مسیرها. این نرم افزار برای ساخت داده های یک گنبد نمکی و سایر سطوح در رابطه با فرآیندهای زمین شناسی گسلش، رسوب و فرسایش آزمایش شده است.

کلید واژه ها:

ساخت و ساز داده های مکانی – زمانی ; درون یابی مورفولوژیکی ; پایگاه داده های مکانی – زمانی ; جمع آوری داده های 4 بعدی ؛ شکل گیری مش ; پارامترهای متقابل ؛ رمشینگ سازگار

1. مقدمه

از آنجایی که رشته علوم زمین تغییرات مکانی و زمانی را در زمین بررسی می کند، ادغام داده های مکانی و زمانی یک نیاز طبیعی بسیاری از کاربردها در علوم زمین است. تاکنون، داده‌های فضایی سه‌بعدی (3D) به خوبی در علوم زمین ادغام شده‌اند، اگرچه ادغام داده‌های زمانی به دلیل پیچیدگی آن موفقیت چندانی کسب نکرده است. هدف کار ما غلبه بر این پیچیدگی با بررسی مفاهیم، توسعه مدل داده و ساختن نرم‌افزار و برنامه‌های کاربردی است. از طریق این رویکرد، ما یک مدل داده مناسب [ 1 ] ایجاد کرده‌ایم که در آن یک محور زمان واقعی را در نظر گرفته‌ایم. این محور زمانی به بازه‌های زمانی تقسیم می‌شود و مستلزم آن است که ویژگی‌های هندسه و علم زمین به طور مداوم در طول بازه‌های زمانی تغییر کنند.

از آنجایی که سیستم‌های نرم‌افزار ژئومدلینگ معمولاً اشیاء را در نمونه‌های زمانی خاص مدل‌سازی می‌کنند، هدف این تحقیق درون‌یابی هندسه‌های میانی یا یافتن الگوریتمی برای ساخت داده‌ها در هر بازه زمانی [ t _i , t _i _{+ 1} ] از دو مدل داده ورودی در زمان t _i و زمان است . t _i _{+ 1}. این مقاله به دلیل نیاز به جمع‌آوری داده‌ها برای یک سیستم اطلاعات زمین‌شناسی مکانی-زمانی با قابلیت پردازش و پاسخگویی به پرسش‌هایی مانند: «با توجه به یک مکان (جئو شی در یک مکان مشخص) و ویژگی‌هایی مانند دما و فشار، برای چه دوره زمانی، ژئو شی در معرض مکان و ویژگی ها بوده است؟» یا “هندسه و خواص یک شیء جغرافیایی در یک زمان معین چیست؟”

ما فرض می کنیم که در یک بازه زمانی به اندازه کافی کوچک، یک لایه زمین شناسی، که در معرض رسوب، فرسایش و بالا آمدن است، به آرامی و به طور منظم تغییر می کند. بنابراین، داده های ساخته شده نشان دهنده تکامل زمانی یک شیء جغرافیایی است. بنابراین، فرآیند ساخت و ساز، ساخت داده های مکانی-زمانی نامیده می شود. این الگوریتم همچنین چندین محدودیت هندسی را در نظر می‌گیرد که تکامل مدل‌سازی شده را قادر می‌سازد تا به تکامل تاریخی «واقعی» نزدیک‌تر باشد. برای ساده کردن مشکل ادغام داده های مکانی-زمانی، تنها مش های مثلثی سه بعدی در نظر گرفته می شوند. جامد و انواع دیگر ژئو اجسام در کار آینده ما در نظر گرفته خواهند شد.

برخی از مطالعات در مورد درونیابی مورفولوژیکی بر اساس ریخت شناسی ریاضی [ 2 ، 3 ، 4 ، 5 ] وجود دارد. این روش‌ها به تصاویر (دودویی/مقیاس خاکستری و رنگی) محدود می‌شدند و برای تولید بخش‌های دو بعدی میانی و بازسازی اشیاء سه‌بعدی از بخش‌های دو بعدی اولیه‌شان استفاده می‌شدند. این مطالعات به طور قابل توجهی با مطالعه ما متفاوت است. ما اشیاء 4 بعدی را از سطوح مش سه بعدی در هر نمونه زمانی ساختیم.

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

در بخش 2 ، کار مرتبط را بررسی می کنیم. الگوریتم در بخش 3 توضیح داده شده است . در بخش 4 ، نرم افزار و آزمایشات ارائه شده است. در نهایت، بخش 5 به بحث و نتیجه‌گیری اختصاص دارد.

2. کارهای مرتبط

این تحقیق به شدت به شکل‌گیری شکل، تغییر شکل شکل، پارامترسازی متقاطع، مش‌بندی سازگار، پارامترسازی دو بعدی یا سه بعدی در حوزه‌های گرافیک کامپیوتری و طراحی هندسی به کمک رایانه مرتبط است. این تکنیک ها مورد توجه بسیاری از محققان، مانند Michael S. Floater [ 6 ، 7 ، 8 ، 9 ]، Bruno Lévy [ 10 ]، Kai Hormann، Konrad Polthier، Alla Sheffer [ 11 ]، Yaron Lipman [ 12 ]، Xin قرار گرفته است. لی [ 13 ] و غیره

فرآیند شکل‌گیری شکل شامل دو مرحله است. مرحله اول به دنبال یک نقشه دوگانه بین شکل منبع و شکل هدف می گردد که به عنوان تطابق راس یا مش های سازگار/سازگار شناخته می شود. مرحله دوم مجموعه‌ای از مسیرها را انتخاب می‌کند، که رئوس مربوطه در طول آن حرکت می‌کنند تا از اولین مجموعه رئوس به مجموعه رئوس دوم تبدیل شوند. این فرآیند به عنوان مسیر/مسیر راس [ 6 ، 14 ، 15 ، 16 ] شناخته می شود. در مورد گام اول، ون کایک و همکاران. [ 17] بررسی اخیر خوبی از مش های مثلثی سازگار ارائه می دهد. مش‌های سازگار معمولاً با تقسیم دو مش به تکه‌های مربوطه، که همومورفیک دیسک هستند، محاسبه می‌شوند. در مرحله دوم، پارامترسازی دو مش در یک دامنه پایه مشترک محاسبه می‌شود. ثالثاً پارامتر متقابل محاسبه می شود و در نهایت مش ها مجدداً مش می شوند [ 18 ، 19 ]. با پیروی از این چارچوب، الگوریتم ما مش های سازگار ایجاد می کند. علاوه بر این، ما از روش برش استفاده می کنیم تا آن را برای کاربرد در زمینه علوم زمین مناسب کنیم. خلاصه ای از تکنیک های پارامترسازی مش در [ 10 و 11 ارائه شده است]. هنگام استفاده از پارامترسازی باید برخی عوامل را در نظر گرفت، مانند اعوجاج، دوجنسیت، آزادی مرز و پیچیدگی. در الگوریتم ما، پارامترسازی مقدار میانگین انتخاب شده است، به دلیل خواص بیجکشن و مرز ثابت این تکنیک. از این رو، ما ثبات را در مرزهای تکه ها حفظ می کنیم.

بیشتر تکنیک‌های شکل‌گیری به مرحله دوم در فرآیند شکل‌گیری شکل مربوط نمی‌شوند، بلکه مرحله اول را در فرآیند شکل‌گیری شکل حل می‌کنند و سپس از مسیرهای خطی، یعنی بخش‌های خط مستقیم رئوس مربوطه استفاده می‌کنند. MS Floater از ترکیبات محدب برای مسیرها استفاده کرد [ 6 ]. یافتن مسیرها با حرکت دادن یک شکل صلب (یا تا حد امکان صلب) در [ 14 ، 16 ] توضیح داده شده است. استفاده از میدان های کرنش برای انتخاب مسیرها در [ 15 ] توضیح داده شده است. در الگوریتم ما، روش فرعی یافتن مسیرها بر اساس روش ترکیب محدب ساخته شده است، همانطور که در [ 6 ] توضیح داده شد.]، با این فرض که سطوح میانی دارای خاصیت “ترکیبی” هستند، یعنی هر رأس داخلی را می توان به صورت ترکیب محدب همسایه خود نشان داد.

3. روش شناسی

فرض کنید M یک مش مثلث سه بعدی در ℝ ³ باشد. روش هایی برای نشان دادن یک مش توسعه داده شده است، با مثال هایی که در [ 10 ] توضیح داده شده است. به طور خلاصه، ما یک مش را یک جفت دنباله ای از رئوس آن و توپولوژی آن M = ( V , T ) در نظر می گیریم . V دنباله ای از n نقطه متمایز است، v _i = ( x _i , y _i , z _i ) در ℝ ³ . V را نیز می توان نقشه ای از مجموعه شاخص در نظر گرفت، I = {1…n } تا ℝ ³ ، که در آن V ( i ) = v _i برای همه i = 1، …، n . T توپولوژی یا ساختار مش است که به طور کامل در مجموعه شاخص تعریف شده است، I . توپولوژی مجموعه ای از مثلث ها یا چهره ها، مجموعه لبه ها، مجموعه مرزها و مجموعه رئوس داخلی/مرز مش را تعریف می کند.

ما داده‌ها را در بازه زمانی [ t _i , t _i _{+ 1} ] از داده‌ها در نمونه‌های زمانی، t _i و t _i _{+ 1} می‌سازیم، با تغییر هموار مش منبع به مش هدف. انتخاب داده در t _i به عنوان مش منبع و داده در t _i _{+ 1} به عنوان مش هدف، یا برعکس ، به کاربر بستگی دارد. با این حال، الگوریتم ما به گونه ای طراحی شده است که وقتی مش پیچیده تر به عنوان مش منبع انتخاب شود، سریعتر می شود (زیرا مسیرهای برش در مش هدف مورد نیاز نیست). ما همیشه مش منبع را با M _{s نشان می دهیم}و مش هدف به صورت M _t . پاراگراف های زیر برخی از اصطلاحات خاص مورد استفاده در مقاله را تعریف می کنند.

یک رأس کنترل مش، M ( V ، T )، یک راس انتخاب شده توسط کاربر، v _i ∈ V است. یک مسیر در مش M ( V , T ) دنباله ای است ( ν _p₁ , ν _p₂ , …, ν _ph ) که در آن p _i ∈ I و [ ν _pi , ν _pi _{+ 1} ] یک یال M برای همه است. i = 1، …،h − 1. مسیر مرزی مسیری است که تمام رئوس آن در مرزها قرار دارند. مسیر برش و مسیر حصار مسیرهایی هستند که به ترتیب در روش برش و روش پارتیشن استفاده می شوند.

یک k چندضلعی منتظم ، k ≥ 3 ، یک چند ضلعی ساده با k رأس در یک صفحه معین است، به طوری که مختصات رئوس آن با فرمول، برای همه i در {1… k } تعریف می شود.

خطای , ε ( M , N ) بین دو مش M و N با شکل ε ( M , N ) = max(max( dist ( x , N): x ∈ V _MI ), max( تعریف می شود . dist ( x,M )،: x ∈ V _NI ))، که در آن V _MI مجموعه ای از رئوس داخلی M است، V _NI مجموعه ای از رئوس داخلی N وdist ( x ، L ) (فاصله بین یک نقطه، p ، و یک مش، L ) حداقل فاصله بین نقطه، p ، و نقاط L است. توجه داشته باشید که در این عبارت فقط رئوس داخلی را در نظر می گیریم نه رئوس مرزی.

تعریف 1. دو مش، M ( V , T ) و N ( U , G ) با هم سازگارند ، اگر (i) V و U تعداد کل رئوس یکسانی داشته باشند و به ترتیب آنها مطابقت داشته باشند، یعنی یک نقشه بی اهمیت. , h , وجود دارد، به طوری که h ( v _i ) = u _i برای همه i = 1, …, n ; و (ii) T = G.

تعریف 2. با توجه به m ≥ 2 و یک شبکه n- راس، M ( V ، T )، مسیرهای مش، M ( V ، T )، که نشان دهنده تکامل پیوسته آن به مش سازگار آن، N ( U ، T )، n رشته خط مجزا هستند، به طوری که برای هر رشته خط، m رئوس وجود دارد، به عنوان مثال ، رشته خط i ، و ، برای همه i = 1، …، n Ijgi 02 00837 i002

تعریف 3. با توجه به m ≥ 2، یک شبکه n- راس، M ( V , T ) و مش سازگار با آن N ( U , T )، مسیرهای خطی مش، M ( V , T ) مسیرهای M هستند، که در آن هر رأس یک مسیر، , برای همه i = 1, …, n تعریف می شود. j = 1، …، m .

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

شکل 1. بلوک دیاگرام الگوریتم.

3.1. برش دادن

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

فرض کنید P مجموعه ای از مسیرهای برش انتخاب شده توسط کاربر در M باشد. این روش مش، M را توسط P قطع می کند. همانطور که در شکل 2 نشان داده شده است، سه نوع مسیر برش پشتیبانی می شود . همه رئوس و لبه های مسیرهای برش تکراری هستند (مانند شکل 2 الف)، به جز راس یک طرفه (مانند شکل 2 ب) یا رئوس دو سر (مانند شکل 2 ج). دایره های چین دار آبی نشان دهنده راس های تکراری هستند.

شکل 2. برش مش ها با برش مسیرها. ( الف ) همه رئوس و لبه ها تکراری هستند. ( ب ) همه رئوس و یال ها، به جز راس یک طرفه، کپی هستند. ( ج ) همه رئوس و یال ها، به جز رئوس دو سر، کپی هستند.

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

3.2. تنظیم محدودیت ها

الگوریتم ما از چهار نوع محدودیت استفاده می کند: راس کنترل ، جفت رأس کنترل ، مسیر حصار ، و محدودیت اتصال . کاربر تمام محدودیت ها را به صورت دستی با یک ابزار خودکار انتخاب می کند، مانند یافتن کوتاه ترین مسیر بین رئوس دو سر. رئوس کنترل و جفت رئوس کنترل، راس های متناظر ثابت (معلوم) را ارائه می کنند و برای کنترل تناظر راس های دیگر استفاده می شوند. رئوس کنترل اغلب رئوس گوشه ای هستند. رئوس کنترل در مش منبع و مش هدف به ترتیب با دو دنباله از رئوس کنترل، Vc و Wc _{نمایش داده می شوند، به طوری که آنها جفت رئوس کنترل را}_با ترتیب آنها استنتاج می کنند.یعنی ( v _c,i , w _c,i ) یک جفت رأس کنترلی است. مسیرهای حصار برای تغییر مسیرهای برش در مش هدف یا برای تقسیم مش منبع و مش هدف به تکه هایی که برای دیسک ها همومورف هستند استفاده می شود. مسیرهای حصار برای اتصال دقیقاً دو راس کنترل مورد نیاز است، به عنوان مثال، یک مسیر حصار با رئوس h در مش منبع، Ms , p ( ν _p₁ , ν _p_{2 ,}_… , ν _ph ) شرایط زیر را برآورده می کند: v _p₁ ، v _ph ∈ V_c و v _pi ∉ V _c برای همه i = 2, …, h − 1. تمام مسیرهای حصار مش منبع یا مش هدف یکدیگر را فقط در رئوس انتهایی خود قطع می کنند. شکل 3 نمونه ای از رئوس کنترل، جفت رئوس کنترل (با ترتیب مربوطه) و مسیرهای حصار را نشان می دهد.

شکل 3. نمونه ای از رئوس کنترل، جفت رئوس کنترل و مسیرهای حصار.

محدودیت های اتصال، چسبندگی رئوس مش منبع را به سطوح کنترل کننده در طول تکامل مش منبع نشان می دهد. اگر یک محدودیت اتصال سطح کنترل 1 بر روی یک راس مش منبع اعمال شود، این راس همیشه در طول تکامل خود بر روی سطح کنترل کننده قرار می گیرد. به طور مشابه، اگر یک محدودیت اتصال سطح 2 کنترلی بر روی یک راس مش منبع اعمال شود، این راس همیشه روی خطی قرار می گیرد که محل تلاقی دو سطح کنترل کننده است. در این مقاله، ما محدود می‌کنیم که محدودیت‌های اتصال فقط بر رئوس مرزی مش منبع اعمال می‌شوند و حداکثر دو سطح کنترل کننده در هر محدودیت اتصال وجود دارد. علاوه بر این، تمام رئوس متصل به دو سطح باید رئوس کنترل باشند.شکل 4 نمونه ای از اتصال محدودیت ها را نشان می دهد. در این شکل، راس های مرزی، 1، 2، 3 و 4، به یک سطح (S1) متصل می شوند، ( یعنی محدودیت اتصال سطح 1 کنترل کننده)، راس مرزی 5 به دو سطح (S1، S2)، ( یعنی 2-محدودیت اتصال سطح کنترلی) و سایر رئوس مرزی به هیچ سطحی متصل نمی شوند، به این معنی که هیچ محدودیت پیوستی بر این راس های مرزی اعمال نمی شود.

شکل 4. نمونه ای از اتصال محدودیت ها.

3.3. تقسیم بندی

این رویه با فرآیند فرعی DefinePatches شروع می شود ، که مش منبع و مش هدف را به تکه هایی با مسیرهای حصار و مرزهای آنها تقسیم می کند.

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

پس از تمام مراحل بالا، مش های Ms و M t به _همان تعداد وصله، k تقسیم _می شوند . اگر این شرط برآورده نشد، برای راه اندازی مسیرهای حصاری بیشتر، لازم است تمامی مراحل بالا تکرار شوند. این شرط را می توان برای هر نوع مش از طریق مجموعه مسیرهای حصار تعریف شده توسط کاربر برآورده کرد. کشف وصله های مربوطه با شناسایی رئوس کنترل و ترتیب آنها در هر پچ انجام می شود. نتیجه این مرحله مجموعه‌ای از جفت‌های وصله ( P _i,s , P _i,t ) برای همه i در {1… k } است.یک بار دیگر، اگر چنین مجموعه ای از جفت پچ ها پیدا نشد، تمام مراحل بالا تکرار می شوند. علت این شکست عدم تطابق بین رئوس کنترل است. این مرحله در صورتی موفقیت آمیز خواهد بود که رئوس کنترل و ترتیب آنها درست باشد.

3.4. در حال محاسبه

در این روش، ما با هر وصله منبع و جفت پچ هدف متناظر آن کار می کنیم که با (Ls, Lt ₎ نشان داده شده است _.این روش شامل دو روش فرعی است: محاسبه پارامترهای متقابل (یا ساخت مش های سازگار) و فرآیند فرعی یافتن مسیرها.

3.5. محاسبه پارامترهای متقابل یا ساخت مش های سازگار

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

با توجه به دو تکه یا مش مثلث، Ls ( V ، T )، L _t₍ W ، F ) ، هر دو به دیسک‌ها همومورف هستند. بگذارید I _cs = ( i _cs_,1 … i _cs,k ) و I _ct = ( i _ct_,1 … i _ct,k ) دنباله های شاخصی از k , k ≥ 3 با رئوس کنترل متمایز در L _s و L _{t باشند.}، به ترتیب؛ علاوه بر این، مطابقت بین دنباله های شاخص به ترتیب آنها وجود دارد. همه رئوس کنترل در مرز مش های خود هستند و به ترتیب در جهت عقربه های ساعت یا خلاف جهت عقربه های ساعت قرار دارند. برای ساخت مش های سازگار، ابتدا یک دوشاخه بین دو مش پیدا می کنیم و سپس با استفاده از این نقشه یک مش جدید می سازیم.

در مرحله اول، هر دو مرز وصله را به مرز یک چند ضلعی k- منظم با استفاده از روش طول “وتر” برای هر مسیر مرزی ترسیم می کنیم ( شکل 5 )، یعنی نگاشت f از یک مسیر، p ( ν _p₁ , ν _p₂ ، …، ν _ph )، با رئوس h به یک قطعه. s ( x ₁ ، x ₂ ). از واحد منظم k- چند ضلعی. این روش با فرمول زیر تعریف می شود: f ( ν _p₁ ) = x ₁ ; برای همه i در 2، …، h ، جایی که . Ijgi 02 00837 i007

شکل 5. نمونه ای از روش طول “وتر”.

پس از آن، ما از پارامتر مقدار میانگین [ 7 ، 9 ] برای به دست آوردن نقشه های دوگانه، f _s و f _t ، به ترتیب _از_Ls و Lt به این چند ضلعی k- منظم واحد استفاده می کنیم. نقشه ترکیب، f = f _t⁻¹ × f _s ، یک انشعاب از Ls به L _t است _.شکل 6 نمونه ای از این پارامترها را نشان می دهد.

شکل 6. پارامترهای واحد k -polygon منظم.

در مرحله دوم ، با مجموعه‌ای از رئوس آن، یک شبکه جدید به نام L _st می‌سازیم که تصویری از V تا f ، U = f ( V ) و توپولوژی T ، L _s ، یعنی L است. _st ( U , T ). توجه داشته باشید که L _st یک مش سازگار از L _s است. تمام رئوس آن روی L _t هستند و مش تقریبی L _t است. ما نیاز داریم که L _stیک تقریب “خوب” از L _t است، به عنوان مثال ، خطا بین L _st و L _t کوچکتر از آستانه کاربر است. از آنجایی که همه رئوس L _st روی L _t هستند، فاصله هر راس L _st تا L _t صفر است. بنابراین، خطای بین L _st و L _t حداکثر فاصله از رئوس داخلی L _t تا L _{st است.}همانطور که در تعریف اصطلاحات نشان داده شده است. برای به دست آوردن خطای کوچکتر از آستانه کاربر، مراحل زیر را تکمیل می کنیم. برای هر رأس داخلی، w _i از مش هدف، L _t ( W ، F )، اگر فاصله، d _i ، از w _i تا مش، L _st ( U ، T )، بزرگتر از آستانه کاربر باشد، ɛ ، و مثلث ( v _i ، v _j ، v _h ) حاوی یک نقطه، p ، جایی که ||w _{i است},p||=d _i ، یک مثلث ( v _i , v _j , v _h ) را با درج یک نقطه جدید در مرکز آن و به روز رسانی Ls به سه مثلث تقسیم می کنیم (به وضوح خطا بین L s قدیمی و _به روز شده است _. L _s صفر است، بنابراین برای وضوح، ما همچنان مش به روز شده را با _Ls ( V , T ) نشان می دهیم. شکل 7 نمونه ای از این زیربخش را نشان می دهد. اگر چنین اصلاحی تکمیل شده باشد، مش جدید، L _st، باید ساخته شود و دوباره برای خطا بررسی شود. توجه داشته باشید که این تقسیم بندی خطای بین L _t و L _st را کاهش می دهد و بر روی سایر وصله ها تأثیر نمی گذارد.

شکل 7. تقسیم یک مثلث ( v _i ، v _j ، v _h ) به سه مثلث جدید، ( v _i ، v _j ، v _c )، ( v _j ، v _h ، v _c )، ( v _h ، v _i ، v _c )، با درج یک نقطه جدید، v _c ، در مرکز مثلث ( v _i ، v _j ، v _h ).

پس از دو مرحله فوق، _Ls ( V ، T ) و L _st ( U ، T ) مش های سازگار هستند و خطای بین L _st و L _t کوچکتر از آستانه، ɛ است. این جفت مش را می توان با مش، Ls ( V _، T ) و دنباله ای از بردارهای جابجایی نشان داد، که در آن هر بردار جابجایی، تفاوت یک راس، u ، در U و راس متناظر آن، v ، در V است..

3.6. یافتن مسیرها

این روش فرعی برای یافتن مسیرهایی استفاده می شود که در آن رئوس مش منبع به رئوس هدف متناظر خود تبدیل می شوند. در صورت عدم وجود محدودیت پیوست، به عنوان مثال ، مش منبع آزاد است که از شکل اصلی خود به شکل هدف خود تبدیل شود، مسیر تمام رئوس آن با مسیرهای خطی آنها تعریف می شود (آزمایش اول و دوم در بخش 4 )، و بقیه این محاسبه را می توان نادیده گرفت. هنگامی که برخی از محدودیت‌های پیوست برای محدود کردن هندسه مش منبع در طول تکامل آن استفاده می‌شود، مسیر رئوس باید از مسیر خطی آنها محاسبه شود (آزمایش سوم در بخش 4) .). مسیرهای رئوس، که محدودیت های اتصال سطح کنترلی 1 یا 2 را اعمال می کنند، به ترتیب خطوطی از مسیرهای خطی آنها به سطح کنترل کننده یا خط تقاطع دو سطح کنترل کننده هستند. مسیرهای رئوس مرزی بدون اتصال قیود، مسیر خطی آنهاست. مسیر تمام رئوس داخلی با حل سیستم های خطی یدکی معادلات محاسبه می شود. الگوریتم به شرح زیر است.

با توجه به یک مش مثلث، L _s ( V , T ) , که در آن V = ( v ₁ , v ₂ , …, v _n ) دنباله ای از n رأس است، اجازه دهید m تعداد رئوس هر مسیر یک کاربر باشد. عدد صحیح تعریف شده، m ≥ 2. با استفاده از قیودهای پیوست، مجموعه رئوس، V , L _s را می توان به زیرمجموعه های مجزا تقسیم کرد:

که در آن V _I مجموعه رئوس داخلی، V _B₀ مجموعه رئوس مرزی بدون قیود است، V _B₁ مجموعه ای از راس های مرزی با محدودیت های اتصال سطح کنترل کننده 1 و V _B₂ مجموعه رئوس مرزی با 2-کنترل محدودیت های اتصال سطح.

ابتدا، مسیر رئوس در V _B₀ ، V _B₁ و V _B₂ با اتصال رئوس V _B₀ ، V _B₁ و V _B₂ به رئوس مربوطه خود برای ایجاد پاره خط مقداردهی اولیه می شوند. سپس، این بخش‌های خط را به زیربخش‌های مساوی m − 1 تقسیم می‌کنیم ، به عنوان مثال ، مسیرهای خطی برای هر مرز ساخته می‌شوند. متعاقبا، مسیر رئوس در V _B₁با جایگزینی رئوس آنها با برآمدگی آنها در سطوح کنترل اصلاح می شوند. مسیر هر رأس در V _B₂ با تغییر رئوس آن به طرح ریزی آن به منحنی، که محل تلاقی دو سطح کنترل کننده راس است، اصلاح می شود.

ما مسیر رئوس را در V _I با محاسبه m – 2 مش های میانی محاسبه می کنیم، زمانی که مش، _Ls ( V ، T )، به مش متناظر خود، L st ₍ U ، T ) تبدیل می شود. L _s را با L ¹ ، L _st را با L ^m و مش های میانی را با L ^t برای هر t = 2، …، m − 1 برچسب گذاری می کنیم . مرز مش، L ^t, توسط مسیرهای رئوس در V _B₀ , V _B₁ و V _B₂ تعریف می شود. همچنین فرض می کنیم که هر رأس داخلی L ^t ترکیبی محدب از همسایگان خود به شرح زیر است. اجازه دهید N ( i ) مجموعه شاخص های رأس همسایگی رأس باشد و I _I مجموعه شاخص V _I باشد. مجموعه ای از مقادیر واقعی غیر منفی، , وجود دارد، به طوری که: Ijgi 02 00837 i010

و معادله (1) زیر برای همه i در I _I برآورده می شود :

(1)

ما بر اساس مقادیر، و از اولین مش و آخرین مش، L ¹ ، L ^m ، مانند رابطه (2) محاسبه می کنیم:

(2)

مقادیر و از L ¹ و Lm با استفاده از مقدار میانگین همانطور که در [ ⁷ ] با معادله (3) و نمادهای شکل 8 توضیح داده شده است، محاسبه می شوند .

(3)

از آنجایی که 0 ≤ α _j₋₁ ، α _j ≤ π، λ _ij در رابطه (3) تعریف شده و غیرمنفی است، در رابطه (2) برای هر t = 2، …، m − 1 غیر منفی است. 1) یک سیستم خطی پراکنده از معادلات را ارائه می دهد که می تواند به اندازه کافی توسط یک حل کننده حل شود، مانند OpenNL [ 20 ] یا Eigen [ 21 ]. این سیستم معادلات دارای یک راه حل منحصر به فرد است که در [ 8 ، 9 ] ارائه شده است. به دلیل راه حل منحصر به فرد، تمام مسیرهای L تعریف شده است. Ijgi 02 00837 i014

شکل 8. نمادهای زاویه.

توجه داشته باشید که با استفاده از نمایش های مش در جایی که توپولوژی به طور صریح ذخیره می شود، تعیین همسایگی، N ( i )، راس v _i بی اهمیت است. چنین نمایش های مش شامل G-Maps، C-Maps، Cell-Tuple-Structure، Halfedge ساختار داده و غیره است.

4. نرم افزار و آزمایش

الگوریتم شرح داده شده در بخش 3 به عنوان یک افزونه gOcad پیاده سازی شده است. این نرم افزار از کتابخانه های Boost C++ [ 22 ] و Computational Geometry Algorithms Library (CGAL) [ 23 ] استفاده می کند. برای استفاده از پارامترسازی CGAL زمانی که دامنه پارامتری یک واحد k -polygon منظم است، یک کلاس جدید پیاده‌سازی مفهوم BorderParameterizer_3 پیاده‌سازی شده است. در این نرم افزار از کتابخانه OpenNL [ 20]، ادغام شده با CGAL، به عنوان حل کننده معادلات خطی پراکنده برای یافتن مسیرها. این نرم افزار یک رابط کاربری گرافیکی برای کاربر نهایی فراهم می کند تا محدودیت ها را وارد کرده و اصلاح کند. کتابخانه نمودار تقویتی برای یافتن کوتاه ترین مسیر برای ساخت مسیرهای برش و حصار استفاده می شود.

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

شکل 9. گنبد نمکی در زمان. ( الف ) t = 1، ( ب ) t = 2/3، ( ج ) t = 1/2، ( d ) t = 0.

در آزمایش دوم، داده های داده شده شامل چهار مجموعه داده در چهار نمونه زمانی، t = 1 ، t = 2، t = 3 و t = 4 بود. در زمان t = 4، شش سطح، یعنی پنج افق زمین‌شناسی وجود داشت. A، B، C، D و E، و خطا ( شکل 10 a). در زمان t = 3، پنج سطح نشان دهنده چهار افق زمین شناسی، A، B، C و D، و گسل ( شکل 10 ب). در زمان t = 2، داده های داده شده شامل چهار سطح A، B و C و خطا بود ( شکل 10 c). در زمان t = 1، سه سطح نشان دهنده دو افق زمین شناسی A و B و گسل (شکل 10 د). گسل در کل بازه زمانی ثابت فرض شد [1، 4]، و افق زمین شناسی، E در بازه [3، 4] ثابت بود. هر افق در هر بازه زمانی با استفاده از نرم افزار اجرا شد. به عنوان مثال، برای ساخت داده های مکانی-زمانی افق زمین شناسی، B، در بازه زمانی [2، 3] از دو شکل آن در موارد زمانی t = 2، 3، ما فقط مجبور شدیم هشت جفت رئوس کنترل را تنظیم کنیم. شکل 11 افق زمین شناسی، B را در بازه زمانی نشان می دهد [2، 3]. با قرار دادن تمام نتایج حاصل از داده های ساخته شده هر افق در هر بازه زمانی در مختصات مکانی و زمانی یکسان، فرآیندهای زمین شناسی را در یک منطقه و در یک بازه زمانی مشخص شبیه سازی می کنیم. شکل 12ساختار زمین شناسی منطقه مورد نظر را در زمان t = 2.50 نشان می دهد.

شکل 10. داده های داده شده در نمونه های زمانی. ( الف ) t = 4، ( ب ) t = 3، ( ج ) t = 2، ( د ) t = 1.

شکل 11. افق زمین شناسی، B، در بازه زمانی [2، 3] .

شکل 12. ساختار زمین شناسی یک منطقه مورد نظر در زمان t = 2.50 .

در آزمایش سوم، ما با چهار سطح، یعنی سطح زیرزمین و سطوح بالایی، A، B و C، به ترتیب رسوبات A، B و C کار کردیم. داده ها در شش نمونه زمانی داده شد: t = 5 ( شکل 13 a)، t = 4 ( شکل 13 ب)، t = 3 ( شکل 13 ج)، t = 2 ( شکل 13 د)، t = 1 ( شکل 13 e) و t = 0 ( شکل 13و) سطح زیرزمین ثابت در نظر گرفته شد. ما داده های سطوح را در بازه زمانی [0, 5] با ساخت داده های هر سطح (A, B, C) در هر بازه زمانی [0, 1], [1, 2], [3,4] ساختیم. و [4، 5]. به منظور اختصار، ما فقط روش ساخت داده های سطح B را در بازه زمانی توصیف می کنیم [1، 2]. در این مورد، مش منبع در زمان t = 2 سطح B بود و مش هدف سطح A در زمان t = 1 بود. سطح کنترل کننده سطح زیرزمین بود. برای نگه داشتن سطح B در تماس دائمی با سطح زیرزمین، از محدودیت‌های اتصال استفاده شد. برخلاف آزمایش اول و دوم، که در آن از مسیرهای خطی استفاده می شد، مسیرها باید با استفاده از روش فرعی یافتن مسیرها، همانطور که در بخش فرعی 3.4 نشان داده شده است، محاسبه می شدند.شکل 14 داده های سطح B را در بازه زمانی نشان می دهد [1، 2]. پس از ساخت تمام داده‌ها، داده‌های نهایی در همان مختصات مکانی و زمانی قرار گرفتند تا فرآیندهای زمین‌شناسی – در این مورد رسوب‌گذاری و فرسایش – شبیه‌سازی شود. شکل 15 ساختار زمین شناسی منطقه مورد نظر را در زمان t = 1.50 نشان می دهد.

شکل 13. داده های داده شده در شش نمونه زمانی. ( الف ) t = 5، ( ب ) t = 4، ( ج ) t = 3، ( د ) t = 2، ( e ) t = 1، ( f ) t = 0.

شکل 14. سطح بالا B در بازه زمانی [1، 2].

شکل 15. ساختار زمین شناسی منطقه مورد نظر در زمان t = 1.5.

5. بحث و نتیجه گیری

روش ما کارایی و اثربخشی خود را برای ساخت خشن داده‌های مکانی-زمانی با محدودیت‌هایی از نظر هندسه (بدون محدودیت فیزیکی و مکانیکی) نشان داده است. زمانی مفید است که هیچ مدل فرآیند فیزیکی یا مکانیکی در دسترس نباشد یا زمانی که داده های کافی برای این مدل ها وجود ندارد. روش ما شامل چهار رویه اصلی است که در آن دو رویه اول نیمه دستی و دو رویه آخر به صورت خودکار هستند. مشارکت های ما شامل یک روش برش جدید و یک روش فرعی جدید برای یافتن مسیرها با استفاده از ترکیبات محدب است. با توجه به روش برش، روش ما می تواند با مش های دلخواه کار کند. با پارتیشن بندی مش ها به تکه ها، به عنوان مثال، مش های مثلثی به دیسک ها همومورف می شود، این روش مشکل اصلی را به مسائل کوچکتر و ساده تر کاهش می دهد. بدیهی است که ما می توانیم از طریق روش های محاسباتی موازی به نتایج سودمندتری دست یابیم. محاسبات اصلی شامل محاسبه فرآیند فرعی پارامترسازی و فرآیند فرعی یافتن مسیرها است. پیچیدگی هر دو برابر است با پیچیدگی یک روش پارامترسازی محدب و با مرز ثابت، به عنوان مثال، روش پارامترسازی مقدار میانگین. زمان بندی برخی از الگوریتم های پارامترسازی در [ 11 ] ارائه شده است.

به طور خلاصه، ما بر نتایج به دست آمده در این مطالعه به شرح زیر تأکید می کنیم:

(1): معرفی روشی جدید برای ساخت داده های مکانی – زمانی در علوم زمین.
(2): پیاده سازی الگوریتم به عنوان یک پلاگین gOcad.
(3): آزمایش با چند نمونه

در آینده، هدف ما بهبود الگوریتم برای یافتن مسیر فرعی و توسعه یک الگوریتم جدید برای اجسام غیر از مش های مثلثی، مانند جامدات یا اجسام در ابعاد بالاتر خواهد بود.

منابع

Le، HH; جبرئیل، پ. گیتزل، جی. Schaeben, H. یک مدل داده زمین شناسی مکانی-زمانی شی رابطه ای. محاسبه کنید. Geosci. 2013 ، 57 ، 104-115. [ Google Scholar ] [ CrossRef ]
ایوانوفسکی، م. Serra, J. درونیابی مورفولوژیکی و تصاویر رنگی. در مجموعه مقالات دهمین کنفرانس بین المللی تجزیه و تحلیل تصویر و پردازش ICIAP’99، ونیز، ایتالیا، 27-29 سپتامبر 1999. انجمن کامپیوتر IEEE: واشنگتن، دی سی، ایالات متحده آمریکا، 1999; ص 50-55. [ Google Scholar ]
سیراکوف، ن.ام. گرانادو، آی. Muge، رویکرد درون یابی FH برای بازسازی صاف سه بعدی اجسام زیرسطحی. محاسبه کنید. Geosci. 2002 ، 28 ، 877-885. [ Google Scholar ] [ CrossRef ]
موراولیانسکی، ن. ماتسوپولوس، جی.کی. دلیباسیس، ک. آسوستاس، پ. نیکیتا، KS ترکیب یک روش درونیابی مورفولوژیکی با یک روش بازسازی سطحی برای نمایش سه بعدی داده های توموگرافی. J. Vis. اشتراک. Image R. 2004 , 15 , 565-579. [ Google Scholar ] [ CrossRef ]
کلز، اس. Dyn, N. بازسازی اشیاء سه بعدی از مقاطع عرضی دوبعدی با طرح تقسیم بندی 4 نقطه ای متناسب با مجموعه ها. محاسبه کنید. نمودار. 2011 ، 35 ، 741-746. [ Google Scholar ] [ CrossRef ]
فلوتر، ام اس; Gotsman, C. چگونه کاشی کاری ها را به صورت تزریقی شکل دهیم. جی. کامپیوتر. Appl. ریاضی. 1999 ، 101 ، 117-129. [ Google Scholar ] [ CrossRef ]
فلوتر، مختصات MS میانگین مقدار. محاسبه کنید. به Geom کمک کرد. دس 2003 ، 20 ، 19-27. [ Google Scholar ] [ CrossRef ]
فلوتر، کاشی کاری پارامترهای MS و تقریب داده های پراکنده. بین المللی J. مدل شکل. 1998 ، 4 ، 165-182. [ Google Scholar ] [ CrossRef ]
فلوتر، MS Parametrization و تقریب صاف مثلث های سطحی. محاسبه کنید. به Geom کمک کرد. دس 1997 ، 14 ، 231-250. [ Google Scholar ] [ CrossRef ]
بوچ، ام. کوبلت، ال. پالی، ام. آلیز، پی. Lévy، B. پردازش مش چند ضلعی ; AK Peters, Ltd.: Natick, MA, USA, 2010; صص 1-230. [ Google Scholar ]
هورمن، ک. پولثیر، ک. Sheffer, A. Mesh Parameterization: Theory and Practice. در SIGGRAPH Asia 2008 یادداشت های دوره ; ACM Press: سنگاپور، 2008; صص 1-87. [ Google Scholar ]
لیپمن، ی. لوین، دی. مختصات کوهن-اور، دی. گرین. ACM Trans. نمودار. 2008 ، 27 ، 1-10. [ Google Scholar ] [ CrossRef ]
لی، ایکس. گو، ایکس. Qin, H. نقشه برداری سطح با استفاده از تجزیه مداوم شلوار. IEEE Trans. Vis. محاسبه کنید. نمودار. 2009 ، 15 ، 558-571. [ Google Scholar ] [ CrossRef ]
لیو، YS; Yan، HB; مارتین، آر. شکل‌گیری سطحی به‌عنوان صلب. جی. کامپیوتر. علمی تکنولوژی 2011 ، 26 ، 548-557. [ Google Scholar ] [ CrossRef ]
Yan، HB; هو، اس ام. مارتین، R. شکل‌گیری سه بعدی با استفاده از درونیابی میدان کرنش. جی. کامپیوتر. علمی تکنولوژی 2007 ، 22 ، 147-155. [ Google Scholar ] [ CrossRef ]
الکسا، م. کوهن-اور، دی. لوین، دی. الحاق شکل به‌عنوان صلب. در مجموعه مقالات بیست و هفتمین کنفرانس سالانه گرافیک کامپیوتری و تکنیک های تعاملی (SIGGRAPH ’00)، نیواورلئان، لس آنجلس، ایالات متحده آمریکا، 23 تا 28 ژوئیه 2000; ACM Press: نیویورک، نیویورک، ایالات متحده آمریکا، 2000; صص 157-164. [ Google Scholar ]
ون کایک، او. ژانگ، اچ. هامارنه، گ. کوهن-اور، دی. نظرسنجی در مورد مکاتبات شکل. محاسبه کنید. نمودار. انجمن 2011 ، 30 ، 1681-1707. [ Google Scholar ] [ CrossRef ]
کرایوی، وی. شفر، الف. پارامترهای متقاطع و مش بندی مجدد مدل های سه بعدی. ACM Trans. نمودار. 2004 ، 23 ، 861-869. [ Google Scholar ] [ CrossRef ]
پراون، ای. سولدنز، دبلیو. شرودر، P. پارامترهای مش سازگار. در مجموعه مقالات بیست و هشتمین کنفرانس سالانه گرافیک کامپیوتری و تکنیک های تعاملی (SIGGRAPH ’01)، لس آنجلس، کالیفرنیا، ایالات متحده آمریکا، 12 تا 17 اوت 2001. ACM Press: نیویورک، نیویورک، ایالات متحده آمریکا، 2001; صص 179-184. [ Google Scholar ]
OpenNL. کتابخانه عددی را باز کنید. در دسترس آنلاین: http://alice.loria.fr/index.php/software/4-library/23-opennl.html (در 20 ژوئیه 2013 قابل دسترسی است).
Eigen. Eigen v3 . در دسترس آنلاین: http://eigen.tuxfamily.org (دسترسی در 20 ژوئیه 2013).
تقویت کنید. کتابخانه های C++ را تقویت کنید. در دسترس آنلاین: http://www.boost.org (در 20 ژوئیه 2013 قابل دسترسی است).
CGAL. کتابخانه الگوریتم های هندسه محاسباتی . در دسترس آنلاین: http://www.cgal.org/ (دسترسی در 20 ژوئیه 2013).

© 2013 توسط نویسندگان; دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution ( http://creativecommons.org/licenses/by/3.0/ ) توزیع شده است.

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب