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
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 ...
2
votes
1answer
748 views

Creating shapes program with multiple classes (different files)

I just started to learn Objective C with Programming in Objective C by Stephen G. Kochanand and I would love to get your feedback to see if I'm getting OOP concept with Objective-C right. ...
1
vote
1answer
62 views

Optimizing mathematical index calculation function

I have made a function which calculates the index of a point to which an arbitrary point on a polygon made of XY points belong. This is a visual representation: And this is the function I made: <...
10
votes
5answers
757 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) ...
5
votes
3answers
3k views

Calculating the area of various 2D shapes

I've made a simple program that can calculate the area of various 2D shapes. I'd like your expereanced eyes to asses my code. Be as harsh as you want but please be specific and offer me ways in which ...
4
votes
1answer
201 views

First Common Lisp vector math code

I'm studying Common Lisp on my own. Coming from C++, Common Lisp feels kind of strange sometimes. I'd like to get some feedback on what I understood so far. For learning purposes, I wrote this simple ...
10
votes
2answers
347 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 ...
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
102 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
617 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
383 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
237 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
128 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
288 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
144 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
6k 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
403 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
591 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? ...