Message Boards Message Boards

[CALL] SpacePartition: design and applications

GROUPS:

This is a call for some feedback on a small utility function I am trying to design. A few times I felt the need in a continuous partitioning of space. Could you please, after reading the post, give me some feedback on:

  • What other applications this function can be used for? (Especially higher-dimensional cases)
  • Do you have a better design suggestions?

Definition

The SpacePartition function is a continuous analog of Partition. It subdivides n-dimensional space into integer number of partitions. The result is a tensor of hyper-blocks spanning the hyperspace without gaps or overlaps. It means currently, and for simplicity of the demo, there are no block offsets, but they could be added in the future.

SpacePartition[space_List, partitions_List] :=
  Outer[List, ##, 1] & @@ MapThread[Partition[Subdivide @@ Append[#1, #2], 2, 1] &, {space, partitions}]

1D Examples

Subdividing 1D interval {2.3,5.7} into 5 consecutive intervals:

part1D = SpacePartition[{{2.3, 5.7}}, {5}]

{{{2.3, 2.98}}, {{2.98, 3.66}}, {{3.66, 4.34}}, {{4.34, 5.02}}, {{5.02, 5.7}}}

NumberLinePlot[Interval @@@ part1D]

enter image description here

2D Examples

Subdividing 2D rectangle into different number of partitions along different dimensions

part2D = SpacePartition[{{2.3, 5.7}, {1.2, 3.4}}, {7, 5}];

and visualizing as a grid

Graphics[grid2D = {FaceForm[], EdgeForm[Black], Rectangle @@ Transpose[#]} & /@ 
Flatten[part2D, 1], Frame -> True]

enter image description here

Subdivisions preserve the neighborhood structure

Graphics[{grid2D, {Opacity[.5], Rectangle @@ Transpose[#]} & /@ 
(part2D[[##]] & @@@ Tuples[{1, 2, 3}, 2])}, Frame -> True]

enter image description here

3D Examples

Subdividing 3D rectangle into different number of partitions along different dimensions

part3D = SpacePartition[{{2.3, 5.7}, {1.2, 3.4}, {-1.1, 2}}, {7, 5, 4}];

and visualizing as a 3D grid

Graphics3D[{Opacity[.6], Cuboid @@ Transpose[#]} & /@ Flatten[part3D, 2], Axes -> True]

enter image description here

Selecting random subsets of subdivisions as Region:

Table[Show[Region[Cuboid @@ Transpose[#]] & /@ 
RandomSample[Flatten[part3D, 2], 20], Axes -> True, Boxed -> True],3]

enter image description here

Application: quarterly temperatures or partitioning PlotRange

Often data are so dense it is hard to distinguish details in a standard plot.

data = WeatherData["KMDZ", "Temperature", {{2015}}];
plot = DateListPlot[data]

enter image description here

SpacePartition can be used to partition PlotRange and make a better visual

With[{pr = PlotRange /. Options[plot]},
  DateListPlot[TimeSeriesWindow[data, #], AspectRatio -> 1/10, ImageSize -> 1000,
     PlotRange -> {Automatic, {-30, 30}}, Filling -> Axis, PlotTheme -> "Detailed"] & /@
      Map[DateList, Flatten[SpacePartition[{pr[[1]]}, {4}], 1], {2}]] // Column

enter image description here

Application: box-counting method for fractal measures

Define an iterated function system (IFS) and iterate it on point sets

IFS[{T__TransformationFunction}][pl_List] := Join @@ Through[{T}[pl]]
IFSNest[f_IFS, pts_, n_Integer] := Nest[f, pts, n]

Sierpiński gasket transformation:

SierpinskiGasket = With[{\[ScriptCapitalD] = DiagonalMatrix[{1, 1}/2]},
   IFS[{AffineTransform[{\[ScriptCapitalD]}], 
     AffineTransform[{\[ScriptCapitalD], {1/2, 0}}], 
     AffineTransform[{\[ScriptCapitalD], {0.25, 0.433}}]}]];

and corresponding iterated point set

ptsSierp = IFSNest[N@SierpinskiGasket, RandomReal[1, {100, 2}], 4];
graSierp = Graphics[{PointSize[Tiny], Point[ptsSierp]}, Frame -> True]

enter image description here

Function that makes partitions

blocks[n_]:=Rectangle@@Transpose[#]&/@Flatten[N@SpacePartition[{{0,1},{0,1}},{n,n}],1]

Show[graSierp,Graphics[{FaceForm[],EdgeForm[Red],blocks[7]}]]

enter image description here

Of course number of partitions grows as a square for 2D case

Length /@ blocks /@ Range[9]

{1, 4, 9, 16, 25, 36, 49, 64, 81}

Function counting partitions that have any points in them

blockCount[pts_, n_] := Length[Select[blocks[n], MemberQ[RegionMember[#, pts], True] &]]

Accumulating data of partition count for different partition sizes

logMes = ParallelTable[Log@{k, blockCount[ptsSierp, k]}, {k, 20}];

Fitting the log-log scale of the data linearly with the slope measuring fractal dimension

fit[x] = Fit[logMes, {1, x}, x]

0.0884774 + 1.70962 x

which deviates a bit from ideal due to probably random inexact nature of IFS system

N[Log[3]/Log[2]]

1.58496

Plot[fit[x], {x, 0, 3.5}, Epilog -> {Red, PointSize[.02], Point[logMes]}]

enter image description here

Missing features

The following features could be added in future:

  • Offset parameter for overlapping or gapped partitions

  • Real (non-integer) number of partitions

Attachments:
POSTED BY: Vitaliy Kaurov
Answer
7 months ago

Hi Vitaliy,

Looks pretty useful in some cases. Though we already have Range and Subdivide which are similar/related. I would opt for a vararg (arbitrary arity) implementation:

ClearAll[SpacePartition]
SpacePartition[specs:{_,_,_Integer}...]:=Tuples[Partition[#,2,1]&/@Subdivide@@@{specs}]

and the use of Tuples rather than Outer, as it is much faster for large lists. Moreover using vararg makes the 1D case more readable and it would use the standard iterator notation of many functions (Table, Do, Sum …).

1D:

SpacePartition[{2.3, 5.7, 5}]
NumberLinePlot[Interval @@@ %]

enter image description here

2D:

SpacePartition[{1.0,5.0,6},{3.0,4.0,4}]
Graphics[Riffle[RandomColor[Length[%]],Rectangle@@@(Transpose/@%)],Frame->True]

enter image description here

The name is ok I think (or perhaps PartitionSpace), other words are already taken or have a different connotation: split, slice, segment, chop (up), cut… But it could also be implemented in the interval-world: SplitInterval or IntervalPartition and then supply intervals… however it should also return intervals then…

POSTED BY: Sander Huisman
Answer
7 months ago

@Sander Huisman, thank you for the review and quick response! This is a very nice idea. Your approach should be faster and clearer. The only thing to consider is a tensor form of my version that preserves local neighborhood of blocks. Yet it is indeed should be examined how much value does that add. And, yes, as yourself, I pondered about the name, thinking mostly about user perception. Order of space and partition was chosen in accord with other functions we have that users are probably familiar (see below). Interval and even Region crossed my mind but they are fundamentally dimension $n \leq 3$ and I wanted to steer users' minds away from low-n towards generality, and also not to make them "extract" partitions from Interval and Region objects when applications are not dealing with those. Again, thanks for the awesome feedback!

enter image description here

POSTED BY: Vitaliy Kaurov
Answer
7 months ago

Just a few minor comments:

  • Have you thought about whether the best representation is a list of intervals ({{0,1},{0,2}}) or a pair of corner points for the box ({{0,0}, {1,2}})? It depends on the most common application. Rectangle and Cuboid (which are also regions) use the latter form. Sometimes we have both variants of functions, e.g. CoordinateBounds vs CoordinateBoundingBox

  • CoordinateBoundingBoxArray is related (but different)

  • For the box counting, BinCounts may be better. (Unfortunately, BoxCounts is still not quite as fast as it should be, though.)

POSTED BY: Szabolcs Horvát
Answer
7 months ago

@Szabolcs Horvát, thanks for looking into this, very useful comments! Responses are below, as you "partitioned" them, pun intended ;-)

  • Yes, I thought of that. Indeed, Graphics likes corner specs. But in my mind, especially for higher dimensions somehow intervals were clearer. Great observation about CoordinateBounds and CoordinateBoundingBox. I agree this deserves some further thinking.

  • CoordinateBoundingBoxArray - great function I was not aware about. Very related.

  • Agree on BinCounts. But what is BoxCounts ?

POSTED BY: Vitaliy Kaurov
Answer
7 months ago

Didn't know about CoordinateBoundingBoxArray, seems to be very much related. One would have to do a nD partition on it, and get the same I guess…

POSTED BY: Sander Huisman
Answer
7 months ago

Group Abstract Group Abstract