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
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 ...
3
votes
1answer
100 views

Zero crossings from a 1D signal

I'm trying to get the peaks/zero crossings from a basic 1D signal and am not sure if my naive/basic approach is correct: ...
7
votes
1answer
613 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 ...
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,...
3
votes
1answer
377 views

Ray reflection with a triangle

I'm trying to reflect a ray of a triangle using Processing and not sure I got the code right. I'm using two bits of pseudo code from two locations: Intersection of a Line with a Plane from Paul ...
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. ...
2
votes
2answers
236 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 ...
2
votes
2answers
127 views

Building 3d geometry from tile description

This code is a mess due the complex nature of the job, so I'd like to know your opinions. The concept is very simple if you know what this is about, but there are some things I'm not being able to ...
2
votes
1answer
2k views

Finding the pairs of intersecting discs

I have been following this question on SO, copied below. I put together a solution, but which is \$O(n^2)\$. In order to get a more efficient \$O(n \log n)\$ or \$O(\log n)\$ solution, I tried to ...
6
votes
1answer
284 views

Is this a good algorithm for 2D collision, or will it allocate too much memory?

I have a Rectangle class, of which I have 5-6 vectors for each instance. The main vectors are the center and color of the object, while the secondary vectors represent more or less the north, south, ...
2
votes
1answer
142 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 ...
6
votes
4answers
5k views

Mathematical Vector2 class implementation

This is my first attempt ever to build a Vector2 class. I scoured the net for anything that might make this class more efficient but know I'm to the point where I'...
3
votes
1answer
2k views

Koch Curve algorithm in Python without using Turtle/Logo logic

Inspired by the motivations expressed in this question. I created some code to generate the point list (and also display a pretty picture) using just analytic geometry (no Logo/Turtle, no ...
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. ...
3
votes
1answer
2k views

Small 3D and 4D vector utilities

I'm a hobby programmer and have started 2 month ago with C++. I had some knowledge of Python, and I learned it all through Internet tutorials. I'm looking for your help, since I don't have a tutor I ...
4
votes
3answers
588 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 ...
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? ...