Here's one for you...

sonyafterdark · 2005-11-13 05:53:49

How can you find the amount of common surface area between 2 triangles, knowing the coordinates of all the 6 tips (and thus being able to calculate areas), without actually calculating intersections between edges, just by adding and substracting the different areas?

mathsyperson · 2005-11-13 07:29:49

It looks tricky. You could sketch the two triangles to see which of the lines overlap, work out the points of the shape formed and use the semi-perimeter rule to work out the area of that shape (splitting the shape up into triangles if it has 4, 5 or 6 sides), but you said you didn't want it to be done that way.

You can't do it by just adding or subtracting the areas of your 2 triangles because they could be completely overlapped, completely separate or somewhere in between, and that would affect the result.

sonyafterdark · 2005-11-13 19:58:56

The only restriction is that I may not calculate any edge intersections. Other than that, anything goes. I have tried splitting the triangles into more triangles and using their areas in additions and calculations, nothing I tried worked...

I know I can't do it by just adding the areas of the 2 triangles, but that is useful too... I have also tried defining a shape that contains the 2 triangles as well as some outside space left over, I have tried a lot of things... Can you please help?

I really don't know how i come up with these crazy problems... I'm not even sure it can be solved. Please try for me!!!

Oh, and it must work for any 2 triangles...

MathsIsFun · 2005-11-13 20:31:58

What a cool project!

The only way I can think of is to calculate the intersection points, and then work out the area of the polygon so created. There will be different cases:

* no intersection at all
* just touching (various types: points touching, point touching line, etc)
* various intersections
* one fully inside another

Have a look at this page, there is a java applet where you can draw and intersect shapes: http://www.cs.mcgill.ca/~gstamm/P507/bool_op.html

Another idea: you can calculate the area of a shape by calculating the area of each line segment down to the x-axis. If you always proceed clockwise (or counter-clockwise) and assign plus or minus area based on whether the line has increasing or decreasing x value, you get the net area (or possibly the negative of the net area). This little trick may help somehow.

Perhaps by defining a polygon made up of the two triangles? In other words triangle ABC and DEF become polygon ABCADEFD, then use my area method above ... worth an experiment.

ryos · 2005-11-14 06:11:36

Why can't you calculate the intersections? Is it too computationally intensive?

Mathematically, it's easy. Say you have two lines in point-slope form,
y = y1 + m(x - x1)
y = y2 + n(x - x2)

...that you know intersect. The intersection happens when both equations produce the same coordinates, so you can set the two variables equal to each other and solve the system by substitution:
y2 + nx - nx2 = y1 + mx - mx1
nx - mx = y1 - y2 + nx2 - mx1
x(n - m) = (y1 - y2) + (nx2 - mx1)

x = [ (y1 - y2) + (nx2 - mx1) ] / (n - m)

This is a general formula for the x coordinate of intersection. Sub back to get a formula for the y:
y = y1 - mx1 + {[ m(y1 - y2) + m(nx2 - mx1) ] / (n - m)}

There are many cases, and you'll have to define them all. In all cases, triangles allow you to find the area of the intersection. I suggest you sketch them all in order to work it out.

Good luck...

sonyafterdark · 2005-11-14 07:09:38

i now realise my approach was wrong. The reason i don't wan't to use edge intersection is that this would lead to a huge increase in complexity when coding. This little problem is only part of a much larger one that involves many other little problems all of which, once solved, will need to be computed as efficiently as possible by a computer... This means that the simplest/fastest formula will need to be used. Of course, a formula is always better than an algo.

I've given up adding and substracting areas as it's now clear this isn't the way to go...

I'm going to try and come up with a function of all of the tip coordinates of 2 triangles that returns the amount of common surface area, without requiring ANY if clauses. This was my goal in the first place.

But first, to avoid and possible needless hassle, I'm going to search for just such a function on the internet... If I fail to find one, I'm going to try and come up with one. Do you know of such a function? No ifs required? Please post if you do. 10x

MathsIsFun · 2005-11-14 08:19:10

Maybe if you explained what your goals are ... give us a wider picture of what you are after.

Perhaps there is a trade-off between speed and accuracy, or another way to achieve your objective.

Math Is Fun Forum

#1 2005-11-13 05:53:49

Here's one for you...

#2 2005-11-13 07:29:49

Re: Here's one for you...

#3 2005-11-13 19:58:56

Re: Here's one for you...

#4 2005-11-13 20:31:58

Re: Here's one for you...

#5 2005-11-14 06:11:36

Re: Here's one for you...

#6 2005-11-14 07:09:38

Re: Here's one for you...

#7 2005-11-14 08:19:10

Re: Here's one for you...

Board footer