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.

Filter by
Sorted by
Tagged with
7
votes
2answers
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 ...
7
votes
2answers
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 ...
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: ...
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 ...
3
votes
1answer
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. ...
8
votes
1answer
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 ...
3
votes
1answer
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 ...
6
votes
2answers
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 ...
11
votes
5answers
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 ...
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 (...
4
votes
1answer
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. ...
4
votes
1answer
331 views

Ray→plane and ray→quad intersection

This checks the intersection between a Ray and a Plane and between a Ray and a ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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? ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
4
votes
2answers
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: ...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
6
votes
2answers
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 ...
5
votes
3answers
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? ...
6
votes
1answer
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 ...
4
votes
2answers
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 ...
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 ...
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 ...
2
votes
2answers
3k 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
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: ...
6
votes
2answers
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 ...
7
votes
1answer
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 ...
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 ...
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 ...
10
votes
5answers
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) ...
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
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 ...
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. ...
4
votes
2answers
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. ...
7
votes
3answers
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 ...
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 ...
-1
votes
1answer
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. ...
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
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 ...
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 ...
4
votes
2answers
4k views
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 ...
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 ...
1
vote
1answer
63 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: <...