Friendly Incenters

Question

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 (0,1), (2,3), and (1,5) is ((2√2+2√17)/(2√2+√5+√17),(10√2+√5+3√17)/(2√2+√5+√17)) (yuck).

A triangle with integer coordinates can have an incenter with rational coordinates in only two cases:

1. the side lengths of the triangle are all integers
2. the side lengths of the triangle are a√d, b√d, and c√d for integers a, b, c, and d (equivalent for d=1).

(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)

Challenge

Given a triangle OAB, it meets the "friendly incenter" condition if all of the following are true:

1. points A and B have nonnegative integer coordinates,
2. If O is the origin, the distances OA, OB, and AB are either:
   • all integers or
   • integers multiplied by the square root of the same integer (a√d, b√d, and c√d as described in the intro).
3. 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=x to reach the other, or the points A and B are the same but swapped.

For example, the triangle with vertices (0,0), (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:

• A(24,32) B(36,27)
• A(27,36) B(32,24)
• A(36,27) B(24,32)

Example Output:

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.

Answer 1

JavaScript (V8),  232  229 bytes

Prints the results as \$X_A,Y_A,X_B,Y_B\$.

n=>{for(o=[0,1,2,k=3];n;)for(z=++k**4;o[A=[x,y,X,Y]=o.map(i=>~~(z/k**i)%k)]|o[[y,x,Y,X]]|o[[X,Y,x,y]]|o[[Y,X,y,x]]|Y*x==X*y|(g=d=>!d||[p,q=X*X+Y*Y,p+q-2*(x*X+y*Y)].some(v=>(v/d)**.5%1)*g(d-1))(p=x*x+y*y)?--z:o[print(A),A]=--n;);}

Try it online!

Commented

n => {                      // n = input
  for(                      // outer loop:
    o = [0, 1, 2, k = 3];   //   o = [0, 1, 2, 3], re-used as an object to store
                            //       the coordinates that were already tried
                            //   k = counter
    n;                      //   loop until n = 0
  ) for(                    //   inner loop:
    z = ++k ** 4;           //     increment k; start with z = k ** 4
    o[  A = [x, y, X, Y] =  //     build the next tuple A = [x, y, X, Y]
          o.map(i =>        //     we try all tuples such that:
            ~~(z / k ** i)  //       0 ≤ x < k, 0 ≤ y < k, 0 ≤ X < k, 0 ≤ Y < k 
            % k             //
          )                 //
    ] |                     //     if [x, y, X, Y] was already tried
    o[[y, x, Y, X]] |       //     or [y, x, Y, X] was already tried
    o[[X, Y, x, y]] |       //     or [X, Y, x, y] was already tried
    o[[Y, X, y, x]] |       //     or [Y, X, y, x] was already tried
    Y * x == X * y |        //     or (0, 0), (x, y) and (X, Y) are co-linear
    ( g = d =>              //     or g returns a truthy value:
      !d ||                 //       stop if d = 0
      [                     //       compute the squared distances:
        p,                  //         OA² = p = x² + y² (computed below)
        q = X * X + Y * Y,  //         OB² = q = X² + Y²
        p + q - 2 *         //         AB² = (X - x)² + (Y - y)² = p + q - 2(xX + yY)
        (x * X + y * Y)     //
      ].some(v =>           //       test whether there's any v in the above list
        (v / d) ** .5 % 1   //         such that sqrt(v / d) is not an integer
      ) * g(d - 1)          //       and that this holds for d - 1
    )(p = x * x + y * y) ?  //     initial call to g with d = p; if truthy:
      --z                   //       decrement z
    :                       //     else:
      o[print(A), A] = --n; //       print A, set o[A] and decrement n
  );                        //
}                           //

Answer 2

05AB1E, 54 bytes

∞<€Ðæ4ùÙεœÙ}€`2δôʒnOy`αnOª¬Lδ/tøεεDïQ}P}ày`R*Ë≠*}4ô€н

Outputs the infinite sequence of \$[[x_A,y_A],[x_B,y_B]]\$, although in a different order than the challenge description.

Try it online. (Extremely slow, so will only output the first five triangles before timing out after 60 seconds on TIO.)

Explanation:

∞<             # Push an infinite list non-negative list: [0,1,2,3,4,...]
  €Ð           # Repeat each item three times: [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,...]
    æ          # Take the powerset of this infinite list
     4ù        # And only keep sublists of length 4:
               #  [[0,0,0,1],[0,0,0,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],...]
       Ù       # Uniquify this list of sublists:
               #  [[0,0,0,1],[0,0,1,1],[0,1,1,1],[0,0,0,2],[0,0,1,2],...]
        ε      # Map each sublist to:
         œ     #  Get all permutations of the current list
          Ù    #  And uniquify it
        }€`    # After the map: flatten it one level down:
               #  [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,1,0,0],...]
            δ  # Map over each sublist again
           2 ô #  And split it into parts of size 2
               #   [[[1,0],[0,0]],[[0,1],[0,0]],[[0,0],[1,0]],[[0,0],[0,1]],...]

We now have an infinite list of triangles in all four permutations of the \$A\$ and \$B\$ coordinates (try ∞<€Ðæ4ùÙεœÙ}€`2δô loose).
Minor pet peeve: If the cartesian product builtin would have sorted in the same order as the powerset for infinite lists instead of [[[0,0],[0,0]], [[0,0],[0,1]], [[0,0],[0,2]], [[0,0],[0,3]], ...], this entire first part could have been ∞<ãÙãÙ instead.. :/

Now we keep all valid triangles:

ʒ              # Filter this list of triangles [[a,b],[c,d]] by:
 n             #  Square all inner values: [[a²,b²],[c²,d²]]
  O            #  Sum each inner list: [a²+b²,c²+d²]
   y           #  Push the original triangle [[a,b],[c,d]] again
    `          #  Pop and push both values separated to the stack
     α         #  Take the absolute difference between the coordinates: [|a-c|,|b-d|]
      n        #  Square the inner values: [|a-c|²,|b-d|²]
       O       #  Sum it: |a-c|²+|b-d|²
        ª      #  And append it to the earlier list: [a²+b²,c²+d²,|a-c|²+|b-d|²]
               #  (let's call this list [OA²,OB²,AB²] for now)
 ¬             #  Push the first item OA² (without popping the list)
  L            #  Pop and push a list in the range [1,OA²]
   δ/          #  Divide the values in both lists double-vectorized:
               #   [[OA²/1,OB²/1,AB²/1],
               #    [OA²/2,OB²/2,AB²/2],
               #    ...,
               #    [OA²/OA²,OB²/OA²,AB²/OA²]]
     t         #  Take the square root of each inner value:
               #   [[sqrt(OA²/1),sqrt(OB²/1),sqrt(AB²/1)],
               #    [sqrt(OA²/2),sqrt(OB²/2),sqrt(AB²/2)],
               #    ...,
               #    [sqrt(OA²/OA²),sqrt(OB²/OA²),sqrt(AB²/OA²)]]
      ø        #  Zip/transpose; swapping rows/columns:
               #   [[sqrt(OA²/1),sqrt(OA²/2),...,sqrt(OA²/OA²)],
               #    [sqrt(OB²/1),sqrt(OB²/2),...,sqrt(OB²/OA²)],
               #    [sqrt(AB²/1),sqrt(AB²/2),...,sqrt(AB²/OA²)]]
       ε       #  Map each inner list to:
        ε      #   Map each number to:
         D     #    Duplicate the number
          ï    #    Cast the copy to an integer
           Q   #    And check if it's still the same as before the cast
               #    (which means this number is an integer)
        }P     #   After inner map: check if all are truthy (by taking the product)
       }à      #  After the outer map: check if any are truthy (by taking the maximum)
 y             #  Push the original triangle [[a,b],[c,d]] again
  `            #  Pop and push both values separated to the stack
   R           #  Reverse the second list ([c,d] to [d,c])
    *          #  Multiply the coordinates: [a*d,b*c]
     Ë≠        #  Check that both are NOT the same: a*d != b*c
 *             #  Check if both checks were truthy

And since we've included all four permutations of the triangle coordinates in the infinite list, we fix this after the filter:

}4ô            # After the filter: split the infinite lists into parts of size 4
               # (which are all four the same triangles, but in different permutations)
   €н          # And only leave a single triangle of each quartet (the first)
               # (after which the infinite list is output implicitly as result)

Answer 3

Husk, 42 bytes

foË(fεṁC2gpṁ□)S:Fz-foV≠Fz/fo§=←▲S+m↔m½π4ΘN

Try it online!

This is an infinite list of point pairs [[xA,yA],[xB,yB]]. For some reason TIO refuses to print an initial segment before running out of time, so the link cuts it after 8 elements (the 9th would take too long).

Explanation

First we generate all point pairs.

m½π4ΘN
     N Infinite list of positive integers: [1,2,3..]
    Θ  Prepend zero: [0,1,2,3..]
  π4   Cartesian 4th power: [[0,0,0,0],[0,0,0,1],[1,0,0,0]..]
m½     Split each in half: [[[0,0],[0,0]],[[0,0],[0,1]],[[1,0],[0,0]]..]

Next we discard duplicates. This is done by creating the list of equivalent point pairs and checking that the current one is the lexicographic maximum.

fo§=←▲S+m↔
fo          Filter by condition:
        m↔    Reverse each: [[yA,xA],[yB,xB]]
      S+      Concatenate with the current point pair: [[xA,yA],[xB,yB],[yA,xA],[yB,xB]]
     ▲        The maximum of this list of 4 points
    ←         and its first element [xA,yA]
  §=          are equal.

Then we remove degenerate triangles by dividing B element-wise by A and checking that the results are distinct. Husk handles division so that this works out:

• Dividing by a nonzero integer gives a rational number by default.
• Dividing a positive number by zero gives infinity.
• Dividing a negative number by zero gives negative infinity.
• Dividing zero by zero gives a special value "Any", which is equal to every finite number, but not equal to the infinities.

foV≠Fz/
fo       Filter by condition:
    F      Fold by
     z/    element-wise division: [xB/xA,yB/yA]
  V≠       This list contains an unequal pair.

Finally, we verify the friendly incenter condition. This is done by computing the squares of the three sides, dividing out square factors and checking that the results are equal.

foË(...)S:Fz-
fo             Filter by condition:
          F      Fold by
           z-    element-wise subtraction
        S:       and prepend to the point pair: [[xB-xA,yB-yA],[xA,yA],[xB,yB]]
  Ë(...)         The results of ... are equal for these three points.

fεṁC2gpṁ□  Compute (a value corresponding to) d from a point (x,y) of magnitude n√d
       ṁ   Map and sum
        □  square: x²+y²
      p    Prime factors, say [2,2,2,2,2,3,5,5]
     g     Group equal adjacent elements: [[2,2,2,2,2],[3],[5,5]]
  ṁ        Map and concatenate
   C2      splitting into chunks of length 2: [[2,2],[2,2],[2],[3],[5,5]]
fε         Keep singletons: [[2],[3]]