Polygon Decomposition Bugs

Posts regarding potential bugs, enhancement requests, and general feedback on use of dyn4j
tridol
Posts: 3
Joined: Sun Jun 08, 2014 3:52 am

Polygon Decomposition Bugs

Postby tridol » Sun Jun 08, 2014 4:22 am

I have been getting errors when decomposing certain concave polygons.

The following

Code: Select all

      Vector2[] physicsArray;
      Decomposer d;
      physicsArray = new Vector2[16];

      physicsArray[0] = new Vector2(9, 2);
      physicsArray[1] = new Vector2(8, 2);
      physicsArray[2] = new Vector2(8, 3.5);
      physicsArray[3] = new Vector2(9, 3.5);
      physicsArray[4] = new Vector2(9, 5);
      physicsArray[5] = new Vector2(8.5, 5);
      physicsArray[6] = new Vector2(8.5, 4);
      physicsArray[7] = new Vector2(6, 4);
      physicsArray[8] = new Vector2(6, 5.5);
      physicsArray[9] = new Vector2(8, 5.5);
      physicsArray[10] = new Vector2(8, 6.5);
      physicsArray[11] = new Vector2(9, 6.5);
      physicsArray[12] = new Vector2(9, 9);
      physicsArray[13] = new Vector2(0, 9);
      physicsArray[14] = new Vector2(0, 0);
      physicsArray[15] = new Vector2(9, 0);

      d = new Bayazit();
      d.decompose(physicsArray);

produces
java.lang.IllegalArgumentException: A simple polygon cannot have crossing edges.
at org.dyn4j.geometry.decompose.Bayazit.decomposePolygon(Bayazit.java:249)
at org.dyn4j.geometry.decompose.Bayazit.decomposePolygon(Bayazit.java:237)
at org.dyn4j.geometry.decompose.Bayazit.decomposePolygon(Bayazit.java:238)
at org.dyn4j.geometry.decompose.Bayazit.decomposePolygon(Bayazit.java:238)
at org.dyn4j.geometry.decompose.Bayazit.decomposePolygon(Bayazit.java:238)
at org.dyn4j.geometry.decompose.Bayazit.decompose(Bayazit.java:78)


however it works fine for EarClipping and SweepLine. This occurs in both dyn4j 3.1.8 and 3.1.9.

Additionally,

Code: Select all

      Vector2[] physicsArray;
      Decomposer d;
      physicsArray = new Vector2[34];

      physicsArray[0] = new Vector2(3.3232234, 6.676777);
      physicsArray[1] = new Vector2(4.323223, 6.676777);
      physicsArray[2] = new Vector2(4.323223, 9.323223);
      physicsArray[3] = new Vector2(3.3232234, 9.323223);
      physicsArray[4] = new Vector2(3.3232234, 10.676777);
      physicsArray[5] = new Vector2(4.323223, 10.676777);
      physicsArray[6] = new Vector2(4.323223, 11.323223);
      physicsArray[7] = new Vector2(2.6767766, 11.323223);
      physicsArray[8] = new Vector2(2.6767766, 9.323223);
      physicsArray[9] = new Vector2(1.3232234, 9.323223);
      physicsArray[10] = new Vector2(1.3232234, 12.676777);
      physicsArray[11] = new Vector2(4.676777, 12.676777);
      physicsArray[12] = new Vector2(4.676777, 11.676777);
      physicsArray[13] = new Vector2(5.676777, 11.676777);
      physicsArray[14] = new Vector2(5.676777, 10.676777);
      physicsArray[15] = new Vector2(9.323223, 10.676777);
      physicsArray[16] = new Vector2(9.323223, 11.323223);
      physicsArray[17] = new Vector2(6.323223, 11.323223);
      physicsArray[18] = new Vector2(6.323223, 14.323223);
      physicsArray[19] = new Vector2(5.676777, 14.323223);
      physicsArray[20] = new Vector2(5.676777, 13.323223);
      physicsArray[21] = new Vector2(2.3232234, 13.323223);
      physicsArray[22] = new Vector2(2.3232234, 14.323223);
      physicsArray[23] = new Vector2(-0.3232233, 14.323223);
      physicsArray[24] = new Vector2(-0.32322332, 5.676777);
      physicsArray[25] = new Vector2(0.6767767, 5.676777);
      physicsArray[26] = new Vector2(0.67677665, 4.676777);
      physicsArray[27] = new Vector2(1.3232232, 4.676777);
      physicsArray[28] = new Vector2(1.3232234, 8.676777);
      physicsArray[29] = new Vector2(2.6767766, 8.676777);
      physicsArray[30] = new Vector2(2.6767766, 4.676777);
      physicsArray[31] = new Vector2(5.323223, 4.676777);
      physicsArray[32] = new Vector2(5.323223, 5.323223);
      physicsArray[33] = new Vector2(3.3232234, 5.323223);
      
      d = new EarClipping();
      d.decompose(physicsArray);

produces
java.lang.IllegalArgumentException: A polygon must be convex.
at org.dyn4j.geometry.Polygon.<init>(Polygon.java:96)
at org.dyn4j.geometry.Geometry.createPolygon(Geometry.java:423)
at org.dyn4j.geometry.decompose.DoublyConnectedEdgeList.getConvexDecomposition(DoublyConnectedEdgeList.java:562)
at org.dyn4j.geometry.decompose.EarClipping.decompose(EarClipping.java:116)


but only for EarClipping; SweepLine and Bayazit are unaffected, and produce a valid decomposition. This occurs in both dyn4j 3.1.8 and 3.1.9.

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Polygon Decomposition Bugs

Postby William » Mon Jun 09, 2014 7:32 am

Thanks for the test cases. Both bugs are confirmed.

I've opened a bug #15 for the EarClipping issue. I've also made an update to the code that I'd like you to test (see the attached .jar).

I'm still working through the issue with Bayazit. I have a feeling this is related to bug #12, but I haven't had a chance to confirm yet.

Thanks,
William
Attachments
dyn4j-v3.1.10-beta2.jar
dyn4j 3.1.10 beta2
(354.88 KiB) Downloaded 120 times

tridol
Posts: 3
Joined: Sun Jun 08, 2014 3:52 am

Re: Polygon Decomposition Bugs

Postby tridol » Tue Jun 10, 2014 11:32 pm

The new code you provided works for the original test, but now fails for the following:

Code: Select all

Vector2[] physicsArray;
      Decomposer d = new EarClipping();
      physicsArray = new Vector2[30];
      physicsArray[0] = new Vector2(9.5, 6.5);
      physicsArray[1] = new Vector2(7.5, 6.5);
      physicsArray[2] = new Vector2(7.5, 5.5);
      physicsArray[3] = new Vector2(6.5, 5.5);
      physicsArray[4] = new Vector2(6.5, 4.5);
      physicsArray[5] = new Vector2(5.5, 4.5);
      physicsArray[6] = new Vector2(5.5, 6.5);
      physicsArray[7] = new Vector2(3.5, 6.5);
      physicsArray[8] = new Vector2(3.5, 7.5);
      physicsArray[9] = new Vector2(4.5, 7.5);
      physicsArray[10] = new Vector2(4.5, 8.5);
      physicsArray[11] = new Vector2(5.5, 8.5);
      physicsArray[12] = new Vector2(5.5, 6.5);
      physicsArray[13] = new Vector2(7.5, 6.5);
      physicsArray[14] = new Vector2(7.5, 7.5);
      physicsArray[15] = new Vector2(9.5, 7.5);
      physicsArray[16] = new Vector2(9.5, 9.5);
      physicsArray[17] = new Vector2(8.5, 9.5);
      physicsArray[18] = new Vector2(8.5, 8.5);
      physicsArray[19] = new Vector2(7.5, 8.5);
      physicsArray[20] = new Vector2(7.5, 9.5);
      physicsArray[21] = new Vector2(3.5, 9.5);
      physicsArray[22] = new Vector2(3.5, 8.5);
      physicsArray[23] = new Vector2(2.5, 8.5);
      physicsArray[24] = new Vector2(2.5, 7.5);
      physicsArray[25] = new Vector2(0.49999997, 7.5);
      physicsArray[26] = new Vector2(0.49999997, 9.5);
      physicsArray[27] = new Vector2(-0.49999997, 9.5);
      physicsArray[28] = new Vector2(-0.5, -0.49999994);
      physicsArray[29] = new Vector2(9.5, -0.49999997);
      d.decompose(physicsArray);

Whereas with 3.1.9 the above works fine. Notably,

Code: Select all

Vector2[] physicsArray;
      Decomposer d = new EarClipping();
      physicsArray = new Vector2[30];
      physicsArray[0] = new Vector2(9.5, 6.5);
      physicsArray[1] = new Vector2(7.5, 6.5);
      physicsArray[2] = new Vector2(7.5, 5.5);
      physicsArray[3] = new Vector2(6.5, 5.5);
      physicsArray[4] = new Vector2(6.5, 4.5);
      physicsArray[5] = new Vector2(5.5, 4.5);
      physicsArray[6] = new Vector2(5.5, 6.5);
      physicsArray[7] = new Vector2(3.5, 6.5);
      physicsArray[8] = new Vector2(3.5, 7.5);
      physicsArray[9] = new Vector2(4.5, 7.5);
      physicsArray[10] = new Vector2(4.5, 8.5);
      physicsArray[11] = new Vector2(5.5, 8.5);
      physicsArray[12] = new Vector2(5.5, 6.5);
      physicsArray[13] = new Vector2(7.5, 6.5);
      physicsArray[14] = new Vector2(7.5, 7.5);
      physicsArray[15] = new Vector2(9.5, 7.5);
      physicsArray[16] = new Vector2(9.5, 9.5);
      physicsArray[17] = new Vector2(8.5, 9.5);
      physicsArray[18] = new Vector2(8.5, 8.5);
      physicsArray[19] = new Vector2(7.5, 8.5);
      physicsArray[20] = new Vector2(7.5, 9.5);
      physicsArray[21] = new Vector2(3.5, 9.5);
      physicsArray[22] = new Vector2(3.5, 8.5);
      physicsArray[23] = new Vector2(2.5, 8.5);
      physicsArray[24] = new Vector2(2.5, 7.5);
      physicsArray[25] = new Vector2(0.5, 7.5);
      physicsArray[26] = new Vector2(0.5, 9.5);
      physicsArray[27] = new Vector2(-0.5, 9.5);
      physicsArray[28] = new Vector2(-0.5, -0.5);
      physicsArray[29] = new Vector2(9.5, -0.5);
      d.decompose(physicsArray);

simply changing all .499.... to .5 works.

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Polygon Decomposition Bugs

Postby William » Sat Jun 14, 2014 10:33 pm

Thanks. Sorry for the long wait. Give the attached jar a try when you get a chance.

William
Attachments
dyn4j-v3.1.10-beta3.jar
dyn4j 3.1.10 beta3
(355 KiB) Downloaded 105 times

tridol
Posts: 3
Joined: Sun Jun 08, 2014 3:52 am

Re: Polygon Decomposition Bugs

Postby tridol » Fri Jun 20, 2014 9:48 pm

Apologies for the long reply, finals are keeping me away. EarClipping and SweepLine now work for my test cases, and I cannot seem to cause it to produce any more errors, though will keep on the look out. I assume Bayazit is still being worked on? As it still fails.

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Polygon Decomposition Bugs

Postby William » Mon Jun 23, 2014 1:05 pm

tridol wrote:Apologies for the long reply, finals are keeping me away.

No worries, I appreciate the testing.

tridol wrote:EarClipping and SweepLine now work for my test cases, and I cannot seem to cause it to produce any more errors, though will keep on the look out.

If you find anything else with it don't hesitate to let me know.

tridol wrote:I assume Bayazit is still being worked on? As it still fails.

Correct. I'm working on a solution, but it may be a while.

Thanks,
William

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Polygon Decomposition Bugs

Postby William » Thu Jun 26, 2014 7:07 am

I have another update that should fix Bayazit. Sadly the fix does make it good bit slower. Still useful for small to medium size polygons and I have a few ideas on how to make things a little faster.

If you'd like to give it try see the attached jar.

William
Attachments
dyn4j-v3.1.10-beta4.jar
dyn4j v3.1.10 beta4
(355.95 KiB) Downloaded 116 times

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Polygon Decomposition Bugs

Postby William » Sun Jul 20, 2014 12:58 pm

I've published version 3.1.10 which includes these fixes.

William


Return to “Bugs, Enhancements, Feedback”

Who is online

Users browsing this forum: No registered users and 1 guest