4
$\begingroup$

I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values.

I want an efficient algorithm to find the single best valued tile that fit in this polygon; or an algorithm that just says if a single tile can fit inside the polygon. And it should run in deterministic time for irregular polygons with less than 100 vertices.

Please consider that you can rotate the polygon and tiles. Answers/hints for both convex and non-convex polygons are appreciated.

$\endgroup$
  • 1
    $\begingroup$ how do you define "best"? $\endgroup$ – Joe Mar 15 '13 at 17:24
  • 1
    $\begingroup$ "Best" apparently means "highest value". $\endgroup$ – JeffE Mar 17 '13 at 3:28
1
$\begingroup$

Let $P=(p_1,\dots,p_n)$ be the polygon and $\overline{P}$ the set of points it contains.

Let $R=(a,b,c,d)$ be the rectangle of width $w$ and length $l$ with $l\ge w$ (and we assume $d(a,b)=w$) and $\overline{R}$ the set of points it contains.

You want $\overline{R}\subset \overline{P}$.


Suppose $\overline{R} \subset \overline{P}$.

Let $q=a+\cfrac{1}{2}\vec{ab}$ and $r=c+\cfrac{1}{2}\vec{cd}$.

Since $q\in [ab]\subset \overline{R}$ and $r\in [cd]\subset \overline{R}$, $[qr]\subset \overline{P}$.

Since $q\not=r$, we can find $s$ and $t$ on the border of $P$ so that $(qr)=(st)$.


Now suppose you are given a convex $P$

Here's the algorithm:

  • $\forall i \in [1,n]$

    • $\forall j \in [i+1,n]$

      • If $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}\ge l$

        • $s = p_i + k_1 \vec{p_ip_{i+1}}$

        • $t = p_k + k_2 \vec{p_jp_{j+1}}$

        • $q = s + k_3 \vec{st}$

        • $r = q + \cfrac{l}{\|\vec{st}\|}\vec{st}$

        • $\vec{v}:=$ a vector so that $\vec{sr}\perp \vec{v}$ and $\|\vec{v}\|=\cfrac{w}{2}$

        • $a := s - v, b:= s + v, c := r+v,d:= r-v$

        • $S:=solve(\{"k_1\in [0,1]", "k_2 \in [0,1]", "k_3 \in [0,1]", "a,b,c,d\in P"\}$

        • If $S\not= \emptyset$, return true

  • return false

The way this algorithm works is it chooses an orientation and an ax for the rectangle by choosing two arbitrary points $s$ and $t$ somewhere on two arbitrary segments of $P$. Then it takes an arbitrary $q$ in $[st]$ and expresses $a,b,c,d$ in terms of the constants $k_i$ determining $s,t$ and $q$. Then for a point, you know how to determine if it is in a convex polygon so you just need to solve those linear inequalities (in $k_1,k_2,k_3$) for all $4$ points. And if you have solutions, $R$ fits in $P$. Otherwise, you just try another one. And if none worked, since we know that if $R$ fits in $P$, then at least one must work, we know $R$ doesn't fit in $P$.

NB: $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}=\max\{d(p_i,p_{i+1}),d(p_j,p_{j+1}),d(p_i,p_j),d(p_{i+1},p_{j+1})\}$


Then for the non-convex case, you loose the fact that: $a,b,c,d\in \overline{P}\Rightarrow \overline{R}\subset \overline{P}$. So I'm not sure how to do it.

If I had to try, I'd break $P$ into several convex polygons and try to apply a similar algorithm except that I'd try every recombination of $A,B,C,D$ with $a\in A,\dots,d\in D$ with $A,B,C,D$ different convex polygons forming $P$ and then check that the segments of $R$ don't cross segments of $P$...

$\endgroup$
  • $\begingroup$ I'm quite sure $q$ and $r$ are useless and could be replaced with $a$ and $d$ with some precautions. Like starting the second loop at $i$ instead of $i+1$, replacing $v$ by $2v$ and setting $b=a+v$, $c=d+v$ and probably a few other things. $\endgroup$ – xavierm02 Mar 14 '13 at 18:51

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.