Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 50 ยท Polygons and Filling

Polygons: Types and Representation

Learn convex, concave and self-intersecting polygons, vertex lists, winding order and signed area, plus the even-odd and nonzero winding inside tests.

Almost every solid shape in computer graphics is built from polygons: closed figures bounded by straight line segments. Icons and fonts are outlines made of polygons and curves. A 3D character is a mesh of thousands of triangles, and each triangle is a polygon. Before we can fill, clip or transform polygons, we need to agree on what they are, how to store them, and how to decide which points are inside.

A polygon is defined by an ordered list of vertices V0, V1, ..., Vn-1. The edges join each vertex to the next one, and the last vertex joins back to the first: V0V1, V1V2, ..., Vn-1V0. A list with a repeated first vertex at the end is a common mistake; the closing edge is implied.

Kinds of polygons

Polygons are classified by how their edges behave.

  • Simple: no two edges cross, and edges touch only at shared vertices. The boundary is one loop without self-contact.
  • Self-intersecting (complex): some edges cross each other, like a bow tie or a five-pointed star drawn in one stroke.
  • Convex: a simple polygon where the segment between any two points inside the polygon stays inside. Equivalently, it turns the same way at every vertex and all its interior angles are at most 180 degrees.
  • Concave: a simple polygon that is not convex. It has at least one reflex vertex, with an interior angle greater than 180 degrees, so some segments between interior points leave the polygon.

Convexity matters because many algorithms are much easier on convex shapes: clipping, filling, collision tests, and splitting into triangles. A convex polygon with n vertices can be cut into n - 2 triangles simply by drawing a fan from one vertex. Concave polygons need more work (ear clipping is a common method), and self-intersecting polygons need a rule that says which regions count as inside.

flowchart TB
  P["Polygon"] --> S["Simple<br/>(no crossing edges)"]
  P --> C["Self-intersecting"]
  S --> V["Convex"]
  S --> N["Concave<br/>(has a reflex vertex)"]
  C --> R["Needs a fill rule:<br/>even-odd or nonzero"]

Classification of polygons. Only simple polygons have an unambiguous inside.

A polygon can also have holes, such as the letter "O" or a washer. The usual representation is a list of several closed contours: an outer boundary plus one contour per hole.

Representing polygons

The simplest representation is an array of vertices:

JavaScript
const house = [
  { x: 10, y: 60 }, { x: 10, y: 30 }, { x: 40, y: 5 },
  { x: 70, y: 30 }, { x: 70, y: 60 }
];

For a single polygon that is all you need. When polygons share vertices (as in a mesh), storing each corner again wastes memory and makes it impossible to tell that two faces touch. The standard fix is an indexed representation: one array of unique points and, for each polygon, a list of indices into it. We use that in the meshes lesson. A third form is an explicit edge list, which fill algorithms use: each edge records its two end points, and the scanline fill lesson builds an edge table from it.

Winding order and signed area

The order of the vertices matters. Walking around the boundary you can go clockwise or counterclockwise, called the winding order. Many systems rely on it: 3D renderers use it to decide which side of a triangle faces the viewer, and fill rules use it to decide what is inside.

The shoelace formula computes the signed area of a polygon from its vertices:

TEXT
A = 1/2 * sum over i of ( x_i * y_(i+1) - x_(i+1) * y_i )

The magnitude is the area. The sign gives the winding order: in a coordinate system with y pointing up, positive means counterclockwise. On a screen, where y points down, the picture is flipped, so a positive result looks clockwise. Keep this in mind whenever you port code between math textbooks and canvas.

The same cross-product idea tells you which way a polygon turns at a vertex. For three consecutive vertices a, b, c:

TEXT
cross = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x)

The sign of cross is the turn direction (left or right). In a convex polygon every turn has the same sign. A reflex vertex of a concave polygon turns the other way.

"All turns have the same sign" is not enough for convexity. A five-pointed star drawn as one stroke (a pentagram) turns the same way at all five vertices, yet it is self-intersecting and wraps around its center twice. A robust test also checks that the exterior angles add up to exactly one full turn (360 degrees). The code below does both.

JS Classify four polygons

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The square comes out simple and convex. The L shape is simple but concave. The bow tie fails the simplicity test and the convex test. The pentagram passes the sign test but fails the full-turn test, as the warning predicted.

Is a point inside? Two rules

Given a polygon and a point P, which side is P on? For simple polygons everyone agrees. For polygons with holes or self-intersections, two standard rules give different answers.

Even-odd rule (parity). Cast a ray from P in any direction (say, to the right) and count how many edges it crosses. If the count is odd, P is inside. If it is even, P is outside. Each crossing flips inside and outside, like crossing a fence.

Nonzero winding rule. Walk along the boundary, and count how many times it winds around P: each edge that crosses the ray counterclockwise adds 1 and each clockwise crossing subtracts 1. If the winding number is not zero, P is inside.

For a simple polygon the two rules agree. They differ where the boundary overlaps itself:

  • In the center pentagon of a pentagram the boundary winds around the point twice. Even-odd says outside (an even number of crossings), nonzero says inside (winding number 2).
  • For a square with a square hole, even-odd always leaves the hole empty. Nonzero leaves it empty only if the inner contour runs the opposite way (winding 1 - 1 = 0). If both contours run the same direction, the hole is filled (winding 2).

Here are both tests in code:

JavaScript
function evenOdd(px, py, contours) {
  let inside = false;
  for (const poly of contours) {
    for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
      const a = poly[i], b = poly[j];
      if ((a.y > py) !== (b.y > py) &&
          px < ((b.x - a.x) * (py - a.y)) / (b.y - a.y) + a.x) {
        inside = !inside;
      }
    }
  }
  return inside;
}

function windingNumber(px, py, contours) {
  let w = 0;
  for (const poly of contours) {
    for (let i = 0; i < poly.length; i++) {
      const a = poly[i], b = poly[(i + 1) % poly.length];
      const left = (b.x - a.x) * (py - a.y) - (px - a.x) * (b.y - a.y);
      if (a.y <= py) { if (b.y > py && left > 0) w++; }
      else if (b.y <= py && left < 0) w--;
    }
  }
  return w;                       // inside when w !== 0
}

The (a.y > py) !== (b.y > py) test is the careful part. It treats each edge as covering its lower end but not its upper end (a half-open interval), so a ray that passes exactly through a vertex is counted once, not twice, and horizontal edges are ignored. The scanline fill algorithm in the next lesson uses the same convention.

flowchart LR
  P["Point P"] --> R["Cast a ray<br/>to the right"]
  R --> E["Even-odd:<br/>count crossings,<br/>odd = inside"]
  R --> W["Nonzero:<br/>+1 / -1 per crossing,<br/>sum != 0 = inside"]

Both rules start from the same ray; they differ in how they score the crossings.

Move the mouse over the shapes below. The left canvas is filled with fill("evenodd"), the right with fill("nonzero"), and the text shows what our own functions return for the point under the mouse. Pick a shape from the menu.

Live inside test: even-odd vs nonzero

Try the center of the pentagram on each canvas, then switch to the two squares. With opposite directions both rules agree and leave the hole open. With the same direction only even-odd does.

Practical advice

  • Pick a winding convention for your whole program (counterclockwise on screen is typical in 3D, front faces) and enforce it when loading data. signedArea is the cheapest way to detect and reverse a polygon.
  • Remove duplicate consecutive vertices and zero-area slivers; they cause divisions by zero in many algorithms.
  • For hit tests on the web, ctx.isPointInPath(path, x, y, rule) does the same job natively. Writing it yourself is how you learn what it computes.
  • Floating-point vertices can leave tiny gaps or overlaps between neighbors. Sharing vertices through indices avoids this.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which statement describes a concave polygon?

    A concave polygon is simple but not convex; the vertex with an interior angle above 180 degrees is called reflex.
  2. 2. A pentagram drawn in one stroke has the same turn direction at every vertex. Why is it still not convex?

    Same-direction turns are necessary but not sufficient. The boundary winds twice around the center, so the total turning is 720 degrees instead of 360.
  3. 3. A point lies in the central pentagon of a pentagram. What do the two rules say?

    The ray crosses an even number of edges, so even-odd says outside. The boundary winds around the point twice, so the winding number is 2 and nonzero says inside.
  4. 4. In a y-up coordinate system, what does a positive result from the shoelace formula mean?

    Positive signed area means counterclockwise in a y-up system. On a y-down screen the same sign looks clockwise.
  5. 5. Why does the inside test treat each edge as covering its lower end but not its upper end?

    The half-open convention prevents double counting at shared vertices and avoids division by zero on horizontal edges.

Summary

  • A polygon is an ordered vertex list with an implied closing edge; holes need extra contours.
  • Simple polygons do not cross themselves; convex ones also have no reflex vertex, which makes filling, clipping and triangulating easier.
  • Winding order is found from the sign of the shoelace signed area (the meaning of the sign depends on whether y points up or down).
  • Convexity needs consistent turn signs and a total turning of exactly one full turn.
  • The even-odd rule counts ray crossings; the nonzero rule sums signed crossings into a winding number.
  • The rules agree on simple polygons and differ on self-overlaps and same-direction holes.

Next: Scanline Polygon Filling.