{'fraction_non_alphanumeric': 0.04688261081344374, 'fraction_numerical': 0.007001948368241598, 'mean_word_length': 3.744367417677643, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Intersecting IFS Fractals with Lines

IFS fractals - the attractors of Iterated Function Systems - have motivated plenty of research to date, partly due to their simplicity and applicability in various fields, such as the modeling of plants in computer graphics, and the design of fractal antennas. The statement and resolution of the Fractal-Line Intersection Problem is imperative for a more efficient treatment of certain applications. This paper intends to take further steps towards this resolution, building on the literature. For the broad class of hyperdense fractals, a verifiable condition guaranteeing intersection with any line passing through the convex hull of a planar IFS fractal is shown, in general R^d for hyperplanes. The condition also implies a constructive algorithm for finding the points of intersection. Under certain conditions, an infinite number of approximate intersections are guaranteed, if there is at least one. Quantification of the intersection is done via an explicit formula for the invariant measure of IFS.

Falconer [7] provides an extensive overview of Fractal Geometry, summarizing the work of several researchers. In particular, he examines the behaviour of Euclidean attractors under projections to hyperplanes. When the projection is carried out in R 2 or R 3 onto a line or plane, we can think of the resulting set as the "shadow" of the fractal, which may be analyzed for its own dimension. Furthermore, we may ask how many fractal points are projected to a certain point on the line, or if there are any at all, in essence trying to uncover the distribution of such a projection. But what is the fundamental underlying question here? Upon further thought, we may realize that the projection problem breaks down into two main questions, since the directional ray of projection can be thought of as an intersecting line.

Preliminary Concepts
The attractors of Iterated Function Systems -IFS Fractals -were first defined and examined by Hutchinson [13], and may be the most elementary fractals possible. They are the attractors of a finite set of affine linear contraction mappings on R d -the "function system" -which when combined and iterated to infinity, converges to an attracting limit set, the IFS fractal itself. We begin by defining the generating maps of an IFS Fractal, and go on to stating its existence and uniqueness.

IFS Fractals
Definition 1.1 Let an affine contraction mapping (briefly: contraction) T : R d R d be defined for all z ∈ R d as T (z) := p + M (z − p) where p ∈ R d is the fixed point of T , and the invertible M ∈ R d×d is the factor of T , with M 2 < 1.
When T is a similitude over the complex plane (d = 2), it may be written in the form T (z) := p + ϕ(z − p) where z, p ∈ C and ϕ = λe θi ∈ C, with λ ∈ (0, 1) and θ ∈ (−π, π]. In higher dimensions, similitudes are M = λR with a unitary R.   Proof The proof follows from the Banach Fixed Point Theorem, once we show that H is contractive in the Hausdorff metric over compact sets [13]. Definition 1.4 Let the set F in the above theorem be called a fractal generated by an IFS with Hutchinson operator H (briefly: IFS fractal). Denote T 1 , . . . , T n = T := F .

The Address Set
The address set results from the iteration of the Hutchinson operator, and it is a way to label the location of each fractal point. Since we can start the iteration towards F with any compact set, we will choose the primary fixed point, which is any point in P of our preference. Definition 1.5 Let N j := N × . . . × N be the index set to the j-th Cartesian power, and call this j the iteration level. Then define the address set as A := {0} ∪ ∞ j=1 N j . For any a ∈ A denote its k-th coordinate as a(k), k ∈ N. Let its dimension or length be denoted as |a| ∈ N so that a ∈ N |a| and let |0| := 0. Define the map with address a ∈ A acting on any z ∈ R d as the function composition T a (z) := T a(1) • . . . • T a(|a|) (z). Let the identity map be T 0 := Id.
The above definition of the address set revises and unites the two standard definitions in use. Common ways include identifying addresses with decimal number representations with a certain basis, and strings of letters usually for a small number of maps. Our formal language representation replaces the cumbersome decimal notation while accounting for finite addresses, by using vectors of numbers preferable to the string formalism when |N | > 24. Theorem 1.2 For any primary fixed point p ∈ P we have We call this the address generation of F .
Proof The proof follows from Theorem 1.1 with either of the initial sets {p} or P. Definition 1.6 Let the address adr(f ) of a fractal point f ∈ F with respect to a primary fixed point p ∈ P be the shortest address a ∈ A for which T a (p) = f .

Hyperdense Fractals
Definition 1.7 Let an IFS fractal in R d be hyperdense if any hyperplane that intersects its convex hull, also intersects the Hutchinson of its convex hull. We will call an IFS fractal a chain fractal, if the Hutchinson of its convex hull is connected. Proof Denote the fractal F = T 1 , . . . , T n and its convex hull C F := Conv(F ). First we see that for any T ∈ T we have T (Conv(S)) = Conv(T (S)) since T is affine. We also note that for any S 1 , . . . , since the convex combination of convex combinations, is a convex combination. Considering the fact that H(F ) = F as well as the above ideas, we have that meaning that C F = Conv(H(C F )). Since F is compact so is C F and thus H(C F ), since H is continuous. We now turn to showing that F is hyperdense. Let us take any hyperplane Otherwise L separates the space into two half spaces, with h 1 in one and h 2 in the other. Since F is a chain fractal, we know that H(C F ) is connected, thus it is path-connected, so there is a path γ ⊂ H(C F ) connecting h 1 and h 2 . Since h 1,2 are on separate sides of L, we must have that L ∩ γ = ∅. This can be shown by parametrizing γ : [0, 1] R d and writing the plane as Thus T −1 a also exists, and it is also an affine mapping, so it takes the hyperplane L into another hyperplane L .  Proof The proof is based on Cantor's Intersection Theorem and the address generation of F = T 1 , . . . , T n ⊂ R d in Theorem 1.2. We will show that the hyperdensity of F implies a decreasing sequence of compact sets, which tend to a point by Cantor's Intersection Theorem. The index sequence itself will correspond to an address, which in the limit locates a fractal point, since the fractal is the closure of all possible addresses. Let us now begin the proof. If a hyperplane L intersects F , it must clearly intersect C F := Conv(F ). On the other hand, if L intersects C F , by the fractal's hyperdensity, it also intersects H(C F ). So L must intersect T k 1 (C F ) for some k 1 ∈ N . Let this intersection be denoted as Continuing to apply Lemma 1.1 in the above recursive procedure, by induction we get a strictly monotonically decreasing sequence (since T k , k ∈ N are contractive) of compact sets in R d : I 1 ⊃ I 2 ⊃ . . . ⊃ I j ⊃ . . . each with a corresponding address composition: According to Cantor's Intersection Theorem ∞ j=1 I j = ∅ and it contains a single point f ∈ R d , since the address composition contracts to a point in the limit. Starting with any p ∈ P ∩ C F we have that f = lim j→∞ T k 1 • . . . • T k j (p) ∈ F by the address generation of F , so L intersects F in f . Note that such an intersection may not be unique, since in our recursive proof, we only chose one indexed set in the Hutchinson union at each step, though L may intersect multiple. The above is under the condition that F is hyperdense. If it is not, then by definition there is a hyperplane which intersects C F but not H(C F ). Since F ⊂ H(C F ) this hyperplane will not intersect F , countering the equivalence.

Corollary 2.1 A line intersects a chain fractal in R 2 if and only if it intersects its convex hull.
Algorithm 2.1 (Fractal-Line Intersection) Let F = T 1 , . . . , T n be a hyperdense fractal (possibly a chain fractal), and assume that its convex hull C F is known explicitly. Furthermore, let L be our line, and ε > 0 an arbitrary stopping parameter.
Step 0: a := (0), I := ∅ Step 1: Step 2: Proof It follows directly from the proof of Theorem 2.1. The algorithm finds a union of intervals -each with length below ε -that covers the points of intersection of the line and the fractal.

Approximate Intersection
We now turn to examining the second question posed earlier, namely the number of intersections within some ε > 0 accuracy. These results are also relevant for applied reasons, such as the signal-reception efficiency of fractal antennas. If an antenna is designed so that it is hyperdense -possibly a chain fractal -then not only will it intercept all signal planes crossing its convex hull -making it space-efficient -but it will do so an infinite number of times, in an approximate sense.

Theorem 2.2
If an open set has a common point with an IFS fractal, then it has an uncountably infinite number.
Proof Let S ⊂ C the open set and f ∈ F ∩ S. We may suppose that f has a finite address a ∈ A, |a| < ∞, since in the address generation of F , the fractal points with a finite address are dense in F , which is their closure according to Theorem 1.2. So we may replace f with another fractal point f that has a finite address, and which is close enough to f to be still be an element of S. Thus we may suppose that f has a finite address, with a corresponding map T a and primary fixed point p, meaning f = T a (p), p ∈ P. Denote the contraction belonging to p as T ∈ T . Let ε > 0 be the radius of some ball centered at f -denoted by B := B(f, ε ) -that is still contained in S. If we show that there are an uncountably infinite number of fractal points in B , then that implies the theorem. Both of the above corollaries follow directly from the theorem. The next theorem is of a slightly different nature, and is not implied by it. We restrict ourselves to IFS fractals in the complex plane, generated by an IFS of similitudes.

Theorem 2.3
Let T be an IFS with at least one map T ∈ T having a rotation angle ϑ for which ϑ 2π is irrational. Then any line L that intersects F = T in some point f with a finite address, intersects it in at least a countably infinite number of points, with any ε > 0 angular accuracy around f , meaning The address of f is finite, meaning that f = T a (p), p ∈ P, a ∈ A, |a| < ∞.
Let us transform back f and L to p ∈ P by T −1 a . Then we have that p = T −1 a (f ), and denote L := T −1 a (L) which is also a line. The ε angular neighborhood of L around f is transformed by T −1 a to an ε angular neighborhood of L around p. Clearly p ∈ L since f = T a (p) ∈ L = T a (L ). For the theorem to hold, it is sufficient to find an infinite number of fractal points within the angular neighborhood of L , since we can map these points with T a to the angular neighborhood of L. Let us choose any q ∈ F, r ∈ L , with α := arg(q−p), β := arg(r−p). Then arg(T k (q)−p) = (kϑ + α) mod 2π and the iterations of q by T will be along a logarithmic spiral around p. We will show that the iterations visit the ε angular neighborhood of L infinitely often. We have supposed that ϑ 2π is irrational, so by the Equidistribution Theorem, the sequence (kϑ mod 2π) k∈N is uniformly distributed in [0, 2π), and thus it is also dense in this interval. So approximating the angle between q and r with respect to p, ie. β − α, we have the following: ∀j ∈ N ∃k j ∈ N : ((k j ϑ + α) − β) mod 2π < ε j < ε Therefore the sequence (T k j (q)) j∈N will be within the ε angular neighborhood of L with respect to p. Thus mapping the sequence back by T a , it will be in the required ε angular neighborhood of L with respect to f , and clearly (T a • T k j (q)) j∈N ⊂ F . So with f j := T a • T k j (q), j ∈ N we have shown a countably infinite number of fractal points in the ε angular neighborhood of the intersecting line.

Corollary 2.4 Suppose a line intersects a planar IFS fractal in a point with a finite address,
and has some ε > 0 angular neighborhood around the point that contains only a finite number of fractal points. Then all contractions in the IFS have a rotation angle ϑ for which ϑ 2π ∈ Q.
The above corollary hints at the relevance of a certain class of planar IFS fractals, having roots of unity as rotation factors. They may hold a special place in a theory of the distribution / connectivity of fractal sets. Examining such "rational fractals" further may prove to be a fruitful venture, and the case of primitive roots of unity may be even more worthwhile. Indeed these theorems seem to call for an investigation into the translational and angular distribution of IFS fractals.

Quantifying Intersection
In the previous section we have shown an infinite number of approximate intersections between a fractal and a line under certain conditions. This implies the problem of determining how much of the fractal falls within a translational or angular neighborhood of the line. Clearly what we need is a probability measure which can be easily evaluated in practice.
We will discuss the well-known IFS invariant measure, and provide a new formula for its computation. for any S ⊂ R d in its domain, with some fixed weights w k ∈ [0, 1], k w k = 1.
When the IFS maps are similitudes of the form T k (z) := p k + λ k R k (z − p k ) with λ k ∈ (0, 1) and unitary R k ∈ R d×d , then there exists a unique s > 0, called the similarity dimension of the fractal, for which k λ s k = 1. In such a case, the weights w k = λ s k seem natural.
Theorem 2.4 (Hutchinson [13]) With respect to any IFS and weights, there exists a unique invariant probability measure with bounded support. We call this the invariant measure with respect to the IFS. For any initial probability measure with bounded support µ 0 , the recursion Proof The functions ν 0 := δ p and ν L (S) := (w a : a ∈ A, |a| = L, T a (p) ∈ S), L ∈ N, S ⊂ R d clearly satisfy the required properties of a measure, considering that The Dirac measure ν 0 has the support {p} which is bounded. We now show that the weighted recursion in Theorem 2.4 holds for ν L , L ∈ N. The key to its derivation, is breaking up the sum according to the first coordinate of each address, which is taken from N = {1, . . . , n}. ν L (S) = (w a : a ∈ A, |a| = L, T a (p) Note that the derivation also holds for L = 1. By the above recursion and Theorem 2.4 we have that ∃ lim(ν L ) =: ν and it is the invariant measure with respect to the IFS T .
The above explicit formula for the invariant measure has clear theoretical and practical advantages over existing methods for its computation. One method well-known in image processing, is to discretize the plane over a rectangle, and approximate the invariant measure via a matrix recursion. Another method is carried out stochastically using Elton's Ergodic Theorem [5]. Our exact formula for the invariant measure ν assigns weights w a to each fractal point T a (p) with an address of length L, and checks which points fall into the set S, then sums the weight of those points. Clearly ν can also be approximated in practice via its recursion up to ν L , with a large enough level L ∈ N. We may thus find the density of intersections with the fractal in between parallel rays of light, reasonably spaced at ε := λ L min diam(P), to see the intensity of the shadow in a particular direction, as illustrated on the figure below. This kind of analysis has clear applications to the design of fractal antennas for instance, and the tomography of fractalline structures.

Conclusive Remarks
In our paper, we have highlighted the connection between the projection of IFS fractals and the Fractal-Line Intersection Problem, relevant to applications in computer graphics and antenna design. We have introduced classes of fractals for which the projection from any direction is a segment in the plane. We have done this in a general setting, examining the intersection of hyperplanes and IFS fractals in R d , d ∈ N. Our method implies an algorithm for finding the points of intersection. We have discussed the cardinality of the intersection, and gave an explicit formula for the well-known invariant measure of IFS, in order to quantify intersection.
We hereby express our gratitude for the support of the Faculty of Mathematics at the University of Waterloo, and primarily that of E.R. Vrscay who is supported by NSERC.