یک روش تشخیص تقعر-تحدب راس برای اجسام فضایی سه بعدی بر اساس جبر هندسی

خلاصه

تشخیص تقعر-تحدب راس برای اجسام فضایی یک الگوریتم اساسی گرافیک کامپیوتری و همچنین پایه ای برای اجرای سایر الگوریتم های گرافیکی است. در سال‌های اخیر، با توسعه مدل‌سازی سه‌بعدی، هوش مصنوعی و سایر فناوری‌های گرافیکی، اهمیت الگوریتم تشخیص تقعر-تحدب راس برای اجسام فضایی سه‌بعدی (3D) به طور فزاینده‌ای برجسته شده است. با این وجود، الگوریتم‌های تشخیص تقعر-تحدب راس موجود در حال حاضر عمدتاً از چند ضلعی‌های دوبعدی (2 بعدی) استفاده می‌کنند، با تحقیقات محدود در مورد الگوریتم‌های تشخیص تقعر-تحدب راس برای چند وجهی‌های سه‌بعدی. این مطالعه به بررسی همبستگی بین محصول بیرونی و توپولوژی جسم فضایی بر اساس ویژگی منحصر به فرد می‌پردازد که عملکرد محصول بیرونی در جبر هندسی دارای مفاهیم هندسی یکپارچه و قطعی در فضا و با ابعاد متفاوت است. علاوه بر این، یک چارچوب الگوریتم تشخیص تقعر-تحدب راس یکپارچه چند بعدی برای اجسام فضایی پیشنهاد شده است و این چارچوب قادر به تشخیص تقعر-تحدب راس برای چند ضلعی های ساده دو بعدی و چند وجهی های ساده سه بعدی است.

کلید واژه ها:

تشخیص تقعر – تحدب ; جبر هندسی ; محصول بیرونی ؛ چند بعدی یکپارچه

1. معرفی

الگوریتم‌های تشخیص تقعر-تحدب رئوس اجسام فضایی اساس بسیاری از الگوریتم‌های گرافیکی هستند، از جمله الگوریتم‌های آزمایشی [ 1 ، 2 ، 3 ، 4 ، 5 ]، الگوریتم تعیین جهت و تحدب- تقعر برای چند ضلعی‌های ساده [ 1 ، 2، 3، 4 ، 5 ] . و پردازش گرافیک کامپیوتری [ 8 ، 9 ]. الگوریتم‌های رایج تشخیص تقعر-تحدب راس برای چند ضلعی‌ها شامل بدنه محدب [ 10 ]، زاویه [ 11 ]، نقطه چپ-راست [ 12 ]، ناحیه برداری [ 13 ]، محصول متقاطع [ 14 ] است.]، شیب [ 15 ]، و روش های دنباله رئوس انتهایی [ 16]. در این میان، روش‌های زاویه، نقطه چپ-راست و ناحیه برداری از ویژگی‌های ذاتی چند ضلعی‌های ساده برای طراحی الگوریتم استفاده می‌کنند، در حالی که روش‌های متقاطع، پرتو، شیب و رئوس انتهایی پیچیدگی الگوریتمی را در طول شناسایی به شدت کاهش می‌دهند. تقعر-تحدب نقاط ثابت چندضلعی های ساده. با این وجود، مطالعات موجود در حال حاضر در مورد تشخیص تقعر-تحدب راس عمدتاً بر روی چند ضلعی های دو بعدی (2 بعدی) متمرکز است و مطالعات در مورد تشخیص تقعر-تحدب راس چند وجهی های فضایی سه بعدی (3D) به ندرت گزارش شده است. با توسعه سریع زمینه هایی مانند مدل سازی سه بعدی و هوش مصنوعی، نیاز به یک الگوریتم تشخیص تقعر-تحدب برای رئوس در شرایط چند بعدی به طور فزاینده ای مهم و ضروری می شود.

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

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

2. ایده اولیه

به عنوان اولین کسی که جبر هندسی را پیشنهاد کرد، ویلیام کی. کلیفورد جبر گراسمن را با جبر کواترنیونی همیلتون ترکیب کرد تا جبر هندسی کلیفورد را به دست آورد که از آن به عنوان جبر کلیفورد نیز یاد می شود [ 17 ]. جبر هندسی در مقایسه با جبر خطی مرسوم، قابلیت های نمایش و محاسبات بالاتری را ارائه می دهد. جبر هندسی می تواند مستقیماً عملیات جبری را انجام دهد که مبتنی بر نمایش اجسام فضایی است، به عنوان مثال، با یک مسئله هندسی به روش جبری می پردازد [ 18 ].]. این منجر به شهودی و سادگی بیشتر می شود. به طور همزمان، استقلال مختصات و استقلال ابعاد جبر هندسی یک مبنای ریاضی برای بیان یکپارچه و تجزیه و تحلیل فضایی و عملکرد اجسام پیچیده در فضای سه بعدی فراهم می‌کند [ 19 ، 20 ]. هستنس و لی و همکاران. جبر هندسی منسجم (CGA) را که مبتنی بر جبر هندسی کلیفورد است، توسعه دهید، که دامنه کاربرد جبر هندسی را بیشتر گسترش می‌دهد [ 21 ، 22 ]. CGA به طور گسترده در زمینه های مختلف مانند هندسه کامپیوتر [ 23 ، 24 ]، بینایی کامپیوتر [ 25 ، 26 ، 27 ] استفاده شده است.]، و تحلیل فضایی جغرافیایی چند بعدی [ 28 ، 29 ، 30 ، 31 ، 32 ، 33 ].

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

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

3. روش شناسی

3.1. تعاریف مربوط به تشخیص تقعر-تحدب راس

قبل از انجام تشخیص تقعر-تحدب راس برای یک شی فضایی، ابتدا باید محدوده شی فضایی مورد علاقه و مفاهیم مربوطه به وضوح تعریف شود. در اینجا، شی فضایی شامل چندضلعی ها و چندوجهی های ساده است که به ترتیب در تعاریف 1 و 2 توضیح داده شده اند.

تعریف 1.

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

تعریف 2.

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

بر اساس تعاریف ذکر شده از چند ضلعی های ساده و چند وجهی ساده، تعریف 3 زاویه داخلی آنها را تعریف می کند.

تعریف 3.

زاویه داخلی یک چند ضلعی ساده به زاویه تقاطع داخل چند ضلعی اشاره دارد که توسط دو لبه مجاور چند ضلعی ساده تشکیل شده است. زاویه داخلی یک چند وجهی ساده به عنوان زاویه تقاطع در داخل چند وجهی تعریف می شود که توسط دو سطح مجاور چند وجهی ساده تشکیل شده است.

از تعاریف 1 و 2 می توان نتیجه گرفت که زاویه داخلی یک چندضلعی یا چند وجهی ساده باید کمتر از π باشد. سپس می توان تحدب راس را با توجه به زوایای داخلی چند ضلعی های ساده و چند وجهی ساده شناسایی کرد که در تعاریف 4 و 5 به تفصیل بیان شده است.

تعریف 4.

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

تعریف 5.

اگر زاویه داخلی که توسط دو سطح مجاور یک چندوجهی ساده تشکیل شده است از π بیشتر باشد، آنگاه دو رأس لبه مشترک بین این دو سطح مجاور، نقاط مقعر هستند. در غیر این صورت، آنها نقاط محدب هستند.

3.2. عملیات بیرونی محصول

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

تعریف 6.

اگر $A_{〈 s 〉}$ و $B_{〈 t 〉}$ هر دو تیغه مستقل خطی در $C L_{p, q}$ فضا (نمادی برای سیستم دسته بندی جبر، که در آن $C l_{3, 0}$ فضای اقلیدسی را نشان می دهد، $C l_{3, 1}$ نشان دهنده فضای همگن و $C l_{4, 1}$ نشان دهنده فضای Conformal) [ 18 ]، که در آن $〈 s 〉$ و $〈 t 〉$ ابعاد متناظر آنها هستند و سپس محصول بیرونی بین آنها به صورت زیر تعریف می شود:

آ ⟨ ها ⟩^ب ⟨ t ⟩ = (| A | | B | گناه θ) من ⟨ s + t ⟩

(1)

جایی که $| A |$ و $| B |$ عملکرد مدول هستند، θ زاویه بین دو تیغه است، $(| A | | B | \sin θ)$ برای تعیین اندازه شیء حاصل از محصول بیرونی استفاده می شود، $i_{〈 s + t 〉}$ عملکرد فضای ابعاد محصول بیرونی است و $〈 s + t 〉$ بعد فضای بیرونی محصول است. چه زمانی $s + t > p + q$ ، نتیجه حاصلضرب بیرونی صفر است.

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

3.3. بیان CGA برای اجسام هندسی بر اساس محصول بیرونی

نقاط موجود در فضای سه بعدی اقلیدسی را می توان با تعریف زیر به CGA تبدیل کرد.

تعریف 7.

اگر $P (x, y, z)$ نقطه ای در فضای اقلیدسی است $C l_{3, 0}$ ، سپس بیان متناظر نقطه CP در CGA $C l_{4, 1}$ به شرح زیر است:

C P = P + پ 2 2 ه \infty + ه 0 = x ه 1 + y ه 2 + z ه 3 + ( ایکس 2 + y 2 + z 2 ) 2 ه \infty + ه 0

(2)

جایی که $e_{1}, e_{2}, e_{3}, e_{0}$ ، و $e_{\infty}$ پنج بردار پایه در CGA هستند، $e_{0}$ نشان دهنده مبدا مختصات مرجع با ضریب 1 و $e_{\infty}$ نقطه بی نهایت را نشان می دهد.

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

تعریف 8.

اگر $C P_{1}$ و $C P_{2}$ دو نقطه مرزی در $C L_{4, 1}$ فضا، CL یک خط مرزی است که توسط $C P_{1}$ و $C P_{2}$ و اگر خط مرزی در فضای CGA با نشان داده شود $G e o S e g m e n t_{〈 4 〉}$ ، جایی که 〈4〉 نشان می دهد که خط مرزی مربوط به زیرفضای سه بعدی در فضای منسجم است، بیان منسجم خط مرزی به صورت زیر تعریف می شود:

G e o S eg_m e n تی ⟨ 4 ⟩ : سی L = C پ 1 \land سی پ 2 \land ه \infty

(3)

همانطور که در تعریف 9 نشان داده شده است، اطلاعات هندسی سطوح مرزی را می توان با حاصلضرب بیرونی در بین سه نقطه منسجم و یک نقطه بینهایت در فضای CGA نشان داد.

تعریف 9.

اگر CF یک سطح مرزی در $C L_{4, 1}$ فضا، $C P_{1}$ ، $C P_{2}$ و $C P_{3}$ سه نقطه مرزی CF هستند. اگر $G e o P o l y g o n_{〈 4 〉}$ بیانگر بیان CGA سطح مرزی در فضای هم‌شکل است، 〈4〉 نشان‌دهنده زیرفضای چهار بعدی در فضای CGA مربوطه است و سپس بیان هم‌شکل سطح مرزی به صورت زیر تعریف می‌شود:

G e o P o l y g o n ⟨ 4 ⟩ : سی اف = سی پ 1 \land سی پ 2 \land سی پ 3 \land ه \infty

(4)

3.4. همبستگی بین نتایج محصول بیرونی و توپولوژی فضایی شی هندسی

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

قضیه 1.

فرض کنید q یک نقطه دلخواه در فضای منسجم باشد. پس از آن، P ₁ ، P ₂ ، …، P _n نقاط همسطحی هستند که در خلاف جهت عقربه های ساعت توالی شده اند، که چند ضلعی ساده A را تشکیل می دهند. نقطه q و چند ضلعی A همسطح هستند. در صورتی که تمام عملیات حاصل از بیرونی بین q و تمام یال های A غیرصفر باشند و علائم ضرایب یکسان باشد، نقطه q در داخل چند ضلعی A قرار می گیرد. اگر در عملیات حاصلضرب بیرونی صفر وجود داشته باشد. نتایج بین q و تمام یال های A و علائم همه ضرایب غیرصفر یکسان است، نقطه q در مرز چند ضلعی A است. اگر علائم حاصلضرب بیرونی بین q و تمام یال های A نباشد. به همین ترتیب، نقطه q خارج از چند ضلعی A قرار دارد.

قضیه 2.

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

همانطور که در قضایای 1 و 2 بیان شد، مشتق پیچیده ریاضی در اثبات همبستگی بین نتیجه حاصلضرب بیرونی و روابط توپولوژیکی اجسام فضایی دخالت دارد. ; بنابراین، برهان قضایا در اینجا ارائه نشده است. جزئیات نظری خاص به خوبی در ادبیات مربوطه بیان شده است [ 19 ]. از این پس، چندضلعی ساده در شکل 2 و چند وجهی ساده نشان داده شده در شکل 3 به عنوان نمونه هایی برای ارائه موارد کاربردی قوانین تصمیم گیری فضای توپولوژیکی اجسام فضایی در قضایای 1 و 2 استفاده می شوند.

در شکل 2 و شکل 3 ، نقاط P ₅ و P ₆ به ترتیب در داخل و خارج شی فضایی قرار دارند. با توجه به نتایج حاصل ضرب بیرونی بین دو نقطه و مرزهای شی فضایی، علائم ضرایب حاصل ضرب متقاطع برای حاصلضرب خارجی بین نقطه داخل شی فضایی و جسم مرزی سازگار است. برای حاصل ضرب خارجی بین نقطه خارج از شی فضایی و جسم مرزی، علائم ضرایب حاصل از ضرب متقاطع ناسازگار است.

3.5. تشخیص فضای داخلی اشیاء فضایی بر اساس محصول بیرونی

در این مقاله، روشی که قادر به مکان یابی سریع فضای داخلی چند ضلعی های ساده و چند وجهی های ساده در یک فضای سه بعدی است، بر اساس ویژگی های همبستگی کشف شده بین علامت ضرایب نتایج حاصل از محصول بیرونی و فضای توپولوژیکی توسعه یافته است. شی فضایی شکل 4 جریان الگوریتم را نشان می دهد. با استفاده از چندضلعی ساده که در شکل 5 به عنوان مثال نشان داده شده است، اصل الگوریتم تعیین فضای داخلی اجسام فضایی که بر اساس نتیجه حاصلضرب بیرونی است، نشان داده شده است. الگوریتم ابتدا راس محدب شی فضایی را جستجو می کند، به طور خاص، برای جستجوی راس با بالاترین مقدار مختصات در امتداد محور X (به عنوان مثال، P ₄ در شکل 5). در صورتی که چندین راس با مقدار محور X یکسان پیدا شود، یکی با بالاترین مقادیر محور Y و Z جستجو می‌شود. راس حاصل ناگزیر یک راس محدب است. علاوه بر این، حاصلضرب بیرونی بین هر رأس انتهایی که راس محدب را به هم متصل می کند ( P ₅ در شکل 5 ) و جسم مرزی، جایی که راس انتهایی دیگر در لبه L ₃₄ از P _{3 است.} ( شکل 5) است.)، نتیجه OPR محاسبه می شود. در نهایت، علائم ضرایب حاصلضرب خارجی بین یک نقطه فضایی دلخواه و مرز چندضلعی به عنوان معیاری برای تعیین اینکه آیا آن در داخل چند ضلعی است استفاده می شود. اگر علامت ضریب حاصلضرب بیرونی یک نقطه فضایی و مرز چندضلعی با نتیجه OPR مطابقت داشته باشد، آنگاه این نقطه فضایی در داخل چندضلعی قرار دارد. این روش می تواند فضای داخلی را هم برای چند ضلعی های ساده دو بعدی و هم برای چند وجهی های ساده سه بعدی تشخیص دهد.

3.6. تشخیص تقعر-تحدب یکپارچه چند بعدی برای اجسام فضایی

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

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

(2) ایجاد مرزهای جدید مربوط به راس قابل تشخیص: همه رئوس انتهایی را که به راس قابل تشخیص متصل هستند (نقاط 8 و 4) شناسایی کنید و از این رئوس شناسایی شده برای تولید چندین صفحه استفاده کنید (یا خطوط مستقیم) که همسطح (یا هم خطی) نیستند. متعاقباً، عبارات منسجم همه سطوح (یا خطوط) ایجاد شده را در مجموعه IdentifyObjects ذخیره کنید (به عنوان مثال، Edge L _{7_9} ایجاد شده توسط نقاط 7 و 9 متصل به نقطه 8، و Edge L _{3_5} تولید شده توسط نقاط 3 و 5 متصل به نقطه 4، در شکل 6 ).

(3) تجزیه و تحلیل توپولوژیکی راس قابل تشخیص: برای هر IObject از مجموعه IdentifyObjects، حاصل ضرب بیرونی این IObject و راس قابل تشخیص برای تعیین اینکه آیا علائم ضرایب خارجی محاسبه می شود یا خیر. محصول با موارد ذخیره شده در IdentifyDirect سازگار است. اگر آنها سازگار باشند، راس قابل تشخیص در داخل مرز جدید قرار دارد (نقطه 4 در شکل 6 ). در غیر این صورت، راس قابل شناسایی خارج از مرز جدید قرار دارد (نقطه 8 در شکل 6 ).

(4) تعیین تقعر-تحدب: اگر راس قابل تشخیص خارج از مرز جدید ایجاد شده قرار داشته باشد، آنگاه این راس یک راس محدب است (نقطه 8 در شکل 6 ). در غیر این صورت، یک راس مقعر است (نقطه 4 در شکل 6 ).

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

4. مطالعات موردی

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

چند وجهی سه بعدی ساده که در شکل 8 نشان داده شده است به عنوان نمونه ای برای تأیید الگوریتم پیشنهادی برای تشخیص تقعر و تحدب راس یکپارچه چند بعدی استفاده می شود. نقاط P ₄ و P ₁₆ رئوس قابل تشخیص هستند. با توجه به چارچوب الگوریتم ( شکل 7 )، الگوریتم هسته برای تشخیص تقعر-تحدب راس یک چند وجهی ساده شامل چهار مرحله زیر است:

(1) ابتدا حاصل ضرب بیرونی فضای داخلی چندوجهی ساده را در شکل 8 محاسبه کرده و علائم ضرایب حاصلضرب بیرونی را مشخص کنید. به طور خاص، نقطه افراطی P ₉ شناسایی می شود و P ₈ به طور تصادفی از رئوس متصل به P ₉ به عنوان نقطه مرجع انتخاب می شود و سطح F _{9_13_14_10} که P ₉ به آن تعلق دارد به عنوان سطح مرجع انتخاب می شود. حاصل ضرب بیرونی P ₈ و F _{9_13_14_10} محاسبه می شود و شکل 8 نتیجه را نشان می دهد.

(2) دوم، گره‌های پایانه‌ای را که مستقیماً با راس قابل شناسایی مرتبط هستند، شناسایی کنید، به عنوان مثال، P ₃ ، P ₅ ، P ₇ و P ₁₆ متصل به P ₄ در شکل 9 و P ₄ ، P ₅ و P ₁₄ به P ₁₆ در شکل 10 متصل شده و سطوح مرزی جدید F _{7_3_16} , F _{5_3_7} , F _{3_5_16} , و F _{7_5_16 ایجاد می کند}F _{4_5_14} با توجه به قوانین توپولوژیکی چند وجهی.

(3) سوم، حاصل ضرب بیرونی راس قابل تشخیص و سطح مرزی تازه ایجاد شده را محاسبه کنید. شکل 9 و شکل 10 نتایج دقیق را نشان می دهد.

(4) در نهایت، تعیین کنید که آیا ضرایب حاصلضرب بیرونی راس قابل تشخیص با ضرایب فضای داخلی چند وجهی مطابقت دارد یا خیر، و متعاقباً تقعر-تحدب راس را تعیین کنید.

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

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

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

منابع

ژائو، جی. گائو، ام. وانگ، اس. الگوریتم های تست جهت گیری، تحدب-تعریف و گنجاندن برای چندضلعی ها. در مجموعه مقالات کنفرانس بین المللی 2009 فناوری اطلاعات و علوم کامپیوتر، کیف، اوکراین، 25 تا 26 ژوئیه 2009. انجمن کامپیوتر IEEE: واشنگتن، دی سی، ایالات متحده آمریکا، 2009. [ Google Scholar ]
لی، دبلیو. Ong، ET; خو، اس. Hung, T. الگوریتم آزمون گنجاندن نقطه برای چند ضلعی های ساده. در مجموعه مقالات علوم محاسباتی و کاربردهای آن-ICCSA 2005، کنفرانس بین المللی، سنگاپور، 9-12 مه 2005. بخش اول. اسپرینگر: برلین/هایدلبرگ، آلمان، 2005. [ Google Scholar ]
وو، اچ. گونگ، جی. لی، دی. Shi, W. یک الگوریتم جبری برای پرس و جو شامل نقطه. محاسبه کنید. نمودار. 2000 ، 24 ، 517-522. [ Google Scholar ] [ CrossRef ]
لی، جی. وانگ، دبلیو. وو، E. تست نقطه در چند ضلعی با تجزیه محدب. محاسبه کنید. نمودار. 2007 ، 31 ، 636-648. [ Google Scholar ] [ CrossRef ]
هورمن، ک. Agathos، A. نقطه در مسئله چند ضلعی برای چند ضلعی های دلخواه. محاسبه کنید. Geom. 2001 ، 20 ، 131-144. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
ژائو، جی. چنگ، ی. گائو، ام. وانگ، اس. الگوریتمی برای تعیین جهت و تحدب – تقعر چندضلعی های ساده. در مجموعه مقالات اولین کارگاه بین المللی در سال 2009 در زمینه فناوری آموزش و علوم کامپیوتر، ووهان، چین، 7 تا 8 مارس 2009. جلد 2، ص 463-467. [ Google Scholar ]
Wu, C. تعیین رئوس محدب – مقعر چند ضلعی با نگاشت توپولوژیکی. جی. کامپیوتر. به دس کمک کرد. محاسبه کنید. نمودار. 2002 ، 14 ، 810-814. [ Google Scholar ]
آماتو، N. تقریبی تجزیه محدب چند وجهی. محاسبه کنید. به Geom کمک کرد. دس 2008 ، 25 ، 503-522. [ Google Scholar ]
Lien, J.-M.; آماتو، NM تجزیه محدب تقریبی چندضلعی ها. محاسبه کنید. Geom. 2006 ، 35 ، 100-123. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
Zhou، P. الگوریتمی برای تعیین رئوس محدب مقعر یک چندضلعی دلخواه. جی. سافتو. 1995 ، 6 ، 276-279. [ Google Scholar ]
خو، آر. Zhang, Z. الگوریتمی برای تعیین سریع تحدب-تعریف رئوس یک چندضلعی دلخواه. J. Huazhong Univ. علمی تکنولوژی 1997 ، 25 ، 103-104. [ Google Scholar ]
ژو، پی. هندسه محاسباتی: طراحی و تحلیل الگوریتم . انتشارات دانشگاه Tsinghua: پکن، چین، 2006. [ Google Scholar ]
فیتو، اف. تورس، جی سی. Ureña، A. تست جهت گیری، سادگی و گنجاندن برای چند ضلعی های مسطح. محاسبه کنید. نمودار. 1995 ، 19 ، 595-600. [ Google Scholar ] [ CrossRef ]
جین، دبلیو. تانگ، دبلیو. Tang, R. یک الگوریتم سریع برای تعیین تحدب – تقعر رئوس چند ضلعی ساده. J. Eng. نمودار. 1998 ، 1 ، 66-70. [ Google Scholar ]
پانگ، ام. Lu, Z. الگوریتمی برای شناسایی سریع رئوس محدب مقعر چندضلعی ساده بر اساس مقایسه شیب دو بردار لبه مجاور. J. Eng. نمودار. 2004 ، 3 ، 71-77. [ Google Scholar ]
ژائو، جی. ژانگ، جی. Qu, S. جهت گیری و شناسایی تحدب-تعرفه برای چندضلعی ها با استفاده از دنباله رئوس انتهایی. J. Eng. نمودار. 2007 ، 1 ، 55-59. [ Google Scholar ]
کلیفورد، WK کاربردهای جبر گسترده گراسمن. صبح. جی. ریاضی. 1878 ، 1 ، 350-358. [ Google Scholar ] [ CrossRef ]
دورست، ال. فونتیجن، دی. مان، اس. جبر هندسی برای علوم کامپیوتر: رویکرد شی گرا به هندسه . Morgan Kaufmann Publishers: San Francisco, CA, USA, 2007. [ Google Scholar ]
یوان، ال. یو، ز. لو، دبلیو. ژو، ال. Lü, G. یک مدل داده مکانی سه بعدی GIS بر اساس AIgebra هندسی منسجم. علمی علوم زمین چین 2011 ، 54 ، 101-112. [ Google Scholar ] [ CrossRef ]
ژانگ، J.-Y. یین، P.-C. لی، جی. گو، H.-H. ژائو، اچ. فو، جی. سی. مدل داده های کاداستر سه بعدی بر اساس جبر هندسه منسجم. ISPRS Int. J. Geo-Inf. 2016 ، 5 ، 20. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
لی، جبرهای ثابت HB و استدلال هندسی . World Scientific: سنگاپور، 2008. [ Google Scholar ]
لی، HB؛ هستنس، دی. Rockwood، A. مختصات همگن تعمیم یافته برای هندسه محاسباتی، محاسبات هندسی با جبر کلیفورد . Springer: برلین، آلمان، 2001; ص 27-59. [ Google Scholar ]
پنواس، سی. Lasenby, J. شرح یکپارچه هندسه چند نما، محاسبات هندسی با جبر کلیفورد . Springer: برلین، آلمان، 2001. [ Google Scholar ]
کامرون، جی. Lasenby، J. جبر هندسی منسجم گرا. در مجموعه مقالات هفتمین کنفرانس بین المللی جبرهای کلیفورد و کاربردهای آنها در فیزیک ریاضی ICCA7، تولوز، فرانسه، 19-29 مه 2005. [ Google Scholar ]
لاسنبی، جی. بایرو-کوروچانو، ای. لاسنبی، ا. Sommer, G. روشی جدید برای محاسبه ثابت‌ها در بینایی کامپیوتر. در مجموعه مقالات سیزدهمین کنفرانس بین المللی تشخیص الگو، موسسه مهندسین برق و الکترونیک (IEEE)، ICPR 96، وین، اتریش، 25-29 اوت 1996. [ Google Scholar ]
لاسنبی، جی. فیتزجرالد، دبلیو. دوران، سی. روش‌های هندسی جدید برای بینایی کامپیوتری: کاربرد در تخمین ساختار و حرکت. بین المللی جی. کامپیوتر. Vis. 1998 ، 26 ، 191-213. [ Google Scholar ] [ CrossRef ]
Penvass, C. کاربردهای جبر هندسی در بینایی کامپیوتری. Ph.D. پایان نامه، دانشگاه کمبریج، کمبریج، انگلستان، 2000. [ Google Scholar ]
یوان، ال. یو، ز. لو، دبلیو. یی، ال. لو، جی. محاسبات روابط توپولوژیکی چند بعدی-یکپارچه: یک رویکرد مبتنی بر جبر هندسی سلسله مراتبی. بین المللی جی. جئوگر. Inf. علمی 2014 ، 28 ، 2435-2455. [ Google Scholar ] [ CrossRef ]
یوان، ال. یو، ز. چن، اس. لو، دبلیو. وانگ، ی. لو، جی. کاستا: تحلیل یکپارچه مکانی-زمانی مبتنی بر جبر کلیفورد. ترانس. GIS 2010 ، 14 ، 59-83. [ Google Scholar ] [ CrossRef ]
یوان، ال. یو، ز. لو، دبلیو. هو، ی. فنگ، ال. زو، A.-X. یک رویکرد مبتنی بر تانسور سلسله مراتبی برای فشرده سازی، به روز رسانی و جستجوی داده های مکانی. IEEE Trans. بدانید. مهندسی داده 2015 ، 27 ، 312-325. [ Google Scholar ] [ CrossRef ]
یو، ز. لو، دبلیو. هو، ی. یوان، ال. زو، A.-X. Lu, G. تشخیص تغییر برای داده‌های برداری سه بعدی: رویکرد تقاطع Delaunay-TIN مبتنی بر CGA. بین المللی جی. جئوگر. Inf. علمی 2015 ، 29 ، 2328-2347. [ Google Scholar ] [ CrossRef ]
لو، دبلیو. هو، ی. یو، ز. یوان، ال. Lü, G. A Representation Hierarchical and Computation Scheme of Arbitrary- بعدی هندسی اولیه بر اساس CGA. Adv. Appl. کلیفورد جبر 2017 ، 27 ، 1977-1995. [ Google Scholar ] [ CrossRef ]
لو، دبلیو. یو، ز. یوان، ال. هو، ی. زو، A.-X. Lü, G. محاسبات GIS مبتنی بر الگو: یک رویکرد جبر هندسی. بین المللی جی. جئوگر. Inf. علمی 2017 ، 31 ، 2045–2067. [ Google Scholar ] [ CrossRef ]

شکل 1. چارچوب کلی.

شکل 2. همبستگی بین نتایج محصول بیرونی و فضای توپولوژیکی یک چندضلعی محدب ساده.

شکل 3. همبستگی بین نتایج محصول بیرونی و فضای توپولوژیکی یک چند وجهی ساده.

شکل 4. گردش کار الگوریتم تشخیص فضای داخلی برای یک شی فضایی بر اساس محصول بیرونی.

شکل 5. نمودار شماتیک روش تشخیص فضای داخلی برای یک شی فضایی.

شکل 6. نمودار شماتیک تشخیص تقعر-تحدب راس برای چند ضلعی های ساده.

شکل 7. چارچوب الگوریتم تشخیص تقعر-تحدب راس برای اجسام فضایی بر اساس محصول بیرونی.

شکل 8. نمودار شماتیک تشخیص تقعر-تحدب راس برای یک چندوجهی ساده.

شکل 9. نمودار شماتیک تشخیص رئوس مقعر در یک چندوجهی ساده.

شکل 10. نمودار شماتیک تشخیص رئوس محدب در یک چندوجهی ساده.

مقالات داخلی و بین المللی

بدون دیدگاه

دیدگاهتان را بنویسید لغو پاسخ

برای نوشتن دیدگاه باید وارد بشوید.

مشاورین هوش پیروزی

خلاصه

کلید واژه ها:

1. معرفی

2. ایده اولیه