Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I was able to find the co-ordinates of inner Polygon using this trick.

Need the co-ordinates of innerPolygon

But, I have some problem in getting the direction from Outer Polygon Point to Inner Polygon inside Point? See this image, I need to make sure that the direction should be from inner to outer.

enter image description here

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

In general, you need to have a parsing convention for your polygon. Once you adopt this for all your polygons, the answer is immediate. For instance, the following picture illustrates “when parsing the list of points, the inside of the polygon is always on the right”:

polygon parsing

Now what if you don't have this information yet? Here is one simple technique:

  • find the leftmost point of the polygon, call it A = P[n]; if there are several such points, pick the uppermost
  • pick the previous point and the next point in the list, B = P[n-1] and C = P[n+1]
  • compute the z coordinate of cross product AB × AC, aka. z = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y)
  • if z is positive, the inside of the polygon is on the right when parsing the list of points.
  • if z is negative, the inside of the polygon is on the left when parsing the list of points.

Note that the above needs only to be done once per polygon.

Now when you travel from A to B, a simple vector pointing to the left of the path is (A.y - B.y, B.x - A.x).

share|improve this answer
    
Thanks. This seems to be little complex. I was thinking that it is very easy. –  user960567 Apr 13 '12 at 6:36
    
@user960567 I believe it is very easy; maybe I wasn't clear enough? I'll update the answer a bit. –  Sam Hocevar Apr 13 '12 at 6:39
    
I don't get 'on the right when parsing the list of points'. –  user960567 Apr 13 '12 at 7:17
    
@user960567 when you parse the list of points making the polygon, you follow a path; on one side of the path there is the inside of the polygon and on the other side there is the outside. The test decides whether the inside is on the left side or on the right side of the path. –  Sam Hocevar Apr 13 '12 at 7:22
    
But in programming, there is no left or right. I need to use + or - during moving distance d from a point p with vector v. –  user960567 Apr 13 '12 at 7:24
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.