The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

224 questions
Filter by
Sorted by
Tagged with
23k 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 ...
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 ...
117 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 ...
186 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 ...
103 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 ...
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-...
302 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), (...
946 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 ...
552 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'...
569 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 ...
421 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 ...
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 ...
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 ...
393 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 ...
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 ...
807 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 ...
61 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 ...
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 ...
582 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. ...
533 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 ...
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, ...
702 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: ...
4k views

Calculate the area of rectangles union

I've been given the following task: Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. ...
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 ...
749 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. <...
419 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 ...
7k views

Checking if the point is on the line segment [closed]

Previously, I wrote the following code: ...
552 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 ...
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 ...
2k 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 ...
83 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 ...
4k 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 ...
5k views

...
846 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 ...
697 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. ...
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): <...
239 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 ...
124 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 ...
138 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 ...
425 views

Find Triangle Triplets from a list of given numbers

If a triplet of segments A, B and C are triangle triplets if and only if A + B > C A + C > B B + C > A Is there a better implementation for this problem? ...
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? ...
150 views

Lazy properties for the angle and length of a line segment

The code below shows the pattern I use to manage properties in my classes when I have the following requirements: Some properties are slow to calculate and are rarely used, so I want them to be lazy ...
453 views

Scale object based on distance between 2 vertices

I made this script so that I can scale objects for 3D printing from Maya. I had fun making it and I'm sure it could be cleaned up or improved. If it can be cleaned up please let me know. ...
219 views

Comparing triangles using Java 8 streams

I'm trying to get more familiar with Java 8 streams as they seem to be very powerful (and shorter), so I rewrote a method to use streams. However I'm not very satisfied with it and would like some ...
899 views

Speeding up 2D shadow algorithm

I wrote a class to represent a set of lights in a 2D game that raycast in order to find shadows. The draw method does a lot of calculations and takes a lot of time. Mainly, the adding of areas and ...
219 views

Implementation of Graham Scan algorithm in Haskell

Here is an implementation of Graham Scan algorithm for computing the convex hull of a finite set of points: ...
285 views

Line passing the most number of points

Given points on a two dimensional graph, find a line that passes the most number of points. Any comments please? ...
198 views

Use of static factory methods for vectors and matrices library

I've been working on a Java-based mathematics library focusing on vectors and matrices. I plan to use it for an important upcoming project, so the classes are analogous to data types available in GLSL ...