Distance from center of an equilateral n-gon in given angle

Question

I'm currently working on a graph visualization that should have arrow links to other nodes where the tip of the array follows the nodes border. I need to calculate the distance of the center of an n-gon to its border for a given angle.

This is trivial for a circle node with it's radius, as the tip of the arrow needs to be radius away from the center of the circle.

It is already trickier for an equilateral triangle but this solution works: Find distance from center of equilateral triangle to edge in given angle, see example of a triangle.

I was now thinking that there must be a way to calculate this distance for any equilateral n-gon as I want to visualize nodes but I just can't come up with anything, see this pentagon as an example.

So I guess there is a way to calculate this distance for any equilateral n-gon just by the parameters angle and n for the corner count, isn't it?

Thanks in advance!

Answer 1

For simplicity, assume the circumradius of the polygon is $1$. The inradius of the polygon is $r=\cos\frac\pi n$.

Suppose your ray is at some angle $\theta$ from an inradius, and that it hits the polygon at a distance $d$. We then have $\cos\theta=\frac rd$, so

$$d=\frac r{\cos\theta}=\frac{\cos\frac\pi n}{\cos\theta}$$

as illustrated below:

$\hskip{3cm}$

Answer 2

You could just treat each polygon edge as a line segment, and find the furthest point in the polygon perimeter that intersects with the desired ray (half-line, starts at the polygon origin).

If you define an $n$-sided polygon, $$\begin{aligned} 0 \lt \theta_{k+1} - \theta_k &\lt \pi \\ r_k &\gt 0 \\ \end{aligned} \quad \iff \quad \begin{aligned} x_k &= r_k \cos \theta_k \\ y_k &= r_k \sin \theta_k \\ \end{aligned}$$ for $i = 1 \dots n$, with $x_0 = x_n$, $y_0 = y_n$, $r_0 = r_n$, $\theta_0 = \theta_n - 2 \pi$, this is very easy to do.

(The above means that the "origin", $(0, 0)$, is always inside the polygon, the polygon does not intersect itself, and its vertices are defined in counterclockwise order – although clockwise works just fine too.)

Let $(x_\Delta, y_\Delta)$ be the direction you're interested in. Its magnitude (distance from "origin") does not matter.

For each polygon edge ending in vertex $k$, you calculate $$t_k = \frac{ x_\Delta y_{k-1} - y_\Delta x_{k-1} }{ ( x_k - x_{k-1} ) y_\Delta - ( y_k - y_{k-1} ) x_\Delta }$$ If and only if $0 \le t_k \le 1$, the edge intersects the direction ray at $(\chi_k, \gamma_k)$, $$\left\lbrace \begin{aligned} \chi_k &= (1 - t_k) x_{k-1} + t_k x_k \\ \gamma_k &= (1 - t_k) y_{k-1} + t_k y_k \\ \end{aligned} \right ., \quad 0 \le t_k \le 1$$ Among the $(\chi_k, \gamma_k)$ found, choose $b$ that maximizes $\chi_b^2 + \gamma_b^2$.

The point on the perimeter is then $(\chi_b, \gamma_b)$, and is at distance $\sqrt{\chi_b^2 + \gamma_b^2}$ from the polygon "origin".

Since nothing beats an actual example, here is a simple Python example program that when run, creates a random non-self-intersecting 10-sided polygon and eight random directions, and finds the corresponding perimeter points. It saves the result as example.svg that you can open in any web browser, with the polygon shaded in blue, red dots showing the random directions (generated by picking random points relative to the polygon), and blue dots showing the corresponding points on the perimeter, with a purple/magenta line between the corresponding red and blue dots. (The red dots can be anywhere, but the blue dots should always be on the perimeter.)

# SPDX-License-Identifier: CC0-1.0
# -*- coding: utf-8 -*-
from math import pi as _pi, sin as _sin, cos as _cos

class Polygon(tuple):
    """Simple immutable polygon type"""

    def __new__(cls, points):
        pts = []
        for p in points:
            if isinstance(p, (tuple, list)):
                pts.append((float(p[0]), float(p[1])))
            else:
                raise TypeError("%s is not a valid 2D point" % str(type(p)))

        n = len(pts) - 1
        while n > 0:
            if (pts[n][0] - pts[n-1][0])**2 + (pts[n][1] - pts[n-1][1])**2 <= 0:
                del pts[n]
            else:
                n -= 1
        while len(pts) > 1 and (pts[0][0] - pts[-1][0])**2 + (pts[0][1] - pts[-1][1])**2 <= 0:
            del pts[-1]

        if len(pts) < 3:
            raise ValueError("Polygon needs at least three unique points")

        return tuple.__new__(cls, pts)

    def __init__(self, *args):
        pass

    def perimeter_towards(self, deltax, deltay=None):
        if deltay is not None:
            dx = float(deltax)
            dy = float(deltay)
        else:
            dx = float(deltax[0])
            dy = float(deltax[1])

        foundx,foundy,found2 = 0,0,0
        nextx,nexty = self[-1]
        for i in range(0, len(self)):
            prevx,prevy = nextx,nexty
            nextx,nexty = self[i]
            if prevx*dx + prevy*dy >= 0 and nextx*dx + nexty*dy >= 0:
                try:
                    t = (dx*prevy - dy*prevx) / (dy*(nextx - prevx) - dx*(nexty - prevy))
                    if t >= 0 and t <= 1:
                        currx = (1-t)*prevx + t*nextx
                        curry = (1-t)*prevy + t*nexty
                        curr2 = currx*currx + curry*curry
                        if curr2 > found2:
                            foundx,foundy,found2 = currx,curry,curr2
                except ZeroDivisionError:
                    pass
        return (foundx, foundy)


def Point(r, degrees):
    radians = _pi*degrees/180
    return (r * _cos(radians), r * _sin(radians))

if __name__ == '__main__':
    from random import Random
    uniform = Random().uniform

    # Generate a ten-sided polygon
    poly = Polygon([ Point(r=uniform(10,490),degrees=360-i*36) for i in range(0, 10) ])

    # Pick eight random directions
    direction = [ (uniform(-490,490),uniform(-490,490)) for i in range(0, 8) ]

    # Find the perimeter points for each direction
    perimeter = [ poly.perimeter_towards(d) for d in direction ]

    with open("example.svg", "w") as out:
        out.write('<?xml version="1.0" encoding="UTF-8" standalone="no"?>\n')
        out.write('<svg xmlns="http://www.w3.org/2000/svg" version="1.1" viewBox="0 0 1000 1000">\n')

        # White background, no border.
        out.write('<rect x="0" y="0" width="1000" height="1000" stroke="none" fill="#ffffff"/>\n')

        # Fill the polygon background with light blue.
        out.write('<path stroke="none" fill="#99ccff" fill-rule="nonzero" d="M')
        for p in poly:
            out.write(' %.3f,%.3f' % (500+p[0], 500-p[1]))
        out.write(' z"/>\n')

        # Draw small red dots at the directions.
        for p in direction:
            out.write('<circle cx="%.3f" cy="%.3f" r="5" fill="#ff0000" stroke="#ffffff"/>\n' % (500+p[0], 500-p[1]))

        # Draw small blue dots at the perimeter.
        for p in perimeter:
            out.write('<circle cx="%.3f" cy="%.3f" r="5" fill="#0000ff" stroke="#ffffff"/>\n' % (500+p[0], 500-p[1]))

        # Draw magenta lines from the dot to the perimeter
        out.write('<path stroke="#ff00ff" fill="none" d="')
        for i in range(0, len(direction)):
            out.write('M%.3f,%.3f %.3f,%.3f ' % (500+direction[i][0], 500-direction[i][1], 500+perimeter[i][0], 500-perimeter[i][1]))
        out.write('"/>\n')

        # Small crosshair at the origin.
        out.write('<path stroke="#000000" fill="none" d="M500,490 500,510 M490,500 510,500" />\n')

        # Stroke the polygon outline.
        out.write('<path stroke="#000000" fill="none" d="M')
        for p in poly:
            out.write(' %.3f,%.3f' % (500+p[0], 500-p[1]))
        out.write(' z"/>\n')

        out.write('</svg>\n')

    print("Saved 'example.svg'.")

Here is an example of the random output from above program: