Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# 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 with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
560 views

### Cubic spline interpolation in Python from scratch

I implemented the cubic spline interpolation explained in https://en.wikipedia.org/wiki/Spline_interpolation as a Python class. Of course, such an interpolation should exist already in some Python ...
453 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 ...
145 views

### Implementing Cyrus Beck algorithm for convex polygons

I have found the coordinates of the centroid for finding the direction of the normal vectors of the edges of the convex polygons. This method seems to work in the cases I tested. Is this fool proof ? ...
1k views

### Function to calculate distances and nearest points between 2 GeoPandas dataframes

I have 2 geoPandas frames and want to calculate the distance and the nearest point (see functions below) from the geoSeries geometry from dataframe 1 (containing ...
321 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: ...
813 views

### Computing intersection of 2D infinite lines

I wrote a small program to compute intersection of 2D infinite lines using Boost Geometry A line is defined by two points in Line class. The ...
172 views

### Graphical editor with geometric intersection

If it is possible I would like some comments on the overall style of the program. It feels like I am writing the whole program as one big script and I'm not sure how to break it down into several ...
2k views

### fftshift implementation for OpenCV

I'm trying to implement fftshift from matlab for OpenCV. Can you please review the correctness of my algorithm? Have I missed something? Also, is there a better and faster way to do it? ...
50 views

### Compute angular distances between data points in a matrix

I am having a hard time speeding up a function that I use to compute angular distances between data points in a matrix. More precisely, I want to compute \sum_{r=1}^n|\pi - \arccos\left(\frac{(X_{i}-...
101 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: ...
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 ...
119 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 (...
43 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 ...
984 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 ...
317 views

### Shortest bitonic tour

This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to ...
1k views

### Optimize QuadTree to find K Nearest Neighbors

I'm looking a way to make my k nearest neighbors search more efficient. The context of the question is that I'm given a list of topics that have a unique ID (integer) and a (x,y) coordinate (floats) ...
61 views

### Get directions for unit movement with conditions

I am developing a bot for Starcraft II. In my code for unit movement, I often find myself doing this: Calculate points around the current position of the unit Check if these points are valid and can ...
511 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. ...
72 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 ...
200 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 ...
426 views

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

Continuing the Algorithm in a Nutshell series, here is the code: ...
822 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 ...