Computer geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.
2
votes
2answers
101 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 ...
7
votes
1answer
61 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 ...
4
votes
1answer
57 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 ...
0
votes
0answers
45 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. ...
4
votes
2answers
87 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:
...
1
vote
0answers
42 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
69 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 ...
8
votes
2answers
148 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
20 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 (...
8
votes
2answers
86 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
88 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
15 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
65 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 ...
9
votes
1answer
466 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.
...
2
votes
0answers
82 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 ...
0
votes
0answers
49 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 ...
6
votes
1answer
287 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 ...
3
votes
1answer
169 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 ...
3
votes
1answer
877 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 ...
3
votes
0answers
92 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:
...
1
vote
1answer
81 views
1
vote
0answers
348 views
Graham scan from Algorithms in a Nutshell in Rust
Continuing the Algorithm in a Nutshell series, here is the code:
...
1
vote
0answers
62 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 ...
3
votes
1answer
114 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:
...
3
votes
1answer
60 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 ...
1
vote
0answers
56 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 ...
4
votes
1answer
191 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 ...
12
votes
4answers
214 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 ...
3
votes
1answer
82 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:
...
7
votes
2answers
66 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\\
...
5
votes
5answers
724 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 ...
0
votes
2answers
149 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 ...
7
votes
1answer
57 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 ...
1
vote
1answer
33 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 ...
5
votes
2answers
88 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 ...
10
votes
1answer
128 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-...
4
votes
1answer
89 views
Generating vertices of the rectified hypercube
The following piece of code generates the vertices of the rectified hypercube in arbitrary dimensions. The 3D case of the rectified hypercube is a cuboctahedron with 12 vertices (±1,±1,0), (±1,0,±1), (...
3
votes
1answer
85 views
Find the largest area polygon built from a given list of vertices
This is code that gets a list of polygon vertices, non-ordered, and finds the order in which they should be arranged in order to create the polygon with the largest area.
There are two key elements ...
10
votes
3answers
293 views
Check if 2 rectangles fit in another one, given their length and height
I was very intrigued with the manner to solve this problem. The program needs to know if 2 rectangles fit in another one, considering the lines of the 2 rectangles are always parallel to the other one'...
6
votes
2answers
121 views
Rectangle-segment collision detection
I am working with C++ and SDL, hoping to create a game later. I am implementing the collision detection between rectangles and segments.
I found this (NateS user's solution) about line-rectangle ...
5
votes
2answers
113 views
Grouping rectangles horizontally and vertically
As you can see the below code for each method is that same, except for the properties it uses. For example X vs Y and ...
5
votes
1answer
203 views
High performance triangle - axis aligned bounding box clipping
Implementation of a Robust (i.e. with a finite plane thickness) Sutherland–Hodgman algorithm for clipping polygons against an axis-aligned bounding box. I use the following code only for clipping ...
2
votes
0answers
84 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 ...
1
vote
0answers
97 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 ...
2
votes
2answers
46 views
Find the best path amongst N random points
For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points.
I wanted to use a dynamic ...
3
votes
0answers
141 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 ...
1
vote
1answer
41 views
Find cells crossed by a line
This method find cells that are crossed by line A-B and adds them to one vector.
I have got some duplicates here and some lines of code are very similiar but they differ in one variable. Should this ...
5
votes
1answer
711 views
Perimeter of a polygon given its vertices
I recently completed this code challenge so just looking for some feedback on my code. The task is to read polygon coordinates from a file and calculate the perimeter, I was provided with a script ...
3
votes
1answer
162 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.
...
10
votes
1answer
209 views
Template class for Andrew's Monotone Chain Algorithm Convex Hull
This is my first attempt at writing a template class. I am implementing Andrew's Monotone Chain algorithm, as described here to calculate a 2D Convex Hull. Since this is my first try at templates, I ...
