C++ Program - Area of a Quadrilateral

[exitwound]

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

Homework Statement

(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.

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.

 

[sylas]

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.

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

 

[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.

 

[nvn]

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

 

[exitwound]

Any four-sided shape is a quadrilateral.

 

[sylas]

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.

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)<br /> \put(0,10){\line(0,1){20}}<br /> \put(0,10){\line(2,1){40}}<br /> \put(0,30){\line(1,-1){30}}<br /> \put(30,0){\line(1,3){10}}<br /> \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)<br /> \put(0,0){\line(0,1){40}}<br /> \put(0,0){\line(1,1){40}}<br /> \put(0,40){\line(1,-2){10}}<br /> \put(10,20){\line(3,2){30}}<br /> \multiput(0,40)(2,0){20}{\line(1,0){1}}<br /> \put(60,0){\line(0,1){40}}<br /> \put(60,0){\line(1,1){40}}<br /> \put(60,40){\line(1,-2){10}}<br /> \put(70,20){\line(3,2){30}}<br /> \multiput(60.5,1)(1,2){10}{\circle{0.4}}<br /> \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.

 

[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.

The grader will test your for these three quadrilaterals, plus some others that are not listed. You are encouraged to test it with others of your own.
(0,2), (0,0), (1.73205, 1), (1.73205, 2)
(-1.8,-1), (0.7,-1), (1.4, 1.4), (-1.1,1.4)
(1,1), (15,6), (17,8), (3,11)
Do not expect or demand parentheses or commas in your input.

All vertices will be supplied in sequence, either in clockwise or anti-clockwise order (no jumping across the middle).

[...]

BONUS Program Feature (5 points)
A convex polygon is one where any line connecting two points in the polygon lies completely within the polygon. All three polygons above are convex.

A concave polygon is one where a line connecting two points within the figure may lie partly outside the figure.

The calculations above can actually be used to determine whether a quadrilateral is concave or convex. Include code and an extra output reliably indicating whether the four input vertices describe a concave or convex polygon.

 

[sylas]

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.

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.

 

[sumthing]

Psu - cse 121?

 

[exitwound]

Indeed!