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.

Filter by
Sorted by
Tagged with
10
votes
1answer
162 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
345 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
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 ...
7
votes
1answer
358 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 ...
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 ...
23
votes
2answers
2k views

Speed up solution to Project Euler problem 75

I wrote this code for Project Euler problem 75, which asks how many integers ≤ 1500000 exist, where the integer is a perimeter length that can be divided into three integer-length sides of a right ...
3
votes
1answer
1k 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 ...
2
votes
1answer
3k 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
1answer
71 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
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 ...
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: ...
13
votes
4answers
346 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 ...
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 ...
4
votes
1answer
142 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: ...
5
votes
1answer
926 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 ...
5
votes
2answers
104 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 ...
3
votes
1answer
776 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
73 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\\ ...
0
votes
2answers
1k 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
119 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 ...
10
votes
3answers
559 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'...
41
votes
1answer
2k views

Finding minimum scalar product using ST Monad

Inspired by a Stack Overflow question, I decided to practice my Haskell by taking a crack at the Google Code Jam's Minimum Scalar Product problem: Given two vectors \$\mathbf{v_1}=(x_1,x_2,\ldots,...
4
votes
1answer
304 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), (...
6
votes
2answers
583 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 ...
2
votes
2answers
237 views

Normal calculation for tile terrain geometry

It does generate pretty decent normals but I'm not sure if I could improve it even more without losing performance. You can find the whole code here: ropp_map.h gnd.cpp What do you think about this ...
5
votes
2answers
431 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 ...
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 ...
6
votes
1answer
1k 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
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
2answers
73 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
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 ...
2
votes
1answer
62 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
5k 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 ...
7
votes
1answer
618 views

Implementing a collection class to represent a Path of Segments

I'm trying to implement a custom made 2D geometry library. Originally I was looking at the problem of intersections of many circles but wanted to widen the scope of the code to deal with many future ...
3
votes
1answer
3k views

Algorithm for merging overlapping rectangles

The following code is part of an application I maintain that has a VT100/Xterm style graphical user interface that is implemented using text (Think Midnight Commander. Retro, I know.) Part of the ...
10
votes
1answer
537 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
1answer
645 views

3D vector CUDA kernel

I designed this CUDA kernel to compute a function on a 3D domain: p and Ap are 3D vectors that are actually implemented as a ...
2
votes
1answer
145 views

Moving circles along a ray to eliminate location check

I have a function that moves circles out of the way of an expanding circle. It moves them along a ray from the center of the expanding circle through the center of the circle to move. This allows all ...
5
votes
1answer
2k views

Quick Hull Algorithm implementation for higher dimensions

Last version of library (performance has been improved drastically since posting). I tried to implement the Quick Hull Algorithm for computing the convex hull of a finite set of D-dimensional points. ...
9
votes
1answer
8k 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): <...
8
votes
3answers
2k 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 ...
9
votes
1answer
754 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
422 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 ...
16
votes
2answers
3k views

Shamos-Hoey algorithm for checking the self-intersection of a closed shape

I implemented the Shamos-Hoey algorithm to check if a closed shape is self-intersected. Is this algorithm ok in terms of performance? ...
2
votes
1answer
826 views

Recursive algorithm to obtain grid points inside a n-cube volume or surface

I wrote two functions to return point coordinates spanning the n-dimensional hypercubic lattice of half size K (meaning that the coordinates along each axis go from -K,.. 0.. K). The n-dimensional ...
4
votes
3answers
592 views

Find the center of n squares which together build a rectangle

I have a rectangle with size w and height h. Now I want to split this rectangle into n new ...