-5

I want to solve a question, but it's a little hard and I need some help. The question is:

we have 2 triangles, and we have the coordinates of the vertices like (x1, y1), (x2, y2), (x3, y3), (a1, b1), (a2, b2), (a3, b3). We want to measure the area that two triangles are on each other. It may be 0 or more.

For example, if we have for first triangle (0,0) (3,0) (0,3) and the second (0,0) (3,3) (3,0), the common area will be 2.25.

How should i write a program to solve this?

Acorbe
  • 8,367
  • 5
  • 37
  • 66
Zoli
  • 588
  • 2
  • 8
  • 13
  • possible duplicate of [area of intersection of two triangles, or a set of halfplanes, or area of a convex point set](http://stackoverflow.com/questions/3074371/area-of-intersection-of-two-triangles-or-a-set-of-halfplanes-or-area-of-a-conv) – harold Oct 26 '12 at 16:07
  • 5
    Smells like someone doesn't want to do their homework. – George Oct 26 '12 at 16:09
  • it is not home work and i am working on it why are giving negative i don't know i – Zoli Oct 26 '12 at 16:14
  • @ZiDom - We get this on Fridays!. The person could simplify the problem as to finding out it two lines intersect. Done that problem when I was 13! – Ed Heal Oct 26 '12 at 16:16
  • why its closed the question is clear and i give an example to i don't want you solve it i want just some idea's – Zoli Oct 26 '12 at 16:16
  • @EdHeal, not that easy, indeed, when you have to do it 1M times per second... I provided an answer, btw. – Acorbe Oct 26 '12 at 16:19
  • 3
    I expect most of the close votes were the result of two things: 1) your original question had no punctuation, which gave the impression you put no effort into asking the question. 2) You didn't show us what you tried so far, which gave the impression that you put no effort into trying to solve the question. – Kevin Oct 26 '12 at 16:23
  • thanks for the editing of the punctuation i didn't notice that and a bout what i tried so far yes maybe i should said that to but it was hard to explain and it wasn't complete btw when i completed my own ideas or when i solved it i will post here – Zoli Oct 26 '12 at 16:33
  • @ZiDoM - I didn't vote to close... but I think you're looking in the wrong place. If you have questions on specific programming problems (logic/syntax errors for example) ask on SO. You're not looking for help on a specific problem, this is an algorithm concept question, I think that'd be better on http://programmers.stackexchange.com/ – Mike Oct 26 '12 at 16:35
  • @Acorbe - Yes it is that easy. You can find out any points where the two triangles intersect. (one line from the first, three from the second, then repeat). This will give you a polygon or say that the two triangles do not intersect. If they do not intersect take any corner and see if it is inside the other. Simple bit of maths. – Ed Heal Oct 26 '12 at 16:36
  • @EdHeal, please consider my answer. Obviously the problem is trivial if you can lose you time reconstructing the structure of the intersection. What if you wanna go through your vertices just once?? i.e. something like `for(i = 0; i< 3 ; i++)` and that's it?..now it's way harder and there are theorems behind. Of course, if you have to solve an homework you don't need this, but my answer is more..general. – Acorbe Oct 26 '12 at 16:42
  • @Acorbe - I have considered your answer and programmed something similar in the past. Just take each vertex of the first triangle and see it it intersects the other vertices of the other triangle. At most that is going to be two points. Do that for all vertices of the first triangle. That may give you a polygon. If not one triangle may be in the other. Use the winding rule http://en.wikipedia.org/wiki/Point_in_polygon - quite simple to program. – Ed Heal Oct 26 '12 at 16:49
  • @EdHeal, still you can be faster than that. What about distances that are close to machine precision? BTW, non standard PDEs and measure based equations are solved using this kind of intersection in large and complicated domains, meshed with triangles. Sorry, I am a bit concerned with this problem ;) . – Acorbe Oct 26 '12 at 16:53
  • 1. You do not use floating point numbers, use integers instead. 2. divide the plane up into squares. 3. If the two lines pass through the same square that is good enough. If want more accuracy - make those squares smaller. i.e. digitize it to you are happy with accuracy – Ed Heal Oct 26 '12 at 17:06

1 Answers1

6

The problem of intersecting triangles (and convex polygon in general) is way tougher than it seems, especially if you wanna solve it in linear time with respect to the number of edges involved.

You can consider this page to have an idea of a working algorithm for general convex polygons (the algorithm is based on rotating calipers. Indeed, there's some abstract geometry behind, in particular, the geometric Hanh-Banach theorem).

Consider that once you have the intersection polygon, which is convex, evaluating the area is trivial.

Thus, you have two options:

  1. You keep the problem abstract (somehow you consider triangles as convex polygons, and that's it) and a fast solution in C/C++ can be achieved through the GPC library (which is written in C) or, alternatively, for instance, through boost::geometry.

  2. You specialize just for triangles: in this case, my advice is to consider this wonderful paper which details topologically the possible ways of intersecting involved, and gives an efficient implementation of the solution.

I have one more thing to say: when you consider your problem with toy triangles (i.e. low skewness, sizes way larger than machine precision) you can still think to implement your own algorithm and play with it. But, when you have to intersect millions of possibly ill-conditioned triangles per second, you'd better rely on a good and fast library.

Acorbe
  • 8,367
  • 5
  • 37
  • 66