-
Notifications
You must be signed in to change notification settings - Fork 78
/
bisectfraction.jl
59 lines (46 loc) · 1.67 KB
/
bisectfraction.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# ------------------------------------------------------------------
# Licensed under the MIT License. See LICENSE in the project root.
# ------------------------------------------------------------------
"""
BisectFractionPartition(normal, fraction=0.5, maxiter=10)
A method for partitioning spatial objects into two half spaces
defined by a `normal` direction and a `fraction` of points.
The partition is returned within `maxiter` bisection iterations.
"""
struct BisectFractionPartition{Dim,T} <: PartitionMethod
normal::Vec{Dim,T}
fraction::Float64
maxiter::Int
function BisectFractionPartition{Dim,T}(normal, fraction, maxiter) where {Dim,T}
new(normalize(normal), fraction, maxiter)
end
end
BisectFractionPartition(normal::Vec{Dim,T}, fraction=0.5, maxiter=10) where {Dim,T} =
BisectFractionPartition{Dim,T}(normal, fraction, maxiter)
BisectFractionPartition(normal::NTuple{Dim,T}, fraction=0.5, maxiter=10) where {Dim,T} =
BisectFractionPartition(Vec(normal), fraction, maxiter)
function partitioninds(rng::AbstractRNG, domain::Domain, method::BisectFractionPartition)
bbox = boundingbox(domain)
n = method.normal
f = method.fraction
c = coordinates(center(bbox))
d = diagonal(bbox)
# maximum number of bisections
maxiter = method.maxiter
iter = 0
a = c - d / 2 * n
b = c + d / 2 * n
subsets = Vector{Int}[]
metadata = Dict()
while iter < maxiter
m = (a + b) / 2
bisectpoint = BisectPointPartition(n, Point(m))
subsets, metadata = partitioninds(rng, domain, bisectpoint)
g = length(subsets[1]) / nelements(domain)
g ≈ f && break
g > f && (b = m)
g < f && (a = m)
iter += 1
end
subsets, metadata
end