Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# 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.

224 questions
Filter by
Sorted by
Tagged with
134 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 ...
553 views

### Finding the maximum pairwise difference in a collection of colors

Note that this problem is equivalent to finding the longest line segment defined by any two points in a collection of 3D coordinates, which may be an easier way to visualize the problem, and is almost ...
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: ...
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 ...
455 views

### Scale object based on distance between 2 vertices

I made this script so that I can scale objects for 3D printing from Maya. I had fun making it and I'm sure it could be cleaned up or improved. If it can be cleaned up please let me know. ...
2k views

### Drawing circles with triangles

As pyglet has no in-built method to return a vertex list of circle, I had to build one myself. This is a critical piece of code that I will use very frequently. I need it to be of very fine ...
84 views

### Remove “lines” from a 2D vec

I have some code here that I am very unhappy with. The task I am trying to accomplish is this. Given a 2d vec like this: [[0 2 0] [1 3 5] [3 3 0]] which can ...
4k views

### Python Trig Calculator

It's big, it's ugly, but it should work. My question is: how could I have implemented the "typeselection" function so it is less repetitive? Any tips on other improvements in coding style are welcomed ...
856 views

### Segment Intersection — Failing on Unknown Edge Cases

I was recently at a programming competition. One of the problems was to determine whether two line segments are parallel, intersect, or do not intersect. For all of the test cases I ran, my solution ...
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 (...
702 views

### Implementing Mitchell's best candidate algorithm

I have written an implementation of Mitchell's best candidate algorithm. Mitchell’s best-candidate algorithm generates a new random sample by creating k candidate samples and picking the best of k. ...
331 views

This checks the intersection between a Ray and a Plane and between a Ray and a ...
482 views

### Tested cartesian plane utility

I am starting to explore automated testing of code, so I decided to write some trivial code about the cartesian plane and test it. I am particularly interested in automated testing conventions and ...
125 views

### Distance between angles as points

This code calculates the distance between angles, particularly for n-tuples of angles. One example where this situation occurs is as follows: I'm using a 2 arms, one 6 degree of freedom and the other ...
428 views

### Find Triangle Triplets from a list of given numbers

If a triplet of segments A, B and C are triangle triplets if and only if A + B > C A + C > B B + C > A Is there a better implementation for this problem? ...
243 views

### Find non duplicate Triangle Triplets from a list of given numbers- version 3

It is a continuation of my previous question: Find non duplicateTriangle Triplets from a list of given numbers After I realized triplet structure using less space than ...
138 views

### Find non duplicateTriangle Triplets from a list of given numbers

I implemented an O(N^2) algorithmic solution but not sure it is better than my previous implementation Find Triangle Triplets from a list of given numbers in case of performance. I adapted almost ...
219 views

### Implementation of Graham Scan algorithm in Haskell

Here is an implementation of Graham Scan algorithm for computing the convex hull of a finite set of points: ...
150 views

### Lazy properties for the angle and length of a line segment

The code below shows the pattern I use to manage properties in my classes when I have the following requirements: Some properties are slow to calculate and are rarely used, so I want them to be lazy ...
219 views

### Comparing triangles using Java 8 streams

I'm trying to get more familiar with Java 8 streams as they seem to be very powerful (and shorter), so I rewrote a method to use streams. However I'm not very satisfied with it and would like some ...
904 views

### Speeding up 2D shadow algorithm

I wrote a class to represent a set of lights in a 2D game that raycast in order to find shadows. The draw method does a lot of calculations and takes a lot of time. Mainly, the adding of areas and ...
285 views

### Line passing the most number of points

Given points on a two dimensional graph, find a line that passes the most number of points. Any comments please? ...
199 views

### Use of static factory methods for vectors and matrices library

I've been working on a Java-based mathematics library focusing on vectors and matrices. I plan to use it for an important upcoming project, so the classes are analogous to data types available in GLSL ...
1k views

### Cubic “bezier” curve of grade n

This is code I wrote for calculating bezier curves as quickly and RAM efficiently as possible. I would like to know if there are faster ways to optimize anything, because I am very new to C++ and ...
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 ...
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 ...
3k views

### Haversine formula in SQL

This is an implementation of the Haversine formula in Microsoft Transact SQL. How can I simplify the function? ...
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: ...
268 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 ...
369 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 ...
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) ...
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 ...
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 ...
765 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) ...
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) ...
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 ...
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 ...
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-...
8k views

### Custom mathematical vector class

My first bigger C++ project: a vector class for personal use and statistical computation. ...
206 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. ...
517 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 ...
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 ...
476 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. ...
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 ...
274 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 ...
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 ...
4k views

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

Here is the function (along with its support functions): ...
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 ...