[jira] [Commented] (LUCENE-8860) LatLonShapeBoundingBoxQuery could make more decisions on inner nodes
[ https://issues.apache.org/jira/browse/LUCENE-8860?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16920960#comment-16920960 ] Adrien Grand commented on LUCENE-8860: -- Why is it a problem? If the query polygon fully contains all left edges of the MBRs on a given node then we would know it intersects all indexed triangles, just like when the query is a box? > LatLonShapeBoundingBoxQuery could make more decisions on inner nodes > > > Key: LUCENE-8860 > URL: https://issues.apache.org/jira/browse/LUCENE-8860 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Adrien Grand >Priority: Minor > Attachments: fig1.png, fig2.png, fig3.png > > Time Spent: 20m > Remaining Estimate: 0h > > Currently LatLonShapeBoundingBoxQuery with the INTERSECTS relation only > returns CELL_INSIDE_QUERY if the query contains ALL minimum bounding > rectangles of the indexed triangles. > I think we could return CELL_INSIDE_QUERY if the box contains either of the > edges of all MBRs of indexed triangles since triangles are guaranteed to > touch all edges of their MBR by definition. In some cases this would help > save decoding triangles and running costly point-in-triangle computations. -- This message was sent by Atlassian Jira (v8.3.2#803003) - To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Commented] (LUCENE-8860) LatLonShapeBoundingBoxQuery could make more decisions on inner nodes
[ https://issues.apache.org/jira/browse/LUCENE-8860?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16914594#comment-16914594 ] Igor Motov commented on LUCENE-8860: Thanks! It is clear now. I think I understood the part about the bounding box queries and I opened PR based on it. Unfortunately, I don't see how to extend this to the polygons queries. If we take a look at the fig3, the bounding box for the red query completely encapsulates the green polygon's bounding box and yet, we cannot make any conclusion about their intersection based on this information. !fig3.png! > LatLonShapeBoundingBoxQuery could make more decisions on inner nodes > > > Key: LUCENE-8860 > URL: https://issues.apache.org/jira/browse/LUCENE-8860 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Adrien Grand >Priority: Minor > Attachments: fig1.png, fig2.png, fig3.png > > Time Spent: 10m > Remaining Estimate: 0h > > Currently LatLonShapeBoundingBoxQuery with the INTERSECTS relation only > returns CELL_INSIDE_QUERY if the query contains ALL minimum bounding > rectangles of the indexed triangles. > I think we could return CELL_INSIDE_QUERY if the box contains either of the > edges of all MBRs of indexed triangles since triangles are guaranteed to > touch all edges of their MBR by definition. In some cases this would help > save decoding triangles and running costly point-in-triangle computations. -- This message was sent by Atlassian Jira (v8.3.2#803003) - To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Commented] (LUCENE-8860) LatLonShapeBoundingBoxQuery could make more decisions on inner nodes
[ https://issues.apache.org/jira/browse/LUCENE-8860?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16911753#comment-16911753 ] Adrien Grand commented on LUCENE-8860: -- I suspect that the confusion is that we don't use minPackedValue and maxPackedValue directly but a combination of them. For instance the current logic short circuits the query on Inner nodes when the query shape fully contains all indexed triangles, using the minimum (x,y) coordinates from minPackedValue and the maximum (x,y) coordinates from maxPackedValue to compute a rectangle that contains all MBRs. In your example this rectangle is [(0,0), (30,20)]. The idea of this issue is that there are weaker conditions we can check that allow us to make the same conclusion. For instance if we take the minimum (x,y) coordinates from minPackedValue, the maximum x from minPackedValue and the maximum y from maxPackedValue we get a smaller rectangle that contains the left edge of all MBRs on the leaf block. If the query fully contains this rectangle then it is guaranteed to intersect all triangles of the leaf given that triangles have at least one point on the left edge of their MBR. In your example this rectangle is [(0,0), (20,20)]. We can do the same test for the right, top and bottom edges. With your red box query, we wouldn't be able to make a decision on the inner node since it doesn't fully contain any of the 4 rectangles that contains all left, right, top and bottom edges. > LatLonShapeBoundingBoxQuery could make more decisions on inner nodes > > > Key: LUCENE-8860 > URL: https://issues.apache.org/jira/browse/LUCENE-8860 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Adrien Grand >Priority: Minor > Attachments: fig1.png, fig2.png > > > Currently LatLonShapeBoundingBoxQuery with the INTERSECTS relation only > returns CELL_INSIDE_QUERY if the query contains ALL minimum bounding > rectangles of the indexed triangles. > I think we could return CELL_INSIDE_QUERY if the box contains either of the > edges of all MBRs of indexed triangles since triangles are guaranteed to > touch all edges of their MBR by definition. In some cases this would help > save decoding triangles and running costly point-in-triangle computations. -- This message was sent by Atlassian Jira (v8.3.2#803003) - To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Commented] (LUCENE-8860) LatLonShapeBoundingBoxQuery could make more decisions on inner nodes
[ https://issues.apache.org/jira/browse/LUCENE-8860?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16910787#comment-16910787 ] Igor Motov commented on LUCENE-8860: I tried looking into this issue but I don't think we have enough information in the inner node to make such determination. For example, if I index two polygons: one L shaped polygon and another small triangle placed inside the L-shape (see blue and green tessellated versions on fig 1): !fig1.png! Then all I have on the inner node level are minPackedValues and maxPackedValue (depicted as purple rectangles on fig 2) this doesn't give me enough information to determine if my query bounding box (red rectangle on fig 2) intersects with blue triangle or not. !fig2.png! So, unless I misunderstood the proposal, I am not really sure how to achieve that on the inner node level. > LatLonShapeBoundingBoxQuery could make more decisions on inner nodes > > > Key: LUCENE-8860 > URL: https://issues.apache.org/jira/browse/LUCENE-8860 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Adrien Grand >Priority: Minor > Attachments: fig1.png, fig2.png > > > Currently LatLonShapeBoundingBoxQuery with the INTERSECTS relation only > returns CELL_INSIDE_QUERY if the query contains ALL minimum bounding > rectangles of the indexed triangles. > I think we could return CELL_INSIDE_QUERY if the box contains either of the > edges of all MBRs of indexed triangles since triangles are guaranteed to > touch all edges of their MBR by definition. In some cases this would help > save decoding triangles and running costly point-in-triangle computations. -- This message was sent by Atlassian Jira (v8.3.2#803003) - To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Commented] (LUCENE-8860) LatLonShapeBoundingBoxQuery could make more decisions on inner nodes
[ https://issues.apache.org/jira/browse/LUCENE-8860?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16879116#comment-16879116 ] Adrien Grand commented on LUCENE-8860: -- I made the issue about box queries, but that would actually work for polygons too. > LatLonShapeBoundingBoxQuery could make more decisions on inner nodes > > > Key: LUCENE-8860 > URL: https://issues.apache.org/jira/browse/LUCENE-8860 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Adrien Grand >Priority: Minor > > Currently LatLonShapeBoundingBoxQuery with the INTERSECTS relation only > returns CELL_INSIDE_QUERY if the query contains ALL minimum bounding > rectangles of the indexed triangles. > I think we could return CELL_INSIDE_QUERY if the box contains either of the > edges of all MBRs of indexed triangles since triangles are guaranteed to > touch all edges of their MBR by definition. In some cases this would help > save decoding triangles and running costly point-in-triangle computations. -- 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
