Siteimprove · rcj-siteimprove · Apr 5, 2024 · Apr 2, 2024 · Apr 2, 2024 · Apr 2, 2024
@@ -0,0 +1,7 @@
+---
+"@siteimprove/alfa-rules": patch
+---
+
+**Fixed:** R113 spacing condition is now calculated more accurately.
+
+The part of the condition requiring computation of intersections between the circle around the center of the target and the bounding box of all other targets has been implemented.
@@ -0,0 +1,5 @@
+---
+"@siteimprove/alfa-rules": minor
+---
+
+**Changed:** R113 now sends more information about how it succeed and the other targets that caused the spacing criteria to fail.
@@ -0,0 +1,5 @@
+---
+"@siteimprove/alfa-rectangle": minor
+---
+
+**Added:** Methods `Rectangle#insersectsCircle` and `Rectangle#distanceSquared`.
@@ -23,6 +23,7 @@ export class Rectangle implements Equatable, Hashable, Serializable<Rectangle.JS
     };
     // (undocumented)
     contains(other: Rectangle): boolean;
+    distanceSquared(other: Rectangle): number;
     // (undocumented)
     static empty(): Rectangle;
     // (undocumented)
@@ -39,6 +40,7 @@ export class Rectangle implements Equatable, Hashable, Serializable<Rectangle.JS
     intersection(other: Rectangle): Rectangle;
     // (undocumented)
     intersects(other: Rectangle): boolean;
+    intersectsCircle(cx: number, cy: number, r: number): boolean;
     // (undocumented)
     isEmpty(): boolean;
     // (undocumented)

@@ -196,6 +196,74 @@ export class Rectangle
     );
   }
 
+  /**
+   * Checks if the rectangle intersects a given circle.
+   *
+   * @remarks
+   * @see ../docs/circle-rectangle-intersection.png for a visual explanation of the case
+   * where the circle center lies in one of the corners of the padded rectangle.
+   *
+   * @privateRemarks
+    * To check intersection, we pad the rectangle by the radius of the circle and divide the problem into three cases:
+    *
+    * 1. The circle center is outside the padded rectangle.
+    * 2. The circle center is inside the padded rectangle, but not in one of the corners.
+    * 3. The circle center lies in one of the corners of the padded rectangle in which case we need to compute the distance to the corner
+    *
+    *                 r
+    *              +-------+-------------------------+-------+
+    *              |       |                         |       |
+    *     1        |       |                         |       |
+    *              +-------+-------------------------+-------+
+    *              |       |                         |       |
+    *              |       |                         |       |
+    *              |       |                         |       |
+    *              |       |                         |       |
+    *              |       |                         |       |
+    *              +-------+-------------------------+-------+
+    *              |       |            2            |       |
+    *              | 3     |                         |       |
+    *              +-------+-------------------------+-------+
+   */
+  public intersectsCircle(cx: number, cy: number, r: number): boolean {
+
+    const center = this.center;
+    const halfWidth = this.width / 2;
+    const halfHeight = this.height / 2;
+
+    const dx = Math.abs(cx - center.x);
+    const dy = Math.abs(cy - center.y);
+
+    if (dx > halfWidth + r || dy > halfHeight + r) {
+      // 1. The circle center is outside the padded rectangle
+      return false;
+    }
+
+    // The circle center is inside the padded rectangle
+    if (dx <= halfWidth || dy <= halfHeight) {
+      // 2. The circle lies at most a radius away from the rectangle in the x or y directions
+      return true;
+    }
+
+    // 3. The circle center lies in one of the corners of the padded rectangle.
+    // If the distance from the circle center to the closest corner of the rectangle
+    // is less than the radius of the circle, the circle intersects the rectangle.
+    return (dx - halfWidth) ** 2 + (dy - halfHeight) ** 2 <= r ** 2;
+  }
+
+  /**
+   * Computes the squared distance between the centers of two rectangles.
+   *
+   * @remarks
+   * The squared distance is used to avoid the expensive square root operation.
+   * If the actual distance is needed, the square root of the squared distance can be taken.
+   */
+  public distanceSquared(other: Rectangle): number {
+    const c1 = this.center;
+    const c2 = other.center;
+    return (c1.x - c2.x) ** 2 + (c1.y - c2.y) ** 2;
+  }
+
   public equals(value: this): boolean;
   public equals(value: unknown): value is this;
   public equals(value: unknown): boolean {

@@ -332,3 +332,86 @@ test("#equals returns false for rectangles with different height", (t) => {
 
   t.equal(rect1.equals(rect2), false);
 });
+
+test("intersectsCircle() returns false when the circle center is to the left of the radius-padded rectangle", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(3, 11, 4), false);
+});
+
+test("intersectsCircle() returns false when the circle center is above the radius-padded rectangle", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(13, 3, 4), false);
+});
+
+test("intersectsCircle() returns false when the circle center is to the right of the radius-padded rectangle", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(23, 11, 4), false);
+});
+
+test("intersectsCircle() returns false when the circle center is below the radius-padded rectangle", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(13, 19, 4), false);
+});
+
+test("intersectsCircle() returns true when the circle center is inside the radius-padded rectangle on the left, but not in the corners", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(5, 11, 4), true);
+});
+
+test("intersectsCircle() returns true when the circle center is inside the radius-padded rectangle on the top, but not in the corners", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(13, 5, 4), true);
+});
+
+test("intersectsCircle() returns true when the circle center is inside the radius-padded rectangle on the right, but not in the corners", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(21, 11, 4), true);
+});
+
+test("intersectsCircle() returns true when the circle center is inside the radius-padded rectangle on the bottom, but not in the corners", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(13, 17, 4), true);
+});
+
+test("intersectsCircle() returns true when the circle center is inside the rectangle", (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(12, 12, 4), true);
+});
+
+test(`intersectsCircle() returns false when the circle center is inside the radius-padded rectangle in the top left corner,
+      but more than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(5, 5, 4), false);
+});
+
+test(`intersectsCircle() returns false when the circle center is inside the radius-padded rectangle in the top right corner,
+      but more than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(21, 5, 4), false);
+});
+
+test(`intersectsCircle() returns false when the circle center is inside the radius-padded rectangle in the bottom right corner,
+      but more than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(21, 17, 4), false);
+});
+
+test(`intersectsCircle() returns false when the circle center is inside the radius-padded rectangle in the bottom left corner,
+      but more than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(5, 17, 4), false);
+});
+
+test(`intersectsCircle() returns true when the circle center is inside the radius-padded rectangle in the top left corner,
+      and less than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(6, 6, 4), true);
+});
+
+test(`intersectsCircle() returns true when the circle center is inside the radius-padded rectangle in the top right corner,
+      and less than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(20, 6, 4), true);
+});
+
+test(`intersectsCircle() returns true when the circle center is inside the radius-padded rectangle in the bottom right corner,
+      and less than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(20, 16, 4),<
10000
/span> true);
+});
+
+test(`intersectsCircle() returns true when the circle center is inside the radius-padded rectangle in the bottom left corner,
+      and less than a radius distance away from the corner`, (t) => {
+  t.equal(Rectangle.of(8, 8, 10, 6).intersectsCircle(6, 16, 4), true);
+});
+
+test(`distanceSquared() returns the squared distance between the centers of two rectangles`, (t) => {
+  const rect1 = Rectangle.of(1, 1, 4, 2);
+  const rect2 = Rectangle.of(6, 10, 4, 8);
+
+  t.equal(rect1.distanceSquared(rect2), 13 ** 2);
+});
@@ -30,6 +30,7 @@
     "@siteimprove/alfa-device": "workspace:^0.76.0",
     "@siteimprove/alfa-dom": "workspace:^0.76.0",
     "@siteimprove/alfa-earl": "workspace:^0.76.0",
+    "@siteimprove/alfa-either": "workspace:^0.76.0",
     "@siteimprove/alfa-equatable": "workspace:^0.76.0",
     "@siteimprove/alfa-hash": "workspace:^0.76.0",
     "@siteimprove/alfa-iana": "workspace:^0.76.0",

@@ -1,8 +1,14 @@
 import { Diagnostic } from "@siteimprove/alfa-act";
+import { Element } from "@siteimprove/alfa-dom";
+import { Either } from "@siteimprove/alfa-either";
 import { Hash } from "@siteimprove/alfa-hash";
 import { Rectangle } from "@siteimprove/alfa-rectangle";
+import { Sequence } from "@siteimprove/alfa-sequence";
+
 import { WithName } from "./with-name";
 
+import * as json from "@siteimprove/alfa-json";
+
 export class WithBoundingBox extends WithName {
   public static of(message: string): Diagnostic;
 
@@ -12,35 +18,92 @@ export class WithBoundingBox extends WithName {
     message: string,
     name: string,
     box: Rectangle,
+    condition: Either<
+      WithBoundingBox.UACondition,
+      WithBoundingBox.SizeAndSpacingCondition
+    >,
+    tooCloseNeighbors: Iterable<Element>,
   ): WithBoundingBox;
 
   public static of(
     message: string,
     name?: string,
     box?: Rectangle,
+    condition?: Either<
+      WithBoundingBox.UACondition,
+      WithBoundingBox.SizeAndSpacingCondition
+    >,
+    tooCloseNeighbors?: Iterable<Element>,
   ): Diagnostic {
     if (name === undefined) {
       return new Diagnostic(message);
     }
 
-    if (box === undefined) {
+    if (
+      box === undefined ||
+      condition === undefined ||
+      tooCloseNeighbors === undefined
+    ) {
       return new WithName(message, name);
     }
 
-    return new WithBoundingBox(message, name, box);
+    return new WithBoundingBox(
+      message,
+      name,
+      box,
+      condition,
+      tooCloseNeighbors,
+    );
   }
 
   protected readonly _box: Rectangle;
+  protected readonly _condition: Either<
+    WithBoundingBox.UACondition,
+    WithBoundingBox.SizeAndSpacingCondition
+  >;
+  protected readonly _tooCloseNeighbors: Sequence<Element>;
 
-  protected constructor(message: string, name: string, box: Rectangle) {
+  protected constructor(
+    message: string,
+    name: string,
+    box: Rectangle,
+    condition: Either<
+      WithBoundingBox.UACondition,
+      WithBoundingBox.SizeAndSpacingCondition
+    >,
+    tooCloseNeighbors: Iterable<Element>,
+  ) {
     super(message, name);
     this._box = box;
+
+    // Copy the objects to ensure they are immutable from the outside.
+    this._condition = condition.either(
+      (uaCond) => Either.left({ ua: uaCond.ua }),
+      (sizeAndSpacingCond) =>
+        Either.right({
+          size: sizeAndSpacingCond.size,
+          spacing: sizeAndSpacingCond.spacing,
+        }),
+    );
+
+    this._tooCloseNeighbors = Sequence.from(tooCloseNeighbors);
   }
 
   public get box(): Rectangle {
     return this._box;
   }
 
+  public get condition(): Either<
+    WithBoundingBox.UACondition,
+    WithBoundingBox.SizeAndSpacingCondition
+  > {
+    return this._condition;
+  }
+
+  public get tooCloseNeighbors(): Iterable<Element> {
+    return this._tooCloseNeighbors;
+  }
+
   public equals(value: WithBoundingBox): boolean;
 
   public equals(value: unknown): value is this;
@@ -50,26 +113,43 @@ export class WithBoundingBox extends WithName {
       value instanceof WithBoundingBox &&
       value._message === this._message &&
       value._name === this._name &&
-      value._box.equals(this._box)
+      value._box.equals(this._box) &&
+      value._condition.equals(this._condition) &&
+      value._tooCloseNeighbors.equals(this._tooCloseNeighbors)
     );
   }
 
   public hash(hash: Hash) {
     super.hash(hash);
     this._box.hash(hash);
+    this._condition.hash(hash);
+    this._tooCloseNeighbors.hash(hash);
   }
 
   public toJSON(): WithBoundingBox.JSON {
     return {
       ...super.toJSON(),
       box: this._box.toJSON(),
+      condition: this._condition.toJSON(),
+      tooCloseNeighbors: this._tooCloseNeighbors.toJSON(),
     };
   }
 }
 
 export namespace WithBoundingBox {
   export interface JSON extends WithName.JSON {
     box: Rectangle.JSON;
+    condition: json.JSON;
+    tooCloseNeighbors: Sequence.JSON<Element>;
+  }
+
+  export interface UACondition {
+    ua: boolean;
+  }
+
+  export interface SizeAndSpacingCondition {
+    size: boolean;
+    spacing: boolean;
   }
 
   export function isWithBoundingBox(