2
$\begingroup$

I've got a programming task at hand, and I should give back a true or false, based on if a point (x,y) is inside of the equilateral shape (circle, triangle, square, hexagon). I've finished with the circle, but I cannot figure out how to calculate the other 3 properly. In the case of circle we've got the center point and the radius (instead of length of the side), but with the other 3 we get the center point and the length of the sides (which is all the same of course given they're equilateral). Lastly, we know that every shape has a side that is parallel to the X axis of the coordinate-system (except the cirlce of course). Any ideas?

$\endgroup$
6
  • $\begingroup$ What have you tried? I wonder if you can do something with the signed areas of the triangles formed by the point and pairs of consecutive vertices of the polygon $\endgroup$ Commented Sep 29, 2023 at 9:11
  • $\begingroup$ I have got a feeling that something can be done with the incircle and circumcircle of the given regular polygon. Just a suggestion… $\endgroup$
    – Soham Saha
    Commented Sep 29, 2023 at 9:29
  • 1
    $\begingroup$ And for the square we get the following boolean: ((x is in between $c_x-\frac{l}{2}$ and $c_x+\frac{l}{2}$) and (y is in between $c_y-\frac{l}{2}$ and $c_y+\frac{l}{2}$)). Where $(c_x,c_y)$ is the center of the square and $l$ is the given side length $\endgroup$
    – Soham Saha
    Commented Sep 29, 2023 at 9:32
  • $\begingroup$ By equilateral shape, do you actually mean regular polygon? And you know not just the centre and the length of the side but also how many sides it has? If so, you can rotate the point around the centre by any multiple of 360/n degrees (n is the number of sides) and this does not change whether it is insode or outside the polygon. After the right rotation, you can compare the y coordinate of the point with the y coordinate of the horizontal side to see if the point lies inside or outside. $\endgroup$ Commented Sep 29, 2023 at 10:17
  • 1
    $\begingroup$ Thank you guys, but I don't need one single solution for all of them. I can use different methods for these, but as an update on the matter, I may have found solutions for all of them except the hexagon. Do you have any idea for that one? $\endgroup$
    – Monte
    Commented Oct 2, 2023 at 15:58

2 Answers 2

2
$\begingroup$

Edit: Corrected condition to include checking $n^{\text{th}}$ side and angles

There's probably a simpler method for just the few simple shapes mentioned, but I decided to write a method for a general $n$-sided regular polygon. Let $C \equiv (x_c, y_c)$ be the centre point, $L$ the length of the sides, and $n$ the number of sides. In summary, a point $(x,y)$ lies within the shape if,

$$ f_k(x,y) f_k(x_c,y_c) \geq 0 \quad \forall \; k = 1,2, \dots, n$$ where, $$ f_k(x,y) \equiv y - y_k - (x - x_k) \frac{y_{k+1} - y_k}{x_{k+1} - x_k}, \quad (x_{n+1}, y_{n+1}) \equiv (x_{1}, y_{1}) \\ \vec{V}_k = \vec{V}_{k-1} + \begin{bmatrix} \cos\left(\frac{2\pi}{n}\right) & - \sin\left(\frac{2\pi}{n}\right) \\ \sin\left(\frac{2\pi}{n}\right) & \cos\left(\frac{2\pi}{n}\right) \end{bmatrix} (\vec{V}_{k-1} - \vec{V}_{k-2}), \quad \vec{V}_k \equiv \begin{bmatrix} x_k \\ y_k \end{bmatrix} \\ V_1 \equiv \begin{bmatrix} x_c - \frac{L}{2} \\ y_c - \frac{L}{2} \cot \left(\frac{\pi}{n}\right) \end{bmatrix}, \quad V_2 \equiv \begin{bmatrix} x_c + \frac{L}{2} \\ y_c - \frac{L}{2} \cot \left(\frac{\pi}{n}\right) \end{bmatrix} $$

Derivation

Consider one side, and draw lines from it's vertices to the centre point to form an isosceles triangle. Since congruent triangles can be formed in the same way with the other sides, the angle of the triangles at the centre are all equal and add up to $2 \pi$. So each angle is $\frac{2\pi}{n}$.

Now draw a line from the centre and perpendicular to the side parallel to the x-axis. Because of the isosceles triangle, this bisects the side (the two smaller and right-angled triangles are congruent) into $\frac{L}{2}$ and $\frac{L}{2}$. These $\frac{L}{2}$ segments are the opposite side for the two right-angled triangles to the centre angle which is also bisected into $\frac{\pi}{n}$ and $\frac{\pi}{n}$. So the length of the perpendicular is $\frac{L}{2} \cot \left(\frac{\pi}{n}\right)$

Because the side is parallel to the x-axis, the perpendicular is in the y-direction. That means the midpoint $M$ of this side is shifted from the centre in the y-direction only by the length of the perpendicular. Assuming the side is below the centre point, $$M \equiv \left(x_c, y_c - \frac{L}{2} \cot \left(\frac{\pi}{n}\right)\right)$$

For even $n$, there will be a parallel side above and below. For odd $n$ (like triangle), if the side is actually above, then just change the $-$ to $+$. Now from the midpoint, we can get the two vertices of this side as, $$V_1 \equiv \left(x_c - \frac{L}{2}, y_c - \frac{L}{2} \cot \left(\frac{\pi}{n}\right)\right), \quad V_2 \equiv \left(x_c + \frac{L}{2}, y_c - \frac{L}{2} \cot \left(\frac{\pi}{n}\right)\right)$$

Now the interior angle of an $n$-regular polygon is $\frac{(n - 2)\pi}{n}$, and the exterior angle is $\frac{2\pi}{n}$. Each side is a continuation of the previous side, but rotated by the exterior angle. So in vector notation and using the rotation matrix, one can calculate each vertex using the previous two vertices, $$\vec{V}_k = \vec{V}_{k-1} + \begin{bmatrix} \cos\left(\frac{2\pi}{n}\right) & - \sin\left(\frac{2\pi}{n}\right) \\ \sin\left(\frac{2\pi}{n}\right) & \cos\left(\frac{2\pi}{n}\right) \end{bmatrix} (\vec{V}_{k-1} - \vec{V}_{k-2})$$

Now with the coordinates of all the vertices, we can construct equations of lines for each side. Since the $n^{\text{th}}$ side is formed by $V_n$ and $V_1$, define $V_{n+1} \equiv V_1$ for algorithmic simplicity. $$\overline{V_k V_{k+1}} := f_k(x,y) = 0, \quad f_k(x,y) \equiv y - y_k - (x - x_k) \frac{y_{k+1} - y_k}{x_{k+1} - x_k}$$

So we know if a point lies on the line, it must make the above equation 0. But what if we plug in a point that doesn't lie on the line, that lies within one of the two half-spaces that the line divides space into? Then we get a non-zero value. Specifically, we get positive values for points on one half-space of the line and negative values for points on the other half-space of the line. Now we could figure out which half-space gives which sign, but that's not important.

Next, let's define what we mean by 'a point lying inside the shape'. Well, one way is if, for each side, the given point lies on the same half-space as the centre point. Meaning that when we plug in the point into all the side equations, it should have the same sign as when we plug in the centre point. So putting the condition together mathematically, $$f_k(x,y) f_k(x_c,y_c) \geq 0 \quad \forall \; k = 1,2, \dots, n $$

If you want strictly inside (excluding points on the side), then it becomes, $$f_k(x,y) f_k(x_c,y_c) > 0 \quad \forall \; k = 1,2, \dots, n $$

As an aside, this idea of lying on the same half-space of every side can be applied to any convex polygon. And if you didn't have the centre point, you could just use another vertex for checking the half-space.

$\endgroup$
2
  • 1
    $\begingroup$ The last paragraph suggests a way to describe your solution that might be easier to understand, perhaps to program. Find the $n$ equations of the lines containing the sides of the figure. Arrange the equations so that the center point is always in the positive half space. Then check that the given point is always in the positive half space. $\endgroup$ Commented Sep 29, 2023 at 20:14
  • $\begingroup$ Thank you but it's way more complicated for my brain though it might be good. $\endgroup$
    – Monte
    Commented Oct 2, 2023 at 15:59
1
$\begingroup$

After some time, I came up with this simpler method (compared to my previous one) by changing the perspective of when a point is inside, by looking at maximal distance from centre. Let $C \equiv (x_c, y_c)$ be the centre point, $L$ the length of the sides, and $n$ the number of sides. In summary, a point $(x,y)$ lies within the shape if, $$\sqrt{(x-x_c)^2 + (y-y_c)^2} \leq R_{max}(\theta)$$ where $$ R_{max}(\theta) = \frac{L}{2} \cot \left(\frac{\pi}{n}\right) \sec \left( \min\left(\theta^*, \frac{2\pi}{n} - \theta^*\right)\right), \qquad \theta^* \equiv \theta \mod \frac{2\pi}{n} \\ \theta \equiv \tan^{-1} \left(\frac{x - x_c}{y-y_c}\right) + \pi (x < x_c \lor (x = x_c \land y > y_c)) $$

And if we let $L \to 0$ while $n \to \infty$ (in a certain manner), we'll get the natural check for a circle.

Derivation

A point can be no further than the circumradius from the circumcentre, as by definition the entire shape is contained within the circumcircle. But this is not a sufficient condition, as depending on the angle, the maximal distance a point can be away may be less.

For regular polygons, the circumcentre and incentre (for incircle) are the same, and is the centre referred to in the question. And so the maximal distance a point can be away varies between the in-radius and the circum-radius. The in-radius is the length of the perpendicular from the centre to any side bisecting it, and the circumradius is the length of the line from centre to any vertex, as shown below where $L$ is the length of the $n$ equal sides. See my previous answer for context on reaching these equations. $$R_I = \frac{L}{2} \cot \left(\frac{\pi}{n}\right), \quad R_C = \frac{L}{2} \csc \left(\frac{\pi}{n}\right)$$

Now consider an arbitrary point $P(x,y)$, the line joining $P$ to the centre $C(x_c,y_c)$, and the angle $\theta$ this line makes with the y-axis, calculated as, $$\theta \equiv \tan^{-1} \left(\frac{x - x_c}{y-y_c}\right) + \pi (x < x_c \lor (x = x_c \land y > y_c))$$

The logical expression is included to add $\pi$ if the point is on the left-side or exactly above of the centre, so that exactly below corresponds to $\theta = 0$. This is required as for odd $n$, there is only one side parallel to the x-axis, and so we are using it as reference (assuming it lies below; the expression can be adjusted if it lies above instead).

When $\theta = 0$, $P$ must lie vertically below the centre. By geometry, the furthest point on the shape it can be is the midpoint of the side parallel to the x-axis, which is at in-radius distance $R_I$ from the centre. If we increase $\theta$, then this maximal distance will increase upto the circumradius $R_C$ at $\theta = \frac{\pi}{n}$. Then it decreases back to $R_I$ at $\theta = \frac{2\pi}{n}$, and this cycle repeats. So using geometry and the modulus operation, we can calculate the maximal allowed distance inside the shape as, $$R_{max}(\theta) = \begin{cases} R_I \sec \theta^*, \; &0 \leq \theta^* \leq \frac{\pi}{n} \\ R_I \sec \left(\frac{2\pi}{n} - \theta^*\right), \; &\frac{\pi}{n} \leq \theta^* \leq \frac{2\pi}{n} \\ \end{cases}, \qquad \theta^* \equiv \theta \mod \frac{2\pi}{n}$$

Since the value of each case's expression is greater than the other in the other's range, we can combine the two cases using a min function, $$R_{max}(\theta) = R_I \sec \left( \min\left(\theta^*, \frac{2\pi}{n} - \theta^*\right)\right) $$

And so a point lies within the shape if its distance from the centre is less than the maximal distance for its angle, $$||\overline{CP}|| \leq R_{max}(\theta)$$

$\endgroup$
3
  • 1
    $\begingroup$ Thank you, what is R though? I mentioned above that I solved like almost all of them except the hexagon, and I don't need necessarily one single solution for all of them at once, it's just as good if I solve them with different methods. $\endgroup$
    – Monte
    Commented Oct 2, 2023 at 16:01
  • $\begingroup$ Each $R$ is different. $R_C$ is the circumradius, $R_I$ the inradius, $R_{max}(\theta)$ a function that tells the furthest distance you can go from the centre along a particular direction (indicated by $\theta$) while remaining within the shape. Are any of these $R$'s unclear? $\endgroup$ Commented Oct 3, 2023 at 4:56
  • $\begingroup$ It's clear now thank you! $\endgroup$
    – Monte
    Commented Oct 3, 2023 at 7:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .