# Equally spaced points between two points inclusive, with a minimum specified gap but no overlap

I’m trying to solve a math problem which I’d really appreciate some help with. I’ve tried to visualise it below to help explain it:

I’ve given two examples here. In both examples, this is the information that is known:

• The length of the horizontal line
• The position of both circles at the ends of the line
• The radius of both circles at the ends of the line
• The minimum gap between any circles to be plotted between the end circles

All four of the above variables can change, I’ve simply shown two examples in the image. My question is, how can I calculate the position(s) of the dashed circle(s)? There are some conditions for these circles:

1. They must be equally spaced between the end (solid) circles
2. They must have the same radius as the end (solid) circles
3. They must be separated by at least the specified gap (to avoid overlap)
4. If the two end (solid) circles are too close to permit a dashed circle between them with the minimum gap on either side, we must not plot a dashed circle.

We can get the available distance, then divide by how much space the circles + their gaps take up to get the number of circles we can fit. Once we have the number of circles that will fit, we can interpolate the coordinates on the line to place the middle circles.

For getting the number of circles that will fit, we can simplify the problem. Changing the minimum gap is the same as changing the radius of the circles. We can see that the we can pretend the minimum gap is 0 if we add half of it to each circle’s radius. In terms of math we have something like

``````using UnityEngine;

public static class CirclePlots
{
// Can be optimized further by
// 1. using diameter and factoring out all of the (2 * radius)
// 2. using sqrMagnitude
public static int GetDashedCircleCount(
Vector3 circle1Position,
Vector3 circle2Position,
float minSpacing)
{
// minSpacing is the same as changing the radius of the circles, so we lump it in.
var availableDistance = (circle2Position - circle1Position).magnitude;
availableDistance -= radius * 2f; // subtract radius of the end circles from the available space.
var circlesThatWillFitFloat = availableDistance / (radius * 2f);
return Mathf.FloorToInt(circlesThatWillFitFloat);
}

// Can be optimized further by taking in a list/array of positions instead of creating them.
public static Vector3[] GetDashedCirclePositions(
Vector3 circle1Position,
Vector3 circle2Position,
float minSpacing)
{
var dashedCircleCount = GetDashedCircleCount(circle1Position, circle2Position, radius, minSpacing);
// This is the number of segments between all of the circles.
// It's the dashed circle count + 1, or it's the total circle count - 1.
var numberOfSegmentsBetweenCircles = dashedCircleCount + 1;
var positions = new Vector3[dashedCircleCount];
for (var i = 0; i < positions.Length; i++)
{
// This number is the distance along the line normalized (i.e. set to a max of 1)
// Doing it this way since we can use Vector3.Lerp which requires a normalized value.
// I used your images to count -- The first position (i = 0) is at the first segment.
var normalizedPositionOnLine = (i + 1) / (float)numberOfSegmentsBetweenCircles;
positions[i] = Vector3.Lerp(circle1Position, circle2Position, percentageAlongLine);
}
return positions;
}
}
``````
3 Likes

@jasonboukheir Thank you so much! I just tried your solution and it works wonderfully. All the points between the ends circles are evenly spaced. And if the gap is too small for even one circle, the “GetDashedCircleCount” function confirms if this is the case. Great work!

Now I just need to understand exactly what you have done.

This is a fairly common math especially in gaming where we all use some sort of abstract grid to line up things nicely or whatever.

All this kind of math does is to treat a normally continuous real space of numbers as integers, or more precisely, as discrete jumps defined by some spacing parameter. You can quickly see that integers are just a special case where this spacing parameter is exactly 1.

So the dividing is what transforms one space into another (in this case, it’s just a line, so 1D “space”), it essentially flexes the original space so that the integers align with whatever your in-between spacing is. The next trick is to cull off the decimal part of the result (aka truncate the result) and this is typically done via flooring, ceiling, or rounding. These are three different flavors of converting a decimal point value to an integer.

Floor will nudge toward the nearest integer on the left of the value. Ceil does the opposite. And rounding will nudge it toward the nearest of the two (with some additional rules if it’s exactly in the middle).

jasonboukheir uses FloorToInt method which will also convert the type of the result from `float` to `int` as a convenience.

Everything else is really just extra fluff with regard to this specific geometry you’re after.

Edit:
Here are some commonly used functions from my libraries

``````// using System;

/// <summary> Rounds down a floating point value to the greatest integer smaller than n. </summary>
static public float floor(float n) => MathF.Floor(n);

/// <summary> Rounds up a floating point value to the smallest integer greater than n. </summary>
static public float ceil(float n) => MathF.Ceiling(n);

/// <summary> Rounds a floating point value to the nearest integer. </summary>
static public float round(float n) => MathF.Round(n);

/// <summary> Returns the fractional part of the floating point value. </summary>
static public float frac(float n) => n % 1f;

/// <summary> Returns the integral part of the number (truncates the fractional part). </summary>
static public float trunc(float n) => MathF.Truncate(n);

/// <summary> Rounds down a floating point value to the greatest step value smaller than n. </summary>
/// <param name="d"> Size of the step interval. No steps if d &lt;= 0. </param>
/// <param name="o"> Optional. Step offset. Default: 0 </param>
static public float floorStep(float n, float d, float o = 0f)
=> d <= 0f? n : d * floor((n - o) / d) + o;

/// <summary> Rounds up a floating point value to the smallest step value greater than n. </summary>
/// <param name="d"> Size of the step interval. No steps if d &lt;= 0. </param>
/// <param name="o"> Optional. Step offset. Default: 0 </param>
static public float ceilStep(float n, float d, float o = 0f)
=> d <= 0f? n : d * ceil((n - o) / d) + o;

/// <summary> Rounds a floating point value to the nearest step value. </summary>
/// <param name="d"> Size of the step interval. No steps if d &lt;= 0. </param>
/// <param name="o"> Optional. Step offset. Default: 0 </param>
static public float roundStep(float n, float d, float o = 0f)
=> d <= 0f? n : d * round((n - o) / d) + o;
``````

These `XStep` variants are particularly useful when it comes to grid-like behavior. I nearly regularly use roundStep in my projects. And you can very easily see what I’ve explained at the top. A value is scaled by the spacing, then rounded to the nearest integer, then scaled back to its original space. This way the input values get snapped to some evenly spaced imaginary points. Imagine if `d` was 1 then it would not scale anything, but `round` would snap the values to whole numbers. The `o` argument is used to optionally offset the regularity of the snapping to the left or right. This is useful when you want the points to land left or right from the 0, but never on the 0 itself.

If you apply this function to a multi-dimensional coordinate system, you get the grid behavior, and you can very easily change the spacing and offset for all desired axes.

``````[SerializeField] Vector2 _grid;
[SerializeField] Vector2 _offset;

Vector2 GetGridPoint(Vector2 point)
=> new(roundStep(point.x, _grid.x, _offset.x), roundStep(point.y, _grid.y, _offset.y));

void OnDrawGizmos() {
var mouse = ... // capture mouse position
DrawPoint(mouse, Color.cyan);
DrawPoint(GetGridPoint(mouse), Color.magenta);
}
``````

Btw `Mathf.FloorToInt` is just

``````public int FloorToInt(float value) => (int)MathF.Floor(value);
``````