Take the 2-minute tour ×

I have n points that determine a polygon. I need to color the interior of this polygon with a color . How can I do this?

share|improve this question
I assume the points are given in order? Because, in general, n points do not determine a polygon (for example, there are multiple polygons with vertices (0,0), (0,1), (1,0), (1,1), and (1/2, 1/2)). Also, are you doing this within a particular programming environment? –  Mitch Schwartz Dec 23 '10 at 8:34
Related to your problem: Point in polygon article on Wikipedia. –  Mitch Schwartz Dec 23 '10 at 8:38
yes, i'm doing it in c#. And yes, the vertices are in order. –  Badescu Alexandru Dec 23 '10 at 8:38
I believe this belongs on StackOverflow rather than here, unless you need to know something more of the mathematics. Does this link suit your needs? homeandlearn.co.uk/csharp/csharp_s15p4.html –  Mitch Schwartz Dec 23 '10 at 8:43

1 Answer 1

Here is one naive approach: triangulate the polygon (that's pretty easy to do and I will leave that to you to figure out) and then colour the triangles. That reduces the problem to determining the interior of a triangle that is given by three points. To do that, you could express the triangle as an intersection of three half planes. Then, each half plane is determined by a linear inequality, so given any point, you can determine whether it's in the interior by checking all three inequalities. The rest is accomplished by obvious loops, with judiciously chosen start and end values.

You can optimise some of that by putting more thought into how to set up the loops. E.g. if the outer loop goes through rows and the inner through the columns, then the starting point of the inner loop can be set to the left most point of the interior.

share|improve this answer

Your Answer


