Questions tagged [geometry]
This challenge is intended to be solved by using, manipulating, or creating shapes or other geometric structures.
397 questions
-4
votes
3
answers
350
views
Render a polygon...in ASCII [closed]
Given the anti-clockwise points of a properly formed, non-self-intersecting, not-necessarily-convex polygon, render it as a filled ASCII art polygon.
Input
A series of at least 3 (x,y) pairs ...
- 8,074
16
votes
7
answers
1k
views
Solve the crossed ladders problem
I'm surprised we don't have the crossed ladders problem as a task here yet.
Two ladders of lengths a and b lie oppositely across an alley, as shown in the figure. The ladders cross at a height of h ...
- 4,749
18
votes
13
answers
1k
views
Make the Stars Shine
We've been given a map of the night sky. The map features three single characters, to match the theme, I'll refer to them O, X ...
- 581
9
votes
2
answers
346
views
Putting the pieces together
In this code-golf challenge, you will count the number of ways of putting together pieces of a building toy which consists of slotted squares that interlock with one another, shown below. In ...
- 8,175
8
votes
1
answer
252
views
How many polygons overlap?
Write a program or function which, given 1 or more polygons, determines the greatest number of polygons overlapping at a single point. That is, if each polygon was a piece of paper positioned ...
- 8,074
9
votes
1
answer
390
views
Ruler-and-compass constructions
In this code-golf challenge, you will work with a construction that was used by the ancient Greeks: the straightedge-and-compass construction. In particular, you will count how many different ...
- 8,175
1
vote
2
answers
315
views
minimum line queries in logarithmic time
Input
You are given 2 positive integers, n, q, followed by q queries. the queries can be of two forms:
0 a b: add the line a*x + b. a and b are integers between -...
- 115
12
votes
14
answers
1k
views
Generate the indices of the corners of the 12 face triangles of a cube
A cube has 6 faces. We can define it in terms of triangles only, by splitting each square face on the diagonal.
Each vertex of the cube is numbered 0 through 7. The coordinates of a vertex are that ...
- 221
9
votes
7
answers
569
views
Malfatti circle radii
Consider a triangle \$ABC\$ whose sides \$BC,CA,AB\$ have lengths \$a,b,c\$ respectively. In this triangle we can construct circles \$G_A,G_B,G_C\$ such that
\$G_A\$ is tangent to \$CA,AB,G_B,G_C\$
\$...
- 4,749
20
votes
6
answers
1k
views
Free Kei Friday
A kei (圭) is an algebraic structure that abstracts the idea of mirror reflections.
The kei is given as a set of mirrors \$X\$ and a closed reflection operation \$(\rhd) : X\times X\rightarrow X\$. We ...
- 103k
12
votes
13
answers
1k
views
Determine the area of biggest rectangle containing exactly one "X"
Your input is a rectangular 2D char array, such as:
.X.......X
..........
.....X....
..X.......
........X.
.X........
..X.....X.
X.........
....X.....
Your goal is ...
- 161
6
votes
2
answers
383
views
Count the symmetries
Find the order (size) of the symmetry group of a finite set of integer points in d-dimensional space.
Input
You will be given the coordinates of a finite set of points in d-dimensional space, in any ...
- 2,072
7
votes
2
answers
355
views
Snake a string through a simplex
An n-simplex is a generalization of 'triangleness' in any dimension (specifically, it is the simplest shape requiring n dimensions). Starting with 0 dimensions, the named simplexes are: point, line ...
- 1,631
16
votes
10
answers
1k
views
Draw a Regular Reuleaux Polygon
Related: Draw A Reuleaux Triangle!, Draw a regular polygon
A Reuleaux polygon is a curve of constant width made up of circular arcs of constant radius. The most well-known Reuleaux polygon is the ...
- 12.6k
12
votes
1
answer
488
views
Plot the ground path of a satellite
If you model a satellite as a free point orbiting a body, you can pretty easily see it has 6 degrees of freedom: three for the X, Y, and Z position, and three for the X, Y, and Z velocity. However, ...
- 1,631
3
votes
7
answers
485
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 ...
- 11.5k
8
votes
4
answers
577
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 ...
- 181
11
votes
4
answers
643
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.
...
- 32.7k
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}^+
\...
- 2,309
17
votes
20
answers
2k
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, ...
- 2,309
-6
votes
1
answer
258
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},...
- 3,167
13
votes
14
answers
2k
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 ...
- 2,309
1
vote
1
answer
629
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 ...
- 3,167
17
votes
2
answers
691
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, \...
- 50.9k
14
votes
1
answer
342
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 ...
- 50.9k
12
votes
8
answers
1k
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
...
- 11.7k
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 ...
- 4,280
11
votes
4
answers
562
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 ...
- 871
25
votes
15
answers
3k
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.9k
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 ...
- 3,448
22
votes
26
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 ...
- 809
23
votes
20
answers
3k
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 ...
- 14.2k
14
votes
5
answers
919
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 ...
- 9,538
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 ...
- 4,749
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, ...
- 871
10
votes
3
answers
702
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 ...
- 3,448
5
votes
2
answers
335
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 ...
- 4,749
4
votes
1
answer
271
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\$ ...
- 4,749
9
votes
5
answers
604
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}&...
- 4,749
5
votes
2
answers
921
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\...
- 4,749
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 ...
- 263
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, ...
- 14.4k
18
votes
4
answers
1k
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 ...
- 51.9k
12
votes
6
answers
1k
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:
...
- 1,255
23
votes
8
answers
2k
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 ...
- 865
5
votes
2
answers
305
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 ...
- 711
20
votes
8
answers
5k
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 ...
- 8,175
15
votes
5
answers
1k
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 ...
- 871
26
votes
37
answers
3k
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 ...
- 150k
7
votes
2
answers
518
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 ...
- 6,478