Geometric Algorithms
Geometric algorithms are a type of algorithm that deal with solving problems related to geometry. These algorithms are used to solve various geometric problems such as computing the area of a polygon, finding the intersection of geometric shapes, determining the convex hull of a set of points, and many other tasks related to geometric objects and their properties. Geometric algorithms are important in various fields such as computer graphics, computer-aided design, robotics, and geographical information systems.
Table of Content
- What are Geometric Algorithms?
- Pattern Printing
- Lines
- Triangle
- Rectangle | Square | Circle
- Quadrilateral
- 3D Objects
- Polygon and Convex Hull
- Standard Problems on Geometric Algorithm
Pattern Printing:
- Print lower triangle with alternate ‘*’ and ‘#’
- Print the pattern 1*2*5*6 –3*4
- Python Program to print the pattern ‘G’
- Pascal’s Triangle
- Program to print pyramid pattern
- Program to print the diamond shape
- Hour-glass Pattern
- Program to print V and inverted-V pattern
- Program to print hollow pyramid, diamond pattern and their modifications
- Code to Generate the Map of India (With Explanation)
Lines:
- Program to find the mid-point of a line
- Section formula (Point that divides a line in given ratio)
- Program to find slope of a line
- Program to find line passing through 2 Points
- Program for Point of Intersection of Two Lines
- Reflection of a point about a line in C++
- Find points at a given distance on a line of given slope
- Given n line segments, find if any two segments intersect
- Count maximum points on same line
- Minimum lines to cover all points
Triangle:
- Check whether triangle is valid or not if sides are given
- Check whether a given point lies inside a triangle or not
- Program to find area of a triangle
- Check if right triangle possible from given area and hypotenuse
- Count Integral points inside a Triangle
- Find all angles of a given triangle
- Program to find Circumcenter of a Triangle
- Number of Triangles that can be formed given a set of lines in Euclidean Plane
- Program to calculate area of Circumcircle of an Equilateral Triangle
- Program to find third side of triangle using law of cosines
Rectangle | Square | Circle:
- Check whether a given point lies inside a rectangle or not
- Program for Area And Perimeter Of Rectangle
- Find if two rectangles overlap
- How to check if given four points form a square
- Number of rectangles in N*M grid
- Program to find Circumference of a Circle
- Program to find area of a circle
- Check whether a point exists in circle sector or not
- Check if two given circles touch or intersect each other
- Program to find area of a Circular Segment
- Check if a line touches or intersects a circle
- Area of a Circumscribed Circle of a Square
- Find minimum radius such that atleast k point lie inside the circle
- Angular Sweep (Maximum points that can be enclosed in a circle of given radius)
Quadrilateral:
- Number of parallelograms when n horizontal parallel lines intersect m vertical parallellines
- Program for Circumference of a Parallelogram
- Program to calculate area and perimeter of Trapezium
- Program to find area of a Trapezoid
- Find all possible coordinates of parallelogram
- Maximum area of quadrilateral
- Check whether four points make a parallelogram
- Find the Missing Point of Parallelogram
3D Objects:
- Find the perimeter of a cylinder
- Program for Volume and Surface area of Frustum of Cone
- Program to calculate volume of Ellipsoid
- Program for volume of Pyramid
- Calculate volume and surface area of a cone
- Calculate Volume and Surface area Of Sphere
- Program for Volume and Surface Area of Cuboid
- Program for Volume and Surface Area of Cube
- Pythagorean Quadruple
- LS3/NS3 sphere generation algorithm and its implementation
Polygon and Convex Hull:
- How to check if a given point lies inside or outside a polygon?
- Area of a polygon with given n ordered vertices
- Tangents between two Convex Polygons
- Find number of diagonals in n sided convex polygon
- Convex Hull using Jarvis’ Algorithm or Wrapping
- Quickhull Algorithm for Convex Hull
- Deleting points from Convex Hull
- Minimum area of a Polygon with three points given
Standard Problems on Geometric Algorithm:
- Finding the vertex, focus
- and directrix of a parabola
- Find Simple Closed Path for a given set of points
- Number of Integral Points between Two Points
- Optimum location of point to minimize total distance
- Find perimeter of shapes formed with 1s in binary matrix
- Draw geometric shapes on images using OpenCV
- Find if it’s possible to rotate the page by an angle or not
- Equable Shapes
Quick Links :
- Learn Data Structure and Algorithms | DSA Tutorial
- ‘Practice Problems’ on Geometric Algorithms
- Recent Articles on Geometric Algorithms
Contact Us