آموزش تسلط بر الگوریتم های هندسه محاسباتی با C++

سرفصل ها و درس ها

مقدمه ای بر هندسه محاسباتی و جبر برداری. Introduction to Computational Geometry and Vector algebra.

• راه اندازی محیط زیست Setting up the Environment

• سلام هندسه محاسباتی Hello Computational Geometry

• اهداف آموزشی این بخش Learning Goals for this Section

• کاربرد هندسه محاسباتی Application of Computational Geometry

• اصطلاحات پایه Basic Terms

• مقدمه ای بر جبر برداری Introduction to Vector Algebra

• وکتور محصول نقطه Vector Dot Product

• وکتور محصول متقابل Vector Cross Product

• مبانی جبر برداری Basics Of Vector Algebra

• اجرای کلاس برداری Implementation of Vector Class

• توابع بزرگی و عادی سازی. Magnitude and Normalize functions.

• عملیات اصلی کلاس برداری Basic operations of Vector Class

• یافتن موقعیت نسبی یک نقطه در مقایسه با یک خط Finding Relative Position of a Point Compared to a Line

• بازنمایی یک خط Representation of a Line

• نمایندگی یک هواپیما Representation of a Plane

• تقاطع دو خط. Intersection of two lines.

• نقطه تقاطع دو خط Intersection Point of Two Lines

• محاسبه زاویه بین دو خط Calculating Angle Between Two Lines

• زاویه بین یک خط و یک صفحه Angle Between a Line and a Plane

• آزمون های خطی و همسطحی Collinear and Coplanar tests

• فاصله بین نقطه و یک خط Distance Between Point and a Line

• فاصله بین نقطه و هواپیما Distance Between Point and a Plane

• تقاطع بین خط و هواپیما Intersection Between Line and a Plane

• تقاطع بین دو صفحه Intersection between two Plane

• مروری بر ساختارها و الگوریتم های داده مورد نیاز Overview of needed Data Structures and Algorithms

پارتیشن بندی چند ضلعی Polygon Partitioning.

• قضیه گالری هنر Art Gallery theorem

• مثلث سازی چند ضلعی با برش گوش - مقدمه Polygon Triangulation by Ear Clipping - Introduction

• نمایش چند ضلعی ساده Simple Polygon Representation

• تست مورب Diagonal Test

• مثلث سازی چند ضلعی با برش گوش - پیاده سازی الگوریتم Polygon Triangulation by Ear Clipping - Algorithm Implementation

• DCEL - مقدمه DCEL - Introduction

• DCEL - ساخت و ساز DCEL - Construction

• DCEL - توابع ابزار و عملکرد تقسیم DCEL - Utility functions and Split function

• مقدمه ای بر چند ضلعی های یکنواخت Introduction to monotone polygons

• توضیح الگوریتم پارتیشن بندی چند ضلعی یکنواخت Explanation of monotone polygon partitioning algorithm

• پیاده سازی پارتیشن بندی چند ضلعی یکنواخت Monotone Polygon Partitioning Implementation

تقاطع بخش خط Line Segment Intersection

• کاربردهای تقاطع پاره خط Applications of line segment Intersection

• خلاصه دستی الگوریتم تقاطع بخش خط Manual rundown of Line segment Intersection algorithm

• مقدمه ای بر الگوریتم جابجایی صفحه برای یافتن تقاطع پاره خط Introduction to Plane Sweep algorithm for finding line segment intersection

• پیاده سازی الگوریتم جابجایی هواپیما Implementation of Plane Sweep Algorithm

بدنه های محدب Convex hulls

• کاربردهای بدنه محدب Applications of Convex hulls

• بدنه محدب 2 بعدی: الگوریتم بسته بندی هدیه Convex hull 2D : Gift wrapping algorithm

• بدنه محدب 2 بعدی: اسکن گراهام اصلاح شده Convex hull 2D : Modified Graham's Scan

• بدنه محدب سه بعدی - مقدمه ای بر الگوریتم Convex hull 3D - Introduction to the algorithm

• بدنه محدب 3D - توابع کاربردی Convex hull 3D - Utility functions

• بدنه محدب 3D - پیاده سازی Convex hull 3D - Implementation

درختان Trees

• درخت جستجوی دودویی - توابع معرفی، ساخت، درج و پیمایش Binary Search Tree - Introduction, Construction, Insert and Traversal functions

• یک اشاره گر به نام والد را به ساختار BSTNode اضافه کنید. Add a pointer called parent to BSTNode structure.

• درخت جستجوی دودویی - جستجو، حداقل، حداکثر، پیشین و جانشین Binary Search Tree - Search, Minimum, Maximum, Predecessor and Successor

• سخنرانی 40: درخت جستجوی باینری - تابع حذف Lecture 40: Binary Search Tree - Delete function

پرس و جوهای محدوده Range Queries

• مقدمه ای بر پرس و جوهای محدوده Introduction to Range Queries

• پرس و جوی محدوده 1 بعدی با BST 1D Range Query with BST

• درختان KD - معرفی و ساخت KD Trees - Introduction and Construction

• درختان KD - پرس و جوهای جستجو KD Trees - Search Queries

• درختان KD - پرس و جوهای جستجو - پیاده سازی قسمت 2 KD Trees - Search Queries - Implementation part 2

• درختان KD - نزدیکترین همسایه و بخشهای همپوشانی و برخوردها KD Trees - Nearest Neighbor and Overlapped Segments and Collisions

• درختان مرتع Range Trees

• پرس و جوی محدوده دوبعدی با درختان محدوده 2D Range Query with Range Trees

بخش 8: چهار درخت Section 8 : Quad Trees

• کاربردهای درختان چهارگانه Applications of Quad trees

• مقدمه ای بر ساخت چهار درخت Introduction to quad tree construction

• اجرای طرح چهاردرختی Implementation of Quad tree construction

• یافتن همسایگان یک گره در چهار درخت Finding neighbors of a node in quad tree

• اجرای تعادل درخت چهار Implementation of balancing a Quad tree

نظریه گراف Graph Theory

• مقدمه Introduction

• بیایید برخی از اصطلاحات مربوط به قسمت 1 را یاد بگیریم Lets learn some jargon part 1

• بیایید برخی از اصطلاحات تخصصی قسمت 2 را یاد بگیریم Lets learn some jargon part 2

• نمایش ماتریس مجاورت یک گراف Adjacency matrix representation of a graph

• نمایش لیست مجاورت یک نمودار Adjacency list representation of a graph

• مقایسه بین دو پیاده سازی Comparison between two implementations

• اولین جستجوی عرض (BFS) Breadth first search (BFS)

• اجرای اولین جستجوی عرض Breadth first search implementation

• ابتدا جستجوی عمق Depth first search

• نمودارهای فرعی سلف Predecessor sub graphs

• طبقه بندی یال ها در نمودار فرعی سلف Classification of edges in predecessor sub graph

• جستجوی توپولوژیکی یک گراف جهت دار Topological search of a directed graph

• اجرای مرتب سازی توپولوژیکی Topological sort implementation

• جزء قوی یک نمودار به هم متصل است Strongly connected component of a graph

• مولفه به شدت مرتبط از اجرای یک گراف Strongly connected component of a graph implementation

• معرفی الگوریتم های کوتاه ترین مسیر Shortest path algorithms introduction

• الگوریتم بلمن فورد Bellman ford algorithm

• پیاده سازی الگوریتم بلمن فورد Bellman ford algorithm implementation

• کوتاه ترین مسیر در DAG Shortest path in DAG

• الگوریتم دایکسترا برای یافتن کوتاهترین مسیر Dijkstra's algorithm of finding shortest path

• الگوریتم دایکسترا برای یافتن توضیح کوتاهترین مسیر Dijkstra's algorithm of finding shortest path explanation

• الگوریتم دایکسترا برای یافتن پیاده‌سازی کوتاه‌ترین مسیر Dijkstra's algorithm of finding shortest path implementation

• معرفی درخت پوشا حداقل Minimum spanning tree introduction

• MST- مقدمه الگوریتم کروسکال قسمت 1 MST- Kruskal's algorithm introduction part 1

• بخش 2 مقدمه الگوریتم MST-Kruskal MST-Kruskal's algorithm introduction part 2

• پیاده سازی الگوریتم MST-Kruskal MST-Kruskal's algorithm implementation

• معرفی الگوریتم MST-Prims MST-Prims algorithm introduction

• پیاده سازی الگوریتم MST-Prims MST-Prims algorithm implementation

• مقدمه ای بر شبکه های جریان Introduction to flow networks

• قضیه برش حداکثر جریان حداقل Max flow min cut theorem