Computer geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.
2
votes
0answers
17 views
2D Convex hull exercise
I'm reading Real World Haskell, and this is my first try with the language.
This is the result of the exercises of chapter 3:
Consider three two-dimensional points a, b, and c. If we look at ...
1
vote
0answers
38 views
Optimize QuadTree to find K Nearest Neighbors
I'm looking a way to make my k nearest neighbors search more efficient. The context of the question is that I'm given a list of topics that have a unique ID (integer) and a (x,y) coordinate (floats) ...
3
votes
1answer
48 views
Calculating the distance squared between all vertex-pairs of a number of 2D polygons
I have implemented my code using Cython. It is the current bottleneck in my computations.
There are two non-numpy functions involved:
calculate_2D_dist_squared ...
11
votes
2answers
169 views
CodeEval's SkyScrapers challenge
This is a solution to CodeEval's SkyScrapers challenge.
You are given a list of triples \$(l, h, r)\$. Each triple represents an axis-aligned rectangle, with top-left corner at \$(l, h)\$ and ...
13
votes
7answers
530 views
Custom mathematical vector class
My first bigger C++ project: a vector class for personal use and statistical computation.
...
-1
votes
1answer
85 views
Custom 2D/3D Graphics Vector Classes vs SFML's
I don't really like SFML's Vector Classes so I tried making my own. Any criticism is welcome.
...
8
votes
6answers
991 views
C++ 3D Vector Implementation
I have been learning C++ now for 2 months and this week I started reading a book on 3D graphics. I like coding whatever mathematical stuff I learn so I can understand it better, so when I learnt about ...
6
votes
1answer
75 views
3D matrix rotation in homogeneous coordinate space
Assuming that the framework is in place to handle the difference between row and column major matrices, I am curious to know if in a header based library such implementation is semantically and ...
2
votes
1answer
81 views
Neighbours from point connections
I am working with a mesh of triangles (in 3D, although I doubt it makes a difference). The mesh is given as list of lists, each list containing the indices of the three vertices of a triangle in said ...
13
votes
2answers
161 views
Detecting Two Intercepting Circles with editable x, y, and radius in JavaFX
I was actually pretty proud of this programming project that I came across in this book I'm working through. I only really had problems on figuring out the formula for detecting whether the two ...
8
votes
1answer
108 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
2answers
128 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 ...
3
votes
1answer
150 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:
...
11
votes
5answers
435 views
Checking if a list of coordinates defines a closed, exact rectangle
I have to determine if an N sized list of coordinates defines 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 ...
3
votes
2answers
145 views
Calculating if a point is within a polygon, or outside of it
Here is the function (along with its support functions):
...
5
votes
1answer
166 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 ...
13
votes
2answers
452 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. ...
4
votes
1answer
327 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
110 views
Point in a polygon algorithm
I am implementing a Point in polygon algorithm.
Inputs:
M, N: size of the matrix
poly: a ...
5
votes
0answers
101 views
3D vector CUDA kernel
I designed this CUDA kernel to compute a function on a 3D domain:
p and Ap are 3D vectors that are actually implemented as a ...
1
vote
1answer
55 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 ...
5
votes
2answers
424 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 ...
5
votes
2answers
349 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 ...
4
votes
0answers
136 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 (...
4
votes
1answer
203 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 ...
3
votes
3answers
664 views
Algorithm to get an arbitrary perpendicular vector
Is there a more efficient/direct way to find an arbitrary perpendicular vector of another vector?
...
9
votes
1answer
518 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 ...
7
votes
2answers
206 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, ...
2
votes
1answer
45 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 ...
4
votes
2answers
114 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. ...
0
votes
1answer
163 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 ...
3
votes
4answers
217 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 ...
2
votes
2answers
119 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 ...
8
votes
1answer
1k 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 ...
5
votes
1answer
183 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 ...
14
votes
3answers
4k 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 ...
7
votes
2answers
400 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 ...
7
votes
3answers
315 views
Optimizing a loop in C for a microcontroller
I am trying to draw a Checkerboard pattern on a LCD using a GUI library called emWin. I have actually managed to draw it using the following code. But having this many loops in the program body for a ...
2
votes
1answer
235 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 ...
14
votes
2answers
754 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 ≤ ...
2
votes
1answer
353 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
58 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:
...
8
votes
5answers
322 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) ...
3
votes
3answers
272 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
111 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
320 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 ...
7
votes
1answer
590 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
1answer
294 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 ...
3
votes
1answer
212 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 ...
7
votes
3answers
667 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.
...
