Find area of a polygon. In C and Obj C.

Question

I've been given an assignment:

Create a console application (using C and Obj C) that will calculate area of a random polygon. The application should process input data as a .txt file with a list of Cartesian coordinates pairs in the following format:

(12;34)
(23;35)
(85;23)
...

From those pairs a polygon should be formed. Sides of the polygon (line segments) should not intersect. If they do - return an error. The application should divide the polygon into triangles, calculate their area, sum and then return the area of the polygon. Input processor, triangles and the sum operation - all should be implemented as a separate classes. The application should support command "help" and return info on how to use the app.

---

So far I've build the following algorithm. It lacks some features (that I need help with) and have several programmatical mistakes.

My questions are:

1. How to check that the sides of a polygon (line segments) - don't intersect? Each line segment should be checked to another. At which point of the algorithm this checking should take place?
2. If the polygon has concave sides, my algorithm of building triangles out of the first point fails. What would be the solution for that? (the app should work for the concave/complex polygons too)

---

1. The app processes the entry data. Form 2 NSMutableArrays one for X, the other for Y coordinates.
2. Count number of values in any array. If less then 3 - display an error "Entry at least 3 pairs to form a polygon".
3. Create class "Corner". Properties of it will be coordinates X and Y. An object of this class will be one corner of our polygon.
4. Create a for loop that should be repeated less than number of values in one of our NSMutableArrays.
5. At the start of the loop, we create one object from our "Corner" class. We take out from our NSMutableArrays coordinates and give it as properties of our "corner" object. This way, at the end of the loop cycle we will have all corners/vertexes created.
6. Every created Corner we will be adding to another array.
7. If the for loop already made at least 3 cycles - we already have 3 vertexes from which we can build the first triangle(from item 10 will learn why we care about triangles)
8. Therefore, we create a new class Triangle. We give it properties: "side1", "side2", "side3", "area".
9. Back to our "for" loop. We create an instance of the Triangle class.

10. Because we will be calculating area of our ultimate polygon, we can split it on triangles, calculate their area and then add them up. We will be drawing triangles from the first vertex: 1v->2v->3v; 1v->3v->4v; 1v->4v->5v... Because we know coordinate points - we can calculate length between points. Therefore, we know length of all sides of a triangle. To find an area of such triangle we can use Heron's formula (more about it in item 13). To calculate length between points we will create a new method inside the Triangle class: sideLengthWithVert:corner1 vert2:corner2 vert3:corner3 . That method takes corners/vertexes of the triangle - objects of "Corner" class and one after another calculates length between corners using formula: d=sqrt((x2-x1)^2+(y2-y1)^2). The length will be assigned to properties of a "Triangle" object - side1 side2 side3

11. (here I have an error in my code, I suspect it is a logical mistake) Since this method takes corners as arguments - we create those 3 corners out of our previously created arrays of corners. An error says: [__NSArrayM objectAtIndex:]:index 567 beyond bounds [0 .. 2] Where is index 567 comes from - I have no clue. In the method of angle creation I pass variable t that equals to number of cycles of the for loop.

12. We use newly created method: sideLengthWithVert:corner1 vert2:corner2 vert3:corner3 and give it our corners. Now our object Triangle has properties side1 side2 side3equaled length between corners.
13. Now we have a complete triangle we can calculate its area. For that we will write a new method inside class Triangle called calcArea. Inside it, we use Heron's formula: p=(a+b+c)/2 then A=sqt(p(p-a)(p-b)(p-c)) Once calculated, we give that to Triangle's property area.
14. We create a new NSMutableArray and add there our triangles that will be created with each cycle of our big for loop.
15. All what is last is to add up areas of triangles inside that last array. For that we create a condition "if we have at least one Triangle object created - perform following code: (inside next items 16, 17, 18) "
16. Calculate number of triangles inside the array. Create a cycle that will loop less or equal number of triangles inside the array. With each step add up triangle's areas.
17. If user enters calcin console - show the result of our computations.
18. If a user enters help in the console - show examples of usage of the application.

Answer 1

After checking that the input data forms a valid polygon, you can compute the area without triangulating the polygon. The key is to recognize that the area formula can be transformed by Green's theorem (http://en.wikipedia.org/wiki/Green%27s_theorem):

$$ A = \int_\Omega 1\,dA = \oint_{\partial\Omega}x\,dy = -\oint_{\partial\Omega} y\,dx= \frac{1}{2}\oint_{\partial\Omega}\left(-y\,dx + x\,dy \right) $$

Since you're given a description of the boundary, it is very natural to compute this line integral over the set of edges. Since you're integrating over linear edges, formulating this integral properly has already been done for you, and it is called the "Shoelace formula." The Wikipedia page for this has the formula written out explicitly several ways, so you can pick the version that is easiest to deal with for you.

http://en.wikipedia.org/wiki/Shoelace_formula

Checking for the intersection of two line segments can be done a lot of different ways, but one conceptually easy way to do it is to write each line n $y=mx + b$ form, compute the intersection of the two lines, then check whether the intersection occurs within the bounds of both line segments. Just be careful to handle perfectly vertical/horizontal lines properly, since that could be a likely opportunity for a divide-by-zero.

EDIT: Triangulation Method

Sorry, I didn't see the part in your question about requiring a triangulation. I came up with a pretty simple and effective way to triangulate the interior of a non-convex polygon. The basic idea is that you keep track of the interior, non-triangulated boundary polygon while you iteratively make triangles from this.

The basic algorithm written in pseudocode is this:

While(interiorPolygon.size() >= 3)

    [v1, v2, v3] = threeConsecutiveVertices in interiorPolygon
    if( isCCW(v1,v2,v3) )
       tris.add(v1,v2,v3)
       Drop v2 from interiorPolygon list
    end
end

The method assumes that the vertices that you are given are order counterclockwise around the border of the polygon. This is necessary because I used a isCCW(v1,v2,v3) function, which determines if {v1,v2,v3} form a triangle that is inside the polygon or outside the polygon. This can be achieved by computing the cross product of (v2-v1) and (v3-v1). If the cross product is positive, then the vertices form a counterclockwise triangle, which is in the interior of the polygon. Otherwise, the triangle formed by the vertices lies outside the interiorPolygon boundary.

I coded it up in Matlab, and a reasonably robust version can be done in < 20 lines of code (I didn't check for polygon validity). I'll leave you to flesh out the details and bookkeeping that need to happen in the code.