Skip to main content

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
3 votes
7 answers
287 views

Find the most isolated point

Given two non-empty sets of points \$P,T = \{(x,y)\ |\ x,y \in \mathbb{Z} \}\$, find the point \$p \in P\$ such that it is the "most isolated" from all points in \$T\$. The "most ...
bigyihsuan's user avatar
  • 9,706
8 votes
4 answers
451 views

How far are you?

Write a program that gets coordinates of two objects on Earth, and calculates how far they are from each other directly in space (a straight line through Earth) and on the surface (through the ...
George Glebov's user avatar
11 votes
4 answers
561 views

Construct the point with two segments

Given a rational point P, return four integral points A, B, C, and D, such that the line segments AB and CD intersect only at P. To make it a bit more interesting, segment AB doesn't include A and B. ...
l4m2's user avatar
  • 24.5k
13 votes
16 answers
3k 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}^+ \...
vengy's user avatar
  • 2,213
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, ...
vengy's user avatar
  • 2,213
-6 votes
1 answer
176 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},...
Simd's user avatar
  • 2,936
10 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 ...
vengy's user avatar
  • 2,213
1 vote
1 answer
546 views

Where to put a circle?

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 ...
Simd's user avatar
  • 2,936
16 votes
2 answers
589 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, \...
caird coinheringaahin g's user avatar
14 votes
1 answer
265 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 ...
caird coinheringaahin g's user avatar
10 votes
6 answers
973 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 ...
ATaco's user avatar
  • 10.8k
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 ...
Yousername's user avatar
  • 4,040
11 votes
4 answers
406 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 ...
Karl's user avatar
  • 621
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, ...
alephalpha's user avatar
  • 48.5k
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 ...
lesobrod's user avatar
  • 3,413
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 ...
blaketyro's user avatar
  • 799
23 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 ...
anatolyg's user avatar
  • 13.7k
12 votes
5 answers
548 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 ...
math scat's user avatar
  • 9,408
19 votes
7 answers
2k 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 ...
Parcly Taxel's user avatar
  • 3,807
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, ...
Karl's user avatar
  • 621
10 votes
3 answers
626 views

Voronoi-Lloyd ASCII art [closed]

Voronoi diagram is a partition of a plane (or part of plane) into regions close to each of a given set of objects ("seeds"). Here we’ll be dealing with discrete arrays or even rather with ...
lesobrod's user avatar
  • 3,413
5 votes
2 answers
268 views

Canonical form of a cubic Bézier curve

On Pomax's Primer on Bézier Curves this "fairly funky image" appears: This is related to the fact that every cubic Bézier curve can be put in a "canonical form" by an affine ...
Parcly Taxel's user avatar
  • 3,807
4 votes
1 answer
198 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\$ ...
Parcly Taxel's user avatar
  • 3,807
9 votes
5 answers
469 views

3D rotation matrix to quaternion

There are multiple ways to represent a 3D rotation. The most intuitive way is the rotation matrix – $$A=\begin{bmatrix}A_{11}&A_{12}&A_{13}\\A_{21}&A_{22}&A_{23}\\A_{31}&A_{32}&...
Parcly Taxel's user avatar
  • 3,807
5 votes
2 answers
880 views

How spherical is my ellipsoid?

Define the (unnormalised) Willmore energy of a surface as the integral of squared mean curvature over it: $$W=\int_SH^2\,dA$$ For surfaces topologically equivalent to a sphere \$W\ge4\pi\$, and \$W=4\...
Parcly Taxel's user avatar
  • 3,807
16 votes
4 answers
1k views

Create a triangle whose colors are determined by the bitsums of coordinates

Write a program that, for any \$n\$, generates a triangle made of hexagons as shown, \$2^n\$ to a side. The colors are to be determined as follows. We may give the triangle barycentric coordinates so ...
Akiva Weinberger's user avatar
18 votes
8 answers
2k views

Roll a painted cube

There is a 1x1x1 cube placed on a infinite grid of 1x1 squares. The cube is painted on every side, so it leaves a mark on the grid when it moves. The sides of the cube are colored 6 distinct colors, ...
mousetail's user avatar
  • 12.7k
18 votes
4 answers
807 views

Intersection area of two rotated rectangles

Given two rectangles, which are possibly not in the orthogonal direction, find the area of their intersection. Input You may take the rectangles as input in one of the following ways: The ...
alephalpha's user avatar
  • 48.5k
12 votes
6 answers
941 views

ASCII-art polygons to GeoJSON coordinates

We're going to turn ascii art versions of polygons into their equivalent GeoJSON. The ASCII shape language The input ASCII language only has 3 possible characters: ...
Hannesh's user avatar
  • 1,225
23 votes
8 answers
1k views

Rolling a 1x1x2 block

Rolling a 1x1x2 block This challenge is inspired by the game Bloxorz. Like that game, there is a 1x1x2 block, which may be moved on a square grid in any of the four cardinal directions. It moves by ...
AlephSquirrel's user avatar
5 votes
2 answers
217 views

Transform a lattice polygon to minimum diameter by shearing

Given is a grid polygon by the list of its integer vertex coordinates arranged along the perimeter, in the form \$(x_1,y_1), (x_2,y_2), \cdots , (x_n,y_n)\$ with \$n \ge 3\$. The polygon is completed ...
Hugo Pfoertner's user avatar
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 ...
Peter Kagey's user avatar
  • 8,689
15 votes
5 answers
951 views

Detect round trips on a dodecahedron

An ant starts on an edge of a dodecahedron, facing parallel to it. At each step, it walks forward to the next vertex and turns either left or right to continue onto one of the other two edges that ...
Karl's user avatar
  • 621
24 votes
34 answers
2k views

Triangle area from side lengths

Output the area \$A\$ of a triangle given its side lengths \$a, b, c\$ as inputs. This can be computed using Heron's formula: $$ A=\sqrt{s(s-a)(s-b)(s-c)}\textrm{, where } s=\frac{a+b+c}{2}.$$ This ...
xnor's user avatar
  • 145k
7 votes
2 answers
306 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 ...
Shieru Asakoto's user avatar
19 votes
7 answers
2k views

Matrix Meets ASCII Art

A binary matrix represents a shape in the plane. 1 means a unit square at that position. 0 means nothing. The background is 0. For example, the array ...
Number Basher's user avatar
14 votes
7 answers
1k views

Euler characteristic of a binary matrix

A binary matrix represents a shape in the plane. 1 means a unit square at that position. 0 means nothing. The background is <...
alephalpha's user avatar
  • 48.5k
8 votes
6 answers
578 views

Calculate the overlapping line

(l, r) defines a line whose left end is at l and the right end is at r, on a 1-dimensional ...
xiver77's user avatar
  • 2,365
17 votes
12 answers
2k views

Random Point from a 2D Donut Distribution

A donut distribution (for lack of a better term) is a random distribution of points in a 2-dimensional plane, forming a donut-like shape. The distribution is defined by two parameters: the radius <...
Jitse's user avatar
  • 7,324
10 votes
3 answers
340 views

Coordinates for a Heronian tetrahedron

Did you know that Heronian Tetrahedra Are Lattice Tetrahedra? A Heronian tetrahedron is a tetrahedron where the length of each edge is an integer, the area of each face is an integer, and the volume ...
Peter Kagey's user avatar
  • 8,689
17 votes
7 answers
486 views

Score a curling end

Curling is a sport where two teams aim to place stones as close to the centre of a target as possible. The winner of a curling end is the team whose stone is closest to the centre – they score as many ...
Parcly Taxel's user avatar
  • 3,807
21 votes
4 answers
932 views

Is this hexagon symmetric?

TLDR: This is the hexagonal version of Is this square symmetrical? Given a hexagonal grid, decide if it is symmetric. The shape of the grid is a regular hexagon. Each cell in the grid has two possible ...
alephalpha's user avatar
  • 48.5k
13 votes
6 answers
554 views

AoCG2021 Day 22: Hyperbolic rescue

Part of Advent of Code Golf 2021 event. See the linked meta post for details. The story continues from AoC2017 Day 11. Crossing the bridge, you've barely reached the other side of the stream when you ...
Wheat Wizard's user avatar
  • 98.8k
14 votes
9 answers
2k views

All distances different on a chessboard

Inspired by this Puzzling SE question: All distances different on a chess board. Introduction Lets define a sequence \$a(n), n\geqslant 1\$ as how many pawns can you put on a \$n \times n\$ chessboard ...
pajonk's user avatar
  • 16.7k
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 ...
Wheat Wizard's user avatar
  • 98.8k
18 votes
4 answers
910 views

Find the sliced sheet of paper

Context : Suppose you have a sheet of paper measuring 8 x 10. You want to cut it exactly in half while maintaining its rectangular shape. You can do this in two ...
Eternal Student's user avatar
14 votes
2 answers
571 views

Draw me a shape

The game shapez.io has a lot of shapes. In my previous challenge, the object was to generate a random code for a shape. Now, your challenge is to render a shape. Specs Shapes Each shape has a unique ...
emanresu A's user avatar
  • 38.8k
28 votes
10 answers
6k views

Distances between keys on a QWERTY keyboard

Inspired by this video by Matt Parker The distances between the letter keys of a QWERTY keyboard are somewhat standardised. The keys are square and both the horizontal and vertical spacing are 19.05mm ...
pxeger's user avatar
  • 23.9k
16 votes
1 answer
375 views

Build the widest unsupported bridge with nothing but frictionless blocks

In this challenge you must write a computer program that creates a stack of a thousand identical \$1 \times 1\$ frictionless homogeneous blocks such that each block is supported and the stack is ...
orlp's user avatar
  • 39.1k
11 votes
4 answers
478 views

Minkowski sum of two convex polygons

Background Minkowski addition is a binary operation on two sets of points (usually geometric objects) in the Euclidean space. The Minkowski sum of two sets \$A\$ and \$B\$ is formally defined as ...
Bubbler's user avatar
  • 76.9k

1
2 3 4 5
8