3
$\begingroup$

With a convex shape, like a circle, we can create a set of similar shapes, all contained within one another, by centering the shape at the origin and scaling it.

So we can get the following:

enter image description here

With a concave shape however, cetnering it at its centroid and scaling won't keep the points inside the original polygon, we would get something like this:

enter image description here

(Diagram was made by hand so this may not be the mathematical result, but it illustrates the point)

My goal is to be able to deform the original polygon such that the result converges to a single point contained in the original polygon, and every new ring is fully contained in the previous ring, as in this image:

enter image description here

How can this be done?

EDIT:

Maintaining the topology in new rings isn't necessary as long as the number of points doesn't change, so if the shape passes from being concave to being convex, that;s fine as well.

Example:

enter image description here

$\endgroup$
  • $\begingroup$ What point do you want it to converge to? In your example you could have moved the smaller polygons a bit upward and still have a construction matching your criteria. I would think any point from which you can draw a straight line to any point inside the starting polygon could be a possible target. $\endgroup$ – Henrik supports the community Jan 31 '19 at 15:25
  • $\begingroup$ Any point inside the polygon works. I guess ideally something close to the center of mass is better, but ANYWHERE inside the polygon that satisfies the properties above is good enough. $\endgroup$ – Makogan Jan 31 '19 at 15:27
  • $\begingroup$ I'm no completely sure of how it works, but if you use any point outside the set I described, I think that would limit what smaller versions you can go through. But if you don't even have to maintain the shape, that's not a major concern. $\endgroup$ – Henrik supports the community Jan 31 '19 at 16:08
  • $\begingroup$ It seems to me that what you want is rather difficult! Neither of the current answers solves your problem. $\endgroup$ – TonyK Jan 31 '19 at 17:08
  • $\begingroup$ The curve one (accepted one) definitely answers the problem. At leas tin theory. But finding the curve to follow is rather difficult. Using the straight skeleton as suggested is one way to generate those curves but that's complicated and costly... i.e the solutions provided do solve the problem, albeit they are not copy pastable. $\endgroup$ – Makogan Jan 31 '19 at 17:11
2
$\begingroup$

You can achieve your goal by choosing a point $O$ inside your shape and constructing then the other shapes via a homothetic transformation of center $O$ and ratio $<1$.

enter image description here

EDIT.

This works only if the shape is a star domain and $O$ one of its centers.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is brilliant, can't believe I didn't think of that. Any suggestion on how to chose the center point? A good heuristic at least? I realized it $\endgroup$ – Makogan Jan 31 '19 at 16:06
  • $\begingroup$ Unfortunately this works only if you have a star domain (see my edit). You can choose any center $x_0$ of the domain. $\endgroup$ – Aretino Jan 31 '19 at 16:11
2
$\begingroup$
  1. Choose the point you want the polygon to converge into, let's call it $C$
  2. For each vertex $V_i$ of the original polygon choose a curve $\gamma_i$ (staying inside the polygon) from that vertex to $C$, parametrised from $0$ to $1$
  3. Now for each $x\in [0,1]$, the polygon with vertices at $\gamma_i(x)$ represent a polygon, and when $x$ moves from $0$ to $1$ those polygons converge from the original to the $C$.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Isn't this answer identical to the homothetic one above? $\endgroup$ – Makogan Jan 31 '19 at 16:16
  • 2
    $\begingroup$ This answer is more general than mine, as it isn't restricted to straight lines and works for any simply-connected domain. +1. $\endgroup$ – Aretino Jan 31 '19 at 16:18
  • 1
    $\begingroup$ @Aretino Then I guess I will select this as the answer for the sake of generality. But this is a bit too theoretical. "choose a curve $\gamma_i$ (staying inside the polygon)". Deciding which $\gamma_i$ to pick is an entire problem of it's own. As is picking $C$ $\endgroup$ – Makogan Jan 31 '19 at 16:22
  • $\begingroup$ There is no guarantee that the resulting polygon will be contained in the original polygon. $\endgroup$ – TonyK Jan 31 '19 at 16:29
  • 2
    $\begingroup$ @Makogan I think this could also be of help: en.wikipedia.org/wiki/Straight_skeleton $\endgroup$ – Aretino Jan 31 '19 at 16:31

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.