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
-4
votes
0answers
25 views

Calculate area and perimeter of different 2-dimensional objects [closed]

Problem statement: Create a class named Shape with an abstract method named print. From this class inherit three classes - <...
4
votes
2answers
72 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
61 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 ...
5
votes
2answers
136 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/...
6
votes
1answer
90 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 ...
11
votes
7answers
19k views

C++ 3D Vector Implementation

I have been learning C++ now for 2 months and this week I started reading a book on 3D graphics. I like coding whatever mathematical stuff I learn so I can understand it better, so when I learnt about ...
5
votes
0answers
58 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
53 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
160 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 ...
3
votes
1answer
69 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
55 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 ...
9
votes
5answers
22k views

Order a list of points by closest distance

I wrote a function that will take a list of points and then order them so they sort of... "chain together". The function will start with point #1 in the list. It will add point #1 to the list of ...
4
votes
2answers
87 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. ...
5
votes
2answers
197 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. ...
6
votes
1answer
790 views

Finding overlaps between two lists of axis-aligned rectangles

I am trying to find an efficient solution for finding overlapping of n rectangles where rectangles are stored in two separate lists. We are looking for all rectangles in ...
13
votes
2answers
4k views

Calculate the area of rectangles union

I've been given the following task: Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. ...
3
votes
0answers
107 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 ? ...
0
votes
0answers
59 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 ...
2
votes
1answer
86 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
61 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 ...
4
votes
1answer
113 views

Count lines with more the X dots on it

I have Python a Algorithm class with a calculate method that takes the list of tuples where every tuple have 2 integers (...
9
votes
2answers
140 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 ...
0
votes
1answer
188 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 ...
5
votes
5answers
5k views

Ramer-Douglas-Peucker algorithm

Ramer-Douglas-Peucker is a great algorithm for reducing the number of samples in a given trace, and also for keeping its general shape (as much as he can). I have a trace with 32.000.000 samples, and ...
15
votes
2answers
2k 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 ...
6
votes
3answers
6k views

Generate sample coordinates inside a Polygon

I have a Polygon named as poly. I attempted to randomly select 5 coordinate points that lies inside the polygon. ...
3
votes
4answers
669 views

Striped closed poly-line

I'm working on class Striped_polyline which represents a closed poly-line filled with equidistant horizontal lines1: stripedpoly.cpp: ...
3
votes
0answers
895 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 ...
4
votes
2answers
848 views

Find the largest area polygon built from a given list of vertices

This is code that gets a list of polygon vertices, non-ordered, and finds the order in which they should be arranged in order to create the polygon with the largest area. There are two key elements ...
7
votes
3answers
1k 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
72 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 ...
28
votes
3answers
37k views

Overlapping rectangles

I received the following question in a technical interview today (for a devops/SRE position): Write a function which returns true if the two rectangles passed to it as arguments would overlap if ...
5
votes
2answers
604 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
61 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
121 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
2k 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 ...
8
votes
1answer
428 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
142 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 ...
11
votes
1answer
3k views

Farthest point algorithm in Python

I am learning Python and I tried to do a program to find K points from a set of N points, farthest as much as possible (I'm not ...
3
votes
1answer
173 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 ...
4
votes
1answer
192 views

Shortest distance from point to line segment in 3D

This function returns the shortest distance from a 3D point P to a line segment defined by two 3D points A and B. It projects P onto the line, then checks if this projected point lies between A and B. ...
3
votes
4answers
104 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
722 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
vote
1answer
114 views

Finding angle and direction between line segments

I'm putting together a short demo on two things: Finding the angle between two line segments and direction (right or left) as you travel counterclockwise around a shape Using newer ecmascript syntax (...
1
vote
1answer
109 views

Angle reflection function

I've developed a function to calculate the exit angle of a projectile after it collides with a boundary/edge inside a rectangular space, based on the entry angle and the axis it is colliding with. ...
7
votes
3answers
4k views

Python implementation of the Ramer-Douglas-Peucker Algorithm

I recently implemented the RDP polygon approximation algorithm in Python and I'm skeptical of whether or not I implemented it correctly of with the greatest efficiency. The algorithm runs in around 0....
0
votes
1answer
47 views

Calculating minimum size of rectangle that contains two smaller ones [closed]

My Rectangle class contains one vertex (x,y), its width a, and its height b; the opposite ...
6
votes
1answer
60 views

Catmull-Rom Interpolator: Template pandemonium avoidance

I have a pull request implementing Catmull-Rom interpolation. I have gotten it pretty fast-to ~25 ns/call-but I feel the design is not enlightened. The code is here, and reproduced below: ...
2
votes
1answer
75 views

Segment road map data with heuristics

Backstory A little while ago I was assigned with the task of clustering some road segments using open street map data. After parsing a huge XML (maybe that should be another review) I ended up with ...