Computer geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.
3
votes
1answer
97 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 ...
2
votes
0answers
35 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:
...
0
votes
1answer
41 views
1
vote
0answers
332 views
Graham scan from Algorithms in a Nutshell in Rust
Continuing the Algorithm in a Nutshell series, here is the code:
...
1
vote
0answers
54 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
99 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
51 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 ...
0
votes
0answers
41 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
60 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
200 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
43 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
61 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
406 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
81 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
43 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
0answers
9 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
74 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 ...
6
votes
0answers
83 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 ...
4
votes
1answer
69 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
56 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
269 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
102 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
86 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
118 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
52 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
54 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
39 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
91 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
38 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
186 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 ...
10
votes
1answer
128 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 ...
8
votes
2answers
2k 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, ...
3
votes
2answers
98 views
Striped closed poly-line
I'm working on class Striped_polyline which represents a closed poly-line filled with equidistant horizontal lines1:
stripedpoly.cpp:
...
7
votes
3answers
362 views
Given a set of points and pairs of lines, count the number of points that are between the pairs of lines
This is a contest problem. The entire description is here.
In resume:
The question gives a point simulating a light explosion that always has a negative x coordinate, a set of pairs line segments on ...
8
votes
1answer
309 views
Count number of isosceles triangles in a set of points
Given a set of points, what is the number of isosceles triangles that can be formed with the combinations of all points in the set?
It is certain that 3 collinear points never exists in the set.
<...
4
votes
1answer
185 views
Project Euler 91 (via HackerRank): Right triangles with integer coordinates
This is my code to solve HackerRank's version of Project Euler Problem 91: on an N × N grid, find the number of possible right triangles where one vertex is (0, 0) and the other two vertices are ...
1
vote
3answers
1k views
0
votes
0answers
41 views
Scale geometry based on distance between 2 vertices - follow-up
Edit: Changes I made from previous script:
Reformatted lines of code to be more readable and correct for Python
Created individual functions for items that were previously crammed into singe ...
7
votes
2answers
204 views
Finding the maximum pairwise difference in a collection of colors
Note that this problem is equivalent to finding the longest line segment defined by any two points in a collection of 3D coordinates, which may be an easier way to visualize the problem, and is almost ...
6
votes
0answers
165 views
Graham scan implementation in Haskell
It looks like this is a really classical question, but I'd like to ask it one more time as all those solutions look quite long and complicated for me (maybe because I am dumb :) )
So this is a Graham ...
8
votes
1answer
546 views
Drawing circles with triangles
As pyglet has no in-built method to return a vertex list of circle, I had to build one myself. This is a critical piece of code that I will use very frequently. I need it to be of very fine ...
3
votes
1answer
72 views
Remove “lines” from a 2D vec
I have some code here that I am very unhappy with. The task I am trying to accomplish is this.
Given a 2d vec like this:
[[0 2 0] [1 3 5] [3 3 0]]
which can ...
6
votes
2answers
820 views
Python Trig Calculator
It's big, it's ugly, but it should work. My question is: how could I have implemented the "typeselection" function so it is less repetitive? Any tips on other improvements in coding style are welcomed ...
0
votes
2answers
448 views
11
votes
5answers
318 views
Segment Intersection — Failing on Unknown Edge Cases
I was recently at a programming competition. One of the problems was to determine whether two line segments are parallel, intersect, or do not intersect.
For all of the test cases I ran, my solution ...
4
votes
1answer
297 views
Implementing Mitchell's best candidate algorithm
I have written an implementation of Mitchell's best candidate algorithm. Mitchell’s best-candidate algorithm generates a new random sample by creating k candidate samples and picking the best of k. ...
7
votes
1answer
2k views
Line segment to circle collision algorithm
I've written a function (in Python 3) which computes if a line segment (constraint) and a circle (body) collide, and returns the point of intersection (closest point to the centre of the circle):
<...
2
votes
2answers
159 views
Find non duplicate Triangle Triplets from a list of given numbers- version 3
It is a continuation of my previous question:
Find non duplicateTriangle Triplets from a list of given numbers
After I realized triplet structure using less space than ...
4
votes
1answer
87 views
Distance between angles as points
This code calculates the distance between angles, particularly for n-tuples of angles. One example where this situation occurs is as follows:
I'm using a 2 arms, one 6 degree of freedom and the other ...
2
votes
1answer
110 views
Find non duplicateTriangle Triplets from a list of given numbers
I implemented an O(N^2) algorithmic solution but not sure it is better than my previous implementation Find Triangle Triplets from a list of given numbers
in case of performance. I adapted almost ...
