Calculating an Area Between Two Line Chart

Eman_321

I have attached a really beautiful image of two line charts :P .
I would like to find out the area between two line charts.
As this link states
http://leavingcertmaths.blogspot.ie/2008/04/simpsons-rule.html
Simpsons rule or Trapezoidal rule are good for finding out the area of an irregular shape.
So what I did was to calculate the area of the two line charts and subtract one from the other. The problem is I don't know if the trapezoidal/simpsons rule will take into account the area shaded in green.

So if it doesn't can any of you here tell me which algorithm I can use to calculate the area between the two charts taken into account the shaded areas or the intersects. Thanks!
I hope my explanation was clear.

srsly78

I did something like this recently, you could try as follows:

Consider two data sequences denoted by points a1, a2, a3.... an, and b1, b2,b3...bn.

It is possible to compose the geometry of the shaded area by "stitching" the vertices together into triangles (this is what I had to do for rendering purposes, but it also works for calculating area):

First triangle: a1, b1, a2
Second triangle: a2, b2, a3
Third triangle: a3, b3, a4

Thus triangle N = an, bn, a(n+1).
With the only special case being where they crossover, in this case you must calculate the intersection point (call this ah, bh). Then there are two triangles, (an,bh,ah) and (ah, bn, b(n+1)).

So you will need functions to do as follows (pretty easy):
Given 3 input vertices calculate the area of a triangle.
Given 2 line segments calculate the intersection point.

Algorithm looks like:
for (iterate over data)
Generate Triangle for this segment
Calculate area for this triangle
Add area to running total
end for

Yes there is probably a better analytic solution to this, but the method above is really simple if you draw it out on paper - no fancy maths involved at all.

Eman_321

srsly78 wrote: »

I did something like this recently, you could try as follows:

Consider two data sequences denoted by points a1, a2, a3.... an, and b1, b2,b3...bn.

It is possible to compose the geometry of the shaded area by "stitching" the vertices together into triangles (this is what I had to do for rendering purposes, but it also works for calculating area):

First triangle: a1, b1, a2
Second triangle: a2, b2, a3
Third triangle: a3, b3, a4

Thus triangle N = an, bn, a(n+1).
With the only special case being where they crossover, in this case you must calculate the intersection point (call this ah, bh). Then there are two triangles, (an,bh,ah) and (ah, bn, b(n+1)).

So you will need functions to do as follows (pretty easy):
Given 3 input vertices calculate the area of a triangle.
Given 2 line segments calculate the intersection point.

Algorithm looks like:
for (iterate over data)
Generate Triangle for this segment
Calculate area for this triangle
Add area to running total
end for

Yes there is probably a better analytic solution to this, but the method above is really simple if you draw it out on paper - no fancy maths involved at all.

I have an algorithm maybe you can help me with. I have made the chart more realistic in the image I have attached.

What I am doing is taking two points from each line chart at a time and working out the intersect. But I can't figure out how to find the intersect.
One image will show the realistic line chart the other image will show the two possible intersects. Thanks for replying!
If you can tell me how to find an intersect, it will be a start.
Finding the slope of the intersect where line is straight will be a problem because there will be a divide by zero exception.

y2-y1/x2-x1 to get the slopes for each line chart
Except as drawn in the image, if one of the line that intersects is straight (having the same x values), there is no slope. Do I just get y2-y1 instead?
I hope that makes sense.

Eman_321

Yeah I think I can see what you mean by the triangles. Although the triangles are not equilateral.
Can you explain this formula:
"Thus triangle N = an, bn, a(n+1).
With the only special case being where they crossover, in this case you must calculate the intersection point (call this ah, bh). Then there are two triangles, (an,bh,ah) and (ah, bn, b(n+1)). "

srsly78

No they aren't equilateral, and I made a few mistakes explaining it. To render stuff with opengl/directx you have to generate strips of triangles, which is why I was doing this in the first place. Using triangles is similar to the other numerical quadrature methods, the others use sums of trapezoids or whatever.

For each pair of line segments (4 input points), you can generate TWO triangles for the relevant area in between. Draw this out on paper to see why, just join the dots going up and down between sequences, just like tying your shoelaces. The datasequences crossing over each other is the special case.

Is easier to just paste some fragments of hlsl code :pac: Your problem is reduced to being able to find the area of an arbitrary triangle really.

float ax1, ay1, ax2, ay2;
float bx1, by1, bx2, by2;
float intersectx, intersecty; // coords where lines intersect
GS_OUTPUT_VERTEX v;

	ax1 = input[0].posA.x;
	ay1 = input[0].posA.y;
	
	ax2 = input[1].posA.x;
	ay2 = input[1].posA.y;
	
	bx1 = input[0].posB.x;
	by1 = input[0].posB.y;
	
	bx2 = input[1].posB.x;
	by2 = input[1].posB.y;

bool test1 = ay1 > by1;
bool test2 = ay2 > by2;

	if ( test1 != test2 ) // crossover special case detected
	{	
		float2 intersection = findLineIntersection( input[0].posA, input[1].posA, input[0].posB, input[1].posB );

		if (ay1 > by1) // first series greater - use it's color
			v.color = shade_color_A;
		else // use second series color
			v.color = shade_color_B;
			
		v.pos = float4(ax1, ay1, 0, 1);		
		TriStream.Append(v);
		v.pos = float4(intersection.x, intersection.y, 0, 1);
		TriStream.Append(v);
		v.pos = float4(bx1, by1, 0, 1);
		TriStream.Append(v);
		TriStream.RestartStrip();	
		
		if (ay2 > by2) // first series greater - use it's color
			v.color = shade_color_A;
		else // use second series color
			v.color = shade_color_B;

		v.pos = float4(intersection.x, intersection.y, 0, 1);
		TriStream.Append(v);
		v.pos = float4(ax2, ay2, 0, 1);
		TriStream.Append(v);
		v.pos = float4(bx2, by2, 0, 1);
		TriStream.Append(v);
		TriStream.RestartStrip();
	}	
	else
	{	
		if (ay1 > by1) // first series greater - use it's color
			v.color = shade_color_A;
		else // use second series color
			v.color = shade_color_B;

		v.pos = float4(ax1, ay1, 0, 1);
		TriStream.Append(v);
		v.pos = float4(bx1, by1, 0, 1);
		TriStream.Append(v);
		v.pos = float4(ax2, ay2, 0, 1);
		TriStream.Append(v);
		TriStream.RestartStrip();	
		
		v.pos = float4(bx1, by1, 0, 1);
		TriStream.Append(v);
		v.pos = float4(ax2, ay2, 0, 1);
		TriStream.Append(v);
		v.pos = float4(bx2, by2, 0, 1);
		TriStream.Append(v);
		TriStream.RestartStrip();	
	}

Eman_321

Hi srsly,
Thanks I managed to get it working.
But why do we need to find the intersect points?

srsly78

Because if the lines intersect it's a special case, and the intersection point gets used as one of the vertices. Draw it out on paper, join the dots and you will see.

Rendered output looks like this from method above: https://dl.dropbox.com/u/4436079/images/work/sampledelta.png

Eman_321

srsly78 wrote: »

Because if the lines intersect it's a special case, and the intersection point gets used as one of the vertices. Draw it out on paper, join the dots and you will see.

Rendered output looks like this from method above: https://dl.dropbox.com/u/4436079/images/work/sampledelta.png

I am not really good at math, so I am not sure what to look for.
But yeah when there is an intersection it could sometimes mean a negative area, is that what you mean?
That image you attached is bang on.

srsly78

Forget about maths. Get pen + paper.

Draw sequence of dots for series A. Join these to form line.
Draw sequence of dots for series B. Join these to form line.

Start joining the dots, start at A1.
Go A1 -> B1 -> A2 -> B2 -> A3 -> B3 -> etc etc.

Now look at paper, notice you have demarcated a bunch of triangles.

Consider a single pair of line segments, denoted by A1, A2, B1, B2. Notice that these segments demarcate two triangles: (A1, A2, B1), (A2, B1, B2).

Now do the operation again, but this time consider a pair of line segments that cross over. Notice how in this case you need the intersection point to make the triangles, this is a special case from above.

There is no such thing as negative area btw, you are getting too hung up on numbers.


edit: I'm feeling generous today.

// line segment A has points A1(x,y) and A2(x,y)
// line segment B has points B1(x,y) and B2(x,y)
float2 findLineIntersection( float2 pointA1, float2 pointA2, float2 pointB1, float2 pointB2 )
{
float2 result;
// see: http://paulbourke.net/geometry/lineline2d/ for example

// precompute needed values
float ua = ( ( pointB2.x - pointB1.x ) * ( pointA1.y - pointB1.y ) ) - ( ( pointB2.y - pointB1.y ) * ( pointA1.x - pointB1.x ) );
float denom = ( ( pointB2.y - pointB1.y ) * ( pointA2.x - pointA1.x ) ) - ( ( pointB2.x - pointB1.x ) * ( pointA2.y - pointA1.y ) );
	ua = ua / denom;

float ub = ( ( pointA2.x - pointA1.x ) * ( pointA1.y - pointB1.y ) ) - ( ( pointA2.y - pointA1.y ) * ( pointA1.x - pointB1.x ) );
	denom = ( ( pointB2.y - pointB1.y ) * ( pointA2.x - pointA1.x ) ) - ( ( pointB2.x - pointB1.x ) * ( pointA2.y - pointA1.y ) );
	ub = ub / denom;
	
// now use ua and ub to find our result
	result.x = pointA1.x + ( ua * ( pointA2.x - pointA1.x ) );
	result.y = pointA1.y + ( ub * ( pointA2.y - pointA1.y ) );

	return result;
}

Eman_321

Wow thanks,
Which is more accurate, trapezoid rule or triangle?

srsly78

Well a trapezoid is just a bunch of triangles so they are equivalent :pac: This is 100% accurate for discrete series of numbers, but other numerical methods using curves are better for real mathematical functions.

Eman_321

srsly78 wrote: »

Well a trapezoid is just a bunch of triangles so they are equivalent :pac: This is 100% accurate for discrete series of numbers, but other numerical methods using curves are better for real mathematical functions.

I posted an image showing the intersection points. And yeah I can see triangles that you speak of. But I could have formed this triangles without the intersects.

Eman_321

I posted a line chart with no intersection, drawing out the triangles. Sorry my drawing sucks

Eman_321

Correct image

srsly78

Image is wrong, you have drawn triangles outside the target area.

Eman_321

srsly78 wrote: »

Image is wrong, you have drawn triangles outside the target area.

Yes, I see ha ha. Thanks!

Eman_321

What about this image? Notice how I skip the intersection?
Using the intersection points do create almost perfect triangles/trapezoids. But without the intersection points I am able to draw some triangles.

Eman_321

Image

srsly78

Nope still wrong. Just join the dots it isn't difficult :pac:

Consider pair of line segments denoted by A1, A2, B1 and B2.

Draw as follows:
Join A1 -> A2 ... this is the normal data line for sequence A.
Join B1 -> B2 ... this is the normal data line for sequence B.

Now... join A1->B1, and B1-> A2 to make first triangle (A1, B1, A2).
For second triangle join A2->B2, to make second triangle (B1, A2, B2).

Just keep repeating.

Drawing any lines outside the "area between curves" is wrong.

Eman_321

srsly78 wrote: »

Nope still wrong. Just join the dots it isn't difficult :pac:

Consider pair of line segments denoted by A1, A2, B1 and B2.

Draw as follows:
Join A1 -> A2 ... this is the normal data line for sequence A.
Join B1 -> B2 ... this is the normal data line for sequence B.

Now... join A1->B1, and B1-> A2 to make first triangle (A1, B1, A2).
For second triangle join A2->B2, to make second triangle (B1, A2, B2).

Just keep repeating.

Drawing any lines outside the "area between curves" is wrong.

It seems the purpose of the points of intersection, is to form a triangle that is within the "area between the curves", without it I find myself drawing triangles outside the intended area. Is that what you see as well?

srsly78

Forget about intersection point, that's a special case. Solve the normal case first before even worrying about this.

The normal case is when lines DON'T cross each other - there is no intersection.

Eman_321

srsly78 wrote: »

Forget about intersection point, that's a special case. Solve the normal case first before even worrying about this.

The normal case is when lines DON'T cross each other - there is no intersection.

I actually found a problem with my algorithm - normal case.
I didn't check if y1==y2, so there isn't any slope equals no triangle. But there is a rectangle. I guess the area of the rectangle should be enough.

srsly78

A rectangle = 2 triangles. No difference.

srsly78

https://dl.dropbox.com/u/4436079/images/work/pikturebetterthanwerds.png
Normal triangles shaded red/blue, special case cross over triangles shaded with green/cyan.

Eman_321

srsly78 wrote: »

https://dl.dropbox.com/u/4436079/images/work/pikturebetterthanwerds.png
Normal triangles shaded red/blue, special case cross over triangles shaded with green/cyan.

That looks fine yeah. I understand that it is a special case - they are special because I can't calculate the area for each triangle as I would normally do - but why we need to find the intersection points is what I don't get.
Apart from the fact that they form new triangles.
And you are using Opengl for this, right?

srsly78

Using directx, but you could do the same with opengl.

Just keep staring at the picture until the penny drops. The intersection point needs to be generated because it gets used as a vertex sometimes.

Eman_321

srsly78 wrote: »

Using directx, but you could do the same with opengl.

Just keep staring at the picture until the penny drops. The intersection point needs to be generated because it gets used as a vertex sometimes.

Ok I think I understand why I need to find the intersection point.
In the attached image.
If I was to pick the drawn trapezoids separately then I am ignoring the fact that there are two distinct areas. So by ignoring the intersection, I am treating it like a normal case.
If it is as simple as that... I will kick myself.

Eman_321

Please tell me if I am wrong... I am dying to know lol

srsly78

I have no idea... Dunno why you are trying to draw trapezoids at all :pac: