Computer geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.
14
votes
3answers
2k 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 ...
14
votes
2answers
2k views
Is this implementation of Shamos-Hoey Algorithm OK?
I implemented Shamos-Hoey algorithm to check if a closed shape is self-intersected. Is this algorithm ok in terms of performance?
EDIT 2013-09-22
I updated the algorithm code - now it correctly ...
13
votes
2answers
655 views
Speed up solution to Project Euler problem 75
I've been programming for a few months now, and have used Stack Overflow a great deal, but this is my first post. Anyway, I wrote this code for Project Euler problem 75, which asks how many integers ≤ ...
13
votes
2answers
196 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. ...
11
votes
5answers
370 views
Checking if a list of coordinates defines a closed, exact rectangle
I have to check if a list of coordinates define 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 answer is:
...
10
votes
2answers
315 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
171 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. ...
8
votes
1answer
79 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 ...
7
votes
1answer
534 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 ...
7
votes
2answers
161 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, ...
7
votes
2answers
102 views
Performance Issues: Finding 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 ...
7
votes
1answer
492 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 ...
6
votes
2answers
320 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 ...
6
votes
1answer
259 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 ...
6
votes
1answer
209 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, ...
6
votes
1answer
244 views
Trying to implement a collection class to represent a Path of Segments
I've posted a few times over on stack.overflow recently and have been advised to try here to sort out a good code implementation once and for all.
I'm trying to implement a custom made 2D geometry ...
5
votes
3answers
436 views
Missed lab, wondering how this bit of Java code could be improved anyway?
I'm not able to get feedback on this because I forgot about the lab due date, but I'd appreciate some critique anyway. It takes in a user specified number of points then finds the two points with the ...
5
votes
2answers
116 views
Class Vector with Python 3
Here is a class vector in python 3, for n-dimmensional vectors. Please suggest ways to improve the code as well as fix bugs and errors.
The only rule is not using: numpy, sympy, scipy and so on. Only ...
5
votes
1answer
171 views
Complex logic that I'm certain can be simplified
This is code from a grappling hook implementation. This is specifically code that, after a block is detected between two way points, it tries to find a path around.
This particular piece of the ...
5
votes
1answer
62 views
Calculating “element-wise” the angles between two lists of vectors
Let's say you have two lists of vectors:
v1s = [a, b, c]
v2s = [d, e, f]
I am interested in generating the following ...
4
votes
4answers
222 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 ...
4
votes
2answers
122 views
Python implementation of the Ramer-Douglas-Peucker Algorithm
I recently implemented the RDP polygon approximation algorithm in Python and I'm skeptical of whether or not I implemented it correctly of with the greatest efficiency. The algorithm runs in around ...
4
votes
1answer
79 views
Optimize vector rotation
I have a trivial function that rotates 2d vectors, and a method in a class representing a polygon that rotates every point in the polygon around an origin. The code is fairly optimized as it is, but I ...
4
votes
1answer
88 views
Centroid of a polygon in Clojure
I am studying Clojure and functional programming. I wrote this function to compute the centroid of a polygon specified as a vector of points, e.g. ...
4
votes
1answer
100 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 ...
4
votes
0answers
87 views
Ways of speeding up this python implementation of SAT (Separating axis theorem)
A project I was working on required the usage of the Separating Axis Theorem to detect collisions between two convex polygons in real time. So I implemented a basic class (...
3
votes
4answers
188 views
Refactor code to find four co-linear points
I am relatively new to Java, but have been reading up on how to improve the quality of my code.
I am writing a system where I take in a series of points from a file with x and y co-ordinates and by ...
3
votes
3answers
321 views
Algorithm to get an arbitrary perpendicular vector
Is there a more efficient/direct way to find an arbitrary perpendicular vector of another vector?
...
3
votes
1answer
870 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 ...
3
votes
1answer
74 views
Point in a polygon algorithm
I am implementing a Point in polygon algorithm.
Inputs:
M, N: size of the matrix
poly: a ...
3
votes
1answer
56 views
Quick Hull Algorithm implementation for higher dimensions
I tried to implement the Quick Hull Algorithm for computing the convex hull of a finite set of D-dimensional points. Here is the repository. Algorithm itself:
...
3
votes
1answer
182 views
Am I doing this ray reflection correctly?
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 ...
3
votes
1answer
59 views
Calculating if a point is within a polygon, or outside of it
Here is the function (along with its support functions):
...
2
votes
2answers
114 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
2answers
82 views
Move Line across Plane
I want move a Vertical line segment across a plane or another way sweep the plane, from Left to right.
The figure illustrates how the segment is moving at the X-axis. When x1 >= X beginning and i ...
2
votes
1answer
188 views
recursive algorithm to obtain grid points inside a n-cube volume or surface
I did wrote in python two functions to return points in the n-dimensional cube of half size K (meaning that the coordinates along each axis go from -K,.. 0.. K). The n-dimensional cube volume should ...
2
votes
1answer
55 views
Calculating the distance between one point, and many others
In my program, I have entities that I call "blobs", because they have a blobby shape. Blobs are polygons. If I have two blobs, then their information array would look like:
...
2
votes
1answer
38 views
How to reduce execution time for this clustering computation?
Is there any way to reduce total execution time for the function getSilhouetteIndex? P.S. I am using weka SimpleKMeans for ...
2
votes
1answer
270 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
2answers
160 views
Normal calculation for tile terrain geometry
What do you think about this one? Other than declaring an Epsilon constant, of couse.
It does generate pretty decent normals but I'm not sure if I could improve it even more without losing ...
1
vote
1answer
44 views
Find triangles from line
I have some lines that form triangles. I'd like to challenge the fastest way to find all triangles.
In particular the code should take an ArrayList of Line2D object and return an ArrayList of ...
1
vote
1answer
56 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:
...
1
vote
1answer
167 views
A sophisticated algorithm for geometric computation (distance between points) [closed]
I am confused by an algorithm for counting the number of pairs of N random points which has a distance closer than d = sqrt((p1.x-p2.x)^2 + (p1.y-p2.y)^2)
The ...
0
votes
1answer
92 views
Computing tangent space basis vectors for an arbitrary mesh
This is more like a share and a request than a question. I converted Eric Lengyel's code, which calculates tangents of a mesh for the purpose of texturing and normal mapping, to support SIMD. For this ...
-1
votes
1answer
83 views
Error caused by c++ iterator in 2D Point structure [closed]
I've written a structure of 2D Point. But it doesn't compile due to some errors caused by iterator. I can't figure it out.
Here is my code:
...
