search

mikemccand / stargazers-migration-test

Testing Lucene's Jira -> GitHub issues migration
0 stars 0 forks source link

GeoComplexPolygon fails when intersection of travel plane with edge is near polygon point [LUCENE-8245] #245

Closed mikemccand closed 6 years ago

mikemccand commented 6 years ago

When a travel plane crosses an edge close to an edge point , it is possible that the above and below planes crosses different edges. In the current implementation one of the crosses is missed because we only check edges that are crossed by the main plain and the within result is wrong.

One possible fix is to check always the intersection of planes and edges regardless if they are crossed by main plane. That fixed the above issue but shows other issues like travel planes crossing two edges when it should be only one due to the fuzziness at edge intersections.

Not sure of a fix so I add the test showing the issue.

Legacy Jira details

LUCENE-8245 by Ignacio Vera (@iverase) on Apr 08 2018, resolved Apr 12 2018 Attachments: LUCENE-8245_case3.patch, LUCENE-8245_Polygon.patch, LUCENE-8245_Random.patch, LUCENE-8245.jpg, LUCENE-8245.patch (versions: 2), LUCENE-8245-case2.patch

mikemccand commented 6 years ago

Commit 1f622d93dcad8ee5f2e1f772408201e077dc16c2 in lucene-solr's branch refs/heads/branch_6x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=1f622d9

LUCENE-8245: Handle parallel planes case properly.

[Legacy Jira: ASF subversion and git services on Apr 11 2018]

mikemccand commented 6 years ago

I believe I've come up with a better way to do this. It involves two basic changes: (1) using only actual intersections with the envelope planes, so no "zone" is needed, and the envelope planes go back to being exactly MINIMUM_RESOLUTION from the main travel planes; and (2) evaluating the envelope plane intersections, one at a time, for whether they constitute a "crossing" from the main travel plane "zone" outside of that "zone".

The second requires the generation of a pair of adjoining points, also on the edge plane, that are about MINIMUM_RESOLUTION away from the intersection. We look at both points, and if one is inside the travel plane "zone" and the other is not, then we call it a crossing.

I'm coding this up now but it's already a very busy work day and this probably won't be completed and debugged until tonight at the earliest.

[Legacy Jira: Karl Wright on Apr 11 2018]

mikemccand commented 6 years ago

The adjoining points code I developed works OK for spheres but not for anything else, which is a problem. Have to think of something better that's not too expensive. No more time today.

[Legacy Jira: Karl Wright on Apr 11 2018]

mikemccand commented 6 years ago

Commit 0c71503448a66e8766008ae0447e36115ffbdd08 in lucene-solr's branch refs/heads/master from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=0c71503

LUCENE-8245: Change how crossings are computed.

[Legacy Jira: ASF subversion and git services on Apr 11 2018]

mikemccand commented 6 years ago

Commit 6ce215d6f2e079e505c664e00b6898056dbcc324 in lucene-solr's branch refs/heads/branch_7x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=6ce215d

LUCENE-8245: Change how crossings are computed.

[Legacy Jira: ASF subversion and git services on Apr 11 2018]

mikemccand commented 6 years ago

Commit 6edfd9f2bd07412ed96c6402cd7c7c1495ae13db in lucene-solr's branch refs/heads/branch_6x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=6edfd9f

LUCENE-8245: Change how crossings are computed.

[Legacy Jira: ASF subversion and git services on Apr 11 2018]

mikemccand commented 6 years ago

@ivera, I committed revised code that I'm happy with, but I needed to disable tests for two cases in the GeoPolygonTest suite. One of the tests fails again because it picks a bad path – I thought maybe you'd like to analyze that one while I look at the other. This is the "bad path picked" bug:

ant test  -Dtestcase=GeoPolygonTest -Dtests.method=testComplexPolygonPlaneOutsideWorld

[Legacy Jira: Karl Wright on Apr 12 2018]

mikemccand commented 6 years ago

Sure! I have a look time permitting.

[Legacy Jira: Ignacio Vera (@iverase) on Apr 12 2018]

mikemccand commented 6 years ago

The remaining other failure is due to inconsistent detection of whether or not one of the envelope planes is intersected. Two edges share the same endpoint, and that endpoint is very close to the envelope travel plane. One of edges detects the intersection, but the other does not, and that leads to a miscount:

   [junit4]   1> The following edges should intersect the travel/testpoint planes:
   [junit4]   1> Travel plane: [lat=-1.4506713533447755, lon=-1.2251247551355924([X=0.04060395941016342, Y=-0.11274773940940182, Z=-0.9927936672533157])] -> [lat=4.9E-324, lon=0.0([X=1.0, Y=0.0, Z=4.9E-324])]
   [junit4]   1> Test point plane: [lat=-1.4506713533447755, lon=-1.2251247551355924([X=0.04060395941016342, Y=-0.11274773940940182, Z=-0.9927936672533157])] -> [lat=4.9E-324, lon=0.0([X=1.0, Y=0.0, Z=4.9E-324])]
   [junit4]   1> Travel plane: [lat=4.9E-324, lon=0.0([X=1.0, Y=0.0, Z=4.9E-324])] -> [lat=0.13953211802880663, lon=-2.443438340098597([X=-0.7585849990851791, Y=-0.6365576248361361, Z=0.139079795174987])]
   [junit4]   1>
   [junit4]   1> Considering edge [lat=-1.4506713533447755, lon=-1.2251247551355924([X=0.04060395941016342, Y=-0.11274773940940182, Z=-0.9927936672533157])] -> [lat=4.9E-324, lon=0.0([X=1.0, Y=0.0, Z=4.9E-324])]
   [junit4]   1>  Edge intersects travel or testPoint plane
   [junit4]   1>  Assessing inner crossings...
   [junit4]   1>   Assessing travel intersection point [X=1.0, Y=-1.3268072236836583E-12, Z=-1.1683123903318337E-11]...
   [junit4]   1>    Adjoining point [X=1.0, Y=-1.2139664266344454E-12, Z=-1.068951082242553E-11] (dist = 9.999999999999994E-13) is within
   [junit4]   1>    Adjoining point [X=1.0, Y=-1.4396480207328712E-12, Z=-1.2676736984211145E-11] (dist = 9.999999999999994E-13) is not within
   [junit4]   1>   Assessing testpoint intersection point [X=0.7540698997149328, Y=-0.07411317803505024, Z=-0.6525992822440554]...
   [junit4]   1>    Adjoining point [X=0.7540698997155896, Y=-0.07411317803496516, Z=-0.6525992822433061] (dist = 1.0000354317132432E-12) is not within
   [junit4]   1>    Adjoining point [X=0.7540698997142758, Y=-0.07411317803513531, Z=-0.6525992822448046] (dist = 1.000023996169918E-12) is within
   [junit4]   1>  Assessing outer crossings...
   // We don't get a travel outer intersection here!!!  But we did below, and that's the problem.  One crossing is direct, the other is oblique, and that's enough to allow
   // numerical imprecision to give us different results even though the endpoint for both edges is the same.
   [junit4]   1>   Assessing testpoint intersection point [X=0.7540698997131794, Y=-0.0741131780352774, Z=-0.6525992822460556]...
   [junit4]   1>    Adjoining point [X=0.7540698997138362, Y=-0.07411317803519231, Z=-0.6525992822453063] (dist = 1.0000354317132432E-12) is within
   [junit4]   1>    Adjoining point [X=0.7540698997125226, Y=-0.07411317803536248, Z=-0.6525992822468049] (dist = 1.0000354317132432E-12) is not within
   [junit4]   1>
   [junit4]   1> Considering edge [lat=4.9E-324, lon=0.0([X=1.0, Y=0.0, Z=4.9E-324])] -> [lat=0.13953211802880663, lon=-2.443438340098597([X=-0.7585849990851791, Y=-0.6365576248361361, Z=0.139079795174987])]
   [junit4]   1>  Edge intersects travel or testPoint plane
   [junit4]   1>  Assessing inner crossings...
   [junit4]   1>   Assessing travel intersection point [X=1.0, Y=-1.326807223683658E-12, Z=2.8989060802487275E-13]...
   [junit4]   1>    Adjoining point [X=1.0, Y=-2.3037607755580197E-12, Z=5.033426107797519E-13] (dist = 1.0E-12) is not within
   [junit4]   1>    Adjoining point [X=1.0, Y=-3.4985367180929626E-13, Z=7.643860526999353E-14] (dist = 1.0000000000000002E-12) is within
   [junit4]   1>  Assessing outer crossings...
   [junit4]   1>   Assessing travel intersection point [X=1.0, Y=6.731927763163422E-13, Z=-1.470841127187181E-13]...
   [junit4]   1>    Adjoining point [X=1.0, Y=-3.037607755580196E-13, Z=6.636789003616112E-14] (dist = 1.0000000000000002E-12) is within
   [junit4]   1>    Adjoining point [X=1.0, Y=1.650146328190704E-12, Z=-3.6053611547359735E-13] (dist = 1.0E-12) is not within

This may be due to the angle of intersection; probably neither should be considered "intersecting", but 1e-12 extra along one is enough, but along the other is not. The only simple way to correct this is to alternatively tighten the cutoff leeway, so that neither detects intersection, or loosen it enough that both edges would detect intersection. I fear that either solution would leave the same situation in place, albeit at a tighter range of values, so I need to think through alternatives.

One potential solution is to notice that the endpoint itself is within the envelope plane. This works in the other case where we're trying to be sure we don't miss an intersection with the actual travel plane, but in that case it's part of a binary decision, and in this case it figures into a count, and we cannot afford to count twice. It's possible we could use isNumericallyIdentical() to make sure there is no duplication; this would likely work because we already know that the edge endpoint is close to the intersection point in that case. The riskier part is that we find intersections with the envelope plane that should not be there at all, such as edges that end within the envelope plane that never intersected the travel plane. Fixing those would require horrific logic, I fear.

Still gotta think about this, but I'm leaning towards the tighter bound for envelope edge ends.

[Legacy Jira: Karl Wright on Apr 12 2018]

mikemccand commented 6 years ago

The issue with the testComplexPolygonPlaneOutsideWorld is straight forward:

The test build the following below plane which it is just outside of the world by just a bit:

[A=1.0, B=0.0; C=0.0; D=-1.0000000000009952]

Because we are testing the validity of the plane in the following way:

if (fixedXBelowPlane.D - planetModel.getMaximumXValue() >= Vector.MINIMUM_RESOLUTION || planetModel.getMinimumXValue() - fixedXBelowPlane.D >= Vector.MINIMUM_RESOLUTION) {
    fixedXBelowPlane = null;
}

we are allowing bellow planes that are just a bit outside of the world.I think we should change those checks to:

Plane fixedXBelowPlane = new Plane(travelPlaneFixedX, false);
if (fixedXBelowPlane.D - planetModel.getMaximumXValue() >= Vector.MINIMUM_RESOLUTION || fixedXBelowPlane.D - planetModel.getMinimumXValue() <= Vector.MINIMUM_RESOLUTION) {
    fixedXBelowPlane = null;
}

So below planes are never outside of the world.

 

 

 

[Legacy Jira: Ignacio Vera (@iverase) on Apr 12 2018]

mikemccand commented 6 years ago

@ivera, I made that change but it did not fix the problem.

Here's the code in question:

    Plane fixedYAbovePlane = new Plane(testPointFixedYPlane, true);
    if (fixedYAbovePlane.D - planetModel.getMaximumYValue() >= Vector.MINIMUM_RESOLUTION || planetModel.getMinimumYValue() - fixedYAbovePlane.D >= Vector.MINIMUM_RESOLUTION) {
        fixedYAbovePlane = null;
    }
    this.testPointFixedYAbovePlane = fixedYAbovePlane;

    Plane fixedYBelowPlane = new Plane(testPointFixedYPlane, false);
    if (fixedYBelowPlane.D - planetModel.getMaximumYValue() >= Vector.MINIMUM_RESOLUTION ||  planetModel.getMinimumYValue() - fixedYBelowPlane.D >= Vector.MINIMUM_RESOLUTION) {
        fixedYBelowPlane = null;
    }
    this.testPointFixedYBelowPlane = fixedYBelowPlane;

    Plane fixedXAbovePlane = new Plane(testPointFixedXPlane, true);
    if (fixedXAbovePlane.D - planetModel.getMaximumXValue() >= Vector.MINIMUM_RESOLUTION || planetModel.getMinimumXValue() - fixedXAbovePlane.D >= Vector.MINIMUM_RESOLUTION) {
        fixedXAbovePlane = null;
    }
    this.testPointFixedXAbovePlane = fixedXAbovePlane;

    Plane fixedXBelowPlane = new Plane(testPointFixedXPlane, false);
    if (fixedXBelowPlane.D - planetModel.getMaximumXValue() >= Vector.MINIMUM_RESOLUTION || planetModel.getMinimumXValue() - fixedXBelowPlane.D >= Vector.MINIMUM_RESOLUTION) {
        fixedXBelowPlane = null;
    }
    this.testPointFixedXBelowPlane = fixedXBelowPlane;

    Plane fixedZAbovePlane = new Plane(testPointFixedZPlane, true);
    if (fixedZAbovePlane.D - planetModel.getMaximumZValue() >= Vector.MINIMUM_RESOLUTION ||planetModel.getMinimumZValue() - fixedZAbovePlane.D >= Vector.MINIMUM_RESOLUTION) {
        fixedZAbovePlane = null;
    }
    this.testPointFixedZAbovePlane = fixedZAbovePlane;

    Plane fixedZBelowPlane = new Plane(testPointFixedZPlane, false);
    if (fixedZBelowPlane.D - planetModel.getMaximumZValue() >= Vector.MINIMUM_RESOLUTION || planetModel.getMinimumZValue() - fixedZBelowPlane.D >= Vector.MINIMUM_RESOLUTION) {
        fixedZBelowPlane = null;
    }
    this.testPointFixedZBelowPlane = fixedZBelowPlane;

The version you have is just sign-reversed (multiplied everywhere by -1 in the second clauses). I tried it anyways, made no difference.

I think the test should be stricter and not include the Vector.MINIMUM_RESOLUTION – that is, all clauses should say "> 0.0". But even when I make that change, the test still fails.

[Legacy Jira: Karl Wright on Apr 12 2018]

mikemccand commented 6 years ago

You need to do it as well for the check point, that should fix the test.

 

[Legacy Jira: Ignacio Vera (@iverase) on Apr 12 2018]

mikemccand commented 6 years ago

Commit 0b1e8ef72e2e9ae75a1929a00b7137dfb1a75b12 in lucene-solr's branch refs/heads/master from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=0b1e8ef

LUCENE-8245: Re-solve the 'intersection outside the world' case.

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Commit 6bab34b15c515feb2dc84cadbe66e688177523f7 in lucene-solr's branch refs/heads/branch_7x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=6bab34b

LUCENE-8245: Re-solve the 'intersection outside the world' case.

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Commit 018886197563ce311b4907544034b022884f6143 in lucene-solr's branch refs/heads/branch_6x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=0188861

LUCENE-8245: Re-solve the 'intersection outside the world' case.

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Commit 832e89748ea97e262437d420f54aac2a1b87b505 in lucene-solr's branch refs/heads/master from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=832e897

LUCENE-8245: Use strict bounds checking for edge planes when assessing envelope crossings. It's the only way to insure we don't overdetect or underdetect such intersections.

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Commit 74de0591a07828ae7a531c3f93d5879feef434f3 in lucene-solr's branch refs/heads/branch_7x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=74de059

LUCENE-8245: Use strict bounds checking for edge planes when assessing envelope crossings. It's the only way to insure we don't overdetect or underdetect such intersections.

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Commit 4f694d5c7259355e7b3c20f5ceef2eb63e50c893 in lucene-solr's branch refs/heads/master from @dsmiley https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=4f694d5

LUCENE-8245: fix unused import

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Please remember ant precommit before committing.

[Legacy Jira: David Smiley (@dsmiley) on Apr 12 2018]

mikemccand commented 6 years ago

Commit 34bbbc4282ad17a206575f9cbfe51416aba90432 in lucene-solr's branch refs/heads/branch_7x from @dsmiley https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=34bbbc4

LUCENE-8245: fix unused import

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

Commit 9587e32b32964d77adff8b20b01baa7a0de440c5 in lucene-solr's branch refs/heads/branch_6x from @dsmiley https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=9587e32

LUCENE-8245: fix unused import

[Legacy Jira: ASF subversion and git services on Apr 12 2018]

mikemccand commented 6 years ago

@dsmiley I ran it. Took 25 minutes. Don't understand why it didn't detect this.

[Legacy Jira: Karl Wright on Apr 12 2018]

mikemccand commented 6 years ago

Commit 1d201f3c18ef150132e329bac6bb8ecc3ca8c4e0 in lucene-solr's branch refs/heads/master from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=1d201f3

LUCENE-8245: Make precommit happy, again.

[Legacy Jira: ASF subversion and git services on Apr 13 2018]

mikemccand commented 6 years ago

Commit 539c7769b2a6ebf605fcdc075d92af4a22979e11 in lucene-solr's branch refs/heads/branch_7x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=539c776

LUCENE-8245: Make precommit happy, again.

[Legacy Jira: ASF subversion and git services on Apr 13 2018]

mikemccand commented 6 years ago

Commit eedd3cea6504c836a6a5ff9c64602546e3a9ff65 in lucene-solr's branch refs/heads/branch_6x from [~kwright@metacarta.com] https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=eedd3ce

LUCENE-8245: Make precommit happy, again.

[Legacy Jira: ASF subversion and git services on Apr 13 2018]

mikemccand commented 6 years ago

edit: I see LUCENE-8251 has been opened for the failing test below:

Reproducing seed for RandomGeoPolygonTest.testComparePolygons() from https://jenkins.thetaphi.de/job/Lucene-Solr-7.x-Windows/545/; reproduces for me on Linux:

Checking out Revision 21f39627624fe4d2b80ca85fae8fdf2b26fd70b6 (refs/remotes/origin/branch_7x)
[...]
   [junit4]   2> NOTE: reproduce with: ant test  -Dtestcase=RandomGeoPolygonTest -Dtests.method=testComparePolygons -Dtests.seed=D6349E776359D46D -Dtests.slow=true -Dtests.locale=ms -Dtests.timezone=Asia/Makassar -Dtests.asserts=true -Dtests.file.encoding=Cp1252
   [junit4] FAILURE 0.15s J0 | RandomGeoPolygonTest.testComparePolygons {seed=[D6349E776359D46D:C13F762B72BE3163]} <<<
   [junit4]    > Throwable #1: java.lang.AssertionError: 
   [junit4]    > Standard polygon: GeoCompositePolygon: {[GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=[[lat=-0.07623836285341265, lon=0.00454700984778178([X=0.998181035951336, Y=0.004538770280526402, Z=-0.07624825759433645])], [lat=-7.476157549743229E-245, lon=0.0([X=1.0011188539924791, Y=0.0, Z=-7.484522278466162E-245])], [lat=0.001511171483804436, lon=-9.688787797923482E-4([X=1.001117233304039, Y=-9.699615469421312E-4, Z=0.0015128616766053018])], [lat=-0.01412589292926225, lon=-0.004052102300342142([X=1.0010100824418215, Y=-0.004056217458151357, Z=-0.01414121792996793])]], internalEdges={}}]}
   [junit4]    > Large polygon: GeoComplexPolygon: {planetmodel=PlanetModel.WGS84, number of shapes=1, address=b597f211, testPoint=[lat=-0.02220757682746917, lon=-1.218087190149091E-4([X=1.000870329530105, Y=-1.2191473334305646E-4, Z=-0.02223055955204728])], testPointInSet=true, shapes={ {[lat=-0.01412589292926225, lon=-0.004052102300342142([X=1.0010100824418215, Y=-0.004056217458151357, Z=-0.01414121792996793])], [lat=-0.07623836285341265, lon=0.00454700984778178([X=0.998181035951336, Y=0.004538770280526402, Z=-0.07624825759433645])], [lat=-7.476157549743229E-245, lon=0.0([X=1.0011188539924791, Y=0.0, Z=-7.484522278466162E-245])], [lat=0.001511171483804436, lon=-9.688787797923482E-4([X=1.001117233304039, Y=-9.699615469421312E-4, Z=0.0015128616766053018])]}}
   [junit4]    > Point: [lat=3.310332671314249E-4, lon=-3.0E-323([X=1.0011187987699837, Y=-3.0E-323, Z=3.314036388489196E-4])]
   [junit4]    > WKT: POLYGON((0.2605244736823189 -4.368136428487497,0.0 -4.283522745751538E-243,-0.05551266494188662 0.08658374814251642,-0.23216835996485705 -0.8093540467004184,0.2605244736823189 -4.368136428487497))
   [junit4]    > WKT: POINT(-1.7E-321 0.018966809085057403)
   [junit4]    > normal polygon: false
   [junit4]    > large polygon: true
   [junit4]    >    at __randomizedtesting.SeedInfo.seed([D6349E776359D46D:C13F762B72BE3163]:0)
   [junit4]    >    at org.apache.lucene.spatial3d.geom.RandomGeoPolygonTest.testComparePolygons(RandomGeoPolygonTest.java:179)
   [junit4]    >    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
   [junit4]    >    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
   [junit4]    >    at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
   [junit4]    >    at java.base/java.lang.reflect.Method.invoke(Method.java:564)
   [junit4]    >    at java.base/java.lang.Thread.run(Thread.java:841)
   [junit4]   2> NOTE: test params are: codec=Lucene70, sim=RandomSimilarity(queryNorm=false): {}, locale=ms, timezone=Asia/Makassar
   [junit4]   2> NOTE: Windows 10 10.0 amd64/Oracle Corporation 11-ea (64-bit)/cpus=3,threads=1,free=73360360,total=97320960

[Legacy Jira: Steven Rowe on Apr 13 2018]