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

217 questions
Filter by
Sorted by
Tagged with
497 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? ...
513 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: ...
89 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 ...
113 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 ...
541 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 ...
389 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 ...
750 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 ...
192 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. ...
139 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 ...
314 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 ...
821 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 ...
453 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: ...
67 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 ...
108 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 (...
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 ...
228 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: <...
365 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 ...
41 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. ...
914 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 ...
184 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 ...
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 ...
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 ...
295 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: ...
230 views

...
414 views

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

Continuing the Algorithm in a Nutshell series, here is the code: ...
805 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: ...
69 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 ...
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 ...
841 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 ...
331 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 ...
692 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\\ ...
22k 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 ...
980 views

### Get all points within given radius for a given vector

I have a vector of ints that represents a point on a N-dimensional grid. I need to find all grid points that are within a given radius. I wrote the following, but ...
113 views

### Kattis “Hitting the Targets” utilizing a polymorphic relashionship

In order to learn C++ I have written a solution to this Kattis "Hitting the Targets" problem Basically the program is to accept some shapes (circles and rectangles) on std in and a set of points and ...
170 views

### Finding shortest distance between a point and a surface using Lagrange Multipliers

I am new to Matlab. Now I need to find the shortest distance between a given point to a surface, which is describe with a function. I am planing to implement the method described in the link below ...
102 views

### Parsing shorts from binary file and finding the closest and furthest points

A few months ago I got rejected at the technical interview for a position. The problem that they gave me is the following: From a binary file, parse two shorts, x and y and build a Point object with ...
Problem from HackerRank:: Problem Statement: There are $N$ lines. Each line has an index between $1$ and $N$. The slope of each line is negative, i.e. it goes from upper-left to lower-...