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?
color polygon interior in different color
-
0I 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? – 2010-12-23
-
1Related to your problem: [Point in polygon](http://en.wikipedia.org/wiki/Point_in_polygon) article on Wikipedia. – 2010-12-23
-
0yes, i'm doing it in c#. And yes, the vertices are in order. – 2010-12-23
-
1I believe this belongs on StackOverflow rather than here, unless you need to know something more of the mathematics. Does this link suit your needs? http://www.homeandlearn.co.uk/csharp/csharp_s15p4.html – 2010-12-23
1 Answers
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.