You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Luc Maisonobe (JIRA)" <ji...@apache.org> on 2012/10/18 15:44:03 UTC
[jira] [Comment Edited] (MATH-880) Polygon difference produces
erronious results in some cases
[ https://issues.apache.org/jira/browse/MATH-880?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13478999#comment-13478999 ]
Luc Maisonobe edited comment on MATH-880 at 10/18/12 1:42 PM:
--------------------------------------------------------------
Here are some news about the investigations done on this issue.
The problem is indeed due to some numerical issues. During the conversion from boundary representation to BSP tree, we build edges from successive pair of points {p0, p1}, {p1, p2}, {p2, p3} ... These edges belong to hyperplanes (i.e. lines) h01, h12, h23 ... These hyperplanes are then inserted into a BSP tree which is built top down. What happens here is that as h12 is inserted in a tree which already contains h01, we compute the intersection of the two hyperplanes and find a point p1' slightly different from p1 due to numerical considerations. This points extends the edge very slightly, and it is considered afterwards to extend on both sides of h01 instead of one side only. So both sides of hyperplane h01 are split by hyperplane h12. The side that should not have been split now contains an additional artificial cut.
I am still looking for a solution to this. It seems doubtful to be able to completely avoid numerical problems and avoid this extra splitting. However, BSP trees allow extra cut hyperplanes to appear in the tree without belonging to the boundary (this happens for example with non-convex shapes). These extra cut sub-hyperplane simply define two neighboring cells which are both inside or outside the polygon. I am looking at a way to detect this case more efficiently and avoid creating an artificial "inside" cell.
This is a difficult problem.
was (Author: luc):
Here are some news about the investigations done on this issue.
The problem is indeed due to some numerical issues. During the conversion from boundary representation to BSP tree, we build edges from successive pair of points {p0, p1}, {p1, p2}, {p2, p3} ... These edges belong to hyperplanes (i.e. lines) h01, h12, h23 ... These hyperplanes are then inserted into a BSP tree which is built top down. What happens here is that as h12 is inserted in a tree which already contains h01, we compute the intersection of the two hyperplanes and find a point p1' slightly different from p1 due to numerical considerations. This points extends the edge very slightly, and it is considered afterwards to extend on both sides of h01 instead of one side only. So both sides of hyperplane h01 are split by hyperplane h12. The side that should not have been split now contains an additional artificial boundary.
I am still looking for a solution to this. It seems doubtful to be able to completely avoid numerical problems and avoid this extra splitting. However, BSP trees allow extra cut hyperplanes to appear in the tree without belonging to the boundary (this happens for example with non-convex shapes). These extra cut sub-hyperplane simply define two neighboring cells which are both inside or outside the polygon. I am looking at a way to detect this case more efficiently and avoid creating an artificial "inside" cell.
This is a difficult problem.
> 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.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira