Shape Detection Challenge Submission

This project is my solution for the Shape Detection Challenge. All the original algorithm code is located in the src/main.ts file, inside the ShapeDetector class.

My Approach

This algorithm works without any external libraries and uses a 4-step pipeline to find shapes:

1. Binarize (Make Black & White): First, the code reads the image and converts it to a simple black-and-white (0 or 1) grid. This is done using a grayscale conversion and a threshold value.
2. Find Blobs (Find All Shapes): Next, the code scans the black-and-white grid to find all groups of connected pixels. This uses a Breadth-First Search (BFS) algorithm. Each group is called a "blob."
3. Trace Contour (Draw Outline): For each blob, the code finds its outer boundary using Moore-Neighbor Tracing. This gives us a list of points (a contour) that looks like the shape's outline.
4. Simplify and Classify (Check Corners):
   • A contour has thousands of points. We use the Ramer-Douglas-Peucker (RDP) algorithm to simplify the outline into just its main "corners" (vertices).
   • We then classify the shape by counting these corners: 3 corners is a Triangle, 4 is a Rectangle, 5 is a Pentagon, and 10 (with a special check) is a Star.
   • For Circles, we use a math formula to check its "circularity." A high score (near 1.0) means it is a circle.

How to Run

1. Install dependencies: npm install
2. Start the server: npm run dev
3. Open the local URL (like http://localhost:5173) in your browser.

A Note on My Results

My solution scores a high F1-Score (0.867) and passes almost all tests. There are two "failures" that I want to explain:

• no_shapes.png (F1 Score: 0.000): This is not a bug in my code. My code correctly detects 0 shapes. The evaluation script sees 0 detections and marks it as a failure, even though 0 is the correct answer.
• Low Area Accuracy (e.g., Pentagon): The area scores for shapes with slanted edges (like the pentagon) are lower than the ground truth. This is an expected discrepancy arising from the two different ways of measuring area:
  • My algorithm calculates the physical area by counting the exact 'shape' pixels.
  • The answer key uses a mathematical formula for an ideal, perfect shape.
  • The 'fuzzy' gray anti-aliased pixels on slanted edges are not included in the pixel count, which naturally leads to a different value than the ideal geometric one.

Citation Note

The algorithms used (Breadth-First Search, Moore-Neighbor Tracing, Ramer-Douglas-Peucker) are standard, well-known algorithms from computer science. I have implemented them from scratch based on their public descriptions.