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$
  • $\begingroup$ Can the polygon surround the circle? And is it a simple polygon (i.e. not self-intersecting)? $\endgroup$ – Jens Dec 31 '16 at 0:52
  • $\begingroup$ @Jens Yes, the polygon P is required to surround the circle. It is also a simple polygon. $\endgroup$ – MikeQ Dec 31 '16 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$ – Joseph O'Rourke Dec 31 '16 at 18:01
  • $\begingroup$ No, that is intentionally left out. The algorithm should hold true for N = 3 (where P is a triangle). $\endgroup$ – MikeQ Dec 31 '16 at 18:16
  • $\begingroup$ I posted a figure illustrating what I meant by the triangle comment. $\endgroup$ – Joseph O'Rourke Dec 31 '16 at 19:07
3
$\begingroup$


                  Star1
                  Star2
                  Star3


$\endgroup$
  • $\begingroup$ Close, but all of the angles have to be convex. $\endgroup$ – MikeQ Dec 31 '16 at 16:42
  • $\begingroup$ @MikeQ: Oh, I missed the convexity requirement, instead concentrated on "random." Now convex. $\endgroup$ – Joseph O'Rourke Dec 31 '16 at 17:17
  • $\begingroup$ Okay, so it is solvable. Can you explain your strategy? $\endgroup$ – MikeQ Dec 31 '16 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$ – Joseph O'Rourke Dec 31 '16 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$ – Joseph O'Rourke Dec 31 '16 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$
  • $\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$ – MikeQ Dec 31 '16 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$ – Joseph O'Rourke Dec 31 '16 at 20:27

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.