# 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.

24 questions
Filter by
Sorted by
Tagged with
5k 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 ...
142 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: ...
3k 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 ...
3k 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? ...
19k 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 ...
360 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 ...
791 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 ...
3k views

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

Here is the function (along with its support functions): ...
2k 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 ...
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 ...
355 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 ...
5k 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'...
94 views

### 'Tis the season for gift-wrapping

When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer: ...
432 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 ...
2k 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 ...
219 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: ...
384 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? ...
61 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 ...
137 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 ...
747 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. ...
86 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 ...
121 views

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

This is a follow up to a previously asked Finding the closest pair of points divide-and-conquer question . The original code changed significantly based on answers from @AJNeufeld therefore I created ...