GeoDegeneratePoints return intersects when located in edge shape [LUCENE-7941]

[asfimport]

If the degenerate Geopoint lays on the boundary of a shape, the relationships between the objects are not symetrical:

The bounding box "thinks" it contains the degenerated point. The degenerated point "thinks" it intersects the shape.

---

Migrated from LUCENE-7941 by Ignacio Vera (@iverase), resolved Aug 26 2017 Attachments: LUCENE-7941-test.patch (versions: 2)

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

Hi @iverase, do you have a proposed solution?

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Attach failing test

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Not sure. I think the problematic methods is:

intersects(final Plane plane, ...)

If the answer is always WITHIN/CONTAINS, it means a point cannot intersects a plane and therefore the method should return always false.

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, the contract for "intersects" means that it must return true if there is intersection between the plane and the shape, within the bounds given. A point lying on the plane clearly intersects it. So that logic is right. The error must be elsewhere.

I notice this code:

  `@Override`
  public boolean intersects(GeoShape geoShape) {
    return false;
  }

That seems incorrect to me. I would think you'd want to call geoShape.within() here. Can you explain why a GeoDegeneratePoint should never be considered to intersect?

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

@DaddyWri, this is exactly the discussion I wanted to rise.

The contract of intersects(GeoShape geoShape) says: "Assess whether a shape intersects with any of the edges this shape." Therefore the current implementation is valid as there is no edges in GeoDegeneratedPoint.

Respect the other intersects method, the key lies in the word "shape". We are trying to make a point behave like a shape. It does not make sense that a point shape intersects a plane of another shape and the spatial relationship is WITHIN/CONTAINS. But I see that the getRelationship contract says:

"t is permissible to return OVERLAPS instead of WITHIN if the shape intersects with the area at even a single point."

I would say that overlaps should be better than within. Therefore point shapes should return OVERLAPS if they lay in an edge.

Make sense?

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, a point is a shape; it just happens to be very very tiny.

I will clarify the GeoArea comments to make sure they are unambiguous. Here is what it says for getRelationship():

   * It is permissible to return OVERLAPS instead of WITHIN if the shape
   * intersects with the area at even a single point.  So, a circle inscribed in
   * a rectangle could return either OVERLAPS or WITHIN, depending on
   * implementation.  It is not permissible to return CONTAINS or DISJOINT
   * in this circumstance, however.

In other words, if it is difficult to determine whether the shape is fully WITHIN, you may return OVERLAPS instead, as long as there is in fact some overlap. For a GeoPoint, this is not ambiguous or difficult at all; the point is either WITHIN the shape, or it's not. We have a method for assessing that: isWithin(). So it should be trivial to do the right thing here.

The contract for GeoShape.intersects() is as follows:

   * Assess whether a plane, within the provided bounds, intersects
   * with the shape.  Note well that this method is allowed to return "true"
   * if there are internal edges of a composite shape which intersect the plane.
   * Doing this can cause getRelationship() for most GeoBBox shapes to return
   * OVERLAPS rather than the more correct CONTAINS, but that cannot be
   * helped for some complex shapes that are built out of overlapping parts.

Here the contract is not clear as to what should happen if the plane within its bounds are entirely contained within the shape. But that's not needed to understand the proper behavior of a GeoDegeneratePoint – the point should be considered to intersect only if it lies on the plane within the bounds. I will try to clarify the comment for other situations.

[asfimport]

ASF subversion and git services (migrated from JIRA)

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

LUCENE-7941: Clarify contract for intersects() method.

[asfimport]

ASF subversion and git services (migrated from JIRA)

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

LUCENE-7941: Clarify contract for intersects() method.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 3b59343f73de1fd0c398a0868da0948f889f0b22 in lucene-solr's branch refs/heads/branch_7x from @DaddyWri https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=3b59343

LUCENE-7941: Clarify contract for intersects() method.

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, I will be away from the computer for some hours, but I think the right approach here is to adhere to the contracts. Please let me know if this doesn't make sense.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

I agree and this discussion is very useful. I understand what you mean and I agree. The kind of shape I have in mind is different to what GeoDegeneratePoint is.

The only solution I find is the following:

Change line 114 of GeoBaseAreaShape to:

if (!(geoShape instanceof GeoPoint) && intersects(geoShape)){ return GeoArea.OVERLAPS; }

That would do as GeoPoint do not OVERLAP.

Thanks!

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, I think what you are trying to say is that this method in GeoDegenerateShape:

  `@Override`
  public boolean intersects(GeoShape geoShape) {
    return false;
  }

... cannot be properly computed because we have no general way to do it, other than implement something special for all GeoAreaShapes when they intersect with points. I see what you are trying to do to work around this issue.

I wonder what would happen if we extend the contract for this method to allow a "true" return for either an intersection with an edge, but also for anything wholly within the shape, if the former is too hard to compute? Then you could use geoShape.isWithin(). Would that yield sensible values for getRelationship()?

I'll try to think about this further while I'm offline.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Nope, that will break getRelationship() as all WITHIN shapes will return OVERLAPS. The method checks if a shape goes in and out (cross and edge) of a shape, therefore OVERLAPS.

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase:

Nope, that will break getRelationship() as all WITHIN shapes will return OVERLAPS. The method checks if a shape goes in and out (cross and edge) of a shape, therefore OVERLAPS.

But that is legal, although not ideal:

* It is permissible to return OVERLAPS instead of WITHIN if the shape
   * intersects with the area at even a single point.

I would opt for this in the case of GeoDegeneratePoint.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 2b8cea09bb38511d065abd9e266c79ef5a6b8694 in lucene-solr's branch refs/heads/master from @DaddyWri https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=2b8cea0

LUCENE-7941: Broaden the contract for intersects() method, and implement the broadened contract in GeoDegeneratePoint.

[asfimport]

ASF subversion and git services (migrated from JIRA)

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

LUCENE-7941: Broaden the contract for intersects() method, and implement the broadened contract in GeoDegeneratePoint.

[asfimport]

ASF subversion and git services (migrated from JIRA)

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

LUCENE-7941: Broaden the contract for intersects() method, and implement the broadened contract in GeoDegeneratePoint.

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, this is what I did.

(1) I broadened the contract for the intersects(GeoShape) method to allow it to legally return true when "within". This is necessary because it's not just GeoDegeneratePoint objects that might have difficulty computing intersection with edges, and by broadening this, we still adhere to the contract of getRelationship() as it has been stated all along, which allows WITHIN situations to be reported as OVERLAPS when computational difficulty arises. At least, I believe this to be true. Please correct me if I am wrong.

(2) I changed the implementation of GeoDegeneratePoint.intersects(GeoShape) accordingly.

Please note that, because of this solution, asymmetrical getRelationship() results are expected for the objects that report OVERLAPS instead of WITHIN for getRelationship(GeoShape), and for methods which report "true" for intersects(GeoShape) in a WITHIN situation. So I did not commit your test; you will probably want to modify it and resubmit the patch when you are ready.

Thanks!

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Hi @DaddyWri,

I think actually the implementation of geoDegeneratePoint complies with the contract as it return CONTAINS/OVERLAPS (instead of WITHIN according to contract) when the geoDegeneratePoint lies in the boundary of the other shape .

On the other hand, the implementation of other shapes might be not fully complaint as any shape that has a point in an edge of another shape will always return OVERLAPS/OVERLAPS. Therefore a circle inscribed in a rectangle will return OVERLAPS/OVERLAPS.

If this is acceptable, then there is nothing to be done.

What it might be missing is a method in the the Plane; crossPlane(Plane lane,...) very similar to intersects but only return trues if intersects and has points in both sides of the other plane. With that functionaly the method getRelationship() can be more accurate according to contract.

Thanks!

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, please see below:

I think actually the implementation of geoDegeneratePoint complies with the contract as it return CONTAINS/OVERLAPS (instead of WITHIN according to contract) when the geoDegeneratePoint lies in the boundary of the other shape .

It sounds like you believe that the currently committed code is correct, then? It's hard to tell for sure.

On the other hand, the implementation of other shapes might be not fully complaint as any shape that has a point in an edge of another shape will always return OVERLAPS/OVERLAPS. Therefore a circle inscribed in a rectangle will return OVERLAPS/OVERLAPS. If this is acceptable, then there is nothing to be done.

Yes, that's been the case all along.

What it might be missing is a method in the the Plane; crossPlane(Plane lane,...) very similar to intersects but only return trues if intersects and has points in both sides of the other plane. With that functionaly the method getRelationship() can be more accurate according to contract.

There is a Plane method already that does this:

  /**
   * Find the points between two planes, where one plane crosses the other, given a set of bounds.
   * Crossing is not just intersection; the planes cannot touch at just one point on the ellipsoid,
   * but must cross at two.
   *
   * `@param` planetModel is the planet model.
   * `@param` q is the plane to intersect with.
   * `@param` bounds are the bounds to consider to determine legal intersection points.
   * `@return` the set of legal crossing points, or null if the planes are numerically identical.
   */
  public GeoPoint[] findCrossings(final PlanetModel planetModel, final Plane q, final Membership... bounds) {
    if (isNumericallyIdentical(q)) {
      return null;
    }
    return findCrossings(planetModel, q, bounds, NO_BOUNDS);
  }

This code eliminates intersections that don't involve the planes actually crossing. It's only used at the moment by GeoComplexPolygon, and has not been tested elsewhere.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

I think using the findCrossing is an overkill for performance.

In the implementation you just committed the check: geoDegeneratedPoint.getRelationship(shape) always return OVERLAPS when the point is inside the shape or in the edge.

In the previous implementation: geoDegeneratedPoint.getRelationship(shape) always return CONTAINS when the point is inside the shape or in the edge.

Note that the opposite: shape.getRelationship(geoDegeneratedPoint) returns WITHIN when it is inside the shape except when it is in the edge that return OVERLAPS.

I think the second one is more accurate but we need to add in the contract of intersection(GeoShape geoShape):

"It is permissible to return false if the shape does not cross any edge but it is difficult to compute intersection with edges"

If you are more happy with your implementation, it is fine with me. We have those two options and I am fine with both as they agree with the contract.

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, I picked the particular contract extension that I did because I knew it was possible to compute, since by definition you can always just call shape.isWithin(this). That's why I prefer it. But in your situation, does it work acceptably that way?

[asfimport]

ASF subversion and git services (migrated from JIRA)

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

LUCENE-7941: Add a crossing primitive in Plane.

[asfimport]

ASF subversion and git services (migrated from JIRA)

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

LUCENE-7941: Add a crossing primitive in Plane.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 2b7dc827c3d0ee80a4ba9f108b393ae307aa8200 in lucene-solr's branch refs/heads/branch_7x from @DaddyWri https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=2b7dc82

LUCENE-7941: Add a crossing primitive in Plane.

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, I've committed an implementation of Plane.crosses(), which is equivalent to Plane.intersects() but does not include single-point intersections. If you want to experiment with this you are welcome to do so.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Thanks for this new function @DaddyWri. My comments:

It seems there is a problem with it. In line 2305 of Plane class I think the condition should read like: if (!point1Valid) { return false; }

If not the function is equivalent to intersects().

I try to implement get relationship() with this new information. First thing I notice is that I need to run intersects() and crosses() in the same function all the time which seems to be running very similar code. I guess it would be better to have a function similar to getRelationship() for planes that return three possibilities: DISJOINT/INTERSECTS/CROSSES.

But It seems that if we go that way we would need to change more things. There is one case, when the intersection point is equal to the edge point that fails. It means that we would need at least two edge points per shape.

Now I am convinced that the current implementation is the most efficient under contract. I am not so keen in change it.

Thanks!

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, line 2500 of Plane.java is the start of a comment. But if I have the right place (line 2305) then this is my response:

(1) The difference between intersects() and crosses() is what the code does with the situation where there is only ONE solution to the line-intersecting-world computation it is performing. The code in question does differ from intersects() to crosses().

(2) The code you point out is trying to determine whether any of the two intersection points found are within the bounds. If neither is within the bounds then we must return false. But at this point we already know there are two intersection points on the globe; it does not matter whether one point is in bounds and the other is outside.

The way crosses() should behave differently from intersects() is that it should exclude solutions where the line of intersection touches the world at exactly one point. That is the only difference. That is what the math can compute; no more, and no less. If you can, in detail, supply an example of where this fails to detect an edge crossing, or detects a crossing where it should not, please do so, and we can analyze it further.

Note that the same logic exactly is used for GeoComplexPolygon, so we have some thoughts that it might be actually doing the right thing, provided you understand what it is actually doing. GeoComplexPolygon also uses infitesimal planes (that is, planes that have been moved a small distance one way or another) to count crossings, so maybe you will need to do something more to come up with a fully viable approach here.

My suspicion, though, is that we really don't get to independently calculate edge crossings from intersections in the way you would like – at least not in a computationally acceptable manner.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Thanks for the explanation, codes behaves as it should. For some reason I though it should only return true if both intersection were on bounds. I attach the test with current values.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 72818637f28a962843faa113e0fd6d1de8b25869 in lucene-solr's branch refs/heads/master from @DaddyWri https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=7281863

LUCENE-7941: Test for GeoDegeneratePoints relationships, committed on behalf of Ignacio Vera.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 9c450c8c2f3e87f142d3b3be337c33097152d9a7 in lucene-solr's branch refs/heads/branch_6x from @DaddyWri https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=9c450c8

LUCENE-7941: Test for GeoDegeneratePoints relationships, committed on behalf of Ignacio Vera.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 23ae00eaa11a5265d0284a7e31a2b63530bc2e47 in lucene-solr's branch refs/heads/branch_7x from @DaddyWri https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=23ae00e

LUCENE-7941: Test for GeoDegeneratePoints relationships, committed on behalf of Ignacio Vera.

[asfimport]

Shalin Shekhar Mangar (@shalinmangar) (migrated from JIRA)

Bulk close after 7.1.0 release