Qubyte Codes

The maths of Domains of points with spokes


It's been a while since my last maths heavy article. I enjoy writing these but struggle to find the time to write many.

This article is on the generative art piece in my last post. I based this on my memory of an image of a piece in a talk by Charlotte Dann. It was a piece of art actually drawn using a pen and paper plotter (which I love), but I lack these tools at present, so I chose to use the browser instead (lucky you).

In hindsight, I should have realized that the domains around points are like a Voronoi diagram. I forged ahead having forgotten all about them, so please excuse my unorthodox terminology below. Looking back on the talk that inspired this, my memory of the drawing wasn't quite correct. See the real deal at about 6:25 in.

Based on my memory, the image was of a number of points. From each point lines (I'll call these spokes) radiated outwards until they reached the edge of the domain of a point. The "domain" as I call it is an area around a point bounded by the half way lines between it and neighbouring points, or the bounding box of the image.

The case of neighbouring points looks like:

Spokes radiating from a point to the halfway line between the point and another point.

I've drawn spokes radiating from the point on the left up to the domain edge shared by both points. A way of looking at this is to draw the domain boundary.

The boundary between two points.

What I need is, given a point and an angle of a spoke radiating from it, how long will that spoke be to reach the closest boundary? Remember, points are randomly located!

The equation of the boundary line is related to the equation of a line between the two points, which is:

y(x)y0=x0x1y0y1(xx0)y(x) - y_0 = \frac{x_0 - x_1}{y_0 - y_1} (x - x_0)

Where the numeric subscripts 0 and 1 are for the two points, and we're interested in the spokes radiating from point 0.

Any two fixed points on the line can be used to place the line. For example, it's just as valid to use the coordinates of the second point (note the subscripts):

y(x)y1=x0x1y0y1(xx1)y(x) - y_1 = \frac{x_0 - x_1}{y_0 - y_1} (x - x_1)

The equation for the boundary line is perpendicular to the point-to-point line and halfway along it. Since the lines cross half-way along the point-to-point line, we can use that location to fix the perpendicular line:

(x0+x12,y0+y12)\left(\frac{x_0 + x_1}{2}, \frac{y_0 + y_1}{2}\right)

The slope is perpendicular to the slope of the point-to-point line:

x1x0y0y1\frac{x_1 - x_0}{y_0 - y_1}

Putting these together and rearranging gave me the equation for a boundary between two points:

y(x)=x1x0y0y1(xx0+x12)+y0+y12y(x) = \frac{x_1 - x_0}{y_0 - y_1}\left(x - \frac{x_0 + x_1}{2}\right) + \frac{y_0 + y_1}{2}

With the equation for a boundary, I needed an equation for each spoke. My intent was to use these simultaneous equations to find the solution for the length of the spoke.

The equation for the boundary line is in Cartesian coordinates (x,y), but given that we have an angle, and we're looking for a length, it's more natural to think of a spoke in polar coordinates (r,Θ). In fact, taking the point as the origin, r is the length we're actually looking for.

A line in polar coordinates can be connected to Cartesian coordinates using the following equations:

xx0=rcosθyy0=rsinθ\begin{align} x - x_0 &= r \cos \theta\\ y - y_0 &= r \sin \theta \end{align}

Substituting these into the boundary equation gave:

rsinθ+y0=x1x0y0y1(rcosθ+x0x12)+y0+y12r \sin \theta + y_0 = \frac{x_1 - x_0}{y_0 - y_1}\left(r \cos \theta + \frac{x_0 - x_1}{2}\right) + \frac{y_0 + y_1}{2}

After some rearranging, the solution for r looks like:

r=12(y1y0)2+(x1x0)2(y1y0)sinθ+(x1x0)cosθr = \frac{1}{2} \cdot \frac{(y_1 - y_0)^2 + (x_1 - x_0)^2}{(y_1 - y_0)\sin \theta + (x_1 - x_0) \cos \theta}

Since the equations for the bounding box edges are more simple:

x=0x=xmaxy=0y=ymax\begin{align} x &= 0\\ x &= x_\text{max}\\ y &= 0\\ y &= y_\text{max} \end{align}

The solutions for r with these bounding box equations are a little simpler too:

r=x0cosθr=xmaxx0cosθr=y0sinθr=ymaxy0sinθ\begin{align} r &= \frac{-x_0}{\cos\theta}\\ r &= \frac{x_\text{max} - x_0}{\cos\theta}\\ r &= \frac{-y_0}{\sin\theta}\\ r &= \frac{y_\text{max} - y_0}{\sin\theta} \end{align}

Given all these equations, for each spoke radiating from each point we need to calculate r for boundaries with every other point and also the bounding box. Spokes radiate away from a point, so all negative values of r can be discarded. Of the remaining possible values of r, the shortest wins!

I settled on using 10 randomly placed points, each with 48 evenly spaced spokes. I've added a gap between spoke ends (both with their point and the boundary) to make the graphic look as I remember it. Points are not drawn.

Finally, I used JavaScript to create an SVG and used line elements to draw each spoke. A little inline CSS in the head applies the foreground colour of the page (the colour of the text) to the lines. This is neat because it means the graphic will look natural on the page in both light and dark modes (although I think it has a certain art deco look to it in dark mode). This ease of theming is in contrast to the effort it took to theme the Game of Life demo in a previous post.