polygon is inside a polygon

[sanghamitra]

How to determine if a polygon is inside a given polygon?
Polygon is represented as list of points(x,y).

Also how to determine if a point in a polygon is on the border of a polygon?

[Gabriel Fleseriu]

Originally posted by sanghamitra
How to determine if a polygon is inside a given polygon?
Polygon is represented as list of points(x,y).

You have a few possibilities:
-- compute each polygon as a list of line segments, and see whether the segments of one polygon cross the segments of the other. Then determine if one point of one polygon is inside the other
-- simply determine if every point of one polygon is inside the other.

This is how you can determine if a point is inside a polygon:

-- compute all line segments that form the polygon
-- compute the intersections of these line segments with the horisontal positive halfline thru the point you want to test. Count the number of intersections. If the number is even, the point is outside the poygon. Watch out for the odd case where the half line hits exactly a poygon vertex.

You will need a bit of linear algebra for this -- have a look in your favorite textbook.

Also how to determine if a point in a polygon is on the border of a polygon?

This means determining whether the point solves one of the line segment equations for the polygon edges. Now the problem is that because of the finite precision of the floating point numbers, you can only determine whether a point is very close to an edge -- as opposed to "exactly on an edge".