2

There is a container polygon C, which can be of arbitrary shape. There is another polygon P, which is of arbitrary shape too. The vertices and their order of both polygons are known.

The Questions are: (1). If place polygon P into polygon C is possible. (2). If (1) is possible, let's place both polygon P and a circle A into polygon C, then how to maximize the radius of this circle A?

3dimensions
  • 21
  • 2
  • you can google a bit i guess, i found these while googling http://stackoverflow.com/questions/4279478/largest-circle-inside-a-non-convex-polygon and http://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/ – advocateofnone Jan 04 '15 at 07:27
  • 1
    Can polygon P be rotated and/or scaled to fit it inside C or can it just be translated? A ist just the maximum inscribed circle that does not relate in any way to P, right? – M Oehm Jan 04 '15 at 08:37
  • @M Oehm, Yes. Polygon P and polygon C are rigid, they can be rotated or translated but can't be scaled. Circle A can be scaled or translated. Circle A and polygon P are both inside C, but don't intersect each other. – 3dimensions Jan 04 '15 at 08:57
  • @sasha, These two posts are helpful, but still can't solve the original questions. – 3dimensions Jan 04 '15 at 09:06
  • what is the desired optimality of result? for optimal solution you have to try all possible placements and then compute max inscribed circle inside the empty space (which is also a polygon). (heuristics for this is that polygons are touching each-other at least in 2 points. (more vertices are touching parallel usually the better). if you need just suboptimal solution then you can use field approach (retractive forces) or just use some direction shifting + rotation steps and always chose the one that leads to bigger inscribed circle – Spektre Jan 29 '15 at 08:40

0 Answers0