Overview
Marching Squares classifies each grid cell by whether its corners are above an isovalue, then emits contour segments from a lookup table.
CoreSource checked
Marching Squares
Extracts 2D contour lines from a scalar grid using cell case tables.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Contour Extraction
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
scalar gridisovalue thresholdcorner bitmaskedge interpolation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(cells)
Average
O(cells)
Worst
O(cells)
Space
O(segments)
When to Use
- Use when collision and intersection tests needs scalar grid.
- Use when the input matches the assumptions behind contour Extraction.
When Not to Use
- Avoid when floating-point robustness is critical and no tolerance strategy is defined.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Extracts 2D contour lines from a scalar grid using cell case tables
- Uses scalar grid and isovalue threshold to guide the work.
- Produces geometric relation, simplified shape, or constructed geometry.
Use Cases
- Collision and intersection tests
- Shape analysis
- Geometry processing
Inputs
- Points, segments, polygons, or meshes
- Query shape or tolerance
Outputs
- Geometric relation, simplified shape, or constructed geometry
Key Formulas (1)
Edge interpolation
p = p1 + ((iso − v1) / (v2 − v1)) · (p2 − p1)
p = p1 + ((iso - v1) / (v2 - v1)) * (p2 - p1)Finds where the contour crosses an edge between scalar samples.
Pseudocode
- 1.Prepare the inputs and state needed for Marching Squares.
- 2.Apply the scalar grid step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return geometric relation, simplified shape, or constructed geometry.
Canonical Example
- Input
- Marching Squares with a minimal inspectable input
- Output
- Geometric relation, simplified shape, or constructed geometry
- Explanation
- Marching Squares applies scalar grid to produce geometric relation, simplified shape, or constructed geometry.
Implementation Notes
- Use robust orientation and tolerance checks for boundary cases.
- Keep the scalar grid step separate enough to test independently.
Common Pitfalls
- Degenerate cases such as collinear points or shared edges often need explicit handling.
- Forgetting to check edge cases can make Marching Squares look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasDraw the input shapes, active tests, and generated geometric result.
Step 1 of 4: Prepare the inputs and state needed for Marching Squares.
geometry-mechanismNotes
Marching Squares should be used with the assumptions and tradeoffs of contour Extraction in mind.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Marching Squares's geometric model, data structures, and robustness concerns.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Marching Squares's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageIt emits contour segments based on interpolated grid-edge crossings.
Conceptual neighborMarching Cubes
Marching Squares is the 2D analogue of Marching Cubes.
Related Algorithms
Tags
Computational GeometrySurface ExtractionGrid SearchGeometry