# C++ Program - Area of a Quadrilateral

1. Sep 8, 2009

### exitwound

(Reminder: This is a 2nd week problem for school. First C++ programming class. very limited input/output knowledge at this point.)

1. The problem statement, all variables and given/known data

(paraphrased) Have user input 4 ordered pairs of coordinates that go around the quadrilateral in either the CW or CCW direction. Output the area according to the standard formula:

.5 * (abs( (x1y2 - x2y1) + (x2y3 - x3y2) + (x3y4 - x4y3) + (x4y1-x1y4) ) )

Then, use Heron's formula to find the area. Break the quadrilateral up into two triangles by connecting vertices 1 & 3. Find area of Triangle 1, then Triangle 2, then sum them up.

Area = sqrt(s(s-a)(s-b)(s-c))
s= .5*perimeter

Then, use Heron's formula again to find the area but splitting the triangle through vertices 2 & 4.

3. The attempt at a solution

Okay, this is all fine and dandy and I have the program working completely, although I get an unsual error that I can't quite figure out how to fix, and it's only when the bonus question is involved.

The bonus question asks "what if the quadrilateral is concave? Write reliable code that can determine whether or not the quad is concave or convex."

And when I input a concave quadrilateral, such as with coordinates: (0,0)(2,0)(0,2)(1,1) I end up with the correct area being computed by the standard formula, but not by Heron's formula. This is because the 2nd triangle that is computed is outside the polygon.

BASICALLY: If I have a convex quad, all of the area found (by splitting up the quad into two triangles) is inside the polygon. If i have a concave quad, one of the triangles lies outside the polygon.

I can't figure out how to remedy this. I have a week to get this done so I'm in no rush.

2. Sep 8, 2009

### sylas

This is a maths question rather than a computing question. If you can sort out what is happening mathematically, then you can put it in the program.

Your formula for the triangle method involves square roots... and when you have square roots, then you might have an issue with plus and minus.

Sometimes you want to add the two triangles. Sometimes you want to subtract. Can you think of a way to tell when you add and when you subtract?

Cheers -- sylas

3. Sep 8, 2009

### exitwound

That's the issue I'm having. I can't visually figure out how to determine whether I should add or subtract the triangles, other than by knowing i already have a convex or concave poly. I also can't figure out mathematically how to determine that either at a glance.

4. Sep 8, 2009

### nvn

(0,0), (2,0), (0,2), (1,1) isn't a simple quadrilateral. That could confuse a program.

Last edited: Sep 8, 2009
5. Sep 8, 2009

### exitwound

Any four-sided shape is a quadrilateral.

6. Sep 8, 2009

### sylas

OK. Let's assume for a start that you don't have the sides of a quadrilateral actually intersecting like this!

$$\setlength{\unitlength}{1mm}\begin{picture}(40,40) \put(0,10){\line(0,1){20}} \put(0,10){\line(2,1){40}} \put(0,30){\line(1,-1){30}} \put(30,0){\line(1,3){10}} \end{picture}$$​

It's not enough to know concave/convex to decide whether you add or subtract the triangles. For example, in the first case you subtract, and in the second you add:
$$\setlength{\unitlength}{1mm}\begin{picture}(100,40) \put(0,0){\line(0,1){40}} \put(0,0){\line(1,1){40}} \put(0,40){\line(1,-2){10}} \put(10,20){\line(3,2){30}} \multiput(0,40)(2,0){20}{\line(1,0){1}} \put(60,0){\line(0,1){40}} \put(60,0){\line(1,1){40}} \put(60,40){\line(1,-2){10}} \put(70,20){\line(3,2){30}} \multiput(60.5,1)(1,2){10}{\circle{0.4}} \end{picture}$$​

It should be enough to decide whether two points are on the same side, or different sides, of a line through two other points. But there may be better methods still.

Are you required to use Heron's formula for the triangles? Is that part of the problem statement? Your input seems to be co-ordinates, not lengths.

Cheers -- sylas

PS. I have crossed posts with nvn. He's raised the same point I did. Sometimes four co-ordinates don't actually give you a four sided figure, because you might have intersecting sides; that's why I note that I'm assuming we don't have intersecting sides, which is technically not a quadrilateral.

7. Sep 8, 2009

### exitwound

Heron's formula is a MUST. We use the lengths of the sides (part of our assignment is learning the cmath operators) in the equation Area = sqrt(s(s-a)(s-b)(s-c)) after we split the quad.

Nice work on the latex code. The homework was stated as this. I believe that, for simplicity, the quads will not cross.

8. Sep 8, 2009

### sylas

The problem occurs, as the assignment states, when line bisecting the quadrilateral is actually outside the quadrilateral. That's what you should be looking for, I suspect.

9. Sep 18, 2009

### sumthing

Psu - cse 121?

10. Sep 19, 2009

Indeed!