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

227 questions
Filter by
Sorted by
Tagged with
2k views

24k views

### Finding points with the shortest distance

This takes in a user specified number of points then finds the two points with the shortest distance. ...
5k views

### Python implementation of the Ramer-Douglas-Peucker Algorithm

I recently implemented the RDP polygon approximation algorithm in Python and I'm skeptical of whether or not I implemented it correctly of with the greatest efficiency. The algorithm runs in around 0....
27k views

### Order a list of points by closest distance

I wrote a function that will take a list of points and then order them so they sort of... "chain together". The function will start with point #1 in the list. It will add point #1 to the list of ...
10k views

### Line segment to circle collision algorithm

I've written a function (in Python 3) which computes if a line segment (constraint) and a circle (body) collide, and returns the point of intersection (closest point to the centre of the circle): <...
2k views

### N dimensional cubes

A python program made with a friend to draw n dimensional hyper-cubes in python using turtle. Any suggestions for improvement. ...
321 views

### Updating positions of enemies every frame

I am making a game for Android using Java and libGdx. I have an ArrayList of enemies that are updated each frame. The update method for the enemy looks like this: <...
989 views

### Count number of isosceles triangles in a set of points

Given a set of points, what is the number of isosceles triangles that can be formed with the combinations of all points in the set? It is certain that 3 collinear points never exists in the set. <...
1k views

### Generate points for smooth movement between two given points

This is one of the methods in a project for generating points between two given points. We add points of route with a 25ms delay in an array and a camera on Google Maps is always at the last point. So ...
2k views

### Given a set of points and pairs of lines, count the number of points that are between the pairs of lines

This is a contest problem. The entire description is here. In resume: The question gives a point simulating a light explosion that always has a negative x coordinate, a set of pairs line segments on ...
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 ...
4k views

### Jarvis's March Convex Hull

I'm more concerned about the coding best practices and how it's written here than the actual algorithm and math. I'm concerned about stack constraints, passing arguments,..etc. If there is anything ...
10k views

### Generate sample coordinates inside a Polygon

I have a Polygon named as poly. I attempted to randomly select 5 coordinate points that lies inside the polygon. ...
1k views

### Calculating angle in isometric view

I have an angle where I need to convert a 'normal' angle to an isometric angle (116 degrees), and I came up with this function. It works, but I was wondering if the math could be optimized/simplified, ...
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 ...
1k views

### Finding largest subset of line segments that don't intersect

I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here. In summary, the challenge is to take a list of line segments, each specified by ...
2k views

### Drawing circles with triangles

As pyglet has no in-built method to return a vertex list of circle, I had to build one myself. This is a critical piece of code that I will use very frequently. I need it to be of very fine ...
486 views

### Lagrange Interpolation over quadrilateral points

I've been working on a program which calculates, given a point and 4 surrounding points, the Lagrange polynomial, in order to interpolate a value. Consider that I'm not a mathematician and I better ...
721 views

### 3D vector CUDA kernel

I designed this CUDA kernel to compute a function on a 3D domain: p and Ap are 3D vectors that are actually implemented as a ...
775 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

### C# code to derive tangential points between two circles to create a trapezoid

These are the steps to determine coordinates of the 4 points (P1, P2, P3, P4) that make up a tangential trapezoid connecting to circles. Another way of looking at it is to think of the tangential ...