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
3answers
101 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
3answers
125 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
1answer
133 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 ...
2
votes
0answers
67 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 ...
2
votes
0answers
200 views

Triangle module in OpenSCAD

I've written the following module to generate arbitrary triangles based on a subset of lengths and angles, like what this provides. It works well enough but as-written it's fairly repetitive. I'm new ...
0
votes
2answers
162 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 ...
4
votes
1answer
92 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 ...
6
votes
2answers
145 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 ...
4
votes
1answer
152 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, ...
2
votes
1answer
1k 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 ...
1
vote
0answers
33 views

Calculating the term of dfdeta [closed]

I am trying to improve the time running of this code. Some dummies variable is defined and it is just some part of a lot of lines of code, but I tried it with dummies variables. It takes too much in ...
6
votes
1answer
116 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 ...
2
votes
0answers
63 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}-...
3
votes
1answer
181 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
4answers
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 ...
7
votes
3answers
1k 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. ...
2
votes
1answer
54 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. ...
0
votes
2answers
166 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 ...
7
votes
3answers
2k 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 ...
4
votes
2answers
106 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, ...
6
votes
1answer
340 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 ...
6
votes
0answers
4k 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 ...
2
votes
2answers
633 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 ...
6
votes
1answer
424 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
2answers
319 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/...
3
votes
1answer
249 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 <...
2
votes
1answer
89 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 ...
6
votes
1answer
73 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 ...
4
votes
2answers
307 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. ...
3
votes
0answers
563 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 ? ...
1
vote
0answers
61 views

Get directions for unit movement with conditions

I am developing a bot for Starcraft II. In my code for unit movement, I often find myself doing this: Calculate points around the current position of the unit Check if these points are valid and can ...
5
votes
2answers
221 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. ...
2
votes
1answer
240 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
2answers
78 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
2answers
197 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 ...
1
vote
1answer
552 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 ...
18
votes
2answers
10k 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 ...
3
votes
0answers
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 ...
7
votes
3answers
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 ...
2
votes
1answer
129 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 ...
5
votes
2answers
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 ...
3
votes
2answers
66 views

Checking where/if another creature lies in a creature's field of view

Note: this is a more specific form of this I am working on a simulation of some virtual creatures. They all have vision that lets them see other creatures. To do this, I calculate the difference ...
2
votes
2answers
325 views

Finding the closest pair of points divide-and-conquer speed improvement

This is a follow up to a previously asked Finding the closest pair of points divide-and-conquer question . The original code changed significantly based on answers from @AJNeufeld therefore I created ...
4
votes
2answers
6k views

Finding the closest pair of points divide-and-conquer

Here is my code for the famous "finding the closest pair of points" problem from CLRS book section 33.4 using a divide-and-conquer approach (this code returns the minimum distance between pair of ...
1
vote
1answer
936 views
8
votes
1answer
520 views

Lagrange Interpolation over quadrilateral points

I've been working on a program which calculates, given a point and 4 surrounding points, the Lagrange polynomial, in order to interpolate a value. Consider that I'm not a mathematician and I better ...
3
votes
2answers
285 views

Math matrix, mainly for graphics

I wrote a matrix library to replace my old matrix library. I was using my old matrix library to do basic operations for 3D rendering but that library grew old and now I'm seeking to replace it. I'm ...
3
votes
1answer
379 views

Draw common tangents to two circles interactively in MATLAB

Requirement After a user draws two circles with their mouse successively, the program should draw all common tangents, if any, to them. Here is my implementation ...
3
votes
4answers
125 views

Solving for <45 degree angles of a multi-vector system

I'm working on a problem from codechef.com. The goals are: Solve for whether or not the driver took a "sharp turn", meaning for some angle θ, θ > 45°. Test each point \$ (x_i, y_i) \$ in the system ...
0
votes
2answers
1k views

Given points on a 2D plane, find line that passes through the most points

Could someone give some feedbacks from perspective of oo design and coding style on the following codes: Question: Given n points on a 2D plane, find the Line with maximum number of points that lie ...

1
2 3 4 5