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.
243
questions
1
vote
2
answers
72
views
2D Point subclass of complex builtin
I'm writing a pure-python geometry tool for technical drawings / computational geometry (not a solver, as a solver has to work with constraints). I've already mentioned a previous version on code ...
- 135
1
vote
0
answers
69
views
Performant 2D Grid Cluster Finder Algorithm
I would like to vastly improve the speed of the second part of this algorithm to find clusters of points on a 2D grid.
Each point is represented by a Region on the ...
1
vote
0
answers
123
views
Algorithm to draw a patterned line by traversing the path through points
So I was in need of a way to draw a patterned line that passes through several points on a 2D space, something that no Python library seems able to do out of the box (at least, the ones I've been ...
- 277
4
votes
1
answer
183
views
Find largest number of collinear points
The following is my submission for LeetCode's Max Points on a Line:
Given an array of points where points[i] = [xi, yi] represents a point
on the X-Y plane, return the maximum number of points that ...
- 141
1
vote
1
answer
154
views
Function to find the closest points between two line segements
The following function is supposed to return the points p1 on line segment a, and p2 line segment b, such that |p1 - p2| is minimized.
...
- 143
1
vote
1
answer
304
views
Create normals from triangulated surface
Objective
I have a 3D face mesh triangulated. I have computed the midpoint of each triangle in the mesh, and I have the normal vector (n1, n2,n3) for each triangle. The objective is to create a 2D ...
- 111
1
vote
2
answers
553
views
Union Polygon Algorithm
This is my attempt at creating a Union Algorithm for an arbitrary set of any number of arbitrary simple polygons. It works for both convex and concave polygons.
...
- 23
3
votes
2
answers
337
views
VBA functions to calculate sun and moon positions
I have the following VBA code (across three modules) to make UDFs to calculate sun & moon position data. The issue I'm facing is that they are very slow to run as I have over 6000 rows (over 10 ...
- 31
2
votes
2
answers
80
views
Sampling from k circles with different radii
Description: I would like to sample n_points points from k circles whose radii and centers are given as lists.
Note: This is my ...
- 121
1
vote
2
answers
66
views
Generate vertices and normals for a flat shaded cylinder
I would like to generate list of vertices and normals (with the correct indices) for rendering a cylinder barrel (I ommited the end caps for brevity).
The normals should not be interpolated (flat ...
- 113
1
vote
2
answers
207
views
Closest Pair of Points - Optimizing Code for big sets of points
I'm trying to create an algorithm that finds the closest pair of points (2D) within a set of points. I'm using a divide and conquer method which is explained here Closest Pair of Points Algorithm.
...
- 11
3
votes
0
answers
67
views
Python: Algorithm for fast boundings box collision between two large sets of m and n rectangles
AABB: Axis Aligned Bounding Box
ALGORITHM:
Compare m number of AABB to n number of AABB to find if there is a collision between m and n sets.
PROBLEM:
Slow implementation for large number of ...
- 31
3
votes
3
answers
384
views
Find smaller angle between minute and hour hands of clock
In this code the angle between the minute and hour hands of an analog clock are found and calculated and the smaller angle between them returned. This code works perfectly and I am getting back the ...
- 33
5
votes
3
answers
176
views
Detect loop in rectilinear path
Given a rectilinear path, find if it has a loop. A rectilinear path is made up of made up of alternating horizontal and vertical segments.
Input => Ordered set of points representing ra ectilinear ...
- 389
1
vote
1
answer
485
views
Check if two triangles intersect
Problem statement: Write a function which checks if two triangles intersect or not. Complete containment or tangential contact is not considered intersection.
Approach: I have considered each triangle ...
- 389
2
votes
0
answers
74
views
Structuring a project that generates triangles inside triangles
Basically I made this completely useless program that generates triangles inside triangles. Its not perfect yet but my question is about the structure. I am generally happy with it but I want to know ...
- 189
0
votes
2
answers
436
views
C++ : Merging two convex hulls
I wrote a C++ program that merges two convex hulls in linear time.
The algorithm is based on http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Plante/CompGeomProject-EPlante/algorithm.html
...
- 1,683
5
votes
1
answer
171
views
Convex polygon-polygon swept collision test
Currently working on a pre-solve collision library. My goal is to have it be potentially usable in potential video game projects of mine, so time constraint is small as this should be used in a game ...
- 61
8
votes
2
answers
261
views
3D torus in Lua
I'm a total beginoob in Lua. The aim is to display a 3D Torus in dots (see Figure1), or at least compute the positions, privileging clarity over performance. Pseudocode link.
Don't hesitate to be ...
- 428
4
votes
1
answer
233
views
C++: k-Nearest Neighbours with Lambdas and Priority Queues
I implemented getting the \$k\$-nearest neighbours of an origin point to a set of points in C++17. I tried to use some more modern C++ lambda techniques and was looking for feedback on use of lambdas, ...
- 139
2
votes
1
answer
3k
views
The intersection of two polygons in C++
I implemented the intersection of two (convex) polygons in C++. It finds the polygon in the intersection like in this image.
Looking for any and all feedback. I left the logic for line intersection ...
- 139
6
votes
1
answer
163
views
Find overlapping area of octagons
Here is my problem statement:
There is a matrix of octagons, for example, 4 octagons in a row and 3 such rows. So 4 columns and 3 rows of octagons. But they are not arranged in a perfect rectangle ...
- 85
2
votes
0
answers
67
views
Compute angular distances between data points in a matrix
I am having a hard time speeding up a function that I use to compute angular distances between data points in a matrix. More precisely, I want to compute $$\sum_{r=1}^n|\pi - \arccos\left(\frac{(X_{i}-...
- 21
3
votes
1
answer
205
views
A program for fun to see how red and blue appears blended to purple due to resolution
I do some art both analog and digital. This time I did some color test digitally. To work on my programming skill so that it's shareable I'm asking for help to get some code review.
How's the ...
7
votes
4
answers
1k
views
Generate points for smooth movement between two given points
This is one of the methods in a project for generating points between two given points. We add points of route with a 25ms delay in an array and a camera on Google Maps is always at the last point. So ...
- 171
7
votes
3
answers
2k
views
Counting the triangles that can be formed from segments of given lengths
Problem Statement:
Given an unsorted array of positive integers. Find the number of
triangles that can be formed with three different array elements as
lengths of three sides of triangles.
...
user188780
2
votes
1
answer
84
views
Find intersection of rectangle with itself rotated
Given \$w, h, \alpha\$ for a rectangle centered at origin with width \$w\$, height \$h\$ and itself rotated by \$\alpha\$ around origin clockwise, I wrote a code to find the intersection area.
...
- 1,446
0
votes
2
answers
246
views
Read coordinates from many files and calculate polygon areas
My goal with this snippet is to create an array of coordinates which in turn is a tuple of 68 elements, area and modified area array for all 10k elements and assign it to the ...
- 824
7
votes
3
answers
3k
views
Determine if a triangle is equilateral, isosceles, or scalene
I've been fiddling around with some easy code challenges and there's one about determining if a triangle is equilateral, isosceles, or scalene.
I've come up with a working solution, but I feel this ...
- 1,348
4
votes
2
answers
128
views
Find 4 points which form a square with the biggest area
I have set of points on the coordinate plane. I need to find the 4 points which form a square with the biggest area.
I'm new in JavaScript so I'd like to get any suggestions about code style, ...
- 395
6
votes
1
answer
737
views
Choosing evenly distributed points from a million points on a sphere
I have \$10^5\$ to \$10^6\$ points on a sphere, and want to choose some points from them which are as close as uniformly distributed as possible. For that reason, I do the following: at each step I ...
- 279
6
votes
0
answers
5k
views
Cubic spline interpolation in Python from scratch
I implemented the cubic spline interpolation explained in
https://en.wikipedia.org/wiki/Spline_interpolation as a Python class. Of course, such an interpolation should exist already in some Python ...
- 61
2
votes
2
answers
830
views
Find all k points which are closest to origin
We have a list of points on the plane. Find the K closest points to
the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean
distance.)
You may return the ...
- 749
6
votes
1
answer
526
views
Searching extreme points of polyhedron
In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points ...
5
votes
2
answers
425
views
Line segment intersection from [de Berg et al, 2000], computational geometry
I've implemented the following algorithm (From "Computational Geometry : Algorithms and Applications").
The code is below:
(All the code actually is here: https://github.com/lukkio88/...
- 121
3
votes
1
answer
420
views
Given a list of coordinates, find the rectangle with minimal area
A problem on leetcode asks the coder to write an algorithm to take a bunch of coordinates in the xy-plane and return the minimum area of a rectangle made from four of these coordinates (or return <...
- 175
2
votes
1
answer
106
views
Project Euler Problem #102 in F#: counting triangles that contain the origin
I've recently decided to get into functional programming with F#, and decided to learn the language through Project Euler. The following is my implementation of problem 102:
Problem:
Three ...
- 1,098
6
votes
1
answer
83
views
Optimal algorithm to move a a rope from one position to another
I'm an engineer working with a deformable membrane that is attached to actuators. The goal is to move the membrane from one shape to another, without ripping the membrane. This imposes "neighbor ...
- 161
4
votes
2
answers
529
views
Computing bezier curves of degree n with recursive functions
I have been looking at homemade CNC and have been wondering how curves are drawn, so I looked into it and found this cool article. I then decided to try coming up with a bezier curve algorithm in C. ...
- 299
3
votes
0
answers
732
views
Implementing Cyrus Beck algorithm for convex polygons
I have found the coordinates of the centroid for finding the direction of the normal vectors of the edges of the convex polygons. This method seems to work in the cases I tested. Is this fool proof ? ...
- 131
5
votes
2
answers
367
views
AI to avoid obstacle
The AI I'm making is really simple, however it might be a bit too inefficient for what it is doing. The chart below shows speed differences between various arithmetic and math operations. ...
- 155
2
votes
1
answer
289
views
Graham Scan Algorithm in Haskell
I have just begun learning functional programming and Haskell.
This is my attempt to implement a solution to Graham Scan Algorithm in Haskell. Note that I am not even sure if this is indeed Graham ...
4
votes
2
answers
91
views
Determine whether path A→B→C on a plane constitutes a left or right turn
I have recently started learning functional programming and Haskell. I have encountered this problem:
Consider three two-dimensional points a, b, and c. If we look at the angle formed by the line ...
10
votes
2
answers
234
views
Where is the most desolate place in Colorado?
The Story
While flying a plane over the forests of Wisconsin a couple years ago, I thought to myself "If I lost an engine, I would be awfully long way from an emergency landing airport. I wonder ...
- 203
1
vote
1
answer
794
views
Drawing concentric circles to console
This prints out a triple layer circle with 12 points per circle and finds the points across a grid.
I had a really hard time with this and I'm planning to implement a lot more code but I don't want ...
20
votes
2
answers
12k
views
Intersection over Union for rotated rectangles
Problem Statement
I am trying to find the intersection over union (IoU) metric for one to several rotated rectangles compared to many different rotated rectangles. Here are some images to help ...
- 21.8k
3
votes
0
answers
2k
views
Function to calculate distances and nearest points between 2 GeoPandas dataframes
I have 2 geoPandas frames and want to calculate the distance and the nearest point (see functions below) from the geoSeries geometry from dataframe 1 (containing ...
- 131
7
votes
3
answers
2k
views
Program to see how many points lie strictly inside a convex polygon
The program takes in a set of coordinates that defines the polygon. It then takes in a set of points. The idea is to find out how many of these points lie strictly inside the convex polygon (not on ...
- 539
2
votes
1
answer
179
views
Curvature data to coordinates
I want to determine a path (x and y coordinates) by using curvature data (radius, with constant distance (length_of_arc) travelled between data points. I want to ...
- 123
5
votes
2
answers
2k
views
Given a list of coordinates check if 4 points make a line
I was doing some preparation for coding interviews and I came across the following question:
Given a list of coordinates "x y" return True if there exists a line ...
- 185