The incenter of a triangle is the intersection of the triangle's angle bisectors. This is somewhat complicated, but the coordinate formula for incenter is pretty simple (reference). The specifics of the formula do not matter much for this challenge.
The formula requires lengths of sides, so it can be very messy for most triangles with integer coordinates because lengths of sides tend to be square roots. For example, the incenter of the triangle with vertices
A triangle with integer coordinates can have an incenter with rational coordinates in only two cases:
- the side lengths of the triangle are all integers
- the side lengths of the triangle are
(Meeting at least one of these two conditions is necessary to having a rational incenter, and the former is sufficient. I am not sure if the second case is sufficient)
Given a triangle OAB, it meets the "friendly incenter" condition if all of the following are true:
Bhave nonnegative integer coordinates,
Ois the origin, the distances
- all integers or
- integers multiplied by the square root of the same integer (
c√das described in the intro).
- The triangle is not degenerate (it has positive area, i.e. the three vertices are not collinear)
Based on wording from the sequence tag, your program may
- Given some index n, return the n-th entry of the sequence.
- Given some index n, return all entries up to the n-th one in the sequence.
- Without taking any index, return an (infinite) lazy list or generator that represents the whole sequence.
But what is the sequence? Since it would be too arbitrary to impose an ordering on a set of triangles, the sequence is the infinite set of all triangles that meet the "friendly incenter" condition. You may order these triangles however you wish, for example:
- in increasing order of the sum of coordinates
- in increasing order of distance from the origin
This sequence must include every "friendly incenter" triangle once and once only. To be specific:
- Every triangle must have finite index in the sequence
- Two triangles are the same if one can be reflected over the line
y=xto reach the other, or the points
Bare the same but swapped.
For example, the triangle with vertices
(32, 24), and
(27, 36) must be included at some point in the sequence. If this is included as
A(32,24) B(27,36), then the following triangles cannot be included because they duplicate that included triangle:
If a program opts to output the first
n triangles and is given
n=10, it may output:
(0,0),(0,4),(3,4) (0,0),(3,0),(3,4) (0,0),(3,0),(0,4) (0,0),(4,3),(0,6) (0,0),(4,4),(1,7) (0,0),(7,1),(1,7) (0,0),(1,7),(8,8) (0,0),(0,8),(6,8) (0,0),(6,0),(6,8) (0,0),(3,4),(0,8)
Of course, the output format is flexible. For example, the
(0,0) coordinates may be excluded, or you may output complex numbers (Gaussian Integers) instead of coordinate pairs.