pabloskimg's blog

Help: Area of intersection between triangle and convex polygon?
By pabloskimg, history, 5 years ago, In English

Hi, I'm trying to solve this problem. The problem turned out to be way harder than I expected, and my current solution has many lines of code, I have debugged it a lot with many hand-made test cases but I'm still getting WA. You can find my code here. I looked for a proper implementation of the area of the intersection between a triangle and a convex polygon but I couldn't find any. I would appreciate if someone with expertise in geometry could share his/her knowledge, or if someone could share a link to a proper implementation of this problem that would be awesome too, that way I can compare my solution with it and figure out what I'm doing wrong too.

Thank you very much.

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can help? maybe some corner cases I'm missing :( Thanks in advance

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for sharing the paper. Did you manage to get accepted using this approach?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        No, but I know even easier way. There is an important operation you can perform on convex hull: cutting it with a line. Not really with a line, because we also after cutting want to know, which side of our polygon we will leave, but with a half plane. It is relatively easy to do in O(n): represent a convex polygon as a list of points, add 0 or 2 points, which will be points of intersection of polygon with your line, leave only those points from polygon that are lying inside the half plane (it can be checked with directed area).

        Now to bound your convex polygon with triangle, cut your polygon 3 times with half planes representing lines that contain each segment from your triangle facing towards the center of triangle.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          I believe the problem with this approach is that, in the linked problem, there can be up to 10^5 points in the polygon and 10^5 triangles to calculate the area. So O(n) per triangle will be too slow.

          As far as calculating the intersection between a triangle and a convex polygon, another simple way is to use the following algorithm which finds the intersection of two convex polygons in O(nm + k log k)*, using the fact that the intersection of two convex polygons is also convex:

          ** being k the number of points in the final polygon (which I believe is O(n + m)). So for the triangle and polygon, this will be O(n log n).

          ConvexIntersectConvex(P1, P2):
  points = [];
  for(point p in P1)
    if(p is inside P2)
      points.add(p);
  for(point p in P2)
    if(p is inside P1)
      points.add(p);
  for(edge e1 in P1)
    for(edge e2 in P2)
      if(e1 intersects e2)
        points.add(intersection(e1, e2));
  return convexHull(points);

          Edit: according to https://discuss.codechef.com/t/chn02-editorial/12138, the set "points" is exactly the vertices of the polygon, so rather than actually calculating the convex hull, you could just sort the points clockwise. The complexity is still the same, but the code is shorter.

          → Reply