French Onion Soup, Ipelets for Points and Polygons

A quadtree is a data structure used to recursively divide two-dimensional space into four regions/nodes, usually named northwest, northeast, southwest, and southeast [6, Ch. 14]. A point quadtree is a specific type of quadtree in which each node houses a point and its four regions are determined by dividing its region into four sub-regions, with the point itself as the center (see Figure 1(b)). A point-region quadtree is another type of quadtree in which each node represents a region of space with a certain maximum capacity of points, such that points are only housed in leaf nodes (see Figure 1(a)). The importance of quadtrees arises from their enabling of efficient operations on data points in two-dimensional space. Consequently, their applications include areas of image representation/processing, mesh generation, and two-dimensional collision detection [6, 16]. We contribute an Ipelet for generating both these types of quadtrees, and we produce the array format for its contents in a copyable form.

Given a collection of line segments, a trapezoidal map is a subdivision of the plane that respects these segments [6, Ch. 6.1]. The trapezoidal map is created by shooting vertical rays up and down from each of the endpoints of the segments until the vertical line intersects another segment or the bounding box (see Figure 2(a)). In practice, trapezoidal maps allow users to perform planar point location, with respect to the trapezoids that make up the map, in $O(\log (n))$ time. This finds applications in many areas, including geographic information systems, computer-aided design, among others [6, 16]. We provide an Ipelet which, given a set of line segments and an optional bounding box, computes a trapezoidal map of these line segments. It also provides a method for copying the details of the map in an array format.

This is the sequence of convex polygons that result by repeatedly taking the convex hull of the set, and then removing these points from the set [15, Ch. 4][3] (see Figure 2(b)). Onion decompositions of points have found a variety of uses in robust statistics [1, 7] and fractional cascading [4]. We provide an Ipelet that allows users to select a point set and generate its onion decomposition in the plane.

Note that the Gabriel graph and the relative neighborhood graph (RNG) of the point set arise as special cases when $\beta =1$ and $\beta =2$, respectively. The beta skeleton[18, Ch. 32] has applications ranging from machine learning [19] to astronomy [10].

Given a convex body $\mathrm{\Omega }\subset {ℝ}^d$, a cap is the intersection of $\mathrm{\Omega }$ with a halfspace $H$. Letting $h$ denote the bounding hyperplane of $H$, the base of the cap is $h\cap \mathrm{\Omega }$. When $d=2$, the area of a cap is its Lebesgue measure.

Generally, the Dupin floating body need not be convex (see Figure 4(b)), but when it is convex it equals the convex floating body [2]. We provide an Ipelet for generating the Dupin floating body in arbitrary convex polygons (see Figure 4). For the purposes of the Ipelet we take $\delta$ as the percentage of the area of the given polygon in ${ℝ}^2$ to cut away with caps. Floating bodies are used for understanding the boundary structure of convex sets through affine surface area [17].

Polygon triangulations are a ubiquitous tool in computer science [6, Ch. 3]. One application of such triangulations is that it allows efficient point sampling inside non-convex polygons. To do this, points are randomly chosen from inside the triangles (weighted by area) using barycentric coordinates. We provide an Ipelet which, given a polygon, decomposes it into a triangulation (based on code by Nils Olovsson[12]) and randomly places a user specified amount of points in it using this method.

The Sierpiński Triangle and Carpet [11, Ch. 1] are two self similar fractals defined on simple polygons. They are known for having a few interesting properties, such as Lebesgue measure 0 and Haussdorf dimensions ${\log }_2(3)$ and ${\log }_3(8)$. They contain uncountably many points.