Overview
The in-circle predicate evaluates the orientation-sensitive determinant defined by three triangle vertices and a query point, commonly to decide Delaunay edge flips.
CoreSource checked
In-Circle Test
Tests whether a point lies inside, on, or outside the circumcircle of three oriented points.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Geometric Predicates
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
delaunay predicatesgeometric predicatesgeometric predicategeometric primitivesgeometry
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)
When to Use
- Use inside Delaunay triangulation, mesh repair, and geometric predicates that need a circumcircle decision.
- Use when the input orientation convention is known and consistent.
When Not to Use
- Avoid naive floating-point predicates when points can be nearly cocircular.
- Avoid using it without first defining how degenerate triangles are handled.
What It Does
- In-Circle Test uses testing whether a point lies inside the circumcircle of a triangle for delaunay predicates
- Organizes the work around delaunay predicates and geometric predicates.
Use Cases
- Production and research workloads requiring geometric predicates via three triangle vertices and a query point, commonly to decide Delaunay edge flips.
- Geometric Predicates pipelines where O(1) time and O(1) space fit system constraints.
- Engineering comparisons against Orientation Test and Shewchuk Adaptive Predicates when tuning geometric predicates.
Inputs
- Points, segments, polygons, or geometric primitives
- Query or construction parameters
Outputs
- Geometric decision, measurement, or constructed structure
Pseudocode
- 1.Ensure the three triangle points have a known orientation
- 2.Translate coordinates so the query point is the origin
- 3.Evaluate the in-circle determinant
- 4.Interpret the determinant sign using the orientation convention
- 5.Return inside, on, or outside
Canonical Example
- Input
- triangle (0,0), (1,0), (0,1) and point (0.25,0.25)
- Output
- inside the circumcircle
- Explanation
- The query point lies nearer the triangle's circumcenter than the circle radius.
Implementation Notes
- Check or enforce triangle orientation before interpreting the determinant sign.
- Use exact or adaptive predicates for robust triangulation code.
- Treat determinant values near zero as boundary cases if using tolerances.
Common Pitfalls
- The sign of the result depends on triangle orientation.
- Nearly cocircular points can flip decisions under ordinary floating-point arithmetic.
- Collinear triangle vertices do not define a stable circumcircle.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow testing whether a point lies inside the circumcircle of a triangle on a small delaunay predicates example.
Step 1 of 5: Ensure the three triangle points have a known orientation
geometry-mechanismNotes
The predicate is simple algebraically but reliability depends on numeric robustness.
Sources (2)
What each reference supports for this entry.
Shewchuk Robust Predicates
PaperSpecific reference for In-Circle Test's robust orientation, in-circle, or adaptive geometric predicate behavior.
Open sourceComputational Geometry: Algorithms and Applications
BookTextbook support for In-Circle Test's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Conceptual neighborLine Segment Intersection
Geometry · Foundation
Both use geometric predicates ideas for related delaunay predicates problems.
Compare with thisRelationships
View full relationship pageConceptual neighborOrientation Test
Both use geometric predicates ideas for related delaunay predicates problems.
Conceptual neighborShewchuk Adaptive Predicates
Both use geometric predicates ideas for related delaunay predicates problems.
Conceptual neighborLine Segment Intersection
Both use geometric predicates ideas for related delaunay predicates problems.
Related Algorithms
Tags
GeometryComputational Geometry