هندسة تحسيبية
| الهندسة |
|---|
 |
| التاريخ (خط زمني) |
| علماء الهندسة |
الهندسة الرياضية التحسيبية إنگليزية: Computational geometry هي فرع من علم الحاسوب التي تختص بدراسة الخوارزميات التي من الممكن تمثيلها هندسياً. بعض المشاكل الهندسية البحتة تبرز أثناء دراسة بعض الخوارزميات الهندسية التحسيبية، والتي تعتبر أيضاً جزءاً من الهندسة التحسيبية.
كان التقدم في كل من رسوميات الحاسوب، والتصميم والتصنيع بمساعدة الحاسوب الدافع الأساسي وراء تطور الهندسة التحسيبية، لكن العديد من المسائل المدروسة فيها ذات طبيعة تقليدية، وقد تأتي من التمثيل الرياضي mathematical visualization.
تضم التطبيقات الهامة للهندسة التحسيبية مواضيع من مثل الروبوتيات (تخطيط الحركة، ومشاكل الرؤية)، نظم المعلومات الجغرافية geographic information systems (GIS) (تحديد المواقع الجغرافية والبحث عنها، خطط السير)، تصميم الدارات المتكاملة، والهندسة بمساعدة الحاسوب.
إن الفرعين الأساسيين للهندسة التحسيبية هما:
- الهندسة التحسيبية التوافقية Combinatorial computational geometry، وأحياناً الهندسة الخوارزمية algorithmic geometry والتي تتعامل مع الكائنات الهندسية على أنها كيانات متقطعة. [1]
- الهندسة التحسيبية العددية Numerical computational geometry، وتسمى أيضاً هندسة الآلة machine geometry، أو التصميم الهندسي بمساعد الحاسوب computer-aided geometric design (CAGD)، أو النمذجة الهندسية geometric modeling، والتي تتعامل بشكل أساسي مع تمثيل كائنات من العالم الواقعي بأشكال يمكن التعامل معها مع نظم التصميم والتصنيع بمساعدة الحاسوب. ويمكن النظر لهذا الفرع أيضاً على أنه تطور للهندسة الوصفية. إن استخدام الهندسة التحسيبية للدلالة على هذا المعنى بدأ منذ عام 1971. [2]
قائمة الخوارزميات
- Closest pair problem: find the pair of points (from a set of points) with the smallest distance between them
- Collision detection algorithms: check for the collision or intersection of two given solids
- Cone algorithm: identify surface points
- Convex hull algorithms: determining the convex hull of a set of points
- Euclidean distance transform: computes the distance between every point in a grid and a discrete collection of points.
- Geometric hashing: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation
- Gilbert–Johnson–Keerthi distance algorithm: determining the smallest distance between two convex shapes.
- Jump-and-Walk algorithm: an algorithm for point location in triangulations
- Laplacian smoothing: an algorithm to smooth a polygonal mesh
- Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm
- Minimum bounding box algorithms: find the oriented minimum bounding box enclosing a set of points
- Nearest neighbor search: find the nearest point or points to a query point
- Nesting algorithm: make the most efficient use of material or space
- Point in polygon algorithms: tests whether a given point lies within a given polygon
- Point set registration algorithms: finds the transformation between two point sets to optimally align them.
- Rotating calipers: determine all antipodal pairs of points and vertices on a convex polygon or convex hull.
- Shoelace algorithm: determine the area of a polygon whose vertices are described by ordered pairs in the plane
- Triangulation
- Delaunay triangulation
- Chew's second algorithm: create quality constrained Delaunay triangulations
- Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations
- Marching triangles: reconstruct two-dimensional surface geometry from an unstructured point cloud
- Polygon triangulation algorithms: decompose a polygon into a set of triangles
- Quasitriangulation
- Voronoi diagrams, geometric dual of Delaunay triangulation
- Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions
- Fortune's Algorithm: create voronoi diagram
- Delaunay triangulation
انظر أيضاً
- List of combinatorial computational geometry topics
- List of numerical computational geometry topics
- CAD/CAM/CAE
- Robotics
- Solid modeling
- طوبولوجيا تحسيبية
- هندسة رقمية
- هندسة متقطعة (هندسة توافقية)
- Space partitioning
- Wikiversity:Topic:Computational geometry
مراجع
- ^ من أوائل الكتب في هذا المجال: Franco P. Preparata and Michael Ian Shamos (1985). ‘’Computational Geometry - An Introduction’’. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3.
- ^ A.R. Forrest, "Computational geometry", ‘’Proc. Royal Society London’’, 321, series 4, 187-195 (1971)
قراءة متقدمة
دوريات
Combinatorial/algorithmic computational geometry
Below is the list of the major journals that have been publishing research in geometric algorithms. Please notice with the appearance of journals specifically dedicated to computational geometry, the share of geometric publications in general-purpose computer science and computer graphics journals decreased.
- ACM Computing Surveys
- ACM Transactions on Graphics
- Acta Informatica
- Advances in Geometry
- Algorithmica
- Ars Combinatoria
- Computational Geometry: Theory and Applications
- Communications of the ACM
- Computer Aided Geometric Design
- Computer Graphics and Applications
- Computer Graphics World
- Discrete & Computational Geometry
- Geombinatorics
- Geometriae Dedicata
- IEEE Transactions on Graphics
- IEEE Transactions on Computers
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Information Processing Letters
- International Journal of Computational Geometry and Applications
- International Journal of Differential Geometry
- Journal of Combinatorial Theory, series B
- Journal of Computational Geometry
- Journal of the ACM
- Journal of Algorithms
- Journal of Computer and System Sciences
- Management Science
- Pattern Recognition
- Pattern Recognition Letters
- SIAM Journal on Computing
- SIGACT News; featured the "Computational Geometry Column" by Joseph O'Rourke
- Theoretical Computer Science
- The Visual Computer
