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

Karl Wright commented on LUCENE-8245:
-------------------------------------

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:

{code}
   [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
{code}

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.



> GeoComplexPolygon fails when intersection of travel plane with edge is near 
> polygon point
> -----------------------------------------------------------------------------------------
>
>                 Key: LUCENE-8245
>                 URL: https://issues.apache.org/jira/browse/LUCENE-8245
>             Project: Lucene - Core
>          Issue Type: Bug
>          Components: modules/spatial3d
>            Reporter: Ignacio Vera
>            Assignee: Karl Wright
>            Priority: Major
>             Fix For: 6.7, 7.4, master (8.0)
>
>         Attachments: LUCENE-8245-case2.patch, LUCENE-8245.jpg, 
> LUCENE-8245.patch, LUCENE-8245_Polygon.patch, LUCENE-8245_Random.patch, 
> LUCENE-8245_case3.patch
>
>
> 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.
>  
>  



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

Reply via email to