Basic and Formula Regions

Adam Strzeboński

Wolfram Research

Region types

A region is a subset R⊆(ℝ^n) for some n∈(SubPlus[ℤ]).

Basic regions

Regions in (ℝ^n)

• EmptyRegion
• FullRegion
• Point
• Line
• Triangle
• Tetrahedron
• Simplex
• Cuboid
• Parallelepiped
• Ball
• Sphere
• Ellipsoid
• InfiniteLine
• HalfLine
• InfinitePlane
• HalfPlane
• ConicHullRegion

Regions in (ℝ^1)

• Interval

Regions in (ℝ^2)

• Rectangle
• Parallelogram
• Polygon
• Disk
• Circle

Regions in (ℝ^3)

• Polygon
• Pyramid
• Prism
• Hexahedron
• Cylinder
• Cone

Formula regions

• ImplicitRegion
• ParametricRegion

Derived regions

• RegionUnion
• RegionIntersection
• RegionDifference
• RegionSymmetricDifference
• BooleanRegion
• RegionProduct
• TransformedRegion
• InverseTransformedRegion
• RegionBoundary

Mesh regions

• MeshRegion
• BoundaryMeshRegion

Visualization for basic regions

Basic regions can be used in Graphics and Graphics3D.

Graphics[{{Green,Triangle[{{0,0},{0,1},{1,0}}]},{Red,HalfLine[{0,0},{1,1}]}}]

Graphics3D[{Opacity[0.5],{{Green,Ellipsoid[{0,0,0},{1,2,3}]},{Red,Simplex[{{0,0,2},{0,2,0},{2,0,0}}]},{Blue,ConicHullRegion[{0,0,0},{},{{-1,-1,-1},{-1,1,-1},{1,-1,-1},{1,1,-1}}]}}}]

Point membership for basic regions

Element gives True/False for constant points and regions.

Element[{1,2,3},Ball[{0,0,0},10]]

If symbolic parameters are present, Element represents a region membership assertion.

Element[{x,y,z},Ellipsoid[{a,b,c},{u,v,w}]]

RegionMember returns explicit conditions for region membership.

RegionMember[Ellipsoid[{a,b,c},{u,v,w}],{x,y,z}]

Dimension properties of basic regions

R=Simplex[{{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}}];

The dimension of the space in which the region is embeded (simple structural check).

RegionEmbeddingDimension[R]

The dimension of the region (requires nontrivial computation in general, but for basic regions the computation is usually simple).

RegionDimension[R]

Bounds for basic regions

R=Cone[{{1,2,3},{4,5,6}},7];

BoundedRegionQ[R]

RegionBounds[R]

Graphics3D[{{Green,R},{Yellow,Opacity[0.5],Cuboid[Transpose[%]]}}]

Distance properties for basic regions

RegionDistance[R, p] - the distance from the point p to the region R.
RegionNearest[R, p] - a point in the region R nearest to the point p.
SignedRegionDistance[R, p] - the signed distance from the point p to the region R.

R=Pyramid[{{-1,-1,-1},{-1,1,-1},{1,1,-1},{1,-1,-1},{0,0,1}}];
Manipulate[With[{d=N[RegionDistance[R,{x,y,z}]],sd=N[SignedRegionDistance[R,{x,y,z}]],np=N[RegionNearest[R,{x,y,z}]]},Show[Graphics3D[{{Opacity[0.5],Green,R},{Text[Style["distance = "<>ToString[PaddedForm[d,{3,3}]],Large],{-2,2,2.75}],Text[Style["signed distance = "<>ToString[PaddedForm[sd,{3,3}]],Large],{-2,2,2.1}],{Red,PointSize[Large],Point[{{x,y,z},np}]},{Red,Line[{np,{x,y,z}}]}}}],PlotRange->{{-3,3},{-3,3},{-3,3}}]],{{x,0},-3,3},{{y,0},-3,3},{{z,0},-3,3}]

Distance properties for basic regions

For many of the basic regions there are closed from formulas for distance and nearest.

RegionDistance[Disk[{0,0},r,{(π/4),((3 π)/4)}],{x,y}]

{conds,vals}=Internal`FromPiecewise[%]

RegionPlot[Evaluate[conds/.r->1],{x,-2,2},{y,-2,2},PlotLegends->{SwatchLegend[Automatic,HoldForm/@vals]},AspectRatio->Automatic]

R=Tetrahedron[];
RegionNearest[R,{x,y,z}]

{conds,vals}=Internal`FromPiecewise[%]

Show[Table[RegionPlot3D[conds[[i]],{x,-1,2},{y,-1,2},{z,-1,2},Mesh->None,PlotPoints->25,PlotStyle->Directive[Opacity[0.5],Hue[i/Length[conds]]]],{i,Length[conds]}],AxesLabel->{x,y,z}]

Measure properties of basic regions

For most basic regions measure and centroid are found using closed form formulas.

R=Tetrahedron[{{a1,a2,a3},{b1,b2,b3},{c1,c2,c3},{d1,d2,d3}}];

RegionMeasure[R]

RegionCentroid[R]

RegionMeasure[Ball[{0,0,0,0,0},r]]

Integration over basic regions

For many basic regions we have specialized integration code.

Integrate a function over a 5D ellipsoid.

(∫_({x,y,z,t,u}∈Ellipsoid[{0,0,0,0,0},{1,2,3,4,5}]))((x^2)(y^2)(z^2)(t^2)(u^2))

Integration over a region of dimension d is performed wrt. the d-dimensional Lebesgue measure.

(∫_({x,y}∈Circle[]))1

Dimensionality of vector variables is determined from the embedding dimensions of regions.

(∫_(x∈Triangle[{{0,0},{1,0},{0,1}}]))(∫_(y∈Ball[{1,2},3]))x.y

Implicit regions

A region defined as the solution set of a condition

{((Subscript[x, 1]),…,(Subscript[x, n]))∈(ℝ^n): Φ((Subscript[x, 1]),…,(Subscript[x, n]))}

is represented as

ImplictRegion[Φ,{(Subscript[x, 1]),…,(Subscript[x, n])}]

R=ImplicitRegion[(x^2)+(z^4)≤1&&(x^4)+(y^2)≤1&&(y^4)+(z^2)≤1,{x,y,z}]

RegionPlot3D[R,PlotPoints->100]

Parametric regions

A parametric region with unrestricted parameters

{((Subscript[f, 1])((Subscript[t, 1]),…,(Subscript[t, m])),…,(Subscript[f, n])((Subscript[t, 1]),…,(Subscript[t, m])))∈(ℝ^n):((Subscript[t, 1]),…,(Subscript[t, m]))∈(ℝ^m)}

is represented as

ParametricRegion[{(Subscript[f, 1]),…,(Subscript[f, m])},{(Subscript[x, 1]),…,(Subscript[x, n])}]

R=ParametricRegion[{((1-(t^2))/(1+(t^2))),((2 t (7-182 (t^2)+1001 (t^4)-1716 (t^6)+1001 (t^8)-182 (t^10)+7 (t^12)))/(((1+(t^2)))^7))},{t}]

RegionPlot[R]

A parametric region with restrictions on parameters

{((Subscript[f, 1])((Subscript[t, 1]),…,(Subscript[t, m])),…,(Subscript[f, n])((Subscript[t, 1]),…,(Subscript[t, m])))∈(ℝ^n):Φ((Subscript[t, 1]),…,(Subscript[t, m]))}

is represented as

ParametricRegion[{{(Subscript[f, 1]),…,(Subscript[f, m])},Φ},{(Subscript[x, 1]),…,(Subscript[x, n])}]

R=ParametricRegion[{{x+y,x y},(x^2)+(y^2)≤1},{x,y}]

DiscretizeRegion[R]

Point membership for formula regions

For ImplicitRegion deciding region membership is simple.

R=ImplicitRegion[(x^2)+(z^4)≤1&&(x^4)+(y^2)≤1&&(y^4)+(z^2)≤1,{x,y,z}];
RegionMember[R,{1,2,3}]

RegionMember[R,{x,y,z}]

For ParametricRegion deciding region membership amounts to quantifier elimination and can be very costly.

R=ParametricRegion[{{x+y,x y},(x^2)+(y^2)≤1},{x,y}];
RegionMember[R,{1,2}]

RegionMember[R,{x,y}]

R=ParametricRegion[{{(u^3)-v,(v^3)-u},(u^2)+(v^2)≤1},{u,v}];
RegionMember[R,{x,y}]//Timing

Dimension properties of formula regions

R=ParametricRegion[{{(u^3)-v,(v^3)-u},(u^2)+(v^2)≤1},{u,v}];

The dimension of the space in which the region is embeded (simple structural check).

RegionEmbeddingDimension[R]

The dimension of the region (requires nontrivial computation).

RegionDimension[R]

R=ImplicitRegion[(x^2)+(w^4)≤1&&(x^4)+(y^2)≤1&&(y^4)+(z^2)≤1&&(z^4)+(w^2)==1,{x,y,z,w}];

RegionDimension[R]//Timing

Bounds for formula regions

Computing bounds for formula regions amounts to solving exact constrained optimization problems.

R=ParametricRegion[{{(u^3)-v,(v^3)-u},(u^2)+(v^2)≤1},{u,v}];

BoundedRegionQ[R]

RegionBounds[R]

Show[{RegionPlot[R,PlotRange->{{-2,2},{-2,2}}],Graphics[{Yellow,Opacity[0.5],Rectangle@@Transpose[%]}]}]

Distance properties for formula regions

Distance and nearest computation for constant formula regions and constant points amounts to solving exact constrained optimization problems.

R=ParametricRegion[{{(u^3)-v,(v^3)-u},(u^2)+(v^2)≤1},{u,v}];
RegionDistance[R,{1,2}]

R=ImplicitRegion[(x^2)+(z^2)≤1&&(x^2)+(y^2)≤1&&(y^2)+(z^2)≤1,{x,y,z}];
pt=RegionNearest[R,{1,2,3}]

Show[{RegionPlot3D[R,PlotPoints->100],Graphics3D[{{Blue,Dashing[0.01],Line[{N[pt],{1,2,3}}]},{Red,PointSize[Large],Point[{N[pt],{1,2,3}}]}}]}]

Parametric problems can in principle be solved (for regions described by polynomial formulas), but can be extremely costly. The computation time is doubly-exponential in the number of parameters and the embedding dimension.

R=ImplicitRegion[(x^4)+(y^4)≤1,{x,y}];
RegionDistance[R,{a,a}]

TimeConstrained[RegionDistance[R,{a,b}],300]

Measure properties of formula regions

Measure properties of implicit regions are computed by decomposing the region into cylindrical cells bounded by algebraic functions and integrating over the cells.

R=ImplicitRegion[(x^2)+(z^2)≤1&&(x^2)+(y^2)≤1&&(y^2)+(z^2)≤1,{x,y,z}];

RegionMeasure[R]

RegionCentroid[R]

For a parametric region R we have two methods. If Mathematica can find a region S in the parameter space such that the parametrization restricted to S is a finite covering of R, then the measure is computed by integrating the square root of Gram determinant of derivative of the parametrization over S. Otherwise the measure is computed by finding an implicit representation of R and using the implicit region method (requires quantifier elimination).

R=ParametricRegion[{{Cos[a]Cos[b],Sin[a]Cos[b],Sin[b]},0≤a≤10&&0≤b≤10},{a,b}];

RegionMeasure[R]

Integration over formula regions

Integrals over implicit regions are computed by decomposing the region into cylindrical cells bounded by algebraic functions and integrating over the cells.

R=ImplicitRegion[(x^2)+(z^2)≤1&&(x^2)+(y^2)≤1&&(y^2)+(z^2)≤1,{x,y,z}];

(∫_(x∈R))x.x

For a parametric region R we have two methods. If Mathematica can find a region S in the parameter space such that the parametrization restricted to S is a finite covering of R, then the integral is computed by integrating the composition of the integrand with the parametrization multiplied by the square root of Gram determinant of derivative of the parametrization over S. Otherwise the integral is computed by finding an implicit representation of R and using the implicit region method (requires quantifier elimination).

R=ParametricRegion[{{v,(v^3)-u},(u^2)+(v^2)≤1},{u,v}];

Integrate[x y,Element[{x,y},R]]

DiscretizeRegion[R]

Derived regions

Boolean combinations of regions

• RegionUnion
• RegionIntersection
• RegionDifference
• RegionSymmetricDifference
• BooleanRegion

R=RegionIntersection[ImplicitRegion[(x^4)+(y^4)+(z^4)≤1,{x,y,z}],RegionUnion[Ball[{-1,0,0},1],Ball[{1,0,0},1]]]

RegionPlot3D[R,PlotPoints->100]

Membership conditions are Boolean combination of membership conditions of component regions.

RegionMember[R,{x,y,z}]

Transformations of regions

• TransformedRegion
• InverseTransformedRegion

R=TransformedRegion[Disk[],{((Indexed[#1,1])^2)+((Indexed[#1,2])^2),Indexed[#1,1] Indexed[#1,2]}&]

RegionPlot[R]

Finding membership conditions for a TransformedRegion requires quantifier elimination.

RegionMember[R,{x,y}]

R=InverseTransformedRegion[Disk[],{((Indexed[#1,1])^2)+((Indexed[#1,2])^2),Indexed[#1,1] Indexed[#1,2]}&]

RegionPlot[R]

Membership conditions for a InverseTransformedRegion can be obtained by a simple substitution.

RegionMember[R,{x,y}]

Cartesian product of regions

R=RegionProduct[ImplicitRegion[(x^4)+(y^4)≤1,{x,y}],Interval[{0,1}]]

RegionPlot3D[R]

RegionMember[R,{x,y,z}]

Topological boundary

For most of the basic regions we have explicit representations for the boundary.

RegionBoundary[Simplex[4]]

RegionBoundary[Ellipsoid[{0,0,0},{1,2,3}]]

For non-full-dimensional regions the boundary is the whole region.

RegionBoundary[ParametricRegion[{(x^2)+(y^2),x y,(x^3)-(y^3)},{x,y}]]

For some formula regions we can compute boundary membership conditions.

R=ImplicitRegion[y^2<x (-1+x^4)-4/(5 5^(1/4)),{x,y}];
B=RegionBoundary[R]

RegionMember[B,{x,y}]

RegionPlot[R,PlotRange->{{-1,2},{-2,2}}]

CylindricalDecomposition[y^2==x (-1+x^4)-4/(5 5^(1/4)),{x,y}]//N

Properties for derived regions

Some properties of derived regions can be easily derived from properties of the component regions. RegionDistance for RegionUnion is the minimum of distances to the component regions.

R=Block[{ph=PolyhedronData["Spikey",#]&},Block[{ce=ph["Centroid"],coords=Rationalize[N[ph["VertexCoordinates"]],0],fi=ph["FaceIndices"]},RegionUnion@@(Simplex[Prepend[Part[coords,#],ce]]&/@fi)]];
Manipulate[With[{d=N[RegionDistance[R,{x,y,z}]],np=N[RegionNearest[R,{x,y,z}]]},Show[Graphics3D[{{Opacity[0.5],Green,List@@R},{Text[Style["distance = "<>ToString[PaddedForm[d,{3,3}]],Large],{-2,2,2.75}],{Red,PointSize[Large],Point[{{x,y,z},np}]},{Red,Line[{np,{x,y,z}}]}}}],PlotRange->{{-3,3},{-3,3},{-3,3}}]],{{x,0},-3,3},{{y,0},-3,3},{{z,0},-3,3}]

SignedRegionDistance for RegionUnion cannot be derived from signed distances to the component regions.

Symbolic computation over regions

Equation and inequality solving

• Reduce
• Solve
• FindInstance
• Resolve

Optimization

• Minimize
• Maximize
• MinValue
• MaxValue
• ArgMin
• ArgMax

Integrate

Assumptions

Equation and inequality solving

Find elements of the unit sphere orthogonal to the given pair of vectors.

R=Sphere[];
u={1,1,1};
v={1,2,-1};
Solve[w∈R && u.w==0&&v.w==0,w]

Graphics3D[{{Opacity[0.5],Green,R},{Blue,Arrow[{{0,0,0},u}],Arrow[{{0,0,0},v}]},{Red,Arrow[{{0,0,0},w/.#}]&/@%}}]

Equation and inequality solving

Find the projection of a rotated 4D hypercube on (ℝ^3).

R=TransformedRegion[Cuboid[{0,0,0,0}],RotationTransform[{{0,0,0,1},{(1/2),(1/2),(1/2),(1/2)}}]];
ineqs=Reduce[(Subscript[∃, {t}]){x,y,z,t}∈R,{x,y,z}];

RegionPlot3D[ImplicitRegion[ineqs,{x,y,z}],PlotPoints->100]

Equation and inequality solving

Find integer points in an ellipsoid.

R=Ellipsoid[{0,0,0},{{5,2,3},{2,3,2},{3,2,5}}];
Solve[x∈R,x,Integers]

Graphics3D[{{Green,Opacity[0.5],R},{Red,Point[x/.%]}}]

Equation and inequality solving

Find a sphere passing through four points.

pts={{0,0,0},{1,2,3},{3,2,1},{2,1,2}};
sol=Solve[pts∈Sphere[{a,b,c},r],{a,b,c,r}]

Graphics3D[{Sphere[{a,b,c},r]/.sol,{Red,PointSize[Large],Point[pts]}}]

Another way of solving the problem.

Circumsphere[pts]

Equation and inequality solving

Solving equations and inequalities over a region requires finding an implicit description of the region. For ParametricRegion and TransformedRegion this requires quantifier elimination.

R=ParametricRegion[{{(u^2),u v,(v^2)},(u^2)+(v^2)≤1},{u,v}];
(Subscript[red, 1])=Reduce[(x^2)+(y^2)+(z^2)==(1/4)&&{x,y,z}∈R,{x,y,z}]

This is equivalent to the following quantifier elimination problem.

(Subscript[red, 2])=Reduce[(x^2)+(y^2)+(z^2)==(1/4)&&(Subscript[∃, {u,v},(u^2)+(v^2)≤1])(x==(u^2)&&y==u v&&z==(v^2)),{x,y,z},Reals]

Resolve[(Subscript[∀, {x,y,z}])((Subscript[red, 1])⧦(Subscript[red, 2])),Reals]

Optimization

Maximize a function over a 4D ball.

Maximize[{x y z t,{x,y,z,t}∈Ball[{0,0,0,0},1]},{x,y,z,t}]

Optimization

Find the distance between a parabola and a line.

u=.;v=.;
R=ImplicitRegion[y==(x^2),{x,y}];
L=InfiniteLine[{0,-1},{1,1}];
Minimize[{Norm[u-v],u∈R&&v∈L},{u,v}]

Show[{DiscretizeRegion[R,{{-2,2},{-2,2}}],Graphics[{L,{Red,PointSize[Large],Point[{u,v}/.%[[2]]]}}]},PlotRange->{{-2,2},{-2,2}}]

Optimization

Find a minimum radius disk containing the given 5 points.

SeedRandom[11];
pts=RandomInteger[{-10,10},{5,2}];
{min,pt}=Minimize[{r,pts∈Disk[{a,b},r]},{r,a,b}]

Graphics[{{Green,Disk[{a,b},r]/.pt},{Red,PointSize[Large],Point[pts]}}]

Optimization

When constraints involve a single ParametricRegion or TransformedRegion computing implicit representation of the region is not required.

R=ParametricRegion[{{Cos[t],Sin[3 t]},0≤t<2 π},{t}];
MaxValue[{(x^2)+(y^2),{x,y}∈R},{x,y}]

If two parametric regions are involved computing implicit representation  is necessary. This requires quantifier elimination and may be costly.

S=ParametricRegion[{{Cos[t],Sin[2 t]},0≤t<2 π},{t}];
MaxValue[{(x^2)+(y^2),{x,y}∈RegionIntersection[R,S]},{x,y}]//Timing

Implicit representation of R⋂S was computed and cached. Optimizing another function over the same region is much faster.

MaxValue[{(x^3)-(y^3),{x,y}∈RegionIntersection[R,S]},{x,y}]//Timing

Show[{MeshRegion[MeshCoordinates[#],MeshCells[#,1],MeshCellStyle->{All->Green}]&[DiscretizeRegion[R]],MeshRegion[MeshCoordinates[#],MeshCells[#,1],MeshCellStyle->{All->Red}]&[DiscretizeRegion[S]]}]

Assumptions

Element[x, region] statements can be used as assumptions.

Simplify[x∈Disk[],x∈Rectangle[{-(1/2),-(1/2)}]]