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
3
votes
0answers
172 views

Graphical editor with geometric intersection

If it is possible I would like some comments on the overall style of the program. It feels like I am writing the whole program as one big script and I'm not sure how to break it down into several ...
4
votes
1answer
322 views

Ray→plane and ray→quad intersection

This checks the intersection between a Ray and a Plane and between a Ray and a ...
2
votes
2answers
2k views

Haversine formula in SQL

This is an implementation of the Haversine formula in Microsoft Transact SQL. How can I simplify the function? ...
6
votes
2answers
265 views

Quaternion rotations and preparing matrices for a shader

I am implementing an OpenGL ES 2.0 renderer in c. I want to use quaternions for rotations. Please take a look at the way I am implementing the rotation math. Everything looks as expected when the ...
6
votes
1answer
98 views

'Tis the season for gift-wrapping

When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer: ...
7
votes
3answers
2k views

Checking for intersection points

The aim of the program is to find those points which comes under the intersection of at least 2 circles.(space is a 1000x1000 matrix) ...
8
votes
1answer
4k views

Jarvis's March Convex Hull

I'm more concerned about the coding best practices and how it's written here than the actual algorithm and math. I'm concerned about stack constraints, passing arguments,..etc. If there is anything ...
7
votes
3answers
7k views

Generate sample coordinates inside a Polygon

I have a Polygon named as poly. I attempted to randomly select 5 coordinate points that lies inside the polygon. ...
7
votes
1answer
366 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 ...
2
votes
0answers
1k 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) ...
4
votes
1answer
243 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 ...
12
votes
2answers
2k 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 bottom-...
17
votes
7answers
8k views

Custom mathematical vector class

My first bigger C++ project: a vector class for personal use and statistical computation. ...
-1
votes
1answer
475 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. ...
11
votes
7answers
20k 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
554 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
273 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 ...
7
votes
2answers
132 views

Isometric Projection and Culling

I'm working on a small isometric drawing system in JavaScript. After much help from the Gamedev section, reading old questions, I've got something working. However, it's still a little hacky. I need ...
14
votes
2answers
3k views

Detecting two intersecting 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 figuring out the formula for detecting whether or not the two ...
8
votes
1answer
1k 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 ...
10
votes
2answers
335 views

Finding the 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 "...
4
votes
1answer
4k 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: ...
12
votes
5answers
3k 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 ...
4
votes
2answers
4k views

Calculating if a point is within a polygon, or outside of it

Here is the function (along with its support functions): ...
7
votes
1answer
3k 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 result:...
15
votes
2answers
2k 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. ...
5
votes
1answer
2k views

Quick Hull Algorithm implementation for higher dimensions

Last version of library (performance has been improved drastically since posting). I tried to implement the Quick Hull Algorithm for computing the convex hull of a finite set of D-dimensional points. ...
4
votes
1answer
933 views

Point in a polygon algorithm

I am implementing a Point in polygon algorithm. Inputs: M, N: size of the matrix poly: a ...
8
votes
1answer
640 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
97 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 ...
7
votes
3answers
4k 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 0....
5
votes
2answers
7k 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 ...
7
votes
1answer
2k views

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 (...
5
votes
1answer
4k 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 ...
6
votes
3answers
15k views

Algorithm to get an arbitrary perpendicular vector

Is there a more efficient/direct way to find an arbitrary perpendicular vector of another vector? ...
13
votes
1answer
6k 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 ...
8
votes
2answers
1k 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
100 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
204 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
552 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
483 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
693 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 ...
9
votes
1answer
6k 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
219 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 ...
29
votes
3answers
38k 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 ...
8
votes
2answers
2k 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 ...
3
votes
1answer
3k views

Algorithm for merging overlapping rectangles

The following code is part of an application I maintain that has a VT100/Xterm style graphical user interface that is implemented using text (Think Midnight Commander. Retro, I know.) Part of the ...
5
votes
5answers
5k views

Ramer-Douglas-Peucker algorithm

Ramer-Douglas-Peucker is a great algorithm for reducing the number of samples in a given trace, and also for keeping its general shape (as much as he can). I have a trace with 32.000.000 samples, and ...
7
votes
3answers
516 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
822 views

Recursive algorithm to obtain grid points inside a n-cube volume or surface

I wrote two functions to return point coordinates spanning the n-dimensional hypercubic lattice of half size K (meaning that the coordinates along each axis go from -K,.. 0.. K). The n-dimensional ...