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

224 questions
Filter by
Sorted by
Tagged with
100 views

### Affine transformations in 2D space

During the past few days, I played around a bit with an SVG file, trying to minimize its size. One thing I stumbled upon was this transformation: ...
838 views

### Solver for some simple tangrams

I decided to write a program to solve Tangram puzzles. This went a bit out of hand and I ended up with 600+ lines of code. I don't think it should have taken so much code. Here is an image of a ...
474 views

### Java algorithm to declutter rectangles

I've been working on an algorithm to declutter rectangles while keeping them as close as possible to their original location (and oriented the same way). It seems to work fine when I have less than 1,...
394 views

### Feynmann lifeguard riddle graphical representation

Physicist Richard Feynman though of a very interesting riddle: Imagine you are a lifeguard at the side of the beach and there is a child drowning in the water. (You must cross both sand and water ...
440 views

### Find the closest parametric values corresponding to a BSpline's control points

On a curve generated by scipy.interpolate.BSpline I want to find the closest parameters relative to each control point, so that the given parametric range is ...
266 views

### Compute shortest distance between point and a rectangle

I want to compute the shortest distance between a position (x,y) and a rectangular box defined by (x_min, y_min) and (x_max, y_max). See the picture below with some examples. I know that in two ...
3k views

### 2D Bin Packing Algorithm Implementation

I wrote a 2D greedy bin packing algorithm using Python 3.6 Heres a quick summary: The algorithm consists of two classes (which I will attach at the end of this file along with a link to my github ...
527 views

### Java - fill triangle function

I am starting to work on a basic 3D renderer for fun, so right now I have made a triangle fill function to be used when I draw faces on models: ...
1k views

### Two circles intersect

Do two circles in a 2D plane disjoint? $$(r_1 + r_2) \cdot (r_1 + r_2) \gt \Delta{X} \cdot \Delta{X} + \Delta{Y} \cdot \Delta{Y}$$ Any comments / corrections on this code? ...
769 views

### Distance too close

Are two points too close? Trying to do the math as efficiently as possible. deltaX + deltaY is going to be > than the actual distance You might use this in game play - are players in range? ...
515 views

### Counting points on a given irregular grid that are inside or outside a circle

Given some points that are represented as (X, Y) coordinates, my task is to count the points that are inside a circle, on the circle, and outside the circle. The input is given in the following way: ...
92 views

### Cythonized Sutherland-Hogman algorithm

I want to cythonise the python implementation of the Sutherland-Hogman algorithm. This algorithm updates a list of vertices according to pretty simple rules (being inside or outside an edge, etc.) but ...
115 views

### Count lines with more the X dots on it

I have Python a Algorithm class with a calculate method that takes the list of tuples where every tuple have 2 integers (...
34 views

### Identifying local peaks among some 2D points

The following MATLAB code takes in multiple peak coordinates and heights and eliminates lesser peaks that are within a certain distance threshold of the highest peak of the vicinity. Is there a better ...
587 views

### Shortest path around a set of points

Problem I'm trying to get into Python and get a bit familiar with it, so I found a problem online to train. The problem was to find the shortest path around some points, given a set of nodes which ...
431 views

### Calculating the perimeter of certain points in a 2D array

I had to write code for a competition which calculates sum of the perimeter of two non-overlapping rectangles in a 2D space. My code is working fine and resulting in expected outputs. But it is taking ...
844 views

### Calculate angle between planes

I have written working code calculating the angle between the adjacent planes. I read subsequently from standart input: n - amount of triangles, m - amount of vertices ind[] - indices of the vertices ...
203 views

### Shortest distance from point to line segment in 3D

This function returns the shortest distance from a 3D point P to a line segment defined by two 3D points A and B. It projects P onto the line, then checks if this projected point lies between A and B. ...
149 views

### Removing undesired points from a mesh

I have a 3D data set made of a certain number of points (x,y,z) that cover a certain region of space. Using the scatteredInterpolant object I can interpolate this ...
316 views

### Python Kohonen algorithm

I've tried to implement the Kohonen algorithm using Python and I've managed to do this, but my result is so slow. I want to know if anyone knows how I can improve it. Objective: I have to read a ...
925 views

### 4-Bar Mechanism Generation

For a school project, I will design and prototype a bicycle brake that uses a four-bar linkage to accomplish its goal. My Python 3 code does this mechanism generation, and implements methods to ...
2k views

### Applying Laplacian smoothing to vertices in a mesh

I'm totally new in Python and I wrote some code. It is a simple algorithm to smooth objects. I need to find adjacent vertices in mesh and sum their coordinates and after that divide by a number of ...
506 views

### Compute the minimum distance between two points in a 2-D plane

I have tried to calculate the minimum distance between the two points in a 2D plane. I have used the divide and conquer strategy to attain the complexity of n logn. ...
7k views

### Closest distance between points in a list

In a course I'm doing, I was given the task of finding the closest pair of points among the given points. The program that passed all test cases was the following: ...
70 views

### AABB Intersections with Space Partitions, A Sample Code Performance and Reliability

I have originally written the following Matlab code to find intersection between a set of Axes Aligned Bounding Boxes (AABB) and space partitions (here 8 partitions). I believe it is readable by ...
2k views

### Another way to find the nearest neighbor points in a 2D plane

I was inspired by another question to post another method of finding the two points in a plane that are closest to each other1. This one is a line-sweep algorithm. It works roughly like this: Sort ...
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 ...
117 views

### Finding vtkCells in the vicinity of or coinciding with vtkPixels

I am looking to optimize this code. In its current state it is working, however, I am looking to improve it. To represent the situation. I have a vtkPixel (...
423 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 ...
240 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: <...
376 views

### Clustering points on a sphere

I have written a short Python program which does the following: loads a large data file ($10^9+$ rows) where each row is a point on a sphere. The code then loads a pre-determined triangular grid on ...
42 views

### Modeling a control polygon for a piecewise spline curve

Aim I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...
92 views

### Finding the coordinates on an edge of a square

I wrote a calculation that finds coordinates on an edge of a square, but it came out as a really long nested tangle of conditions. After some reduction and finding common pieces I arrived at this ...
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. ...
967 views

### Find k nearest points

I'm working on a problem to select k nearest points for a given point. Any advice for bugs, improvements are appreciated, including general advice to implement find nearest k points. My major idea is ...
198 views

### Find overlaps between lists of axis-aligned rectangles using line sweep

Triggered by Finding overlaps between two lists of axis-aligned rectangles, I tried to code "rectilinear" intersection using line sweep - in python. I'm not keen on discussing (2D) line sweep in ...
868 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 ...
1k views

### Generating a random coordinate (x, y) inside of a given polygon/area

I'm creating a virtual mapping software that essentially breaks coordinates into Areas. An Area is comprised of a defined list of boundary coordinates (coordinates ...
3k views

### Finding closest pair of 2D points, using divide-and-conquer

I'm learning C++ as well as algorithms. Here's my implementation of finding the closest pair problem. I tried to minimize memory by using only iterators. And points are being read from ...
308 views

### Divide-and-conquer approach for finding the closest pair of points

This is an algorithm for finding the closest pair of points on a 2d plane by dividing the problem by half recursively, as illustrated here: ...
237 views

...
422 views

### Graham scan from Algorithms in a Nutshell in Rust

Continuing the Algorithm in a Nutshell series, here is the code: ...
821 views

### Check if a point is inside a polygon

To check if a given point is inside a polygon or not is a very useful piece of code. Here is my implementation in JavaScript of an algorithm counting the number of times a ray crosses the perimeter ...
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: ...
70 views

### Replacing nodal values in a mesh with >1e6 inputs selectively using a polygon

I have a set of data which represents a set of nodes, each node is associated with a value (represented by a color in the image). What I want to achieve is selectively changing those values. The mesh ...
231 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 ...
897 views

### Calculating a circle with bezier curves

I am new to Haskell, and have been reading Learn You a Haskell for Great Good!. I've rewritten a problem that I recently solved in JavaScript in Haskell to practice what I have been reading. A ...
345 views

### Lines, intersections and terrible unit tests

I needed Line and LineF for the next stage of a project I'm working on, so I developed them. I also needed to determine if two ...
738 views

### Simple geometry problems involving rectangles and circles in Python 3

I'm working with some simple geometry problems featuring rectangles and circles. My code is as follows: ...
73 views

### Parametrization of a curve

For a set of 2D or 3D points $\{\mathbf P_0, \mathbf P_1,\cdots,\mathbf P_n\}$, their parameters $\mathbf T = \{t_0,t_1,\cdots,t_n \}$ could be computed as follow: \begin{align} t_0&=0\\ ...