نیمه لبه دوگانه - یک ساختار داده اولیه/دوگانه توپولوژیکی و اپراتورهای ساخت برای مدل‌سازی و دستکاری مجتمع‌های سلولی

خلاصه

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

کلید واژه ها:

مدل سازی سه بعدی ; مدل سازی جامد ; ساختارهای داده ؛ اپراتورهای اویلر

1. تاریخچه GIS

این مقاله یک توصیف فنی دقیق و ویژگی‌های ساختار داده توپولوژیکی نیمه لبه دوگانه (DHE) و کاربرد آن در علوم اطلاعات جغرافیایی (GIS)، به ویژه در مدل‌سازی داخلی ساختمان را ارائه می‌کند. این شامل ناوبری مرتبط و اپراتورهای ساخت و ساز لازم برای استفاده راحت از DHE است. مقالات قبلی که DHE [ 1 ، 2 ، 3 ] را توصیف می‌کردند، اهمیت رویکرد اولیه/دوگانه، برخی کاربردها، نمایش مدل و توسعه اولیه را گزارش کردند، اما تنها با یک بحث مختصر در مورد جزئیات فنی و ویژگی‌ها. DHE با برخی دیگر از ساختارهای داده مشابه مقایسه می شود.

ساختارهای داده GIS دوبعدی اولیه برای نقشه‌های چندضلعی (کورپلث) طراحی شدند، جایی که هدف ترکیب مجموعه‌های مرزهای چندضلعی دیجیتالی جداگانه برای تشکیل یک شبکه بود. رویکردهای مختلفی تلاش شد، اما در نهایت یک ساختار مبتنی بر قوس غالب شد، که در آن یک “قوس” شامل یک مجموعه میانی از نقاط دیجیتالی بین “گره‌ها” در اتصالات مرزی بود. این ارتباط نزدیک با ساختار لبه بالدار [ 4 ]، با اشاره گر به چهار کمان مجاور و دو چند ضلعی محدود بود. ساختار لبه بالدار توسط باومگارت [ 4] و راهی برای اتصال لبه های مختلف یک دو منیفولد با استفاده از ساختاری که از اشاره گر دنبال می شود، ارائه کرد. به این ترتیب می‌توان در اطراف لبه‌ها و چهره‌های b-rep (نمایش مرزی) یک مدل CAD حرکت کرد. از این، Mäntylä [ 5 ] ساختار نیمه لبه را توسعه داد و از آن برای توسعه «اپراتورهای اویلر» استفاده کرد، مجموعه‌ای از عملیات محلی برای ساخت مدل که تضمین می‌کرد اتصال توپولوژیکی مدل را در صورت معتبر بودن پارامترهای ورودی حفظ کند.

با ظهور مدل‌سازی زمین مبتنی بر مثلث (TIN) از روش‌های مختلفی برای بیان روابط بین مثلث‌ها، لبه‌ها و گره‌ها به صورت دو بعدی استفاده شد. در حال حاضر، متداول ترین آنها سازه های مثلثی و سازه های لبه محور (لبه های بالدار و نیمه لبه) هستند. مثلث دلاوی (DT) معمولاً مورد استفاده قرار می گیرد، زیرا دارای چندین ویژگی ارزشمند است – به ویژه اینکه ممکن است به صورت محلی در زمان ثابت مورد انتظار به محض یافتن مثلث محصور به روز شود.

دوگانه آن نمودار Voronoi (VD) است که اغلب به خودی خود به عنوان یک ابزار تحلیلی ارزشمند است. اگر هر دو ساختار مورد نیاز است، ساختار ترکیبی، چهار لبه [ 6 ] اغلب استفاده می شود. این امکان پیمایش در صفحه را در فضای اولیه یا دوگانه فراهم می‌کند و فقط به ارجاعات اشاره گر نیاز دارد تا هر مسیری را در نمودار ترکیبی دنبال کنید.

اخیراً، GIS از نمای مسطح فراتر رفته و مدل‌های شهری با ساختمان‌های اکسترود شده، گاهی اوقات با ساختارهای بیرونی دقیق‌تر را شامل می‌شود [ 7 ]. با این حال، اینها معمولاً شامل سازه‌های داخلی نیستند و اگر اتاق‌ها و راهروهای مدلی داشته باشند، از نظر توپولوژیکی برای اجازه ناوبری داخلی به هم متصل نیستند – برای مثال، برنامه‌ریزی مسیر فرار. برای مدل‌سازی سه بعدی کامل با حجم‌های متعدد (مثلاً فضای داخلی ساختمان، اتاق‌ها)، ساختار داده‌ای متفاوت (جدید) مورد نیاز بود. مجتمع‌های سلولی سه‌بعدی به‌عنوان مدل‌های ریاضی (توپولوژیکی) برای اجسام سه بعدی غیر چندگانه در هندسه محاسباتی [ 8 ، 9 ] و طراحی به کمک رایانه [ 10 ، 11] پذیرفته شدند.]. دو منیفولد یک فضای توپولوژیکی است که در آن هر نقطه دارای یک همسایگی است که از نظر توپولوژیکی معادل یک دیسک دو بعدی باز است. مدل هایی که این را برآورده نمی کنند غیر چندگانه هستند [ 11 ]. اشیاء ساده دو منیفولد و غیر منیفولد در شکل 1 نشان داده شده است .

هدف تحقیق ما گسترش مفهوم اولیه/دوگانه چهار لبه به ساختارهای سلولی سه بعدی بود. در نظر گرفتن دوگانگی پوانکاره برای VD سه بعدی نشان داد که دوتایی یک وجه یک لبه نافذ و دوتایی یک حجم یک راس است – هم در فضای اولیه (DT) و هم در فضای دوگانه (VD). (در دوبعدی، دوتایی یک چند ضلعی یک راس است و دوتایی یک یال یک یال “نفوذ” است.) هر سلول ورونوی سه بعدی ممکن است به عنوان یک پوسته ساده b-rep ساخته شود و یک اشاره گر به لبه دوگانه نفوذ کند. هر چهره همین امر در مورد مجموعه سلولی 3D Delaunay نیز صادق است ( شکل 2). بنابراین، هر وجه لبه دارای یک اشاره گر به یک وجه لبه در ساختار دوگانه است – بنابراین یک وجه n لبه دارای n لبه نافذ در دوتایی است که هر یک از اینها بخشی از سلول دوتایی است که هر یک از n راس را احاطه کرده است. صورت.

این ساختار “چهار لبه تقویت شده” (AQE) [ 12 ، 13 ] را می دهد، که از ساختار داده چهار لبه (QE) [ 6 ] برای نمایش هر چند وجهی به صورت جداگانه استفاده می کند. پیمایش از یک سلول Delaunay به سلول بعدی شامل رفتن به لبه نفوذی، تغییر جهت معکوس در آن لبه و بازگشت به صفحه Voronoi سلول مجاور است. هر دو مجتمع سلولی اولیه و دوگانه از یک ساختار هستند. لدوکس و طلا [ 12] نشان داد که این سازه روش های ناوبری و ساخت سازه های سه بعدی Voronoi/Delaunay را فراهم می کند. با این حال، ساخت و ساز به افزودن یک راس جدید و وجوه مثلثی مرتبط به تسلاسیون محدود می‌شود و مدل‌های سه بعدی دلخواه و موارد غیر منیفولد پشتیبانی نمی‌شوند.

2. Dual Half-Edge

اگرچه رویه‌ها ساخت VD سه بعدی را با استفاده از AQE مجاز می‌دانستند، اما برای ساخت مجتمع‌های سلولی دلخواه مانند فضای داخلی ساختمان غیرعملی بود. AQE برای ساخت مش های چهار وجهی طراحی شده است. هیچ عملگر اویلر یا سایر اپراتورها برای مدیریت ساخت اشکال نامنظم ایجاد نشد.

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

پاسخ این بود که جفت هایی متشکل از یک نیمه لبه دوتایی اولیه و یک (به طور دائم به هم مرتبط) حفظ شوند. اینها را می‌توان در صورت لزوم با دیگر جفت‌های نیمه لبه به هم متصل کرد تا مجتمع‌های سلولی هندسی (اولیه) را تشکیل دهند. در این وضعیت، تمام نیمه لبه های داخلی، هم در فضای اولیه و هم در فضای دوگانه، به هم متصل شدند تا جفت های همسان را تشکیل دهند. با این حال، لبه‌های دوتایی که به قسمت بیرونی مدل نفوذ می‌کردند جفت نشده باقی ماندند. شرایط مرزی کامل را می‌توان هم برای مرز مطلق و هم برای فضای داخلی اتاق‌های نیمه یا کاملاً محصور، با افزودن یک مجموعه «خارجی» از نیم لبه‌ها به هر عنصر اتمی جدید حفظ کرد، بنابراین معادل سه‌بعدی را به دو بعدی داد. عملگر make-edge. عنصر اتمی نهایی (با خواص ناوبری کامل) از چهار جفت نیمه لبه تشکیل شده است.

ساختار داده DHE اصلاحی از AQE [ 12 ] برای پشتیبانی از ساخت مجتمع های سلولی دلخواه است. این به ساختارهای لبه وجهی [ 9 ]، لبه شعاعی [ 14 ] و نیمه لبه [ 5 ] مربوط می شود. به منظور ارائه روش های بصری ساخت مدل و پیمایش آن، مجموعه ای از عملگرها شامل اپراتورهای ناوبری، اپراتورهای اویلر و اپراتورهای اویلر توسعه یافته برای ساخت مدل های هندسی غیر منیفولد مبتنی بر پیچیده توسعه داده شد. جزئیات فنی به طور کامل در [ 15 ] توضیح داده شده است.

موجودیت های موجود در مدل عبارتند از: سلول ها، چهره ها، لبه ها و رئوس. سلول یک پوسته 3 بعدی b-rep با حجم صفر یا مثبت است. توجه داشته باشید که اگر برای مثال، یک سلول از دو وجه یکسان تشکیل شده باشد که توسط یک مجموعه از لبه ها به یکدیگر متصل شده اند، حجم می تواند صفر باشد. یک سلول توسط چهره هایی که یک پوسته بسته را تشکیل می دهند محدود می شود. چهره ها چند ضلعی های محدب یا مقعر هستند – هیچ محدودیتی برای وجه های مثلثی که اغلب در برنامه های GIS استفاده می شوند وجود ندارد. فرض بر این است که چهره‌ها مسطح هستند، اگرچه وجه‌های غیرمسطح در مراحل میانی فرآیند ساخت ظاهر می‌شوند. یک وجه توسط لبه هایی که یک چرخه حلقه را تشکیل می دهند محدود می شود و یال ها توسط رئوس محدود می شوند. یک لبه با دو DHE متصل نشان داده می شود. رئوس حاوی اطلاعات مختصات منحصر به فردی هستند اما پیوندهای توپولوژیکی ندارند.

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

ایده مشابهی از سلول خارجی قبلا توسط سایر محققان استفاده شده بود. لی و لی [ 10 ] یک منطقه باز بی نهایت (معادل سلول خارجی) را معرفی کردند که سایر مناطق بسته محدود را در بر می گرفت. مدل‌های تسلیت دوبعدی پیاده‌سازی شده با QE [ 6] دارای ویژگی یکسانی هستند: سلول های داخلی توسط یک سلول خارجی محصور شده اند که بی نهایت است. با این حال، اگر مدل بر روی یک کره سه بعدی ترسیم شود، سلول خارجی یک چندضلعی محدود است که بقیه سطح کره را نشان می دهد (سلول های داخلی + سلول خارجی = سطح کره). نمایش DHE دارای ماهیت دوگانه است، با تقارن کامل بین دو ساختار – نمودارهای اولیه و دوگانه – و مطابق با دوگانگی پوانکره سه بعدی است: در هر یک از فضاها، یک سلول با یک راس در فضای دوتایی خود، و یک چهره با یک یال در فضای دوگانه خود نشان داده می شود. این نوع ساختار را به دو نوع کاهش می دهد: راس و یال.

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

یکی دیگر از ویژگی های مهم مدل این است که سوراخ ها و حفره ها مجاز هستند: یک “لبه پل” [ 5 ] ( e _b در شکل 4 a) برای اتصال حلقه های داخلی (سوراخ ها) به حلقه بیرونی (روی) استفاده می شود ( f _INT) . و f _OUT به ترتیب در شکل 4 a). و یک “وجه پل” ( f _b در شکل 4 ب) برای اتصال یک سلول داخلی (یک حفره) با سلول خارجی ( _{به ترتیب}c _INT و c _OUT در شکل 4)ب). لبه‌های پل و وجه‌های پل مانند سایر مدل‌ها به یک مدل اضافه می‌شوند، اما ویژگی خاصی دارند که توسط اپراتورهای ناوبری مورد توجه قرار می‌گیرد. در صورت لزوم می توان این لبه را در طول فرآیند ناوبری حذف کرد. وجهه های پل دارای ویژگی هایی هستند که به لبه های دوگانه آنها اختصاص داده شده است: یک یال پل در نمودار اولیه نمایانگر یک وجه پل در دوتایی است و بالعکس .

DHE با تعریف یک مدل هندسی غیر منیفولد مبتنی بر پیچیده مطابقت دارد [ 11 ] – این امکان را برای نمایش جامدات فراهم می کند که در آن یک گره دوگانه حجم را نشان می دهد و تمام لبه ها و گره های اولیه متصل به این گره مرز حجم را مشخص می کنند. صورت های آویزان، لبه ها و ترکیب آنها نیز امکان پذیر است.

2.1. اطلاعات معنایی

یکی از جنبه های مهم یک مدل داده در GIS، توانایی تخصیص ویژگی ها (اطلاعات معنایی) به عناصر جداگانه است. تنها موجودیت‌های ساختاری که در مدل DHE نگهداری می‌شوند، نیمه لبه‌ها و رئوس هستند: چهره‌ها و حجم‌ها در ساختار دوگانه نشان داده می‌شوند. (این در گراف اولیه یا دوتایی اصلی صادق است.) بنابراین، ممکن است ویژگی ها به هر یک از این عناصر متصل شوند.

به عنوان مثال، در مدل نشان داده شده در شکل 5سه جعبه متصل وجود دارد که نشان دهنده سه اتاق مجاور است. اتاق ها با راس های دوگانه نشان داده می شوند، بنابراین یک ویژگی توصیف کننده یک سلول اولیه (به عنوان مثال، نام اتاق) را می توان به یک راس دوگانه اختصاص داد. دو ویژگی دیگر “Dijkstra distance” و “next escape connection” توسط الگوریتم پیمایش گراف دوگانه برای جستجوی مسیر فرار استفاده می شوند. همین ایده برای دیوارها و اتصالات بین اتاق ها اعمال می شود – یک ویژگی موجود اولیه را می توان به همتای دوگانه آن اختصاص داد: اطلاعات مربوط به رنگ دیوار یا وجود در را می توان به یک لبه دوگانه که نمایانگر دیوار اولیه است، اختصاص داد. از آنجایی که همه دیوارها دو طرفه هستند، می توان ویژگی های متفاوتی را به هر طرف دیوار نسبت داد، زیرا اغلب آنها تزئینات متفاوتی دارند. خاصیت ارتباط بین اتاق ها (به عنوان مثال، “وزن اتصال” مورد استفاده توسط یک الگوریتم مسیریابی که نشان دهنده هزینه پیمایش از طریق اتصال است) یک ویژگی موجودیت دوگانه است و مستقیماً به لبه ای که این اتاق ها را به هم متصل می کند اختصاص داده می شود. هر ویژگی مانند شماره شناسه را می توان به یال ها و رئوس اولیه و دوتایی نسبت داد.

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

2.2. اپراتورهای ناوبری

لبه عنصر اصلی ساختمان است: نیم لبه ها برای تقسیم یک لبه به دو نیمه جهت دار استفاده می شود که با نماد نشان داده شده در شکل 6 نشان داده شده است: الف: نیمی از یک لبه (خط مستقیم) با یک صورت (یک مربع) مرتبط است. در وسط) و یک راس (یک نقطه در انتها). چنین عنصری که یک راس، یک یال و یک وجه را که متقابل یکدیگر هستند گروه بندی می کند، پرچم [ 16 ] نامیده می شود. جهت با یک فلش در انتهای مرتبط با راس نشان داده می شود ( شکل 6 ب).

تمام نیمه لبه های یک مدل از نظر توپولوژیکی با استفاده از اشاره گر به هم متصل می شوند. دو نیمه متصل یک لبه را تشکیل می دهند (نیم لبه های a و b در شکل 7 a). یک لبه دو وجه مجاور یک سلول را تقسیم می کند. با این حال، اگر یک وجه مسطح نباشد، یک لبه می تواند به یک وجه برخورد کند، برای مثال یک وجه جانبی استوانه. تمام نیم یال های یک سلول با راس یکسان به هم متصل شده و یک ستاره را تشکیل می دهند (نیم لبه های a ، b و c در شکل 7 ب). با این حال، نیمه لبه‌های با راس یکسان از سلول‌های مختلف مستقیماً به هم متصل نیستند، اما راس یکسانی دارند. نیم لبه هایی که یک وجه را محدود می کنند نیز به هم متصل شده و یک حلقه تشکیل می دهند (نیم لبه های a ,b ، c و d در شکل 7 ج). هر نیم لبه در یک فضا به طور دائم با نیم لبه در دوتایی مرتبط است – این اتصال ایجاد شده در فرآیند ساخت هرگز اصلاح نمی شود. لبه های نیمه در دوگانه به همان روشی که در اولیه است به هم متصل می شوند.

ساختار داده ای که برای نمایش DHE استفاده می شود شامل ده نشانگر است ( پنج نشانگر برای نمایش نیم لبه در ابتدایی و پنج نشانگر برای نیمه لبه دوگانه): V ، S ، N _V ، N _F و D. یک مرجع به یک راس به V اختصاص داده می شود . دو نیم لبه توسط S به هم متصل می شوند . N _V و N _Fبرای ذخیره اطلاعات مربوط به نیم یال بعدی به ترتیب در یک ستاره (در اطراف یک راس مشترک) و در یک حلقه (در اطراف یک صورت) استفاده می شود. “بعدی” به عنوان “بعدی” در جهت خلاف جهت عقربه های ساعت در نظر گرفته می شود که از بیرون یک سلول نگاه می کند. لبه های نیمه از فضای اولیه و دوگانه توسط اشاره گر D به هم متصل می شوند و در طول فرآیند ساخت تنظیم می شوند.

چهار اپراتور ناوبری مستقیماً از نشانگرها استفاده می کنند: Sym ، Next _V ، Next _F و Dual . Sym ( شکل 8 الف) از S برای حرکت از یک نیمه به لبه دیگر استفاده می کند. _V بعدی ( شکل 8 ب) از N _V برای حرکت در اطراف یک راس مشترک و _F بعدی ( شکل 8 ج) از N _F برای حرکت در اطراف یک صورت مشترک استفاده می کند (در هر دو مورد در جهت خلاف جهت عقربه های ساعت که از بیرون یک سلول نگاه می شود). استفاده دوگانه Dبرای حرکت از یک نیم لبه در یک فضا به نیمه لبه مرتبط در فضای دوگانه.

عملگرهای ناوبری مرکب بر اساس مجموعه پایه نیز تعریف می شوند: Prev _V ، Prev _F ، Next _E ، Prev _E و Adjacent . Prev _V و Prev _F به همان روشی که همتایان خود Next _V و Next _F دارند، امکان ناوبری را می دهند ، اما در جهت مخالف. _E بعدی ( شکل 8 d را ببینید) و قبلی _E امکان پیمایش در اطراف یک دسته از لبه ها را فراهم می کند. مجاوربرای پیمایش به سلول مجاور استفاده می شود – نتیجه عملگر یک یال در سلول مجاور است که مختصات یکسانی دارد و با طرف مقابل وجه مشترک مرتبط است. شکل 9 a دو سلول مجاور ( c ₁ و c ₂ ) را نشان می دهد که یک صورت مشترک دارند. این صورت دو طرفه است – یک طرف برای هر سلول. نیم لبه e در c ₁ نشان داده شده در شکل 9 b یکی از چهار لبه است که حلقه صورت را تشکیل می دهد. e.Adjacent یک نیم لبه مجاور در c ₂ است .

لازم به ذکر است که مجموعه اپراتورهای فوق الذکر امکان ناوبری در هر دو جهت، CW و CCW را در مدل هایی از جمله ساختارهای غیر منیفولد، به عنوان مثال، زمانی که دو سلول توسط یک گره یا لبه مشترک به هم متصل می شوند، می دهد. ممکن است تعداد نشانگرها در مورد مدل‌هایی که تمام سلول‌ها توسط یک چهره به هم متصل شده‌اند یا دوتایی مورد نیاز نیست کاهش یابد (به بخش 3.3 مراجعه کنید ).

نماد اشاره گر در اینجا استفاده می شود: برای مثال، عملگر مجاور با یک دنباله توصیف می شود: e.Adjacent = eDN _F .DS ، که در آن e نیم لبه منبع است. این باید به صورت زیر گسترش یابد: به نیمه لبه دوگانه e بروید، سپس نیم لبه بعدی را در خلاف جهت عقربه های ساعت به دور یک صورت بروید، سپس به فضای اصلی برگردید و به طرف مقابل لبه بروید.

مجموعه کامل اپراتورهای ناوبری توسط معادلات (1) – (9) توضیح داده شده است.

ه . اس y m \to e . اس

(1)

ه . ن e x تی V \to e . ن V

(2)

ه . ن e x تی اف \to e . ن اف

(3)

ه . D u a l \to e . D

(4)

ه . پ r e v V \to e . تو یک .__ن e x تی V . D u a l

(5)

ه . پ r e v اف \to e . تو یک .__اس y متر_ن e x تی اف . تو یک .__اس y متر

(6)

ه . A d j a c e n t \to e . تو یک .__ن e x تی اف . تو یک .__اس y متر

(7)

ه . ن e x تی E \to e . تو یک .__ن e x تی اف . D u a l

(8)

ه . پ r e v E \to e . اس y متر_تو یک .__ن e x تی اف . تو یک .__اس y متر

(9)

2.3. ساخت و ساز-اپراتورهای اویلر

ساخت پیشنهادی یک مدل کامپیوتری سه بعدی که به عنوان یک مجموعه سلولی نمایش داده می‌شود، به سلول‌های دلخواه (چند وجهی) با اشکال مختلف اجازه می‌دهد. فرآیند ساخت سلول “اتمیزه” می شود تا ساخت تدریجی (لبه به لبه) امکان پذیر شود. این امر با عملگرهای اویلر امکان پذیر است، که برای اصلاح اشیاء b-rep استفاده می شوند زیرا یکپارچگی توپولوژیکی را حفظ می کنند.

ساخت یک سلول واحد (بدون سلول دوگانه) یک فرآیند ساده با استفاده از عملگرهای سنتی اویلر است. برای مدل‌های غیر منیفولد، نیاز است که بتوان ساختارهای پیچیده‌تری ساخت: برای ایجاد مجتمع‌های سلولی غیر منیفولد، عملگرهای استاندارد اویلر باید برای مدیریت ارتباطات بین سلول‌ها و شامل عملیاتی مانند اتصال دو سلول توسط یک وجه مشترک، یال، گسترش داده شوند. یا رأس عملگرهای اویلر بسط یافته برای مدلسازی غیر منیفولد شامل کمپلکس های سلولی توسط Masuda [ 11 ] و Masuda و همکاران ارائه شد . [ 17 ].

سلول‌هایی که توسط یک صورت به هم می‌پیوندند یک وضعیت عادی در ساخت مجموعه سلولی است. دو سلول نیز می توانند توسط یک یال یا راس مشترک به هم متصل شوند. در این دو حالت امکان پیمایش مستقیم از یک سلول به سلول دیگر وجود ندارد. با این حال، سلول ها از طریق سلول خارجی به هم متصل می شوند و ناوبری بین سلول های داخلی در دوگانه امکان پذیر است. لازم به ذکر است که برخی از مدل های غیر منیفولد را می توان بدون سلول خارجی با استفاده از روش Cardboard and Tape [ 1 ] شبیه سازی کرد.

اپراتورهای ساخت و ساز در لایه ها گروه بندی می شوند ( شکل 10 ). اپراتورها به اپراتورهای سطح پایین تر وابسته هستند. فقط عملگرهای پایین‌ترین سطح براساس اشاره‌گرها و سایر عملیات‌های اساسی هستند. اپراتورهای سطوح بالاتر پیچیده تر و تخصصی تر هستند.

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

اپراتورهای سطح 2 امکان ساخت و اتصال لبه ها ( Make Complex Edge و Complex Splice ) و چهره ها ( Make Face and Sew ) را می دهند. این سطح ممکن است در برنامه های کاربردی برای ساخت مدل استفاده شود («مقوا و نوار» از Make Face و Sew استفاده می کند ).

اپراتورهای سطح 1 و 0 مستقیماً ساختار DHE را تغییر می‌دهند: اپراتورهای سطح 1 با لبه‌ها کار می‌کنند و اپراتورهای سطح 0 را که با دو نیم لبه کار می‌کنند: آنها نشانگرها را تغییر می‌دهند یا اختصاص می‌دهند و اپراتورهای دیگر را از مجموعه فراخوانی نمی‌کنند. Make Half Edge تنها اپراتوری است که حافظه کامپیوتر را برای DHE ذخیره می کند.

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

Make/Kill Edge, Vertex, Vertex, Face and Shell (MEVVFS) یک عملگر که می تواند برای ایجاد یک سلول جدید (پوسته) استفاده شود: یک لبه جدید در فضای خالی ایجاد می شود (شکل 11 ) . این لبه سلولی را تشکیل می دهد که ممکن است برای به دست آوردن یک چند وجهی بیشتر توسعه یابد. سلول خارجی و لبه های دوگانه نیز ساخته شده اند. چهار لبه در این فرآیند دخیل است – دو لبه در ابتدایی (خطوط سیاه و سفید)، و دو در دوتایی (خطوط چین دار سیاه). و چهار راس: دو راس در فضای اولیه ( P1 و P2 )، و دو راس در دو ( I و E ). رئوس P1 و P2 یک یال جدید را محدود می کنند. رئوس I و Eگره های دوگانه ای هستند که سلول های داخلی و خارجی یک مجتمع جدید را نشان می دهند – بنابراین این سلول ها توسط لبه های آویزان تشکیل می شوند: لبه ساخته شده از نیم لبه های a و b یک سلول داخلی مرتبط با راس I را تشکیل می دهد. لبه ساخته شده از نیم لبه های c و d یک سلول خارجی مرتبط با راس E را تشکیل می دهد . تمام اتصالات تنظیم شده توسط اپراتور در جدول 2 نشان داده شده است : نیم لبه های ایجاد شده در فرآیند (با برچسب a – h ) در ستون اول نشان داده شده است و مقدار اشاره گرها ( S , N _V , N _F , D و V .) در ستون های دیگر.

MEVVFS یک عملگر اویلر مناسب نیست زیرا عناصر زیادی را به یک مدل وارد می کند: یک لبه، دو راس، یک وجه و یک پوسته (یک یال یک عنصر توپولوژیکی حداقلی و معتبر است که امکان ناوبری را فراهم می کند؛ یک راس ایزوله هیچ اطلاعات توپولوژیکی را به همراه نمی آورد. ). یک چهره به طور خودکار ایجاد می شود و نتیجه نمایش DHE است. تعداد پوسته ها با تعداد کمپلکس های سلولی که متقابلاً قطع شده اند تعیین می شود. MEVVFS دو اپراتور استاندارد اویلر MFVS و MEV را ترکیب می کند – دو مرحله اول ساخت را در شکل 4.1 در [ 18 ] ببینید.

سایر عملگرهای پیاده سازی شده ( به عنوان مثال ، Make Edge and Vertex (MEV)، Make Vertex and Edge (MVE)، Make Zero-length Edge and Vertex (MZEV) و Make Edge and Face (MEF)) به عنوان عملگرهای استاندارد اویلر در نظر گرفته می شوند ( شکل 12 ). دوگانه در شکل 12 نشان داده نشده است ، اما توسط اپراتورها به روز شده است. لازم به ذکر است که برخی از اپراتورها را می توان تنها در فرآیند ساخت یک سلول قبل از اضافه شدن به یک مجموعه (مثلا MZEV) استفاده کرد.

اپراتورهای اویلر بررسی نمی کنند که آیا پارامترهای ورودی معتبر هستند یا خیر. به عنوان مثال، معمولاً انتظار می رود که دو نیمه لبه از یک حلقه چهره به عنوان ورودی برای MEF داده شود. نتیجه یک لبه جدید است که یک وجه را به دو قسمت تقسیم می کند. یک ساختار “عجیب”، که ممکن است یک نتیجه غیرمنتظره باشد، ایجاد می شود اگر دو نیمه لبه از حلقه های مختلف چهره به عنوان ورودی داده شود. به عنوان مثال، اگر نیمه لبه‌ها از سلول‌های مختلف باشند، اپراتور MEF ممکن است برای پیاده‌سازی اپراتور اضافی MEKFS (Make Edge و Kill Face و Shell) استفاده شود. آزمایش‌های اضافی ممکن است قبل از استفاده از اپراتور اویلر انجام شود تا سلول‌های سه بعدی معتبر را تضمین کند.

لازم به ذکر است که عملگرهای اویلر می توانند ساختارهای غیر سلولی را همانطور که توسط Akleman و همکاران تعریف شده اند ایجاد کنند. [ 19 ]، به عنوان مثال، یک چند ضلعی با سوراخ، بدون لبه بین حلقه های داخلی و خارجی. این وضعیت را می توان توسط یک سطح اضافی از اپراتورها مدیریت کرد که آزمایش های توپولوژیکی و عملگرهای اویلر را به منظور ایجاد ساختارهای سلولی معتبر با استفاده از “لبه های پل” انجام می دهند. نمونه ای که نیاز به چنین نمایشی دارد، یک مدل معماری است، که در آن پنجره سوراخی در دیوار است: آنها مرزهای مشترکی ندارند و ممکن است توسط یک “لبه پل” به هم متصل شوند.

2.4. اپراتورهای اویلر توسعه یافته

Join مجموعه‌ای از سه عملگر برای اتصال دو سلول است—ممکن است سلول‌ها توسط یک وجه، لبه یا راس مشترک به هم متصل شوند ( شکل 13 ). روابط بین سلول‌ها به این ترتیب تغییر می‌کند تا پیمایش مستقیم بین سلول‌ها امکان‌پذیر باشد و سلول‌ها بخشی از یک مجموعه باشند حتی اگر قبل از عملیات در دو مجتمع متفاوت باشند. “پیوستن” لبه های اولیه سلول خارجی را تغییر می دهد. اتصالات دوگانه به طور خودکار تغییر می کنند تا پیمایش مستقیم بین سلول ها امکان پذیر باشد (در شکل 13 خطوط نقطه چین و چهره های خاکستری نشان دهنده دوتایی هستند). “پیوستن” یک معکوس دارد – “جدا کردن”.

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

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

همان نتیجه (دو سلول متصل) را می توان به روشی متفاوت به دست آورد ( شکل 14 را ببینید ). این روش و مجموعه ای از عملگرهای اویلر استفاده شده بر اساس [ 20 ] است. لازم به ذکر است که در این فرآیند آخرین KEF از چهار KEF قبل از اتصال دو سلول توسط یک وجه معنای متفاوتی دارد زیرا با برداشتن آخرین لبه، وجه اصلی به دو قسمت تقسیم می‌شود. همین امر در مورد سلول نیز صدق می کند. بنابراین، آخرین عملگر را می توان KEMFS نامید.

مثال بالا را می توان با استفاده از عملگر توسعه یافته Split by Face ساده کرد ( شکل 15 را ببینید ).

ادغام ، مانند “ پیوستن” ، مجموعه‌ای از سه عملگر است – امکان ادغام سلول‌ها توسط یک صورت، لبه یا راس مشترک وجود دارد ( شکل 16 ). در این حالت دو سلول در یک سلول ادغام می شوند. “ادغام” لبه های اولیه سلول داخلی را تغییر می دهد. سلول هایی که باید متصل شوند باید ابتدا به هم متصل شوند—ادغام دو سلول که در کمپلکس های مجزا هستند دو مرحله دارد: اول، سلول ها به هم متصل می شوند، سپس می توان آنها را ادغام کرد. “ادغام” یک معکوس دارد – “Split”.

3. مقایسه با DHE

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

نویسندگان سعی کردند ساختارهای مشابهی را بیابند که به خوبی توصیف شده باشند و بتوانند در کاربردهای مشابه مورد استفاده قرار گیرند. سه ساختار انتخاب شدند: موجودیت جفت [ 21 ، 22 ]، لبه شعاعی [ 14 ]، و نهاد جزئی [ 10 ]. همچنین ساختارهای داده جدیدی برای مدلسازی غیر چندگانه اخیراً توسعه یافته است [ 23 ، 24 ، 25 ، 26 ] اما آنها بر اساس ساختارهای داده قدیمی تر [ 4 ، 10 ، 14 ، 21 ، 27 ، 28 ] هستند.] یا مقایسه مستقیم دشوار است: آن‌ها بسیاری از موجودیت‌های ساختاری را معرفی می‌کنند که به صراحت ذخیره شده‌اند، مانند مناطق، پوسته‌ها، چهره‌ها، لبه‌ها، راس‌ها، حلقه‌ها، دیسک‌ها و غیره – در حالی که در مدل‌های DHE فقط لبه‌ها و رئوس وجود دارد، شبیه به پر معرفی شده در ساختار داده کوپلینگ موجودیت.

یک مدل فضایی جدید به تازگی در زمینه GIS توسعه یافته است [ 29 ، 30 ] بر اساس جبر هندسی منسجم بر محاسبه روابط توپولوژیکی تمرکز دارد. یک ساختار داده پیشنهاد شده برای نشان دادن مدل، موجودیت های اضافی را معرفی می کند، به عنوان مثال، جفت نقطه، دایره، چهار وجهی، کره، و غیره ، که مقایسه با DHE را حتی دشوارتر می کند.

3.1. Coupling-Entity-The Feather

احتمالاً نزدیکترین ساختار داده CAD به رویکرد پیشنهادی، ساختار یاماگوچی و همکاران است. [ 22 ] و یاماگوچی و کیمورا [ 21 ]. مقایسه دقیق با DHE توسط Boguslawski و Gold [ 2 ] ارائه شد.

مدلی که از پر به عنوان عنصر اصلی استفاده می کند را می توان با ساختار داده DHE شبیه سازی کرد. همچنین می توان نشان داد که یک نسخه ساده شده از DHE وجود دارد، و این معادل پر است [ 2 ]]. بنابراین، پر زیر مجموعه ای از DHE است. در واقع، DHE ساده شده محدودیت‌های مشابهی با پر دارد: اتصال دو سلول در یک راس مشترک، مدلی را تولید می‌کند که معتبر نیست. با این حال، تمام یال هایی که راس یکسانی دارند می توانند در یک چرخه به هم متصل شوند، اما ناوبری معتبر نیست – ناتوانی در پیمایش در اطراف یک صورت رخ می دهد. این خطا با تعریف چرخه حلقه با استفاده از چرخه دیسک ایجاد می شود. با این حال، در یک مجتمع سلولی در حال تجزیه فضای سه بعدی، که در آن تمام سلول ها توسط چهره های مشترک به هم متصل می شوند، می توان از روش های دیگری برای پیمایش بین لبه های دارای راس یکسان استفاده کرد. یک سلول منفرد در یک مجتمع یک 2 منیفولد است و فقط یک چرخه دیسک برای حرکت در اطراف یک راس مشترک لازم است. چرخه‌های دیسک در سلول‌های دیگر به هم متصل نیستند، اما پیمایش از طریق چهره‌های مشترک امکان‌پذیر است و دسترسی به این چرخه‌ها امکان‌پذیر است.

یکی دیگر از تفاوت ها و یک مزیت بزرگ در GIS نسبت به موجودیت جفت این است که DHE (نسخه کامل) قادر است یک سلول/حجم را با یک راس دوگانه و یک موجودیت چهره را با یک بسته (لبه) نشان دهد. بنابراین، برای مثال، ویژگی‌ها ممکن است به هر گره، لبه، چهره یا موجودیت حجمی در فضای اولیه یا دوگانه اختصاص داده شوند.

3.2. ساختار لبه شعاعی و نهاد جزئی

ساختار جزئی موجود توسط لی و لی [ 10 ] یک ساختار داده فشرده است که از لبه شعاعی [ 14 ] مشتق شده است. ذخیره سازی داده ها به طور قابل توجهی کاهش می یابد (حدود 50٪) بدون از دست دادن کارایی زمانی.

در مقایسه ارائه شده در زیر، مورد یک مجموعه سلولی متشکل از 1000 مکعب (10 × 10 × 10) مانند [ 10 ] استفاده شده است.

کل اندازه گرفته شده توسط مدل ساخته شده با استفاده از لبه شعاعی 1,457,303 بایت و برای نهاد جزئی 644,192 بایت است [ 10 ]. اینها در جدول 3 آمده است . از همان محدودیت ها در محاسبه استفاده می شود: اندازه نشانگرهای ذخیره کننده فیلد چهار بایت است. فیلدها برای ویژگی ها یا داده های هندسی در نظر گرفته نمی شوند (فقط ذخیره سازی برای توپولوژی محاسبه می شود).

تجزیه و تحلیل برای سه مورد انجام می شود: نسخه کامل DHE، و دو نسخه DHE ساده شده: الف) بدون حلقه های چهره – نشانگر N _F حذف می شود. ب) بدون ساختار دوگانه – اشاره گر D برای اتصال سلول های مجاور استفاده می شود.

یک مجموعه سلولی در مدل وجود دارد: 1000 مکعب در مجموعه وجود دارد. هر مکعب از 12 لبه تشکیل شده است. در DHE، هر یال با دو نیمه یال دوتایی نشان داده می شود. هر DHE شامل پنج نشانگر در هر فضا است – اولیه و دوگانه (که ده نشانگر برای هر DHE می دهد). همچنین یک سلول خارجی در مدل وجود دارد – یک مکعب بزرگ که تمام مکعب های داخلی را در بر می گیرد. هر وجه مکعب خارجی به شبکه‌های 10 × 10 مربعی منطبق با وجه‌های بیرونی مجتمع داخلی تقسیم می‌شود که 1200 لبه در سلول خارجی ایجاد می‌کند. پرچم ها یا لیست ها در DHE استفاده نمی شوند.

برای DHE، فضای ذخیره سازی مجتمع داخلی برابر است: 1000 مکعب × 12 لبه × 2 DHE × 10 نشانگر × 4 بایت = 960000 بایت. و برای سلول خارجی: 1200 لبه × 2 DHE × 10 نشانگر × 4 بایت = 96000; در مجموع 1,056,000 بایت. این امتیاز ساختار کامل DHE را بین ساختارهای لبه شعاعی و ساختار جزئی در جدول 3 قرار می دهد .

3.3. DHE ساده شده

لازم به ذکر است که در نسخه کامل، وضعیتی که دو سلول توسط یک راس به هم متصل می شوند و حجم ها (دو گره) به طور صریح ذخیره می شوند، قابل مدیریت است. با این حال، اگر تمام سلول‌ها در مدل تحلیل‌شده توسط چهره‌ها به هم متصل شوند، نسخه ساده‌شده بدون اشاره‌گر حلقه چهره N _F ممکن است مناسب‌تر باشد (نسخه ساده‌شده a). تعداد اشاره گرها در DHE از ده به هشت کاهش یافته است. بنابراین فضای ذخیره سازی مورد نیاز برای مدل به صورت زیر محاسبه می شود: 1000 مکعب × 12 لبه × 2 DHE × 8 نشانگر × 4 بایت = 768000 بایت. و برای سلول خارجی: 1200 لبه × 2 DHE × 8 نشانگر × 4 بایت = 76800; در مجموع 844800 بایت. این باعث صرفه جویی 20٪ در فضا می شود.

اگر نیازی به استفاده از موجودیت های حجمی نباشد، ساده سازی بیشتر حتی فضای کمتری را مصرف می کند. ساختار دوگانه حذف شده است (نسخه ساده شده b) و تمام اتصالات بین سلول ها در مدل در اولیه ذخیره می شود. بنابراین تنها چهار اشاره گر برای ذخیره اطلاعات توپولوژی کافی است. فضای ذخیره سازی مورد نیاز برای این مورد عبارت است از: 1000 مکعب × 12 لبه × 2 DHE × 4 اشاره گر × 4 بایت = 384000 بایت. و برای سلول خارجی: 1200 لبه × 2 DHE × 4 اشاره گر × 4 بایت = 38,400 — در مجموع 422,400 بایت. ساختار داده DHE به حدود 30 درصد از اندازه ذخیره سازی لبه شعاعی و 65 درصد از موجودیت جزئی برای نمایش مجتمع سلولی نیاز دارد.

جدول 3 لبه شعاعی، جزئی و سه نسخه DHE را مقایسه می کند. نسخه کامل همراه با نمودار دوگانه برای زمانی مفید است که اطلاعات باید برای حجم ها ذخیره شود و نمایش صریح اتصالات بین سلول ها مهم است: پیمایش پیچیده سلولی با استفاده از نمودار دوگانه آسان تر است و اجرای برخی از الگوریتم ها، به عنوان مثال، Dijkstra الگوریتم [ 31 ]، ساده است. برای صرفه‌جویی در فضای ذخیره‌سازی، می‌توان از نسخه ساده‌شده برای ساخت مدل اولیه استفاده کرد و سپس زمانی که نیاز به تحلیل پیشرفته‌تری از مدل باشد، می‌توان آن را به نسخه کامل گسترش داد.

4. ساخت مدل ساختمان

ساختار حاصل با موفقیت برای بازسازی دو ساختمان به هم پیوسته در پردیس دانشگاه گلامورگان (در حال حاضر دانشگاه ولز جنوبی) مورد استفاده قرار گرفته است. مطابق با اهداف طراحی آن، لبه به لبه از پلان های اصلی ساخته شد – با اضافه شدن تمام لبه های مربوطه، چهره ها و حجم ها به طور خودکار تکمیل شدند. اپراتورهای اویلر و توسعه یافته اویلر مورد استفاده قرار گرفتند که ساختار دوگانه را به صورت موازی به روز کردند. در نتیجه، تمام ناوبری در هر مرحله ساخت و ساز قابل اجرا بود، که جستجوی بخش های مربوطه را برای پیوست کردن ساده می کند. در نهایت، ناوبری از اتاقی به اتاق دیگر در فضای دوگانه به آسانی توسط ناوبری مبتنی بر اشاره گر انجام می شود، که امکان اجرای کارآمد الگوریتم های استاندارد پیمایش نمودار، مانند Dijkstra’s را فراهم می کند. تنها موجودیت های حفظ شده گره ها/حجم های اولیه و دوگانه هستند. و لبه ها/صورت های اولیه و دوگانه. هر ویژگی دلخواه ممکن است به آنها متصل شود، که امکان جستجوهای هوشمندانه در کل مجموعه ساختمان را فراهم می کند.

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

مدل بازسازی شده – دو ساختمان از پردیس دانشگاه گلامورگان (نگاه کنید به شکل 17 الف) که توسط یک گذرگاه روی زمین به هم متصل شده اند ( شکل 17 ب) – فرض می کند که دیوارها ضخامت صفر دارند و ممکن است توسط درهایی با ضخامت صفر به هم متصل شوند (که هنوز یک گره دوگانه دارند) ( شکل 18 را ببینید ).

در مجموع بیش از 1300 سلول وجود دارد. سلول ها ممکن است اتاق، در یا راهرو باشند. مدل و استفاده از آن برای برنامه ریزی مسیر فرار از نقشه های کاغذی اسکن شده بازسازی شد. این پلان ها به عنوان پس زمینه شطرنجی در اتوکد مورد استفاده قرار گرفتند – طبقات بعدی در لایه هایی در ارتفاعات مختلف قرار گرفتند (فاصله بین لایه ها در ارتفاع اتاق دلخواه تنظیم شد) ( شکل 19 را ببینید ). این کار مجموعه ای از سلول های منفرد را تولید کرد، یکی برای هر اتاق اما به هم متصل نبودند ( شکل 20 را ببینید ). این مدل به Autodesk 3DS Max وارد شد، جایی که برچسب‌ها ( به عنوان مثال، شماره اتاق و نام) به هر سلول متصل شد. مدل نهایی (هنوز به عنوان مجموعه ای از چند وجهی جداگانه نشان داده می شود) به فرمت تبادل OBJ که یک فرمت فایل تعریف هندسه است صادر شد. تمام اتصالات بین اتاق های مجاور در طول فرآیند ساخت و ساز با استفاده از اپراتورهای DHE و Euler تنظیم شدند، با هر دو نمودار اولیه و دوگانه به طور همزمان به روز می شوند. وزن ها به اتصالات بین اتاق ها اختصاص داده شد. آنها توضیح دادند که انتقال به اتاق بعدی چقدر دشوار است: یک مقدار بی نهایت به معنای عدم دسترسی است، هر مقدار (مثبت) دیگری از فاصله هندسی بین گره های دوگانه که سلول های مجاور را نشان می دهند محاسبه می شود. وزن ها فقط در صورت وجود در تعیین می شد. مسیرهای فرار به سمت بیرون با افزودن سلول‌های نازک (شاید سنگفرش بتنی) به مدل مدل‌سازی شدند که امکان ناوبری در خارج از ساختمان را فراهم می‌کرد.

الگوریتم Dijkstra مستقیماً روی نمودار دوگانه برای یافتن کوتاه‌ترین مسیر بین دو اتاق مشخص استفاده شد ( شکل 21 a,b) – هیچ ساختار اضافی مورد نیاز نیست: یک شبکه قابل کشتیرانی در ساختمان توسط نمودار دوگانه با وزن‌های تعیین‌شده نشان داده می‌شود. از همین الگوریتم برای یافتن مسیری از یک اتاق به نزدیکترین خروجی از یک ساختمان استفاده شد ( شکل 21 ج) – یک اتاق منبع و چندین خروجی وجود دارد. خروجی می تواند هر سلولی در یک مجتمع باشد، اما معمولاً این سلولی است که نمایانگر دری است که ساختمان را با نمای بیرونی متصل می کند.

5. نتیجه گیری ها

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

DHE و اپراتورهای ساخت و ساز برای ساختن یک مدل 3 بعدی b-rep، که به عنوان مجموعه ای از سلول های نامنظم نشان داده شده بود، با استفاده از دو موجودیت ساختاری، نیمه لبه ها و گره ها، کافی بودند، در حالی که نمایش حجم ها، چهره ها، لبه ها و رئوس با اجرای کامل ارائه شد. دوگانگی سه بعدی پوانکاره ساخت مدل، بر اساس عملگرهای اویلر، شامل به‌روزرسانی‌های خودکار دوگانه است که ساختار منطقی مدل را نشان می‌دهد. تنها عنصر مورد استفاده برای اتصالات توپولوژیکی یک نیم لبه بود، در حالی که یک گره فقط برای ذخیره مختصات یک راس استفاده می شد. ویژگی ها را می توان به نیمه لبه ها یا گره ها متصل کرد. این ویژگی‌ها الزامات مدل‌های GIS را برآورده می‌کنند که در آن ادغام هندسه، توپولوژی و معناشناسی بسیار مهم است.

لازم به ذکر است که اپراتورهای اویلر و توسعه یافته اویلر تضمین نمی کنند که پارامترهای ورودی ارائه شده منجر به پوسته صحیح شود. به عنوان مثال، اگر دو نیمه لبه از حلقه های چهره مختلف به عنوان ورودی برای MEF داده شود، نتیجه با تقسیم صورت به دو قسمت متفاوت خواهد بود که نتیجه پیش بینی شده است. برخی از عملگرها، به عنوان مثال، JoinByEdge ، ممکن است دو منیفولدهای غیر قابل جهت گیری، مانند نوار Möbius را تولید کنند، که ممکن است نتیجه مورد انتظار در ساخت پیچیده سلولی نباشد. ممکن است سطح بالاتری از عملگرها به منظور بررسی صحت پارامترهای ورودی و فراخوانی اپراتور مناسب ایجاد شود. علاوه بر این، اپراتورهای تخصصی جدید ممکن است برای کاربردهای خاص مانند مدل سازی معماری مورد نیاز باشند.

نشان داده شد که راندمان ذخیره سازی DHE با سایر ساختارهای CAD غیر منیفولد قابل مقایسه است و چندین نسخه ساده شده پیشنهاد شده است که در آن ناوبری کامل همه انواع مجاورت توپولوژیکی ممکن (به عنوان مثال، فقط راس به راس) مورد نیاز نیست. در این تحقیق، تمرکز بر نیازهای ذخیره سازی قرار گرفت، زیرا ساختارهای داده توپولوژیکی معمولاً حافظه گیر هستند. در مقابل، پرس و جوهای توپولوژیکی به دلیل وجود اتصالات توپولوژیکی در ساختار داده، سریعتر هستند. تجزیه و تحلیل عملکرد مقایسه ای در کار آینده در نظر گرفته خواهد شد.

ساختار داده DHE ارائه شده برای مدل های سه بعدی کامل مناسب است. با این حال، پتانسیل آن بسیار بزرگتر است و در حال حاضر تحقیقات جدیدی را آغاز کرده است. نشان داده شد که ادغام 2 بعدی/3 بعدی بین فضای داخلی ساختمان سه بعدی و زمین خارجی 2 بعدی قابل اجرا است [ 32 ]. مفهوم جدیدی از DHE اصلاح شده، نیمه قوس دوگانه، توسط آنتون و همکاران معرفی شد. [ 33 ].

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

در دنیای GIS، علاقه قابل توجهی به تعمیم خودکار مدل‌های ساختمانی برای نمایش در مقیاس‌های مختلف وجود دارد. این در اینجا تلاش نشده است، اما برای کارهای آینده در نظر گرفته شده است. در نهایت، هیچ ابزار اعتبارسنجی، برای بررسی معقول بودن هندسه، تلاش نشده است – دوباره بحث برای کارهای آینده در جریان است. با این حال، تلاشی برای اعتبارسنجی مدل‌های اطلاعات ساختمان با استفاده از DHE توسط Kraft و Huhnt [ 35 ] انجام شد.

منابع

بوگوسلاوسکی، پ. اپراتورهای طلا، سی اویلر و ناوبری مدل های ساختمان چند پوسته. در تحولات در علوم ژئو اطلاعات سه بعدی ; Neutens, T., Maeyer, P., Eds. Springer: برلین، آلمان، 2010; صص 1-16. [ Google Scholar ]
بوگوسلاوسکی، پ. Gold, C. مدلسازی سریع فضای داخلی ساختمانهای پیچیده. در پیشرفت در علوم ژئو اطلاعات سه بعدی ؛ Kolbe, TH, König, G., Nagel, C., Eds.; Springer: برلین، آلمان، 2011; صص 43-56. [ Google Scholar ]
بوگوسلاوسکی، پ. طلا، CM؛ Ledoux, H. مدل‌سازی و تحلیل ساختمان‌های سه بعدی با ساختار داده اولیه/دوگانه. ISPRS J. Photogram. Remote Sens. 2011 ، 66 ، 188-197. [ Google Scholar ] [ CrossRef ]
باومگارت، BG یک نمایش چند وجهی برای بینایی کامپیوتر. در مجموعه مقالات کنفرانس ملی کامپیوتر (AFIPS ’75)، آناهیم، کالیفرنیا، ایالات متحده آمریکا، 19-22 مه 1975.
Mäntylä, M. Introduction to Solid Modeling ; انتشارات علوم کامپیوتر: نیویورک، نیویورک، ایالات متحده آمریکا، 1987; پ. 401. [ Google Scholar ]
گیباس، ال. Stolfi، J. Primitives برای دستکاری زیربخش های کلی و محاسبه نمودارهای voronoi. ACM Trans. نمودار 1985 ، 4 ، 74-123. [ Google Scholar ] [ CrossRef ]
کلبه، تی. گروگر، جی. Plümer, L. CityGML—مدل های سه بعدی شهر و پتانسیل آنها برای واکنش اضطراری. در فناوری اطلاعات جغرافیایی برای واکنش اضطراری ؛ زلاتانوا، اس.، لی، ج.، ویرایش. CRC Press: Boca Raton، FL، USA، 2008; صص 257-274. [ Google Scholar ]
برگ، ام. چئونگ، او. کرولد، ام. Overmars, M. Computational Geometry: Algorithms and applications , 3rd ed.; Springer: برلین، آلمان، 2008. [ Google Scholar ]
دوبکین، DP. Laszlo، MJ Primitives برای دستکاری زیربخش های سه بعدی. در مجموعه مقالات سومین سمپوزیوم سالانه هندسه محاسباتی، واترلو، ON، کانادا، 8 تا 10 ژوئن 1987.
لی، SH; لی، ک. ساختار موجودیت جزئی: یک نمایش مرزی فشرده غیر چندگانه بر اساس موجودیت های توپولوژیکی جزئی. در مجموعه مقالات ششمین سمپوزیوم ACM در مورد مدلسازی جامد و کاربردها، ان آربور، MI، ایالات متحده آمریکا، 4-8 ژوئن 2001. صص 159-170.
ماسودا، اچ. عملگرهای توپولوژیکی و عملیات بولی برای مدل‌های هندسی غیرمنیفولد مبتنی بر پیچیده. محاسبه کنید. به دس کمک کرد. 1993 ، 25 ، 119-129. [ Google Scholar ] [ CrossRef ]
لدوکس، اچ. طلا، CM ذخیره سازی همزمان زیربخش های سه بعدی اولیه و دوگانه. محاسبه کنید. محیط زیست سیستم شهری 2007 ، 31 ، 393-408. [ Google Scholar ] [ CrossRef ]
Ledoux, H. مدل‌سازی میدان‌های سه‌بعدی در علوم زمین با نمودار ورونوی و دوگانه آن. دکتری پایان نامه، دانشگاه گلامورگان، پونتیپرید، انگلستان، 2006. [ Google Scholar ]
Weiler، K. ساختار داده لبه شعاعی: یک نمایش توپولوژیکی برای مدل‌سازی مرز هندسی غیر منیفولد. در مدل سازی هندسی برای برنامه های Cad ; Encarnacao، JL، Wozny، MJ، McLaughlin، HW، Eds. الزویر: آمستردام، هلند، 1988; صص 3-36. [ Google Scholar ]
Boguslawski، P. مدل‌سازی و تحلیل فضای داخلی ساختمان‌های سه بعدی با ساختار داده‌های نیمه لبه دوگانه. دکتری پایان نامه، دانشگاه گلامورگان، ولز، انگلستان، 2011. [ Google Scholar ]
گرونباوم، بی. Shephard, GC کاشی و الگوهای ; WH Freeman & Company: نیویورک، نیویورک، ایالات متحده آمریکا، 1986; پ. 700. [ Google Scholar ]
ماسودا، ح. شیمادا، ک. نومائو، ام. Kawabe, S. یک نظریه ریاضی و کاربردهای مدل‌سازی هندسی غیر چندگانه. در مجموعه مقالات سمپوزیوم بین المللی مدلسازی هندسی پیشرفته برای کاربردهای مهندسی، برلین، آلمان، 8-10 نوامبر 1989. صص 89-103.
Stroud، I. تکنیک های مدل سازی نمایندگی مرزی . Springer: نیویورک، نیویورک، ایالات متحده آمریکا، 2006. [ Google Scholar ]
آکلمان، ای. چن، جی. مش‌های ناخالص، JL Block: مدل‌سازی شکل از نظر توپولوژیکی قوی با نمودارهای تعبیه‌شده روی 3 منیفولد. محاسبه کنید. نمودار 2015 ، 46 ، 306-326. [ Google Scholar ] [ CrossRef ]
لی، ک. اصول سیستم های CAD/CAM/CAE . Prentice Hall: Upper Saddle River، NJ، USA، 1999; پ. 582. [ Google Scholar ]
یاماگوچی، ی. کیمورا، F. توپولوژی غیر چندگانه بر اساس موجودیت های جفت. محاسبات IEEE. نمودار Appl. 1995 ، 15 ، 42-50. [ Google Scholar ] [ CrossRef ]
یاماگوچی، ی. کوبایاشی، ک. Kimura, F. مدل‌سازی هندسی با توپولوژی و هندسه تعمیم‌یافته برای مهندسی محصول. در مدل سازی محصول برای طراحی و ساخت به کمک رایانه ؛ Turner, J., Pegna, J., Wozny, M., Eds. الزویر: آمستردام، هلند، 1991; صص 97-115. [ Google Scholar ]
زنگ، ال. لیو، ی.-جی. لی، SH; یوئن، MM-F. Q-complex: نمایش مرز غیر چندگانه کارآمد با توپولوژی گنجاندن. محاسبه کنید. به دس کمک کرد. 2012 ، 44 ، 1115-1126. [ Google Scholar ] [ CrossRef ]
کازیر، دی. Kraemer, P. X-maps: یک مدل کارآمد برای مدلسازی غیر منیفولد. در مجموعه مقالات کنفرانس بین المللی مدل سازی شکل (SMI)، واشنگتن، دی سی، ایالات متحده آمریکا، 21-23 ژوئن 2010; ص 226-230.
دی فلوریانی، ال. ماگیلو، پ. پوپو، ای. Sobrero، D. یک نمایش توپولوژیکی با وضوح چندگانه برای مش های غیر منیفولد. محاسبه کنید. به دس کمک کرد. 2004 ، 36 ، 141-159. [ Google Scholar ] [ CrossRef ]
دی کارلو، آ. پائولوزی، ا. Shapiro، V. نمایش جبری خطی برای ساختارهای توپولوژیکی. محاسبه کنید. به دس کمک کرد. 2014 ، 46 ، 269-274. [ Google Scholar ] [ CrossRef ]
گورسوز، EL; چوی، ی. پرینز، نمایش مرزی مبتنی بر راس FB از مرزهای غیر چندگانه. در مدلسازی هندسی برای مهندسی محصول ; Wozny, MJ, Turner, JU, Priess, K., Eds. هلند شمالی: آمستردام، هلند، 1990; صص 107-130. [ Google Scholar ]
Lienhardt، P. مدل‌های توپولوژیکی برای نمایش مرز: مقایسه با نقشه‌های تعمیم‌یافته n بعدی. محاسبه کنید. به دس کمک کرد. 1991 ، 23 ، 59-82. [ Google Scholar ] [ CrossRef ]
یو، ز. لو، دبلیو. یوان، ال. هو، ی. زو، تبر; Lü, G. مدل جبر هندسی برای محاسبه رابطه توپولوژیکی هندسه گرا. ترانس. GIS 2015 . [ Google Scholar ] [ CrossRef ]
یوان، ال. یو، ز. لو، دبلیو. ژو، ال. Lü, G. یک مدل داده های مکانی سه بعدی GIS بر اساس جبر هندسی منسجم. علمی علوم زمین چین 2011 ، 54 ، 101-112. [ Google Scholar ] [ CrossRef ]
Dijkstra، EW یادداشتی در مورد دو مشکل در ارتباط با نمودارها. عدد. ریاضی. 1959 ، 1 ، 269-271. [ Google Scholar ] [ CrossRef ]
بوگوسلاوسکی، پ. طلا، C. ساختمان ها و زمین یکپارچه – ساختار داده دوگانه چند بعدی برای GIS. ژئو اسپات. Inf. علمی 2015 ، 18 ، 151-158. [ Google Scholar ] [ CrossRef ]
آنتون، اف. بوگوسلاوسکی، پ. Mioc, D. ساختار داده نیمه قوس دوگانه: به سمت ساختار داده جهانی b-rep. در Geoinformation برای تصمیمات آگاهانه ; عبدالرحمن، ع.، بوگوسلاوسکی، پی.، آنتون، ف.، سعید، م.ن.، عمر، ک.م.، ویرایش. Springer: برلین، آلمان، 2014; صص 103-117. [ Google Scholar ]
بوگوسلاوسکی، پ. مهجوبی، ل. زوروویچ، وی. بارکی، ح. Fadli, F. ساخت خودکار شبکه های قابل پیمایش با چگالی متغیر در یک محیط داخلی سه بعدی برای پاسخ اضطراری. خودکار ساخت و ساز 2016 . تحت بررسی [ Google Scholar ]
کرافت، بی. هانت، دبلیو. مدل های ساختمانی از نظر هندسی کامل. در مجموعه مقالات بیست و یکمین کارگاه بین المللی: محاسبات هوشمند در مهندسی، کاردیف، انگلستان، 16 تا 18 ژوئیه 2014.

شکل 1. دو منیفولد و غیر منیفولد: سطح ( a ) یک کره; ( ب ) یک مکعب؛ ( ج ) چنبره دو منیفولد است. دو مکعب که توسط ( d ) یک راس به هم وصل شده اند. ( ه ) یک لبه؛ ( f ) یک صورت یک شی غیر چندگانه را تشکیل می دهد.

شکل 2. دوگانه پوانکاره سه بعدی: ( الف ) راس اولیه مربوط به یک سلول دوگانه (حجم) است. ( ب ) لبه اولیه مربوط به یک وجه دوتایی است. ( ج ) وجه اولیه مربوط به یک لبه دوگانه است. ( د ) سلول اولیه مربوط به یک راس دوگانه است.

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

شکل 4. سوراخ‌ها و حفره‌ها: ( الف ) سوراخ در لبه‌ی پل وجهی e _b حلقه‌ی داخلی f _INT را به حلقه بیرونی f _OUT متصل می‌کند . ( ب ) حفره در وجهی پل سلولی f _b سلول داخلی c _INT را به سلول بیرونی c _OUT متصل می کند .

شکل 5. ویژگی ها را می توان به گره ها و لبه های اولیه و همچنین به عناصر دوگانه نسبت داد.

شکل 6. یک نماد نیمه لبه: ( الف ) یک نمایش پرچم. ( ب ) جهتی که با یک فلش تاکید شده است.

شکل 7. نیم لبه ها در یک سلول از نظر توپولوژیکی به هم متصل شده اند و تشکیل می دهند: ( الف ) یک لبه. ( ب ) یک ستاره؛ ( ج ) یک حلقه.

شکل 8. عملگرهای ناوبری: ( a ) Sym ; ( ب ) _V بعدی ; ( ج ) بعدی _F ; ( د ) _E بعدی (عملگر مرکب).

شکل 9. عملگر مجاور : ( الف ) صورت خاکستری توسط سلول های مجاور c ₁ و c ₂ مشترک است . ( ب ) عملگر مجاور امکان پیمایش بین سلول ها را فراهم می کند: از e در c ₁ تا e. مجاور در c ₂ .

شکل 10. اپراتورهای ساخت و ساز سازماندهی شده در لایه ها: سطح 3 – اپراتورهای اویلر و توسعه یافته اویلر. سطح 2 – عملگرهای مرکب. سطح 1 – عملگرهای ساده سطح 0 – اپراتورهای نیمه لبه دوگانه.

شکل 11. اپراتور اویلر MEVVFS/KEVVFS.

شکل 12. عملگرهای اویلر: MEV/KEV، MVE/KVE، MZEV/KZEV، MEF/KEF (a, b—نیمه لبه های جدید).

شکل 13. عملگرها را برای ساخت مجتمع سلولی بپیوندید/جدا کنید.

شکل 14. تقسیم یک جعبه به مجموعه ای از دو سلول.

شکل 15. تقسیم یک جعبه به مجموعه ای از دو سلول با استفاده از عملگر Split by Face .

شکل 16. عملگرهای Merge/Split برای ساخت مجتمع سلولی.

شکل 17. دو ساختمان از پردیس دانشگاه گلامورگان توسط یک گذرگاه بالای زمینی که با استفاده از ساختار داده DHE مدل‌سازی شده است به هم متصل شده‌اند: ( الف ) سلول‌های خاکستری روشن زمین، سلول‌های خاکستری نشان‌دهنده اتاق‌ها، سلول‌های خاکستری تیره نشان‌دهنده گذر از سطح زمین هستند. بین ساختمان ها؛ ( ب ) یک گذرگاه روی زمین بین دو ساختمان – سلول های تاریک.

شکل 18. دو اتاق مجاور V ₁ و V ₂ با درب “مسطح” V _D در بین آنها.

شکل 19. پلان های ساختمان به صورت لایه پس زمینه شطرنجی برای همه طبقات سازماندهی شده است.

شکل 20. مدل کامل به عنوان مجموعه ای از سلول های غیر متصل نشان داده شده است.

شکل 21. کوتاه ترین مسیرها (خاکستری تیره، زمین خارجی که با سلول های خاکستری روشن نشان داده می شود) بین دو اتاق (سیاه): ( الف ) مسیر کاملاً در داخل ساختمان. ( ب ) مسیر محاسبه شده با توجه به یک زمین خارجی. ( ج ) کوتاهترین مسیر بین اتاق و نزدیکترین خروجی.

جدول 1. مجموعه ای از عملگرهای اویلر و عملگرهای اویلر توسعه یافته.

جدول 2. جدول اتصالات ایجاد شده توسط لبه، راس، راس، صورت و پوسته ( MEVVFS) ایجاد/کشتن .

جدول 3. الزامات ذخیره سازی برای مجموعه سلولی 1000 مکعبی (10 × 10 × 10).

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

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

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

09120049370

8 صبح تا 12 شب