Questions tagged [geometry]

This challenge is intended to be solved by using, manipulating, or creating shapes or other geometric structures.

Filter by
Sorted by
Tagged with
23 votes
5 answers
5k views

Find the Convex Hull of a set of 2D points

When you hammer a set of nails into a wooden board and wrap a rubber band around them, you get a Convex Hull. Your mission, should you decide to accept it, is to find the Convex Hull of a given set ...
12 votes
15 answers
2k views

The primitive circle problem

Challenge The primitive circle problem is the problem of determining how many coprime integer lattice points \$x,y\$ there are in a circle centered at the origin and with radius \$r \in \mathbb{Z}^+ \...
16 votes
25 answers
2k views

Code-Golf: Lattice Points inside a Circle

The following picture shows the problem: Write a function that, given an integer as the circle radius, calculates the number of lattice points inside the centered circle (including the boundary). ...
9 votes
12 answers
1k views

Counting Collinear Points

Given two points \$(x_1, y_1)\$ and \$(x_2, y_2)\$ with integer coordinates, calculate the number of integer points (excluding the given points) that lie on the straight line segment joining these two ...
17 votes
19 answers
1k views

Ellipse Lattice Point Counter

Challenge Determine how many integer lattice points there are in an ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} \leq 1$$ centered at the origin with width \$2a\$ and height \$2b\$ where integers \$a, ...
18 votes
16 answers
965 views

What are my dimensions?

Task: Given the area of a triangle, find a Heronian triangle with that area. Any Heronian triangle with the specified area is allowed. A Heronian triangle is a triangle with integer sides and integer ...
-6 votes
1 answer
167 views

Where to stand to throw circles over sticks

Consider a horizontal line with vertical lines centered on the x-axis and placed at gaps of \$\sqrt{2}/2\$. For a positive integer \$n \geq 3\$, the first half of the lines have lengths \$0, \sqrt{2},...
1 vote
1 answer
504 views

Find the optimum circle in an infinite grid

Consider an \$n \times n\$ grid of integers which is part of an infinite grid. The top left coordinate of the \$n \times n\$ grid of integers is \$(0, 0)\$. The task is to find a circle which when ...
33 votes
27 answers
4k views

Circumference of an ellipse

Challenge Unlike the circumference of a circle (which is as simple as \$2\pi r\$), the circumference (arc length) of an ellipse is hard. Given the semi-major axis \$a\$ and semi-minor axis \$b\$ of an ...
20 votes
6 answers
842 views

The Caged Circles

This problem will have you analyzing circles drawn on the grid, with the gridlines drawn at integer values of \$x\$ and \$y\$. Let \$\varepsilon\$ be a very small number (think, \$\varepsilon = 0.0001\...
15 votes
2 answers
568 views

Construct this point

Given a constructible point \$(x, y) \in \mathbb R^2\$, output the steps required to construct \$(x, y)\$ Constructing a point Consider the following "construction" of a point \$(\alpha, \...
13 votes
1 answer
253 views

Construct the Constructability sequence

Consider compass-and-straightedge construction, where you can construct new points from existing ones by examining intersections of straight lines and circles constructed with one of the following two ...
25 votes
15 answers
2k views

Vertices of a regular dodecahedron

A regular dodecahedron is one of the five Platonic solids. It has 12 pentagonal faces, 20 vertices, and 30 edges. Your task is to output the vertex coordinates of a regular dodecahedron. The size, ...
51 votes
31 answers
9k views

Covering a Skyline with brush strokes

Given a non-negative integer skyline height list, answer how many uninterrupted 1-unit-high horizontal brush strokes are needed to cover it. [1,3,2,1,2,1,5,3,3,4,2]...
27 votes
29 answers
5k views

Count the number of triangles

Given a list of positive integers, find the number of triangles we can form such that their side lengths are represented by three distinct entries of the input list. (Inspiration comes from CR.) ...
30 votes
3 answers
2k views

Golf the smallest sphere!

Inspired by this challenge, as well as a problem I've been working on Problem: Given a non-empty set of points in 3D space, find the diameter of the smallest sphere ...
19 votes
14 answers
2k views

The Area of Rectangles

Getting the area covered by a rectangle is really easy; just multiply its height by its width. However in this challenge we will be getting the area covered by multiple rectangles. This is equally ...
20 votes
7 answers
3k views

The smallest area of a convex grid polygon

I got an email from Hugo Pfoertner, an Editor-in-Chief at the On-Line Encyclopedia of Integer Sequences, with a terrific idea for a fastest-code challenge, which will also help verify or expand the ...
22 votes
25 answers
4k views

Given 4 fence lengths, what's the largest rectangular yard you can make?

Here's a very simple little problem that I don't believe has been asked before. Challenge Write a program or a function that takes in four positive integers that represents the lengths of movable but ...
112 votes
87 answers
27k views

Draw the national flag of Iceland

This year's UEFA Euro 2016 is over and besides a couple of negative headlines there has been a very positive surprise as well – the Iceland national football team. Let's draw their national flag. ...
15 votes
16 answers
900 views

Euler-Poincaré-Characteristic of Polyhedra

Given a triangulation of the surface of a polyhedron p, calculate its Euler-Poincaré-Characteristic χ(p) = V-E+F, where ...
4 votes
1 answer
189 views

4D rotation matrix to quaternions

It is well-known that a 3D rotation can always be represented by a quaternion. It is less well-known that a 4D rotation can always be represented by two quaternions, sending a point \$p=(a,b,c,d)^T\$ ...
18 votes
7 answers
1k views

Draw the GKMS aperiodic tile

Chaim Goodman-Strauss, Craig Kaplan, Joseph Myers and David Smith found the following simple (both objectively and subjectively) polygon that tiles the plane, but only aperiodically: Indeed they ...
10 votes
6 answers
962 views

Calculate the Distance to a Line Segment

The Challenge Given two vertexes and a point calculate the distance to the line segment defined by those points. This can be calculated with the following psudocode ...
7 votes
2 answers
301 views

Find the Circle-Tangent Polynomials

Introduction A circle-tangent polynomial is a polynomial of degree \$N\ge3\$ or above that is tangent to the unit circle from inside at all of its N-1 intersection points. The two tails that exits the ...
20 votes
9 answers
2k views

Cutting a Circular Pizza Vertically

Most people would cut circular pizzas into circular sectors to divide them up evenly, but it's also possible to divide them evenly by cutting them vertically like so, where each piece has the same ...
34 votes
3 answers
2k views

Placing circles along a square spiral

In this code golf challenge, you'll be computing the placement of (open) circles of areas \$\pi, 2\pi, 3\pi, \dots\$ when greedily placed along integer points in a square spiral in such a way that no ...
43 votes
44 answers
5k views

The Crow vs The Taxicab

Imagine travelling to a point lying A miles away horizontally and B miles away vertically from your current position. Or in other words, travelling from (0, 0) to ...
11 votes
4 answers
377 views

Generate the vertices of a geodesic sphere

As in this challenge, the task is to generate the vertices of a polyhedron. The polyhedron here is the one obtained by dividing a regular icosahedron's triangular faces into smaller triangles so that ...
25 votes
45 answers
8k views

Distance between two points in n-dimensional space

Here is another simple one: The Challenge Given two points in an n-dimensional space, output the distance between them, also called the Euclidean distance. The coordinates will be rational numbers; ...
19 votes
18 answers
2k views

Hypercube elements

Write a function or program that outputs the number of each type of element (vertex, edge, face, etc.) of an N-dimensional hypercube. As an example, the 3 dimensional cube has 1 cell (i.e. 1 3-...
19 votes
5 answers
775 views

Triangular battleships (A computational geometry problem)

You are the captain of a battleship. The engineering department's been cutting corners with designs this year, so the ship you're on takes the shape of a simple triangle. You walk out onto the deck ...
14 votes
2 answers
910 views

Counting generalized polyominoes

This challenge will have you count pseudo-polyforms on the snub square tiling. I think that this sequence does not yet exist on the OEIS, so this challenge exists to compute as many terms as possible ...
50 votes
81 answers
10k views

Is my triangle right?

Given a, b, c the length of the three sides of a triangle, say if the triangle is right-angled (i.e. has one angle equal to 90 degrees) or not. Input Three positive ...
22 votes
20 answers
2k views

Calculate Euclidean distance on a torus

Euclidean distance between two lattice points \$(x_1, y_1)\$ and \$(x_2, y_2)\$ on a plane is: \$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\$. Imagine now a lattice ...
11 votes
6 answers
550 views

Is this a cube?

This challenge is a riff on Dion's challenge "Is this a rectangle?". The goal of this challenge is to write a program to decide whether or not some collection of tuples of integers represents a ...
14 votes
8 answers
1k views

Euclidean distance on projective plane

Motivated by this challenge Background Let we have a square sheet of flexible material. Roughly speaking, we may close it on itself four ways: Here the color marks the edges that connect and the ...
16 votes
6 answers
1k views

Detect round trips on a hyperbolic grid

You're driving a car in an infinite city whose blocks are pentagons arranged in the order-4 pentagonal tiling. At each step, you proceed to the next intersection and choose whether to continue left, ...
106 votes
96 answers
23k views

Draw the national flag of France

There have been many other flag challenges posted but not one for the national flag of France. This week seems like an appropriate time. Produce this flag in the fewest bytes possible: The image must ...
11 votes
5 answers
457 views

Elliptic system

Introduction Given five points in the plane, your task is to compute the area of the ellipse passing through these points. You can assume that exactly one non-degenerate ellipse can be constructed ...
29 votes
6 answers
9k views

Let's draw the flag of Nepal

Nepal’s flag (Wikipedia, Numberphile) looks very different from any other. It also has specific drawing instructions (included in the Wikipedia article). I want you guys to make a program which will ...
14 votes
1 answer
659 views

Circular robot instructions

This challenge is based on Project Euler problem 208. Also related to my Math Stack Exchange question, Non-self-intersecting "Robot Walks". You have a robot that moves in arcs which are \$1/...
12 votes
7 answers
1k views

Number of holes in a polygon

The Problem: Count the number of holes in a connected polygon. Connectivity of the polygon is guaranteed by the condition that every triangle in the input triangulation shares at least 1 side with ...
28 votes
20 answers
5k views

Draw A Reuleaux Triangle!

The Reuleaux triangle is the shape formed by the intersection of three circles, with each circle passing through the others' centers. Regardless of rotation, a Reuleaux triangle's width will always ...
13 votes
7 answers
2k views

Who Took My Toilet Paper?

You step into the restroom, and notice that the toilet paper has missing! It occurs to you that someone had stolen it. Strangely enough, the first thing you would like to know is the amount of toilet ...
14 votes
3 answers
548 views

Where does the spaceship go?

Based on an idea suggested by Zgarb. A spaceship is moving around a regular 3D grid. The cells of the grid are indexed with integers in a right-handed coordinate system, xyz. The spaceship starts at ...
24 votes
5 answers
2k views

Count the rectangles in a diagonal grid

As a follow-up to this challenge, we now want to count the number of rectangles in grid with r rows and c columns where there is a line crossing through every diagonal of a square in the grid. Now, we ...
169 votes
8 answers
36k views

Draw an Image as a Voronoi Map

Credits to Calvin's Hobbies for nudging my challenge idea in the right direction. Consider a set of points in the plane, which we will call sites, and associate a colour with each site. Now you can ...
105 votes
3 answers
4k views

Sprocket Science: Animating a Chain Drive System

The goal of this challenge is to produce an animation of a chain drive system, comprised of a set of sprocket gears connected together by a chain. General Requirements Your program will be given a ...
12 votes
5 answers
484 views

Enumeration of free polyominoes

A polyomino with \$n\$ cells is a shape consisting of \$n\$ equal squares connected edge to edge. No free polyomino is the rotation, translation or reflection (or a combination of these ...

1
2 3 4 5
8