NullPointerException in SweepLine

Posts regarding potential bugs, enhancement requests, and general feedback on use of dyn4j
William
Site Admin
Posts: 349
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Sat Jan 11, 2014 8:11 pm

Ok, no problem. Give this one a try.

William
Attachments
dyn4j-v3.1.9-beta4.jar
dyn4j beta 4
(346.12 KiB) Downloaded 103 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Mon Jan 13, 2014 1:36 pm

Haven't had much time to try out but I managed to get sweepline (beta4) stuck again. Sadly I did not have logging of every vertex enabled so I don't know what the data was. But I will try to get it stuck again and see what I can find.

I also managed to run Ear clipping into:

Code: Select all

Exception in thread "main-AWTAnimator" java.lang.IllegalArgumentException: A polygon must have Counter-Clockwise vertex winding.
   at org.dyn4j.geometry.Polygon.<init>(Polygon.java:99)
   at org.dyn4j.geometry.Triangle.<init>(Triangle.java:54)
   at org.dyn4j.geometry.Geometry.createTriangle(Geometry.java:527)
   at org.dyn4j.geometry.decompose.DoublyConnectedEdgeList.getTriangulation(DoublyConnectedEdgeList.java:611)
   at org.dyn4j.geometry.decompose.EarClipping.triangulate(EarClipping.java:128)


Same problem here, I did not keep the input data :-( But in general, is this something "internal" or something I could've prevented by checking the polygon before sending it in?

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Mon Jan 13, 2014 2:06 pm

Here is another one that sweepline beta4 gets stuck on:

Code: Select all

   private final Vector2[] testData4 = {
      new Vector2(43.908292589851285, 78.68948789240166),
      new Vector2(36.46077665485198, 76.64339871234114),
      new Vector2(36.55772072677519, 76.61314449012383),
      new Vector2(36.83774577044181, 75.94476513193842),
      new Vector2(39.4416173547993, 76.90145504100248),
      new Vector2(40.51547260238483, 76.93003331289938),
      new Vector2(41.037214946794755, 75.97813877782743),
      new Vector2(40.51783220697889, 75.00526185195228),
      new Vector2(37.024478014324636, 72.11292284029174),
      new Vector2(37.132881185268786, 71.4779895091023),
      new Vector2(35.49369812011719, 69.97874156058067),
      new Vector2(35.49369812011719, 69.12505340576172),
      new Vector2(36.11511163580499, 69.12505340576172),
      new Vector2(39.54404760010683, 72.78118641689032),
      new Vector2(39.90824751318205, 72.77953344608797),
      new Vector2(43.5631239726889, 76.93176630177666),
      new Vector2(44.634376372930895, 76.82986130374076),
      new Vector2(45.044220015866216, 75.81701100192825),
      new Vector2(44.608871146357394, 72.61295610542547),
      new Vector2(44.98049654106943, 71.96196945906102),
      new Vector2(44.77724472816143, 69.12505340576172),
      new Vector2(47.34813895296208, 69.12505340576172),
      new Vector2(46.87483754124205, 71.6773128434162),
      new Vector2(47.143414369023525, 72.83779067581642),
      new Vector2(47.81772270142552, 72.99149218460478),
      new Vector2(46.9794641765016, 75.20382247711967),
      new Vector2(46.86385248821962, 76.46504464002412),
      new Vector2(47.82231825548691, 77.32706566945102),
      new Vector2(49.046840435507406, 76.80940629292719),
      new Vector2(51.08136169521118, 75.48347198947219),
      new Vector2(50.96294261285211, 76.53414962442032),
      new Vector2(51.9432160364557, 77.17928553862694),
      new Vector2(55.011115692695206, 76.25372479933783),
      new Vector2(55.38816430017073, 76.95878536703015),
      new Vector2(55.493698120117195, 76.96573404912499),
      new Vector2(55.49369812011719, 78.22130940381507),
      new Vector2(48.19641993252272, 78.88079654307253),
      new Vector2(47.19690468617096, 79.3134499986603),
      new Vector2(46.94925641753653, 80.41444827629876),
      new Vector2(51.06703892023312, 84.06215352202999),
      new Vector2(51.02816349527818, 84.14658238287907),
      new Vector2(51.65796190395037, 84.90760683359858),
      new Vector2(55.011521397353185, 88.05350350902806),
      new Vector2(54.934646439271916, 88.40984920556062),
      new Vector2(55.49369812011718, 88.95965421695458),
      new Vector2(55.49369812011719, 89.12505340576172),
      new Vector2(53.97950104846256, 89.12505340576172),
      new Vector2(52.86205011581448, 87.80820579324475),
      new Vector2(52.268570997048236, 87.13402248401675),
      new Vector2(51.60515751895773, 87.27992339070175),
      new Vector2(48.85400481589285, 83.60890291293062),
      new Vector2(48.103626145476525, 83.11721498454467),
      new Vector2(47.297077150990845, 83.49284213686241),
      new Vector2(47.157458727600584, 84.41711988218638),
      new Vector2(48.04522690632645, 87.24092049168524),
      new Vector2(47.47702313561414, 87.30190959118279),
      new Vector2(47.10642659927953, 88.10346477934522),
      new Vector2(47.2899273326785, 89.12505340576172),
      new Vector2(44.99291994072672, 89.1250534057617),
      new Vector2(45.03116352347675, 88.36137031564458),
      new Vector2(44.78170306804308, 87.34885271285498),
      new Vector2(44.51609261442175, 87.24555235687862),
      new Vector2(44.92498987707547, 83.84903937372793),
      new Vector2(44.61179239816473, 83.48999357651309),
      new Vector2(45.20590667852616, 80.54946011152391),
      new Vector2(45.084974147593186, 79.23543266466608)
   } ;

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

Re: NullPointerException in SweepLine

Postby William » Mon Jan 13, 2014 8:44 pm

Thank you again. I have made another fix and would like you to try again.

As to the stacktrace from EarClipping...It's really hard to tell. The stacktrace says that the EarClipping portion of the algorithm completed and the DCEL should have a valid triangulation. From which point the DCEL loops over the faces and generates the triangles. At this point they should all be CCW winding. More than likely, it was a triangle that had near zero area. Right now I'm only checking if the area is larger than Epsilon.E (somewhere around 1.0E-16) which is pretty small.

Let me know if you get some data that causes it again.

William
Attachments
dyn4j-v3.1.9-beta5.jar
dyn4j v3.1.9 beta5
(346.14 KiB) Downloaded 96 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sat Jan 18, 2014 1:49 am

William wrote:Thank you again. I have made another fix and would like you to try again.
William

New day, new polygons and new exception this time for beta5 sweepline ;)

java.lang.IndexOutOfBoundsException: Index: 2, Size: 2
at java.util.ArrayList.rangeCheck(ArrayList.java:638)
at java.util.ArrayList.get(ArrayList.java:414)
at org.dyn4j.geometry.decompose.DoublyConnectedEdgeList.triangulateMonotoneY(DoublyConnectedEdgeList.java:759)
at org.dyn4j.geometry.decompose.SweepLine.createTriangulation(SweepLine.java:409)
at org.dyn4j.geometry.decompose.SweepLine.triangulate(SweepLine.java:349)

Code: Select all

private final Vector2[] testData6 = {
      new Vector2(80.77196448011058, 33.012895162881584),
      new Vector2(81.21186092471575, 31.837541371471822),
      new Vector2(80.47902034650072, 30.810590296051608),
      new Vector2(75.82778534972147, 24.725270297745848),
      new Vector2(75.97718510781385, 24.81586173589281),
      new Vector2(76.41683835428547, 24.55856892214857),
      new Vector2(79.01769604608533, 28.383762673024933),
      new Vector2(79.84793019016624, 29.00870382023813),
      new Vector2(80.8312111794988, 28.660304325110214),
      new Vector2(81.01714228017751, 27.598205543824054),
      new Vector2(80.47377687766536, 25.070014098450248),
      new Vector2(80.7357970600193, 25.05698676517179),
      new Vector2(81.20955209851837, 23.89966845407798),
      new Vector2(80.82815161250164, 20.334665445776583),
      new Vector2(80.87784200379288, 19.519780894145413),
      new Vector2(80.63828137748064, 17.046672821044922),
      new Vector2(83.12327207108976, 17.046672821044922),
      new Vector2(82.92920134057591, 20.36720333243137),
      new Vector2(83.36890350661261, 20.779469907772125),
      new Vector2(83.11294620832679, 23.438666612985976),
      new Vector2(83.11506194343843, 24.443728542275856),
      new Vector2(83.57938033496501, 24.76936901224217),
      new Vector2(83.08663707030969, 27.700989198042954),
      new Vector2(83.27093629800773, 28.648959171696088),
      new Vector2(84.19159305766877, 28.90002306727725),
      new Vector2(84.3998793107783, 28.730784041746674),
      new Vector2(82.83123638755089, 31.791764609625165),
      new Vector2(83.28527398678403, 32.81866524565359),
      new Vector2(84.33741291657955, 33.00818671901541),
      new Vector2(87.4523677829778, 32.95240854475014),
      new Vector2(88.43792531936423, 33.142841517293164),
      new Vector2(98.18814086914062, 33.2928731743894),
      new Vector2(98.18814086914061, 34.92423204216172),
      new Vector2(96.29529043379888, 34.70211086784479),
      new Vector2(95.07426417881625, 35.12022248897971),
      new Vector2(94.94077719573292, 35.76342536504683),
      new Vector2(92.42395134088409, 35.22725442212482),
      new Vector2(91.52481825860515, 35.2487855357523),
      new Vector2(91.15804692321888, 35.97520403896833),
      new Vector2(88.65124734364676, 35.15677397051555),
      new Vector2(87.6037754653795, 35.05978906720259),
      new Vector2(86.93666265222113, 35.88087052035753),
      new Vector2(87.34212027149833, 36.89841697870343),
      new Vector2(91.12941414785648, 39.72879054498605),
      new Vector2(91.01524582084052, 40.23473721978297),
      new Vector2(91.71685576872684, 40.976619457972774),
      new Vector2(94.97150395937732, 43.68518894985178),
      new Vector2(94.89927557263469, 43.75877929986757),
      new Vector2(94.98878425552154, 44.01358141421196),
      new Vector2(84.30530816877973, 34.860548854517404),
      new Vector2(83.14656874604808, 35.124877442947465),
      new Vector2(82.8635205207299, 36.292618097432985),
      new Vector2(83.48265942938374, 39.268264478315004),
      new Vector2(83.40071277908191, 39.28212738783476),
      new Vector2(83.06686640385995, 40.166913878038066),
      new Vector2(83.45786212817133, 43.3351202170515),
      new Vector2(83.40576966239556, 43.34833926213752),
      new Vector2(83.12994030808538, 44.17553648199879),
      new Vector2(83.40493784693047, 47.42507135147585),
      new Vector2(83.1706529369342, 48.133815062464095),
      new Vector2(83.23010049496959, 49.04667282104492),
      new Vector2(80.83654890053911, 49.046672821044915),
      new Vector2(80.89124420729823, 48.399195676702746),
      new Vector2(80.79731114646232, 47.42401526788546),
      new Vector2(80.4448383209876, 47.273309896968186),
      new Vector2(80.83352640959141, 44.1013278573851),
      new Vector2(80.73697814460571, 43.90356279387443),
      new Vector2(81.20275533901948, 40.41884556257697),
      new Vector2(80.97285031568597, 39.15097089645424),
      new Vector2(80.16411988462063, 38.87221088723674),
      new Vector2(81.00362729047318, 36.455940311463166),
      new Vector2(80.91834009073199, 35.329618177026425),
      new Vector2(79.86002110082046, 34.827187078913184),
      new Vector2(73.13548501992999, 39.97002059310742),
      new Vector2(73.17920308804621, 39.536138565795476),
      new Vector2(72.66678570019296, 39.10950991359797),
      new Vector2(76.41838182977921, 36.720636085541),
      new Vector2(76.91969499535422, 35.994224143883805),
      new Vector2(76.43003623282947, 35.241912817625355),
      new Vector2(75.55251216295277, 35.233428789667656),
      new Vector2(72.86937791472853, 36.117649425226865),
      new Vector2(72.54959657536988, 35.32327601467032),
      new Vector2(71.70763386306105, 35.199742399175456),
      new Vector2(68.89039187371151, 35.77850428712437),
      new Vector2(68.91677759683982, 35.62364485877995),
      new Vector2(68.12332641259627, 34.95297978729455),
      new Vector2(66.18814086914062, 35.215269609451326),
      new Vector2(66.18814086914062, 33.99096814014214),
      new Vector2(79.49872040972909, 33.205398267976584)
   };


Earclipping just keeps on triangulating, it is a work horse that one.

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

Re: NullPointerException in SweepLine

Postby William » Sat Jan 18, 2014 2:13 pm

I hope you don't mind going back and forth like this. These test cases have been key in debugging and hardening algorithm (well...my implementation really). Give the attached jar a try and see if you can break it again.

EarClipping is a much simpler algorithm to implement, which is likely why its working all the time. I feel we are pretty close to fully fixing the problems with SweepLine, thanks to these test cases you've been posting.

William
Attachments
dyn4j-v3.1.9-beta6.jar
dyn4j 3.1.9 beta6
(346.11 KiB) Downloaded 105 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sun Jan 19, 2014 12:59 pm

William wrote:I hope you don't mind going back and forth like this. These test cases have been key in debugging and hardening algorithm (well...my implementation really). Give the attached jar a try and see if you can break it again.

EarClipping is a much simpler algorithm to implement, which is likely why its working all the time. I feel we are pretty close to fully fixing the problems with SweepLine, thanks to these test cases you've been posting.

William


I don't mind in the least, this is how open source ought to work :-) I happened to find a polygon that beta6 sweepline have problem with. I hope I don't produce self-intersecting or degenerate polygons, I'm using an external library to generate the polygon and I don't sanity check the results. Do you happen to have some code to test for those edge cases so we don't spend time chasing ghosts?

Anyhoo, here is a new one:

Code: Select all

final Vector2[] testData7 = {
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999),
      new Vector2(15.559614181518556, 49.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.559614181518553, 39.75668042743856),
      new Vector2(15.559614181518555, 36.7413444519043),
      new Vector2(47.55961608886719, 36.7413444519043),
      new Vector2(47.559616088867195, 41.629350269988755),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(47.55961608886719, 49.50000000000001),
      new Vector2(47.55961608886719, 53.49999999999999),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(47.559616088867195, 56.361038905361234),
      new Vector2(47.55961608886719, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(47.55961608886719, 64.19622603618669),
      new Vector2(47.55961608886719, 67.20571990769268),
      new Vector2(47.31756632734533, 67.27192113137582),
      new Vector2(47.02437239283416, 68.2004591206922),
      new Vector2(47.48747674808809, 68.74134826660155),
      new Vector2(45.672113061800715, 68.74134826660156),
      new Vector2(44.36903911271112, 67.26399203556608),
      new Vector2(43.54384062549501, 67.29931445969684),
      new Vector2(43.1973839669848, 68.03018706178432),
      new Vector2(43.63594542737858, 68.66970991612573),
      new Vector2(43.690259126558594, 68.74134826660156),
      new Vector2(41.744826340580026, 68.74134826660156),
      new Vector2(40.90158745811996, 67.41669983264048),
      new Vector2(39.95820193180524, 66.97728016584936),
      new Vector2(39.0416810963307, 67.49078880604793),
      new Vector2(39.12763400379722, 68.54948483760832),
      new Vector2(39.2194870743269, 68.74134826660156),
      new Vector2(37.097683959166346, 68.74134826660156),
      new Vector2(36.80810529594982, 67.90472830655348),
      new Vector2(36.3232933854467, 67.26535102044595),
      new Vector2(35.49247834190054, 67.3320487867053),
      new Vector2(35.23812571325456, 68.11620365384829),
      new Vector2(35.3876946710454, 68.74134826660156),
      new Vector2(33.298736991558954, 68.74134826660156),
      new Vector2(33.22359594956513, 68.05004748462076),
      new Vector2(32.647463203565046, 66.96202874486765),
      new Vector2(31.37973897601256, 66.86317754812887),
      new Vector2(30.772914764102747, 67.97521262357041),
      new Vector2(30.733350389694206, 68.74134826660156),
      new Vector2(29.04144884321284, 68.74134826660156),
      new Vector2(29.14967377829277, 67.51259949005915),
      new Vector2(28.159039913374485, 66.7524584858557),
      new Vector2(26.983391696711237, 67.24575429402505),
      new Vector2(26.511523427685113, 68.74134826660156),
      new Vector2(24.734895227714215, 68.74134826660156),
      new Vector2(24.764558771991837, 68.67180447662106),
      new Vector2(24.96613256092293, 67.65689725393848),
      new Vector2(24.182555246935255, 66.99154652548154),
      new Vector2(23.209805882932535, 67.31471765893966),
      new Vector2(22.392418451920914, 68.74134826660156),
      new Vector2(20.444004054411863, 68.74134826660156),
      new Vector2(20.68665909991947, 68.39206634600691),
      new Vector2(20.732105071310333, 67.55809648965521),
      new Vector2(19.976346571491717, 67.17569960543902),
      new Vector2(19.252858298156763, 67.5911970243192),
      new Vector2(18.29967505955627, 68.74134826660155),
      new Vector2(16.551938961894457, 68.74134826660156),
      new Vector2(16.552802010779477, 68.7404281517103),
      new Vector2(16.932322949564586, 67.8916020317239),
      new Vector2(16.359988616093805, 67.10425668877444),
      new Vector2(15.559614181518555, 67.22917210749591),
      new Vector2(15.559614181518555, 65.37491489985952),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(15.559614181518555, 58.5),
      new Vector2(15.559614181518556, 56.823559201567704),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(15.559614181518555, 53.49999999999999)
   };

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sun Jan 19, 2014 1:54 pm

Found a simpler polygon that sweepline have problem with, which also ran into the same exception I had with earclipping previously (although earclipping throws no exceptions for this). Yay \o/ for finding test data :)

Exception in thread "main-AWTAnimator" java.lang.IllegalArgumentException: A polygon must have Counter-Clockwise vertex winding.
at org.dyn4j.geometry.Polygon.<init),(Polygon.java:99)
at org.dyn4j.geometry.Triangle.<init),(Triangle.java:54)
at org.dyn4j.geometry.Geometry.createTriangle(Geometry.java:527)
at org.dyn4j.geometry.decompose.DoublyConnectedEdgeList.getTriangulation(DoublyConnectedEdgeList.java:611)
at org.dyn4j.geometry.decompose.SweepLine.triangulate(SweepLine.java:349)

Code: Select all

   
   final Vector2[] testData8 = {
      new Vector2(15.5, 37.66666555404663),
      new Vector2(14.746791839599608, 37.36630086687434),
      new Vector2(14.74679183959961, 27.746788024902344),
      new Vector2(46.74679183959961, 27.746788024902344),
      new Vector2(46.74679183959961, 48.5),
      new Vector2(37.66666555404663, 48.5),
      new Vector2(37.66666555404663, 49.5),
      new Vector2(42.477803224203164, 53.5),
      new Vector2(39.33333444595337, 53.5),
      new Vector2(39.33333444595337, 54.5),
      new Vector2(42.5273727021464, 58.5),
      new Vector2(41.0, 58.5),
      new Vector2(41.0, 59.5),
      new Vector2(41.160625591455116, 59.746788024902344),
      new Vector2(22.878639641207986, 59.74678802490234),
      new Vector2(23.0, 59.5),
      new Vector2(23.0, 58.5),
      new Vector2(22.404971368252205, 58.49999999999999),
      new Vector2(24.666667461395264, 54.5),
      new Vector2(24.666667461395264, 53.5),
      new Vector2(23.264814069201424, 53.50000000000001),
      new Vector2(26.333332538604736, 49.5),
      new Vector2(26.333332538604736, 48.5),
      new Vector2(15.5, 48.5)
   };

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

Re: NullPointerException in SweepLine

Postby William » Sun Jan 19, 2014 4:26 pm

Thanks! I think I've finally fixed the problem(s).

The first problem was with the way I was handling near equal y valued vertices. This has been fixed to do a straight equality check against 0.0. Secondly, there was a poor assumption, by myself, that was being used to sort the edges in the binary tree. I've fixed this in the attached jar.

I also found that the check in the Polygon class for counter-clockwise winding would fail in small area triangles (area less than 1.0e-10 and lower). I have replaced this with a different check which allows the near zero area triangles to be retained in the triangulation (you could always go through them after the triangulation and remove them using whatever you consider "zero area", 1.0e-10 for example, of course this would depend on the scale you are using).

So, no ghosts yet, all real problems that needed fixing. When you get a chance try out the attached jar.

As for checking for crossing edges, I don't have any thing on hand, but if you were doing it offline (it may even be fast enough at runtime), you could just use the Segment.getSegmentIntersection() method to test the current edge against all other edges (other than the two adjacent ones) to see if it has crossing edges. I know I've seen some algorithms out there that are faster than this brute force method. I'll see if I can turn some up.

William
Attachments
dyn4j-v3.1.9-beta7.jar
dyn4j 3.1.9 beta 7
(346.39 KiB) Downloaded 92 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sun Jan 19, 2014 5:53 pm

Nice :) I'll give this a spin. As for the self-intersecting I was thinking about these test cases, so I could verify that it was valid polygons I chucked at the triangulator.
For my particular use case I can probably throw a few close-to-zero-area triangles at OpenGL, it most probably wont affect the performance or the rendering much.

Edit: My test cases failed in earclipping this time, might be a valid exception, I'll check it out in a day or so but are you sure about the double negatives in the text?
"A polygon cannot not have coincident vertices."


Return to “Bugs, Enhancements, Feedback”

Who is online

Users browsing this forum: No registered users and 1 guest