Barycentric Coordinates for Point-in-Triangle Tests

Topic Overview

Expressing Any Point as a Weighted Blend

Given triangle vertices A, B, and C, any point P in the plane can be written as:

cCopy
Loading…

The triple (u, v, w) is the barycentric coordinate of P relative to the triangle. Geometric meaning:

• All coordinates positive: P is strictly inside
• One coordinate zero: P lies on an edge
• Any coordinate negative: P is outside

Edge Functions Compute Coordinates

Barycentric coordinates come from edge functions, a 2D cross product:

cCopy
Loading…

For a counter-clockwise triangle ABC:

• u = edge(P, B, C) / edge(A, B, C)
• v = edge(P, C, A) / edge(A, B, C)
• w = edge(P, A, B) / edge(A, B, C)

For example, if all three numerators are non-negative for pixel center P, that pixel is inside the triangle. The denominator is twice the signed triangle area. GPUs compute these values in fixed-function rasterizer hardware for attribute interpolation.

For This Exercise

You will compute barycentric coordinates for test points and determine whether each lies inside a given triangle. This task asks you to implement edge functions and print inside/outside results. The same math underlies Pixar's REYES renderer and every ray-triangle intersection test in path tracers like PBRT.

Your Task

Barycentric coordinates say where a point sits relative to a triangle's corners: P = w0·A + w1·B + w2·C with w0 + w1 + w2 = 1. Rasterizers get them almost for free from the edge functions, and use them for both the inside test and attribute interpolation. Compute them exactly, as reduced fractions. Classify points as inside, outside (naming the edges they are beyond), on an edge, or at a vertex, and interpolate a per-vertex attribute.

Input

# starts a comment line.

cCopy
Loading…

Rules

• Edge function: E(P, Q, R) = (Qx-Px)(Ry-Py) - (Qy-Py)(Rx-Px). Twice the signed area is E(A, B, C).
• Weights: w0 = E(B, C, P), w1 = E(C, A, P), w2 = E(A, B, P), and the barycentrics are wᵢ / area.
• Pixel centres: compute everything on a doubled grid (vertices × 2, centre = (2PX+1, 2PY+1)). The raw weights and the area are then 4 times larger. Print those raw values.
• Classification: use signs relative to the area's sign.
  • Any negative weight means outside (beyond BC CA AB), listing the negative ones in that order (w0 ↔ BC, w1 ↔ CA, w2 ↔ AB).
  • Otherwise, two zeros mean at vertex A|B|C (the non-zero one), one zero means on edge BC|CA|AB, and none means inside.
• Attribute: (w0·VA + w1·VB + w2·VC) / area, printed as a reduced fraction and as a decimal with 4 places, rounded half away from zero.

Output

cCopy
Loading…

• Fractions: reduced, with the sign on the numerator, and written as an integer when the denominator is 1. The winding is positive winding or negative winding.
• Errors:
  • tri: AX AY BX BY CX CY, tri: coordinates within +-10000
  • tri: degenerate (zero area) (the previous triangle is kept)
  • attr: A B C
  • point: X Y / pixel: X Y, point: define a triangle first
  • unknown command X

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Everything is integer arithmetic: edge functions, fraction reduction with a GCD, and the rounded decimal.
2. The classification must work for both windings. Compare signs against the area's sign, not against zero.

Hidden tests cover a clockwise (negative) triangle, points on each edge and at each vertex, a point beyond two edges, pixel centres, negative and fractional attribute results, and input errors.