0
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ The typical name for what you call an n-angle is n-gon, as in pentagon, hexagon, etc. $\endgroup$
    – Tbw
    Mar 28, 2021 at 21:10
  • $\begingroup$ Thanks that makes totally sense, will adjust the title :) $\endgroup$ Mar 28, 2021 at 21:19
  • $\begingroup$ The exact term is "regular polygon with n vertices" $\endgroup$
    – Jean Marie
    Mar 28, 2021 at 21:21
  • $\begingroup$ The internal angle at any vertex of a regular $n$-gon is $\frac{n-2}n\pi$. Then use trigonometry. $\endgroup$
    – Théophile
    Mar 28, 2021 at 21:33
  • $\begingroup$ @Théophile yes I also thought about thinking of the n-gon as a bunch of triangles and calculate the distance this way, but how can I calculate the distance then? I have the parameters: incoming angle of the arrow, max distance at the corners and min distance in the middle of each edge. Could you give me another tip or an example? $\endgroup$ Mar 30, 2021 at 18:29

2 Answers 2

0
$\begingroup$

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}$enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Thanks a lot, I looked for 90° angles but didn't see this one, anyways this worked flawlessly for me! $\endgroup$ Apr 3, 2021 at 11:21
0
$\begingroup$

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: Example output from the Python program

$\endgroup$
1
  • $\begingroup$ Thanks for your very elaborate answer, thats actually what I did for the triangle but for equilateral n-gons there is most likely a simple solution which I didn't come up with yet. Nevertheless still helpful for non equilateral shapes! $\endgroup$ Mar 30, 2021 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.