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
5
votes
0answers
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 ...
4
votes
0answers
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 ...
3
votes
0answers
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 ? ...
3
votes
0answers
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 ...
3
votes
0answers
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: ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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? ...
2
votes
0answers
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}-...
2
votes
0answers
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: ...
2
votes
0answers
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 ...
2
votes
0answers
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 (...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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) ...
1
vote
0answers
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 ...
1
vote
0answers
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. ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
426 views

Graham scan from Algorithms in a Nutshell in Rust

Continuing the Algorithm in a Nutshell series, here is the code: ...
1
vote
0answers
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 ...
1
vote
0answers
239 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 ...
1
vote
0answers
397 views

Get vertical acceleration from rotation vector and accelerometer values

My goal here is to calculate the acceleration towards the ground, which I call "vertical acceleration". This seems to be working OK for the most part, except when there is a lot of rotation going on ...