# Questions tagged [computational-geometry]

Computer geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.

25 questions
Filter by
Sorted by
Tagged with
7k views

### Faster computation of barycentric coordinates for many points

I'm just starting to understand the Python syntax and I created a module that does what I wanted, but really slow. Here are the stats of cProfile, top 10 ordered by ...
157 views

### Naive convex hull from Algorithms in a Nutshell book

I am working through the book Algorithms in a Nutshell by George T. Heineman and trying to translate the pseudocodes into Rust. Here is a naive convex hull algorithm: ...
41k views

### Overlapping rectangles

I received the following question in a technical interview today (for a devops/SRE position): Write a function which returns true if the two rectangles passed to it as arguments would overlap if ...
4k views

### Shamos-Hoey algorithm for checking the self-intersection of a closed shape

I implemented the Shamos-Hoey algorithm to check if a closed shape is self-intersected. Is this algorithm ok in terms of performance? ...
6k views

### Farthest point algorithm in Python

I am learning Python and I tried to do a program to find K points from a set of N points, farthest as much as possible (I'm not ...
24k views

### C++ 3D Vector Implementation

I have been learning C++ now for 2 months and this week I started reading a book on 3D graphics. I like coding whatever mathematical stuff I learn so I can understand it better, so when I learnt about ...
763 views

### Find the nearest point of a given set of points (part 2)

This is a continued discussion from here, and I use new a approach (bounding box/or envelop algorithm) to improve the algorithm efficiency. Any code bugs, algorithm time complexity improvement or ...
1k views

### Finding overlaps between two lists of axis-aligned rectangles

I am trying to find an efficient solution for finding overlapping of n rectangles where rectangles are stored in two separate lists. We are looking for all rectangles in ...
4k views

### Calculating if a point is within a polygon, or outside of it

Here is the function (along with its support functions): ...
2k views

### Graham Scan convex hull algorithm

I'm beginning to learn Haskell. I've implemented the Graham Scan algorithm for detection of convex hull following the Real World Haskell book. I'm looking for general advice regarding the style and ...
3k views

### Given a collection of points on a 2D plane, find the pair that is closest to each other

Full disclosure: I'm working on this for an online course. However, my goal is really just to get a pointer to where the issue is. The goal is to implement the closest points problem, that is, given ...
384 views

### 2D Convex hull exercise

I'm reading Real World Haskell, and this is my first try with the language. This is the result of the exercises of chapter 3: Consider three two-dimensional points a, b, and c. If we look at ...
7k views

### Mathematical Vector2 class implementation

This is my first attempt ever to build a Vector2 class. I scoured the net for anything that might make this class more efficient but know I'm to the point where I'...
105 views

### 'Tis the season for gift-wrapping

When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer: ...
5k views

### Finding the closest pair of points divide-and-conquer

Here is my code for the famous "finding the closest pair of points" problem from CLRS book section 33.4 using a divide-and-conquer approach (this code returns the minimum distance between pair of ...
230 views

### Implementation of Graham Scan algorithm in Haskell

Here is an implementation of Graham Scan algorithm for computing the convex hull of a finite set of points: ...
444 views

### Find Triangle Triplets from a list of given numbers

If a triplet of segments A, B and C are triangle triplets if and only if A + B > C A + C > B B + C > A Is there a better implementation for this problem? ...
524 views

### Tested cartesian plane utility

I am starting to explore automated testing of code, so I decided to write some trivial code about the cartesian plane and test it. I am particularly interested in automated testing conventions and ...
66 views

### Checking where/if another creature lies in a creature's field of view

Note: this is a more specific form of this I am working on a simulation of some virtual creatures. They all have vision that lets them see other creatures. To do this, I calculate the difference ...
275 views

### Find non duplicate Triangle Triplets from a list of given numbers- version 3

It is a continuation of my previous question: Find non duplicateTriangle Triplets from a list of given numbers After I realized triplet structure using less space than ...
140 views

### Find non duplicateTriangle Triplets from a list of given numbers

I implemented an O(N^2) algorithmic solution but not sure it is better than my previous implementation Find Triangle Triplets from a list of given numbers in case of performance. I adapted almost ...
754 views

### Creating shapes program with multiple classes (different files)

I just started to learn Objective C with Programming in Objective C by Stephen G. Kochanand and I would love to get your feedback to see if I'm getting OOP concept with Objective-C right. ...
154 views

### Graham Scan Algorithm in Haskell

I have just begun learning functional programming and Haskell. This is my attempt to implement a solution to Graham Scan Algorithm in Haskell. Note that I am not even sure if this is indeed Graham ...