script: Add support for polygons in `HtmlAreaElement::hit_test` (#37064)

Uses raycasting to determine whether point is in polygon

Testing: Added unittest
Fixes: None to my knowledge

---------

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

2 files changed, 39 insertions, 2 deletions

diff --git a/components/script/dom/htmlareaelement.rs b/components/script/dom/htmlareaelement.rs
index a9d94cbd7b2..535d296a29f 100644
--- a/components/script/dom/htmlareaelement.rs
+++ b/components/script/dom/htmlareaelement.rs
@@ -46,6 +46,8 @@ pub enum Area {
         bottom_right: (f32, f32),
     },
     Polygon {
+        /// Stored as a flat array of coordinates
+        /// e.g. [x1, y1, x2, y2, x3, y3] for a triangle
         points: Vec<f32>,
     },
 }
@@ -203,8 +205,28 @@ impl Area {
                     p.y >= top_left.1
             },
 
-            //TODO polygon hit_test
-            _ => false,
+            Area::Polygon { ref points } => {
+                // Ray-casting algorithm to determine if point is inside polygon
+                // https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
+                let mut inside = false;
+
+                debug_assert!(points.len() % 2 == 0);
+                let vertices = points.len() / 2;
+
+                for i in 0..vertices {
+                    let next_i = if i + 1 == vertices { 0 } else { i + 1 };
+
+                    let xi = points[2 * i];
+                    let yi = points[2 * i + 1];
+                    let xj = points[2 * next_i];
+                    let yj = points[2 * next_i + 1];
+
+                    if (yi > p.y) != (yj > p.y) && p.x < (xj - xi) * (p.y - yi) / (yj - yi) + xi {
+                        inside = !inside;
+                    }
+                }
+                inside
+            },
         }
     }
 
diff --git a/tests/unit/script/htmlareaelement.rs b/tests/unit/script/htmlareaelement.rs
index be4cb12c0cc..becfd17b88a 100644
--- a/tests/unit/script/htmlareaelement.rs
+++ b/tests/unit/script/htmlareaelement.rs
@@ -187,4 +187,19 @@ fn test_hit_test_polygon() {
         points: vec![7.0, 7.5, 8.2, 9.0, 11.0, 12.0],
     };
     assert!(!poly2.hit_test(&Point2D::new(10.0, 5.0)));
+    let poly3 = Area::Polygon {
+        points: vec![0.0, 0.0, 5.0, 0.0, 5.0, 5.0, 0.0, 5.0],
+    };
+    assert!(poly3.hit_test(&Point2D::new(1.0, 1.0)));
+    assert!(poly3.hit_test(&Point2D::new(2.0, 4.0)));
+    assert!(poly3.hit_test(&Point2D::new(4.0, 2.0)));
+    assert!(!poly3.hit_test(&Point2D::new(6.0, 0.0)));
+    assert!(!poly3.hit_test(&Point2D::new(0.0, 6.0)));
+    assert!(!poly3.hit_test(&Point2D::new(6.0, 6.0)));
+    // Concave polygon test
+    let poly4 = Area::Polygon {
+        points: vec![0.0, 0.0, 1.0, 1.0, 2.0, 0.0, 2.0, 2.0, 0.0, 2.0],
+    };
+    assert!(poly4.hit_test(&Point2D::new(1.5, 1.5)));
+    assert!(!poly4.hit_test(&Point2D::new(1.0, 0.0)));
 }