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.
240
questions
1
vote
2
answers
83
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 ...
1
vote
0
answers
120
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
163
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 ...
4
votes
1
answer
211
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 ...
1
vote
1
answer
205
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.
...
1
vote
1
answer
499
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 ...
1
vote
2
answers
977
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.
...
3
votes
2
answers
525
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 ...
2
votes
2
answers
102
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 ...
1
vote
2
answers
72
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 ...
1
vote
2
answers
258
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.
...
3
votes
0
answers
75
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 ...
3
votes
3
answers
454
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 ...
5
votes
3
answers
213
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 ...
1
vote
1
answer
688
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 ...