computational geometry - OpenGenus IQ: Learn Algorithms, DL, System Design (Page 2)

Voronoi Diagram

In this article, we discuss the voronoi diagram in depth and how to use Fortunes Sweep Line algorithm to compute it. This is an important topic in Computational Geometry.

Algorithms

Oriented area of a triangle

In this article, we discuss how to find the area of an oriented Polygon using the shoelace algorithm and as an example we find the area of an oriented triangle.

Algorithms

Self Crossing Problem

This article delves into the illustrious Self Crossing problem and looks at how we can solve it. This can be solved efficiently using Computational Geometry ideas.

Algorithms

Check if given point is inside a convex polygon

In this post, we discuss how to check if a given point is inside a convex polygon using the Graham scan algorithm and list application areas for the solution.

Algorithms

Pick’s Theorem in Computational Geometry

In this post, we discuss Pick's theorem, its proof and example use cases where its application would be efficient to solve a problem. Using Pick's Theorem, we can compute the area of simple polygons.

Algorithms

Number of Integral points inside a triangle

In this article, we have explored an insightful approach/ algorithm to find the number of interior integral points of a triangle. This is an important concept in the field of computational geometry.

Algorithms

Find mirror image of point in 2D plane

In this article, we will learn how to find the mirror image position of a point in a 2D plane along with C++ implementation of the approach.

computational geometry

Number of integral points between two points

In this post, we solve an algebraic geometrical problem using programming whereby we find the number of integral points between two given two points.

Algorithms

Orientation of three ordered points

In this article, we will discuss about algorithms to detect the orientation of three given ordered points. Orientation imply collinear, Clockwise or Anti-clockwise.

Algorithms

Simple closed path in a set of points

In this article, we have explored an insightful approach/ algorithm to find a simple closed path in a set of points. This is an important concept in the field of computational geometry.

Algorithms

Klee's algorithm (Union of Line Segments)

In this article, we will dive deep into Klee's algorithm and understand it better. Klee's algorithm is used to find the union of overlapping line segments when projected on a line.

Algorithms

Flood Fill Algorithms

Flood Fill algorithm is an Algorithm that determines the area connected to a given node in a N-dimensional array. Some operations are performed on the connected nodes like color change. This is also known as Seed Fill Algorithm.

Algorithms

Maximum points on a line

In this article, we have explored an insightful approach/ algorithm to find the maximum number of points on a straight line. This problem finds many uses in computational geometry.

Algorithms

Inside Outside Test [2 algorithms: Even-Odd and Winding Number]

In Computer Graphics, Inside Outside is performed to test whether a given point lies inside of a closed polygon or not. Mainly, there are two methods to determine a point is interior/exterior to polygon: Even-Odd / Odd-Even Rule or Odd Parity Rule and Winding Number Method.

Algorithms

Number of rectangles from a given set of points

We have discussed how to find the number of rectangles (parallel to the axes) possible from a given set of coordinate points.

Algorithms

Xiaolin Wu's Line Drawing Algorithm

Xiaolin Wu's Line Drawing Algorithm is a recognized Line Drawing Algorithm in Computer Graphics which is used to produce Anti-aliased lines. In this article, we have explored this in depth.

Algorithms

Cohen Sutherland Line Clipping Algorithm

Cohen Sutherland Algorithm is a linear time complexity line clipping algorithm that cuts lines to portions which are within a rectangular area. It eliminates the lines from a given set of lines which belongs outside the area of interest and clip those lines which are partially inside

convex hull

Kirkpatrick-Seidel Algorithm (Ultimate Planar Convex Hull Algorithm)

Algorithm Complexity Applications Reading time: 15 minutes | Coding time: 9 minutes The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm", is an algorithm for computing the

convex hull

Chan's Algorithm to find Convex Hull

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space. The algorithm takes O(n log h) time, where h is the number of vertices of the output (the convex hull).

convex hull

Graham Scan Algorithm to find Convex Hull

Graham's Scan Algorithm is an efficient algorithm for finding the convex hull of a finite set of points in the plane with time complexity O(N log N). The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary.

convex hull

Gift Wrap Algorithm (Jarvis March Algorithm) to find Convex Hull

Gift Wrap Algorithm ( Jarvis March Algorithm ) to find the convex hull of any given set of points. We start from the leftmost point (or point with minimum x coordinate value) and we keep wrapping points in a counterclockwise direction. Find pseudocode, implementations, complexity and questions

convex hull

Divide and Conquer algorithm to find Convex Hull

Divide and Conquer algorithm to find Convex Hull. The key idea is that is we have two convex hull then, they can be merged in linear time to get a convex hull of a larger set of points. It requires to find upper and lower tangent to the right and left convex hulls C1 and C2

convex hull

Quick Hull Algorithm to find Convex Hull

Quickhull is a method of computing the convex hull of a finite set of points in the plane. It uses a divide and conquer approach. It was published by C. Barber and D. Dobkin in 1995. average case complexity is considered to be Θ(n * log(n))