Commons Math
  1. Commons Math
  2. MATH-668

Polygon difference function produces erroneous results with certain polygons

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Not a Problem
    • Affects Version/s: 3.0
    • Fix Version/s: 3.0

      Description

      For some polygons, the difference function produces erroneous results. This appears to happen when one polygon is completely encompassed in another, and the outer has multiple concave sections.

      1. PolygonsSetTest.java
        6 kB
        Curtis Jensen
      2. PolygonsSetCircleTest.java
        4 kB
        Curtis Jensen

        Activity

        Hide
        Curtis Jensen added a comment -

        There are two test cases here. The first "testdifference1" produces 3 polygons, two of which are correct (one outer polygon and one inner hole polygon). The third polygon is a rectangular region in the lower left corner of the outer polygon and should not be there.

        The second test case "testdifference2" is a simpler example. Technically, the results are not incorrect, but they are strange. This example is included because it seems interesting and may help understand the problem. The inner resultant polygon has two extra points that are collinear with two edges on the polygon. The extra points don't change the shape of the polygon, but they don't need to be there.

        Show
        Curtis Jensen added a comment - There are two test cases here. The first "testdifference1" produces 3 polygons, two of which are correct (one outer polygon and one inner hole polygon). The third polygon is a rectangular region in the lower left corner of the outer polygon and should not be there. The second test case "testdifference2" is a simpler example. Technically, the results are not incorrect, but they are strange. This example is included because it seems interesting and may help understand the problem. The inner resultant polygon has two extra points that are collinear with two edges on the polygon. The extra points don't change the shape of the polygon, but they don't need to be there.
        Hide
        Curtis Jensen added a comment -

        Never mind on testdifference1. I think I see the problem (bottom left corner of outer polygon is ambiguous). I'll work on creating a better example. Though, testdifference2 is still an interesting case.

        Show
        Curtis Jensen added a comment - Never mind on testdifference1. I think I see the problem (bottom left corner of outer polygon is ambiguous). I'll work on creating a better example. Though, testdifference2 is still an interesting case.
        Hide
        Curtis Jensen added a comment -

        This circle test case takes the difference of two concentric circles. The results produces is an empty list of vertices, when it should be the outer circle with a hole where the inner circle is.

        Show
        Curtis Jensen added a comment - This circle test case takes the difference of two concentric circles. The results produces is an empty list of vertices, when it should be the outer circle with a hole where the inner circle is.
        Hide
        Thomas Neidhart added a comment -

        I have checked the attached test cases:

        • circle test: you remove the outer circle from the inner one, resulting in an empty polygon set, which is correct behaviour. If you switch the two circles, the correct result is returned: a PolygonsSet with two loops: the two circles itself.
        • testdifference2: the described behaviour is implementation specific due to the way the hyperplane is cut when subtracting the two regions.
        Show
        Thomas Neidhart added a comment - I have checked the attached test cases: circle test: you remove the outer circle from the inner one, resulting in an empty polygon set, which is correct behaviour. If you switch the two circles, the correct result is returned: a PolygonsSet with two loops: the two circles itself. testdifference2: the described behaviour is implementation specific due to the way the hyperplane is cut when subtracting the two regions.
        Hide
        Luc Maisonobe added a comment -

        The fix would probably not imply API change, so it can be delayed to 3.1.

        Show
        Luc Maisonobe added a comment - The fix would probably not imply API change, so it can be delayed to 3.1.
        Hide
        Luc Maisonobe added a comment -

        I agree with Thomas analyses.

        Concerning the difference2 case, the two points are explained by the vertical line at x = 5.0 which comes from the outer shape. The internal representation is a BSP tree and one of this part of the outer boundary creates an hyperplane that splits the inner triangle. When the boundary representation is rebuilt, the two segments are glued together and the points appear there. There is no post-processing that simplifies the representation afterwards.

        Concerning the circle test, I guess you mixed the arrays. What is really in the code is that the vertices2 array is build first from outer circle and the vertices1 array is built afterwards from inner circle. So you are really subtracting a big disk from a smaller one. As Thomas explained, computing set2 minus set1 give the expected two boundaries. Another possible change is to build the circles clockwise instead of counter-clockwise, and in this case the two regions are infinite wich a whole at the center, then subtracting set2 from set1 returns a disk with a hole.

        Show
        Luc Maisonobe added a comment - I agree with Thomas analyses. Concerning the difference2 case, the two points are explained by the vertical line at x = 5.0 which comes from the outer shape. The internal representation is a BSP tree and one of this part of the outer boundary creates an hyperplane that splits the inner triangle. When the boundary representation is rebuilt, the two segments are glued together and the points appear there. There is no post-processing that simplifies the representation afterwards. Concerning the circle test, I guess you mixed the arrays. What is really in the code is that the vertices2 array is build first from outer circle and the vertices1 array is built afterwards from inner circle. So you are really subtracting a big disk from a smaller one. As Thomas explained, computing set2 minus set1 give the expected two boundaries. Another possible change is to build the circles clockwise instead of counter-clockwise, and in this case the two regions are infinite wich a whole at the center, then subtracting set2 from set1 returns a disk with a hole.

          People

          • Assignee:
            Luc Maisonobe
            Reporter:
            Curtis Jensen
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Time Tracking

              Estimated:
              Original Estimate - 168h
              168h
              Remaining:
              Remaining Estimate - 168h
              168h
              Logged:
              Time Spent - Not Specified
              Not Specified

                Development