# [CALL] SpacePartition: design and applications

Posted 1 year ago
2245 Views
|
5 Replies
|
24 Total Likes
|

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] # 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] Subdivisions preserve the neighborhood structure

Graphics[{grid2D, {Opacity[.5], Rectangle @@ Transpose[#]} & /@
(part2D[[##]] & @@@ Tuples[{1, 2, 3}, 2])}, Frame -> True] # 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] Selecting random subsets of subdivisions as Region:

Table[Show[Region[Cuboid @@ Transpose[#]] & /@
RandomSample[Flatten[part3D, 2], 20], Axes -> True, Boxed -> True],3] # 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] 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[]}, {4}], 1], {2}]] // Column # 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]


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] 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}]] Of course number of partitions grows as a square for 2D case

Length /@ blocks /@ Range


{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/Log]


1.58496

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

The following features could be added in future:

• Offset parameter for overlapping or gapped partitions

• Real (non-integer) number of partitions Attachments: Answer
5 Replies
Sort By:
Posted 1 year 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 @@@ %] 2D: SpacePartition[{1.0,5.0,6},{3.0,4.0,4}] Graphics[Riffle[RandomColor[Length[%]],Rectangle@@@(Transpose/@%)],Frame->True] 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… Answer
Posted 1 year 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!  Answer
Posted 1 year 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.) Answer
Posted 1 year 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 ? Answer
Posted 1 year 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… Answer