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.

Filter by
Sorted by
Tagged with
13
votes
1answer
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 ...
4
votes
1answer
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: ...
11
votes
1answer
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 ...
16
votes
2answers
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? ...
11
votes
7answers
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 ...
8
votes
1answer
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 ...
6
votes
1answer
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 ...
4
votes
2answers
3k views

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

Here is the function (along with its support functions): ...
8
votes
2answers
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 ...
8
votes
2answers
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 ...
7
votes
1answer
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 ...
6
votes
4answers
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'...
6
votes
1answer
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: ...
4
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
2answers
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: ...
4
votes
1answer
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? ...
3
votes
2answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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. ...
2
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
2answers
236 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 ...
1
vote
0answers
217 views

Given a polygon with weighted vertices, calculate a value for an interior point

I want to be able to find out the value of a point inside a polygon if I have assigned weights to its vertices. In the figure below, some weights have been applied to the green dots. For some red ...