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.

Filter by
Sorted by
Tagged with
1
vote
1answer
137 views

Angle reflection function

I've developed a function to calculate the exit angle of a projectile after it collides with a boundary/edge inside a rectangular space, based on the entry angle and the axis it is colliding with. ...
7
votes
3answers
4k 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....
0
votes
1answer
47 views

Calculating minimum size of rectangle that contains two smaller ones [closed]

My Rectangle class contains one vertex (x,y), its width a, and its height b; the opposite ...
6
votes
1answer
62 views

Catmull-Rom Interpolator: Template pandemonium avoidance

I have a pull request implementing Catmull-Rom interpolation. I have gotten it pretty fast-to ~25 ns/call-but I feel the design is not enlightened. The code is here, and reproduced below: ...
2
votes
1answer
76 views

Segment road map data with heuristics

Backstory A little while ago I was assigned with the task of clustering some road segments using open street map data. After parsing a huge XML (maybe that should be another review) I ended up with ...
12
votes
1answer
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 ...
22
votes
8answers
3k views

Area of the triangle generated by the hands of a clock

Problem explanation: Let’s suppose we have a clock that has an hour hand 3 units long, a minute hand 4 units long, and a second hand 5 units long. The hour hand moves once every hour, the minute hand ...
7
votes
2answers
1k views

Triangle area computation and linear transformations

I have a task to learn how to write clear and understandable documentation of written code in python. Please, can you give me a feedback to attached code below? I need to know if the code and comments ...
0
votes
1answer
67 views

Yaw (Z-rotation) angle linear interpolation without quaternions

I need to write a function performing linear interpolating between two Euler angles in 2D, perfectly without the use of quaternions as conversion seems to be an overkill for such a simple task. Here'...
9
votes
2answers
14k views

Point inside Polygon check

I have written a method to determine whether a Vector2 lies inside a polygon or outside of it. The polygon is defined by an array of clockwise vertices, p[]. It returns true if the point is inside, ...
12
votes
2answers
531 views

Compute the perimeter of a polygon

This is taken from HackerRank, which I hope is okay. I've been playing around with Haskell and I haven't really been able to find anything that really goes beyond toy examples in terms of how to ...
8
votes
1answer
394 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 ...
0
votes
1answer
306 views

Find triangle types

This challenge I am working on involves checking the sides of a triangle and returning the type of triangle as a symbol. For example, :equilateral if all sides ...
2
votes
0answers
98 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: ...
4
votes
0answers
437 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 ...
10
votes
3answers
384 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 ...
6
votes
2answers
467 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,...
6
votes
1answer
805 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 ...
5
votes
3answers
246 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 ...
3
votes
1answer
516 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: ...
7
votes
3answers
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: ...
1
vote
3answers
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? ...
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? ...
-1
votes
3answers
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? ...
3
votes
2answers
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 ...
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 ...
5
votes
1answer
575 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 ...
2
votes
2answers
412 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 ...
6
votes
1answer
816 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 ...
3
votes
2answers
579 views

Convex envelope algorithm of random set of points

This is my "naive" implementation of a convex hull algorithm. By naive I mean that I am not using any of the advanced algorithms that exist to solve this problem. ...
4
votes
1answer
147 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 ...
2
votes
2answers
315 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 ...
5
votes
2answers
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: ...
7
votes
1answer
887 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 ...
5
votes
1answer
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
1
vote
0answers
492 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. ...
8
votes
2answers
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 ...
2
votes
0answers
114 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 (...
9
votes
2answers
234 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: <...
5
votes
1answer
371 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 ...
2
votes
0answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
181 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 ...
9
votes
1answer
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. ...
10
votes
1answer
160 views

Determining position of point W.R.T to given line equation

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-...
9
votes
3answers
22k 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. ...
10
votes
2answers
328 views

Finding the nearest polygon

Finding the nearest polygon out of a list of polygons seems to be quite a challenge on performance, due to lack of optimization. Consider the following image: I'll give the concept behind this. The "...
2
votes
0answers
952 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 ...