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
40
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,...
28
votes
3answers
37k views

Overlapping rectangles

I received the following question in a technical interview today (for a devops/SRE position): Write a function which returns true if the two rectangles passed to it as arguments would overlap if ...
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 ...
22
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 ...
17
votes
7answers
8k views

Custom mathematical vector class

My first bigger C++ project: a vector class for personal use and statistical computation. ...
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? ...
15
votes
2answers
2k views

Intersection over Union for rotated rectangles

Problem Statement I am trying to find the intersection over union (IoU) metric for one to several rotated rectangles compared to many different rotated rectangles. Here are some images to help ...
15
votes
2answers
2k views

Calculate the intersection between two intervals on the same circle

I want to calculate the ratio of intersection between two intervals; the length of the intersection divided by the length of the shorter interval. If two intervals do not intersect, the ratio is 0. ...
14
votes
2answers
3k views

Detecting two intersecting circles with editable x, y, and radius in JavaFX

I was actually pretty proud of this programming project that I came across in this book I'm working through. I only really had problems figuring out the formula for detecting whether or not the two ...
13
votes
4answers
331 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 ...
13
votes
1answer
5k views

Faster computation of barycentric coordinates for many points

I'm just starting to understand the Python syntax and I created a module that does what I wanted, but really slow. Here are the stats of cProfile, top 10 ordered by ...
13
votes
2answers
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. ...
13
votes
1answer
392 views

Is this a BSP tree? Am I missing something?

I've been practicing using BSP trees as I hear they are a good start to create procedural spaces such as houses. For ease-of-deployment purposes, I've tested this code in Lua and it seems to work. ...
12
votes
5answers
3k views

Checking if a list of coordinates defines a closed, exact rectangle

I have to determine if an N sized list of coordinates defines a closed, exact rectangle. I start with the question "How do I check if a list of coordinates is in the shape of a rectangle?" The ...
12
votes
2answers
2k views

CodeEval's SkyScrapers challenge

This is a solution to CodeEval's SkyScrapers challenge. You are given a list of triples \$(l, h, r)\$. Each triple represents an axis-aligned rectangle, with top-left corner at \$(l, h)\$ and bottom-...
12
votes
2answers
526 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 ...
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 ...
11
votes
7answers
19k views

C++ 3D Vector Implementation

I have been learning C++ now for 2 months and this week I started reading a book on 3D graphics. I like coding whatever mathematical stuff I learn so I can understand it better, so when I learnt about ...
11
votes
5answers
805 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 ...
11
votes
1answer
3k views

Farthest point algorithm in Python

I am learning Python and I tried to do a program to find K points from a set of N points, farthest as much as possible (I'm not ...
10
votes
3answers
539 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'...
10
votes
3answers
362 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 ...
10
votes
2answers
344 views

Artifact collision in plane module

Here's something I tried putting together as I'm learning. Critiques on anything are welcome. There's also a logic bug in the Plane module I can't identify. The long and the short are that it takes ...
10
votes
1answer
513 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 ...
10
votes
5answers
748 views

Calculating angles and distances

I am running a simulation with 250 interacting agents and have a few functions that are called over and over again. Even with precomputing all distances between agents before the N2 (250x250) ...
10
votes
2answers
301 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 "...
10
votes
1answer
159 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. ...
9
votes
2answers
13k 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, ...
9
votes
5answers
22k 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 ...
9
votes
1answer
6k views

Best way to work out angle between points?

I have the following JavaScript code to work out the angle between two points (clockwise). The code I have seems a bit "hacky" to me, as I have a while loop ensuring the number is not negative (to ...
9
votes
1answer
7k 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): <...
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. ...
9
votes
2answers
140 views

Where is the most desolate place in Colorado?

The Story While flying a plane over the forests of Wisconsin a couple years ago, I thought to myself "If I lost an engine, I would be awfully long way from an emergency landing airport. I wonder ...
9
votes
2answers
228 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: <...
9
votes
1answer
718 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. <...
8
votes
3answers
1k 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
2answers
2k views

Graham Scan convex hull algorithm

I'm beginning to learn Haskell. I've implemented the Graham Scan algorithm for detection of convex hull following the Real World Haskell book. I'm looking for general advice regarding the style and ...
8
votes
1answer
4k views

Jarvis's March Convex Hull

I'm more concerned about the coding best practices and how it's written here than the actual algorithm and math. I'm concerned about stack constraints, passing arguments,..etc. If there is anything ...
8
votes
2answers
1k views

Calculating angle in isometric view

I have an angle where I need to convert a 'normal' angle to an isometric angle (116 degrees), and I came up with this function. It works, but I was wondering if the math could be optimized/simplified, ...
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 ...
8
votes
1answer
1k views

Finding largest subset of line segments that don't intersect

I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here. In summary, the challenge is to take a list of line segments, each specified by ...
8
votes
1answer
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 ...
8
votes
1answer
428 views

Lagrange Interpolation over quadrilateral points

I've been working on a program which calculates, given a point and 4 surrounding points, the Lagrange polynomial, in order to interpolate a value. Consider that I'm not a mathematician and I better ...
8
votes
1answer
629 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 ...
8
votes
1answer
359 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 ...
8
votes
1answer
1k views

C# code to derive tangential points between two circles to create a trapezoid

These are the steps to determine coordinates of the 4 points (P1, P2, P3, P4) that make up a tangential trapezoid connecting to circles. Another way of looking at it is to think of the tangential ...
7
votes
3answers
1k views

Program to see how many points lie strictly inside a convex polygon

The program takes in a set of coordinates that defines the polygon. It then takes in a set of points. The idea is to find out how many of these points lie strictly inside the convex polygon (not on ...
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 ...
7
votes
3answers
513 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: ...