4
$\begingroup$

This is not a homework problem. It is meant as a challenge for people who really enjoy math and have time to spare.

Background Info

Suppose you have a 2D Cartesian coordinate system. There are three shapes: R, C, and P.

R is a large rectangle. Its left side is along the vertical axis, and its bottom side is along the horizontal axis, such that its bottom-left corner is at the origin (0, 0).

C is a small circle that is located somewhere inside of R. The center of C is not necessarily at R's geometric center. C's border cannot intersect with any part of R's border.

P is an irregular polygon of N sides. It is a simple, convex polygon (not self-intersecting, all angles under 180 degrees). R surrounds P, and P surrounds C. In other words, P's corners and sides exist in the region between C's border and R's border. The corners of P do not necessarily touch the sides of R. Any of P's sides may be tangent to C, but none of P's sides may overlap inside of C.

Objective

Design an algorithm that generates a random variation of P's corners. The corners of P are placed at random distances and random angles relative to C's center. The algorithm's output is an ordered set of Cartesian coordinates, arranged by counter-clockwise position around C.

You are given the following constant values:

  • the width and height of the bounding rectangle R
  • the radius and center of the circle C
  • the number N of corners for polygon P
  • the maximum distance between the center of C and any of P's corners

If this is solvable, how would you implement this algorithm?

Or if this is not solvable, can you explain why not? What would need to change so that it becomes solvable?

$\endgroup$
5
  • $\begingroup$ Can the polygon surround the circle? And is it a simple polygon (i.e. not self-intersecting)? $\endgroup$ Commented Dec 31, 2016 at 0:52
  • $\begingroup$ @Jens Yes, the polygon P is required to surround the circle. It is also a simple polygon. $\endgroup$ Commented Dec 31, 2016 at 2:11
  • $\begingroup$ You need to add the condition that $n \ge 4$, because if the circle $C$ nearly fills the rectangle $R$, $C$ cannot be enclosed by a triangle that fits inside $R$. $\endgroup$ Commented Dec 31, 2016 at 18:01
  • $\begingroup$ No, that is intentionally left out. The algorithm should hold true for N = 3 (where P is a triangle). $\endgroup$ Commented Dec 31, 2016 at 18:16
  • $\begingroup$ I posted a figure illustrating what I meant by the triangle comment. $\endgroup$ Commented Dec 31, 2016 at 19:07

2 Answers 2

Reset to default
3
$\begingroup$

                  Star1
                  Star2
                  Star3

$\endgroup$
5
  • $\begingroup$ Close, but all of the angles have to be convex. $\endgroup$ Commented Dec 31, 2016 at 16:42
  • $\begingroup$ @MikeQ: Oh, I missed the convexity requirement, instead concentrated on "random." Now convex. $\endgroup$ Commented Dec 31, 2016 at 17:17
  • $\begingroup$ Okay, so it is solvable. Can you explain your strategy? $\endgroup$ Commented Dec 31, 2016 at 17:33
  • $\begingroup$ @MikeQ: I created rays from the circle center out to the rectangle, then clipped the rays to start on the circle (rather than its center). Then I placed points at the midpoints of the rays. Then I took the convex hull of those points (as there are circumstances where the points determine a slightly nonconvex polygon). $\endgroup$ Commented Dec 31, 2016 at 17:36
  • $\begingroup$ @MikeQ: There is, however, a flaw. When nn is small (e.g., $3$ or $4$), the polygon sometimes clips the circle. So this is not a entirely general solution for arbitrary $n \ge 3$. Small-$n$ cases might need special handling. Oh, I just realized that $n=3$ sometimes has no solution. $\endgroup$ Commented Dec 31, 2016 at 18:06
0
$\begingroup$

Without some geometric condition on what it means for $R$ to be "large" and $C$ to be "small," there may not be a solution for $n=3$, i.e., $P$ a triangle:

                      TriangleImpossible

$\endgroup$
2
  • $\begingroup$ P must exist. So to modify the problem, you would need the ratio between C's radius and R's shorter side. If this ratio is 0.5, does that guarantee a solution? $\endgroup$ Commented Dec 31, 2016 at 19:43
  • $\begingroup$ @MikeQ: I think it is more complicated than that. It might be best to simply require that there exists a $\triangle$ such that $R \supset \triangle \supset C$. Or better yet, just stipulate that $n \ge 4$. $\endgroup$ Commented Dec 31, 2016 at 20:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.