algorithm - How to find best fit of convex polygon into other convex polygon -

-

i'm looking algorithm calculate translation, rotation , scaling required position convex polygon (p1) inside convex polygon (p2). need return "best fit", meaning p1 contained within p2 , has maximum area possible.

consider following diagram: http://i.imgur.com/ckaiiv7.png

the black polygon on right (p1) needs placed optimally inside blue polygon on left (p2).

i have found lots of written papers online polygon containment algorithms algorithms determine whether or not polygons can fit inside polygon given ability translate , rotate them.

the algorithm i'm looking should produce result because includes ability scale polygon p1. understand type of algorithm produce multiple optimal answers , that's okay.

any help?

ok, if nobody has better idea, give not-so-good algorithm.

let's have p1 p vertices , p2 q vertices, , want fit p1 inside p2.

you found articles describing how determine whether p1 can fit inside p2. example this article gives algorithm in o(pq^2) time. i'm not sure if can still faster if know both p1 , p2 convex.

so, start large number a such a(p1) cannot fit inside (p2), , binary search on value of a.

this not clever, @ least gives answer. if else posts better answer, please ignore mine...


Comments

Post a Comment

Popular posts from this blog

c - Bitwise operation with (signed) enum value -

-
i using enumerator values flags: typedef enum { = 0x00, b = 0x01u, // u has no influence, expected c = 0x02u, // u has no influence, expected ... } enum_name; volatile unsigned char* reg = someaddress; *reg |= b; according misra-c:2004 bitwise operations shall not done signed type. unfortunately, compiler iar use signed int (or short or char) underlying type of enums, , option can find relates size, not signedness ("--enum-is-int"). according iar c/c++ development guide arm , pages 169 , 211, can define type of enum s if enable iar language extensions ( -e command-line option, or project > options > c/c++ compiler > language > allow iar extensions in ide). in particular, should define "sentinel" value, make sure compiler chooses correct type. prefers signed types, , uses smallest possible integer type, sentinel should largest positive integer corresponding unsigned integer type can describe. example, typedef enum
Read more

xslt - Unnest parent nodes by child node -

-
in xml there items 0-n attributes , item should copied each attribute new item 1 attribute. given xml this: <?xml version="1.0" encoding="utf-8" ?> <items> <item> <name>a</name> <attributes> <attribute> <key>attribute1</key> <value>1</value> </attribute> </attributes> </item> <item> <name>b</name> </item> <item> <name>c</name> <attributes> <attribute> <key>attribute1</key> <value>5</value> </attribute> <attribute> <key>attribute2</key> <value>2</value> </attribute> <attribute> <key>attri
Read more

YouTubePlayerFragment cannot be cast to android.support.v4.app.Fragment -

-
im stuck on 3 days , have tried have come across after lots of searching ,this post last resort, im trying open youtubeplayerfragment using navigation drawer youtubeplayerfragment cannot cast android.support.v4.app.fragment problem edit question : have updated code have used youtubeplayersupportfragment instead of youtubeplayerfragment ,i error in displayview method (case 4: fragment = new youtube(); break;) in main activity saying cannot convert youtube fragment , cannot logcat since cant run it edit question 2: code updated again have runtime problem ,heres logcat 07-22 22:15:09.782: e/androidruntime(20603): fatal exception: main 07-22 22:15:09.782: e/androidruntime(20603): process: net.frankandwalters, pid: 20603 07-22 22:15:09.782: e/androidruntime(20603): java.lang.nullpointerexception: attempt invoke virtual method 'void com.google.android.youtube.player.youtubeplayerview.a()' on null object reference 07-22 22:15:09.782: e/androidruntime(20603): @ com.goog
Read more