commons-issues mailing list archives

Site index · List index
Message view
Top
From "Luc Maisonobe (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-880) Polygon difference produces erronious results in some cases
Date Mon, 22 Oct 2012 14:40:12 GMT

[ https://issues.apache.org/jira/browse/MATH-880?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13481399#comment-13481399
]

Luc Maisonobe commented on MATH-880:
------------------------------------

Well, the remaining problem is worse than expected. The current version even fails on the
simplistic following case:

{code}
Vector2D[] vertices = new Vector2D[] {
new Vector2D(-6, -4), new Vector2D(-8, -8), new Vector2D(  8, -8),
new Vector2D( 6, -4), new Vector2D(10,  4), new Vector2D(-10,  4)
};
PolygonsSet set = new PolygonsSet(1.0e-10, vertices);
{code}

Still working on it :-(

> Polygon difference produces erronious results in some cases
> -----------------------------------------------------------
>
>                 Key: MATH-880
>                 URL: https://issues.apache.org/jira/browse/MATH-880
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>            Reporter: Curtis Jensen
>             Fix For: 3.1
>
>         Attachments: PolygonDiffAll.png, PolygonDiffResults.png, PolygonInputs.png
>
>
> The 2D polygon difference method is returning incorrect
> results.  Below is a test case of subtracting two polygons (Sorry,
> this is the simplest case that I could find that duplicates the
> problem).
> There are three problems with the result. The first is that the first
> point of the first set of vertices is null (and the first point of the
> second set is also null).  The second is that, even if the first null
> points are ignored,  the returned polygon is not the correct result.
> The first and last points are way off, and the remaining points do not
> match the original polygon boundaries.  Additionally, there are two
> holes that are returned in the results.  This subtraction case should
> not have holes.
> {code:title="Complex Polygon Difference Test"}
> public void testComplexDifference() {
>         Vector2D[][] vertices1 = new Vector2D[][] {
>             new Vector2D[] {
>                     new Vector2D( 90.08714908223715,  38.370299337260235),
>                     new Vector2D( 90.08709517675004,  38.3702895991413),
>                     new Vector2D( 90.08401538704919,  38.368849330127944),
>                     new Vector2D( 90.08258210430711,  38.367634558585564),
>                     new Vector2D( 90.08251455106665,  38.36763409247078),
>                     new Vector2D( 90.08106599752608,  38.36761621664249),
>                     new Vector2D( 90.08249585300035,  38.36753627557965),
>                     new Vector2D( 90.09075743352184,  38.35914647644972),
>                     new Vector2D( 90.09099945896571,  38.35896264724079),
>                     new Vector2D( 90.09269383800086,  38.34595756121246),
>                     new Vector2D( 90.09638631543191,  38.3457988093121),
>                     new Vector2D( 90.09666417351019,  38.34523360999418),
>                     new Vector2D( 90.1297082145872,  38.337670454923625),
>                     new Vector2D( 90.12971687748956,  38.337669827794684),
>                     new Vector2D( 90.1240820219179,  38.34328502001131),
>                     new Vector2D( 90.13084259656404,  38.34017811765017),
>                     new Vector2D( 90.13378567942857,  38.33860579180606),
>                     new Vector2D( 90.13519557833206,  38.33621054663689),
>                     new Vector2D( 90.13545616732307,  38.33614965452864),
>                     new Vector2D( 90.13553111202748,  38.33613962818305),
>                     new Vector2D( 90.1356903436448,  38.33610227127048),
>                     new Vector2D( 90.13576283227428,  38.33609255422783),
>                     new Vector2D( 90.13595870833188,  38.33604606376991),
>                     new Vector2D( 90.1361556630693,  38.3360024198866),
>                     new Vector2D( 90.13622408795709,  38.335987048115726),
>                     new Vector2D( 90.13696189099994,  38.33581914328681),
>                     new Vector2D( 90.13746655304897,  38.33616706665265),
>                     new Vector2D( 90.13845973716064,  38.33650776167099),
>                     new Vector2D( 90.13950901827667,  38.3368469456463),
>                     new Vector2D( 90.14393814424852,  38.337591835857495),
>                     new Vector2D( 90.14483839716831,  38.337076122362475),
>                     new Vector2D( 90.14565474433601,  38.33769000964429),
>                     new Vector2D( 90.14569421179482,  38.3377117256905),
>                     new Vector2D( 90.14577067124333,  38.33770883625908),
>                     new Vector2D( 90.14600350631684,  38.337714326520995),
>                     new Vector2D( 90.14600355139731,  38.33771435193319),
>                     new Vector2D( 90.14600369112401,  38.33771443882085),
>                     new Vector2D( 90.14600382486884,  38.33771453466096),
>                     new Vector2D( 90.14600395205912,  38.33771463904344),
>                     new Vector2D( 90.14600407214999,  38.337714751520764),
>                     new Vector2D( 90.14600418462749,  38.337714871611695),
>                     new Vector2D( 90.14600422249327,  38.337714915811034),
>                     new Vector2D( 90.14867838361471,  38.34113888210675),
>                     new Vector2D( 90.14923750157374,  38.341582537502575),
>                     new Vector2D( 90.14877083250991,  38.34160685841391),
>                     new Vector2D( 90.14816667319519,  38.34244232585684),
>                     new Vector2D( 90.14797696744586,  38.34248455284745),
>                     new Vector2D( 90.14484318014337,  38.34385573215269),
>                     new Vector2D( 90.14477919958296,  38.3453797747614),
>                     new Vector2D( 90.14202393306448,  38.34464324839456),
>                     new Vector2D( 90.14198920640195,  38.344651155237216),
>                     new Vector2D( 90.14155207025175,  38.34486424263724),
>                     new Vector2D( 90.1415196143314,  38.344871730519),
>                     new Vector2D( 90.14128611910814,  38.34500196593859),
>                     new Vector2D( 90.14047850603913,  38.34600084496253),
>                     new Vector2D( 90.14045907000337,  38.34601860032171),
>                     new Vector2D( 90.14039496493928,  38.346223030432384),
>                     new Vector2D( 90.14037626063737,  38.346240203360026),
>                     new Vector2D( 90.14030005823724,  38.34646920000705),
>                     new Vector2D( 90.13799164754806,  38.34903093011013),
>                     new Vector2D( 90.11045289492762,  38.36801537312368),
>                     new Vector2D( 90.10871471476526,  38.36878044144294),
>                     new Vector2D( 90.10424901707671,  38.374300101757),
>                     new Vector2D( 90.10263482039932,  38.37310041316073),
>                     new Vector2D( 90.09834601753448,  38.373615053823414),
>                     new Vector2D( 90.0979455456843,  38.373578376172475),
>                     new Vector2D( 90.09086514328669,  38.37527884194668),
>                     new Vector2D( 90.09084931407364,  38.37590801712463),
>                     new Vector2D( 90.09081227075944,  38.37526295920463),
>                     new Vector2D( 90.09081378927135,  38.375193883266434)
>             }
>         };
>         PolygonsSet set1 = buildSet(vertices1);
>         Vector2D[][] vertices2 = new Vector2D[][] {
>             new Vector2D[] {
>                     new Vector2D( 90.13067558880044,  38.36977255037573),
>                     new Vector2D( 90.12907570488,  38.36817308242706),
>                     new Vector2D( 90.1342774136516,  38.356886880294724),
>                     new Vector2D( 90.13090330629757,  38.34664392676211),
>                     new Vector2D( 90.13078571364593,  38.344904617518466),
>                     new Vector2D( 90.1315602208914,  38.3447185040846),
>                     new Vector2D( 90.1316336226821,  38.34470643148342),
>                     new Vector2D( 90.134020944832,  38.340936644972885),
>                     new Vector2D( 90.13912536387306,  38.335497255122334),
>                     new Vector2D( 90.1396178806582,  38.334878075552126),
>                     new Vector2D( 90.14083049696671,  38.33316530644106),
>                     new Vector2D( 90.14145252901329,  38.33152722916191),
>                     new Vector2D( 90.1404779335565,  38.32863516047786),
>                     new Vector2D( 90.14282712131586,  38.327504432532066),
>                     new Vector2D( 90.14616669875488,  38.3237354115015),
>                     new Vector2D( 90.14860976050608,  38.315714862457924),
>                     new Vector2D( 90.14999277782437,  38.3164932507504),
>                     new Vector2D( 90.15005207194997,  38.316534677663356),
>                     new Vector2D( 90.15508513859612,  38.31878731691609),
>                     new Vector2D( 90.15919938519221,  38.31852743183782),
>                     new Vector2D( 90.16093758658837,  38.31880662005153),
>                     new Vector2D( 90.16099420184912,  38.318825953291594),
>                     new Vector2D( 90.1665411125756,  38.31859497874757),
>                     new Vector2D( 90.16999653861313,  38.32505772048029),
>                     new Vector2D( 90.17475243391698,  38.32594398441148),
>                     new Vector2D( 90.17940844844992,  38.327427213761325),
>                     new Vector2D( 90.20951909541378,  38.330616833491774),
>                     new Vector2D( 90.2155400467941,  38.331746223670336),
>                     new Vector2D( 90.21559881391778,  38.33175551425302),
>                     new Vector2D( 90.21916646426041,  38.332584299620805),
>                     new Vector2D( 90.23863749852285,  38.34778978875795),
>                     new Vector2D( 90.25459855175802,  38.357790570608984),
>                     new Vector2D( 90.25964298227257,  38.356918010203174),
>                     new Vector2D( 90.26024593994703,  38.361692743151366),
>                     new Vector2D( 90.26146187570015,  38.36311080550837),
>                     new Vector2D( 90.26614159359622,  38.36510808579902),
>                     new Vector2D( 90.26621342936448,  38.36507942500333),
>                     new Vector2D( 90.26652190211962,  38.36494042196722),
>                     new Vector2D( 90.26621240678867,  38.365113172030874),
>                     new Vector2D( 90.26614057102057,  38.365141832826794),
>                     new Vector2D( 90.26380080055299,  38.3660381760273),
>                     new Vector2D( 90.26315345241,  38.36670658276421),
>                     new Vector2D( 90.26251574942881,  38.367490323488084),
>                     new Vector2D( 90.26247873448426,  38.36755266444749),
>                     new Vector2D( 90.26234628016698,  38.36787989125406),
>                     new Vector2D( 90.26214559424784,  38.36945909356126),
>                     new Vector2D( 90.25861728442555,  38.37200753430875),
>                     new Vector2D( 90.23905557537864,  38.375405314295904),
>                     new Vector2D( 90.22517251874075,  38.38984691662256),
>                     new Vector2D( 90.22549955153215,  38.3911564273979),
>                     new Vector2D( 90.22434386063355,  38.391476432092134),
>                     new Vector2D( 90.22147729457276,  38.39134652252034),
>                     new Vector2D( 90.22142070120117,  38.391349167741964),
>                     new Vector2D( 90.20665060751588,  38.39475580900313),
>                     new Vector2D( 90.20042268367109,  38.39842558622888),
>                     new Vector2D( 90.17423771242085,  38.402727751805344),
>                     new Vector2D( 90.16756796257476,  38.40913898597597),
>                     new Vector2D( 90.16728283954308,  38.411255399912875),
>                     new Vector2D( 90.16703538220418,  38.41136059866693),
>                     new Vector2D( 90.16725865657685,  38.41013618805954),
>                     new Vector2D( 90.16746107640665,  38.40902614307544),
>                     new Vector2D( 90.16122795307462,  38.39773101873203)
>             }
>         };
>         PolygonsSet set2 = buildSet(vertices2);
>         PolygonsSet set  = (PolygonsSet) new
> RegionFactory<Euclidean2D>().difference(set1.copySelf(),
>               set2.copySelf());
>         Vector2D[][] verticies = set.getVertices();
>         Assert.assertTrue(verticies[0][0] != null);
>         Assert.assertEquals(1, verticies.length);
>     }
> {code}

--
This message is automatically generated by JIRA.