Computational Geometry
In this article I am going to cover the following questions regarding computational geometry.
- What is Computational geometry?
- What are the use of Computational geometry?
- What are the application of Computational geometry?
- What are the goals of Computational geometry?
- Things you should know about Computational geometry.
- Course Overview. (Topics)
What is Computational geometry?
The term first appeared within the 70’s, originally mentioned computational aspects of solid/geometric modelling. Computational geometry is an integral part of mathematics and computer science deals with the algorithmic solution of geometry problems, algorithms for manipulating curves and surfaces in solid modelling.
Simply said, It’s the sub-field of algorithm theory that involves the planning and analysis of efficient algorithms for problems involving geometric input and output. It has great applications in special effects , Robot Motion planning, and lots of such fields.
The main branches of computational geometry are:
Combinatorial computational geometry: also known as algorithmic geometry, which deals with geometric objects as discrete entities.
Numerical computational geometry: also known as machine geometry, computer-aided geometric design (CAGD), or geometric modelling, which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems.
This branch could also be seen as an extra development of projective geometry and is usually considered a branch of special effects or CAD.
What are the uses of Computational geometry?
Geometry is useful for statistics/optimization: There are stuffs like linear/convex programming (or nonlinear programming), which are very geometrical algorithms. This gets utilized in computer vision - for instance for bundle adjustment (for example linear programming), also gets used a lot in economics.
It’s also use in mesh enveloping - this is often used tons on current games/3d programs.
It’s the sub-field of algorithm theory that involves the design and analysis.
Following are some domains or fields where we practically use computational geometry.
--Robot Motion Planning
--Computer Graphics - Rendering
--Computer games
--Packing
--Casting and moulds
--Nearest cab search
What are the application of Computational geometry?
Computational geometry has many applications in different domains / fields
--Applications in Computer Graphics:
-Visibility Culling
-Global Illumination
- Windowing & Clipping
-Model Simplification
-3D Polyhedral Morphing
-Collision Detection
--Applications in Geometric Modelling
- A Motion Planning
-Boolean Operations
-Surface Intersections
-Finite Element Mesh Generation
-Surface Fitting
-Polyhedral Decomposition
--Applications in Robotics
-Assembly Planning
-Grasping & Reaching
-Applications in Vision & Imaging
-Shape/Template Matching
-Pattern Matching
-Structure from motions
-Shape Representation (Core)
-Motion Representation (KDS) etc.
What are the goals of Computational geometry?
-To get an appreciation of geometry,
-Understand considerations and trade-offs in designing algorithms
-To be able to read & analyse literature in computational geometry.
Course Overview.
-Computer Graphics
-Geometric Modeling
-Robotics & Automation
-Vision & Imaging
-Scientific Computing
-Geographic Information Systems
Things you should know:(Algorithms)
Clear your concepts in Geometry
If you're a newbie in geometry or revisiting it after an extended time, I suggest you read the primary chapter from the O’Rourke’s Text Computational Geometry in C and clear your basic concepts.
Triangulation and Partitioning
Dividing an outsized geometrical structure into contiguous smaller structures that we will easily affect is extremely common in these geometric algorithms. Simplest object we will have during a planar 2-D figure may be a triangle.
Turns out triangulation of a polygon helps solve plenty of problems in Computational Geometry.
This problem has been the main target of this subject for years.
-Convex Hull Computation
The Convex Hull of the polygon is that the minimal convex set wrapping our polygon.
-Plane Sweep technique is another one of the most common technique used in algorithms.
-Graham’s Algorithm
A little on Orientations:
The idea of how the points are oriented plays a key role in understanding graham’s algorithm, so make sure you read this before fiddling with the algorithm.