# 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.

229 questions
Filter by
Sorted by
Tagged with
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 ...
112 views

### Curvature data to coordinates

I want to determine a path (x and y coordinates) by using curvature data (radius, with constant distance (length_of_arc) travelled between data points. I want to ...
41k 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 ...
2k views

### Given a list of coordinates check if 4 points make a line

I was doing some preparation for coding interviews and I came across the following question: Given a list of coordinates "x y" return True if there exists a line ...
66 views

### Checking where/if another creature lies in a creature's field of view

Note: this is a more specific form of this I am working on a simulation of some virtual creatures. They all have vision that lets them see other creatures. To do this, I calculate the difference ...
294 views

### Finding the closest pair of points divide-and-conquer speed improvement

This is a follow up to a previously asked Finding the closest pair of points divide-and-conquer question . The original code changed significantly based on answers from @AJNeufeld therefore I created ...
5k views

### Finding the closest pair of points divide-and-conquer

Here is my code for the famous "finding the closest pair of points" problem from CLRS book section 33.4 using a divide-and-conquer approach (this code returns the minimum distance between pair of ...
489 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 ...
247 views

### Math matrix, mainly for graphics

I wrote a matrix library to replace my old matrix library. I was using my old matrix library to do basic operations for 3D rendering but that library grew old and now I'm seeking to replace it. I'm ...
7k 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 ...
344 views

### Draw common tangents to two circles interactively in MATLAB

Requirement After a user draws two circles with their mouse successively, the program should draw all common tangents, if any, to them. Here is my implementation ...
585 views

### Shortest distance from point to line segment in 3D

This function returns the shortest distance from a 3D point P to a line segment defined by two 3D points A and B. It projects P onto the line, then checks if this projected point lies between A and B. ...
123 views

### Solving for <45 degree angles of a multi-vector system

I'm working on a problem from codechef.com. The goals are: Solve for whether or not the driver took a "sharp turn", meaning for some angle θ, θ > 45°. Test each point $(x_i, y_i)$ in the system ...
1k views

### Given points on a 2D plane, find line that passes through the most points

Could someone give some feedbacks from perspective of oo design and coding style on the following codes: Question: Given n points on a 2D plane, find the Line with maximum number of points that lie ...
126 views

### Finding angle and direction between line segments

I'm putting together a short demo on two things: Finding the angle between two line segments and direction (right or left) as you travel counterclockwise around a shape Using newer ecmascript syntax (...
50 views

### Calculating minimum size of rectangle that contains two smaller ones [closed]

My Rectangle class contains one vertex (x,y), its width a, and its height b; the opposite ...
103 views

### Catmull-Rom Interpolator: Template pandemonium avoidance

I have a pull request implementing Catmull-Rom interpolation. I have gotten it pretty fast-to ~25 ns/call-but I feel the design is not enlightened. The code is here, and reproduced below: ...
86 views

### Segment road map data with heuristics

Backstory A little while ago I was assigned with the task of clustering some road segments using open street map data. After parsing a huge XML (maybe that should be another review) I ended up with ...
4k 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 repo)...
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 ...
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 ...
127 views

### Yaw (Z-rotation) angle linear interpolation without quaternions

I need to write a function performing linear interpolating between two Euler angles in 2D, perfectly without the use of quaternions as conversion seems to be an overkill for such a simple task. Here'...
17k 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, ...
606 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 ...
858 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 ...
376 views

### Find triangle types

This challenge I am working on involves checking the sides of a triangle and returning the type of triangle as a symbol. For example, :equilateral if all sides ...
107 views

### Affine transformations in 2D space

During the past few days, I played around a bit with an SVG file, trying to minimize its size. One thing I stumbled upon was this transformation: ...
584 views

### Find the closest parametric values corresponding to a BSpline's control points

On a curve generated by scipy.interpolate.BSpline I want to find the closest parameters relative to each control point, so that the given parametric range is ...
934 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 to ...
570 views

### Java algorithm to declutter rectangles

I've been working on an algorithm to declutter rectangles while keeping them as close as possible to their original location (and oriented the same way). It seems to work fine when I have less than 1,...
2k views

### Solver for some simple tangrams

I decided to write a program to solve Tangram puzzles. This went a bit out of hand and I ended up with 600+ lines of code. I don't think it should have taken so much code. Here is an image of a ...
986 views

### Compute shortest distance between point and a rectangle

I want to compute the shortest distance between a position (x,y) and a rectangular box defined by (x_min, y_min) and (x_max, y_max). See the picture below with some examples. I know that in two ...
954 views

### Java - fill triangle function

I am starting to work on a basic 3D renderer for fun, so right now I have made a triangle fill function to be used when I draw faces on models: ...
527 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: ...
1k views

### Two circles intersect

Do two circles in a 2D plane disjoint? $$(r_1 + r_2) \cdot (r_1 + r_2) \gt \Delta{X} \cdot \Delta{X} + \Delta{Y} \cdot \Delta{Y}$$ Any comments / corrections on this code? ...
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? ...
772 views

### Distance too close

Are two points too close? Trying to do the math as efficiently as possible. deltaX + deltaY is going to be > than the actual distance You might use this in game play - are players in range? ...
100 views

### Cythonized Sutherland-Hogman algorithm

I want to cythonise the python implementation of the Sutherland-Hogman algorithm. This algorithm updates a list of vertices according to pretty simple rules (being inside or outside an edge, etc.) but ...
35 views

### Identifying local peaks among some 2D points

The following MATLAB code takes in multiple peak coordinates and heights and eliminates lesser peaks that are within a certain distance threshold of the highest peak of the vicinity. Is there a better ...
899 views

### Shortest path around a set of points

Problem I'm trying to get into Python and get a bit familiar with it, so I found a problem online to train. The problem was to find the shortest path around some points, given a set of nodes which ...
627 views

### Calculating the perimeter of certain points in a 2D array

I had to write code for a competition which calculates sum of the perimeter of two non-overlapping rectangles in a 2D space. My code is working fine and resulting in expected outputs. But it is taking ...
1k views

### Calculate angle between planes

I have written working code calculating the angle between the adjacent planes. I read subsequently from standart input: n - amount of triangles, m - amount of vertices ind[] - indices of the vertices ...
605 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. ...
286 views

### Removing undesired points from a mesh

I have a 3D data set made of a certain number of points (x,y,z) that cover a certain region of space. Using the scatteredInterpolant object I can interpolate this ...
382 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 ...
11k 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: ...
2k 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 ...
3k 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 ...
74 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 ...
3k 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 ...