1

I'm interested in writing a my own function that subtracts one 2D triangle from another, returning the remainder as a n array of triangles. (not using an existing geometry library)

Two examples of input & output, triangles are numbered, order isn't important.

enter image description here

While I'm familier with these kinds of algorithms, this seems like a general enough problem that there may be a known robust solution already written (if not I may look into writing one as an answer to this question)

ideasman42
  • 42,413
  • 44
  • 197
  • 320
  • It's not clear to me what the question is. Are you asking for links to polygon clipping literature, or example code, or libraries that can do polygon clipping? CGAL, for example, includes such functionality, using the idea of nef polygons. – Paul Hankin Sep 05 '20 at 08:45
  • What happen if the blue triangle is : exactly the same of the red triangle ( just scaled down ) and place in the middle of the red triangle ? – Goozzi Sep 05 '20 at 09:13
  • @paul-hankin I'm interested in example code or a paper that shows a tried & true method, e.g. https://stackoverflow.com/a/40902741/432509 – ideasman42 Sep 05 '20 at 10:54
  • @goozzi it will fill the area with triangles, I didn't include every possible case, there are however a limited number, this should be a reasonably straightforward solvable problem. _(why I'm asking here)._ – ideasman42 Sep 05 '20 at 10:55
  • 1
    This topic belongs to the group of CSG (constructive solid geomtry) operations. 99 % of cases are usually straight-forward to implement. The final 1%, however, are extra-ordinarily nasty and contain all kinds of corner-cases like non-manifold output, inconsistent decisions due to floating point precisions, etc. What are your robustness requirements? If you need something robust, I would suggest a mature CSG library (don't have one in my mind, but there should be some). – Nico Schertler Sep 06 '20 at 16:34
  • I was thinking since this is a simple enough problem, I wouldn't need a more complete CSG library. As for how robust, I'm interested in as robust as possible, without having to use a more generalized solution, since it should be possible to perform this faster than a function that operates on arbitrary polygons. – ideasman42 Sep 07 '20 at 06:03

1 Answers1

0

I recently work on this problem and resolved it.

I tried to describe all the possibilities of layering and I got there. There are 16 cases classified by number of points of the dimunuende triangle in the diminishing triangle and of the dimunutor in the diminuende. For information in the subtraction a - b = c, a is the dimunende and b is the diminutive, c is the difference. In the subtraction table, the diminishing triangle is represented in blue and the diminutive in red, at the bottom right of each box are indicated the points of each triangle included in the other. The number of triangles in the difference is at the top left of each box and finally the number of intersections in red at the bottom left.

My method consist to count intersections and points insides triangles. In some cases we must also determine the validity of the triangles either by intersection detection or by checking that it does not contain points. Finally i think, I believe, I managed to solve this problem.

Take a look on this forum for code source and more informations : https://gb32.proboards.com/post/2112/thread

Nicolas
  • 41
  • 2