10556 - Biometrics

[Lain]

Hi All!

To solve this problem I used assumption, that two poligons should have same angles between corresponding edges and have the same scale factor for all corresponding edge's lengths.
Does it right?

[ditrix]

yes, it's a basic idea, but you must also verify if the polygons has the same orientations. It means that you have to consider the angles from 0 to 180 deg as from 180 to 360 if the orientation is different.

[Lain]

Sorry I don't get it! =(
It's said that "The vertices for both polygons correspond to the same set of features in the same order"

For examle we may have:
1poligon: right ear tip, chin cleft, right eye, nose, left eye, left ear tip, space between front teeth
2poligon: space between front teeth, right ear tip, chin cleft, right eye, nose, left eye, left ear tip

Can you give me example.

[BiK]

I use the following idea: If the polygon's vertices are denoted by 1,2,3,...,n, then I chek if the triangles 123, 234, 345, ..., (n-2)(n-1)n, (n-1)n1, n12 are similar to the corresponding triangles in the second polygon. If this is the case, then I also check if the angles between the vectors 21 and 23, 32 and 34, 43 and 45, ..., n(n-1) and n1, and 1n and 12, have the same sign as their corresponding angles in the second polygon, thus checking if the polygons have the same orientation.

Is this correct? I keep receiving WA...

SM for BiK

[Lain]

2ditrix:
I don't know why, but when I rewrote my program it's got AC.
I understood what were you talking about, but I haven't had that mistake.
I didn't use angles, I used sin and cos instead:

sin = vx1*vy2-vx2*vy1;
cos = vx1*vx2+vy1*vy2;
where vx1, vy1, vx2, vy2 - two standardized vectors

[humaira]

1) Can anybody send me some critical inputs for this problem.
2) What is the criteria of scaling in the problem. whether the scaling would be done by fixing one particular point and then stretching the rest or whether it would be done with respect to a mid point.
3) Is it posible that a polygon is scaled first, translated to the third quardrant from the first quardrant and then reflected?

[gvcormac]

1) You can find the judges' data at plg.uwaterloo.ca/~acm00
2 & 3) I'm not sure I understand your questions, but I'll point out that when you do linear scaling, translation, and rotation, it doesn't make any difference what order you do them in.