liveBook · Manning

Point-in-triangle predicate

As explained in Geometry for Programmers

A point-in-triangle predicate determines whether a point lies inside, on the boundary of, or outside a specified triangle.

A point-in-triangle predicate receives three 2D vertices and a candidate point, then decides whether the candidate lies inside the triangle. A practical solution uses cross-product signs to turn geometric orientation into simple Boolean tests. section 9.3.3

The cross-product method works by:

  • Embedding each 2D point in the 3D x-y plane by adding a zero z-coordinate. section 9.3.3
  • Computing the cross product for the candidate relative to each triangle side; only the z-coordinate remains, representing signed area. section 9.3.3

Boolean implementation

A compact implementation compares each candidate-to-vertex vector with the corresponding side vector and combines the three sign checks with and. The alternative listing expands each comparison into the equivalent cross-product expression.

How Geometry for Programmers covers it

How deep it goes
Explains the 3D embedding, signed-area orientation, and Boolean implementation, without developing every alternative method.
Examples
Uses three 2D vertices, one candidate point, orientation diagrams, and Python predicate listings.
What it assumes
Assumes familiarity with 2D points and vectors while developing the needed cross-product interpretation.
What you can do after
Apply cross-product orientation tests to implement a point-in-triangle function.
How it connects
Connects cross products, vectors, signed area, orientation, and triangle geometry.
Cover of Geometry for Programmers
liveBookmanning.com
Read Geometry for Programmers on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Geometry for Programmers. The section links point to the parts of the book it draws on.