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
8
votes
1answer
478 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 ...
3
votes
2answers
186 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 ...
12
votes
1answer
5k 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 ...
3
votes
1answer
276 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 ...
4
votes
1answer
285 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. ...
3
votes
4answers
119 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 ...
0
votes
2answers
947 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 ...
1
vote
1answer
122 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 (...
0
votes
1answer
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 ...
6
votes
1answer
86 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: ...
2
votes
1answer
83 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 ...
11
votes
1answer
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 ...
23
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 ...
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 ...
0
votes
1answer
89 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'...
10
votes
2answers
16k 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, ...
12
votes
2answers
563 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 ...
8
votes
1answer
605 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 ...
0
votes
1answer
355 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 ...
2
votes
0answers
106 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: ...
4
votes
0answers
512 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 ...
10
votes
3answers
502 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 ...
6
votes
2answers
518 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,...
6
votes
1answer
1k 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 ...
5
votes
3answers
476 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 ...
3
votes
1answer
770 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: ...
7
votes
3answers
525 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: ...
1
vote
3answers
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? ...
3
votes
1answer
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? ...
-1
votes
3answers
769 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? ...
3
votes
2answers
96 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 ...
2
votes
0answers
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 ...
5
votes
1answer
767 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 ...
2
votes
2answers
504 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 ...
6
votes
1answer
982 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 ...
3
votes
2answers
589 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. ...
4
votes
1answer
201 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 ...
2
votes
2answers
361 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 ...
5
votes
2answers
9k 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: ...
7
votes
1answer
1k 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 ...
5
votes
1answer
2k 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 ...
1
vote
0answers
73 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 ...
4
votes
1answer
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 ...
1
vote
0answers
543 views

Compute the minimum distance between two points in a 2-D plane

I have tried to calculate the minimum distance between the two points in a 2D plane. I have used the divide and conquer strategy to attain the complexity of n logn. ...
8
votes
2answers
3k 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 ...
2
votes
0answers
126 views

Finding vtkCells in the vicinity of or coinciding with vtkPixels

I am looking to optimize this code. In its current state it is working, however, I am looking to improve it. To represent the situation. I have a vtkPixel (...
9
votes
2answers
278 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: <...
5
votes
1answer
405 views

Clustering points on a sphere

I have written a short Python program which does the following: loads a large data file (\$10^9+\$ rows) where each row is a point on a sphere. The code then loads a pre-determined triangular grid on ...
2
votes
0answers
50 views

Modeling a control polygon for a piecewise spline curve

Aim I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...