Details

Type: Improvement

Status: Open

Priority: Major

Resolution: Unresolved

Affects Version/s: None

Fix Version/s: None

Component/s: modules/spatial3d

Labels:None

Lucene Fields:New
Description
Hi,
Working with geosahpes and trying to resolve spatial relationships between them I came accross a big limitation when trying to solve the relationship between two geopolygons. This object does not expose the internal structure. In particular at some point, it is necessary to check if one polygon intersects the edges of the other polygon which currently is not possible as edges are not exposed.
To be able to perform such operation it can be several options. The ones I can think of are:
1) Expose the edges of the polygon ( and probably the notable points for the edges) adding getters in the GeoPolygon interface. Easy to implement and leave users the responsability of coding the spatial relationship.
2) Extends GeoPolygon interface to extends geoarea and leave the object make the spatial relationship.
3) Extends GeoShape interface so all shapes can infer the spatial relationship with other GeoShapes.
I might be bias as my interest is in 2d Shapes in the unit sphere and there might be some cases which what I propose cannot be implemented or are againts the aim of the library.
What do you think?
Cheers,
Ignacio

 LUCENE7906.patch
 79 kB
 Ignacio Vera
Activity
 All
 Comments
 Work Log
 History
 Activity
 Transitions
Hi Karl Wright,
I would try to do so. I have already some code that works for simple polygons. Let see if I manage for more complex cases. I am concern with the case of GeoComplexPolygon but I will have a try.
By the way, there is something in the implementation of getRelationship in GeoRectangle that seems wrong. The method call another method in GeoBaseBox called isShapeInsideBBox. In this methods there is the following call:
final GeoPoint[] pathPoints = path.getEdgePoints();
Expecting more than one point returned that is not true as the doc says:
/**
 Return a sample point that is on the outside edge/boundary of the shape.
*  @return samples of all edge points from distinct edge sections. Typically one point
 is returned, but zero or two are also possible.
*/
public GeoPoint[] getEdgePoints();
I think that method is not doing what it is expected. Still the overall method getRelationship seems to work.
Cheers,
I.
Multiple edge points must get returned when there are disconnected sections of the shape, when projected onto the world surface. This happens in a couple of situations, most notably for XYZSolids, which can slice straight through a world and manifest themselves as multiple actual areas.
There is also no harm in returning more than one point, even for a connected area, except for performance loss.
Ok, I understand and I will try to follow similar strategy for polygons when possible.
Thanks!
Ignacio
Hi Karl Wright,
Attached is the patches implementing GeoArea for polygons. I provide extended testing,
Some notes:
a) I have to modified the method getEdgePoints() from GeoCompositeMembershipShape. It ewas returning only the edge points for the first shape which seems incorrect. My implementation is not very efficient but works.
b)To be able able to bound the intersection of convex polygons I create the conves counter part. Maybe there is more efficient way of doing that.
c) Would it be worthy to push the geoArea interface down to GeoShape?
Cheers,
I.
Hi Ignacio Vera, we do not want to push GeoArea implementation down to GeoShape, because of shapes that cannot compute intersections readily, e.g. GeoCircle.
I agree that your implementation of GeoCompositePolygon.getEdgePoints() is correct.
I'll review your patch when time permits; it will have to wait until tomorrow, most likely.
I had a quick look at the diff, and found this issue:
+ @Override + public int getRelationship(GeoShape shape){ + boolean isWithin = false; + boolean isContains = false; + for (int i=0; i<shapes.size(); i++) { + GeoPolygon pol = (GeoPolygon) shapes.get(i); + int relationship = pol.getRelationship(shape); + switch (relationship){ + case GeoArea.OVERLAPS: return relationship; + case GeoArea.WITHIN: isWithin=true; break; + case GeoArea.CONTAINS: isContains=true;break; + case GeoArea.DISJOINT: break; + } + }
I note that OVERLAPS subcomponents return OVERLAPS as the result. But this cannot be correct because an OVERLAP between a subcomponent might actually be WITHIN.
I thought it was enough with skipping the internal edges but I can reproduce the behavior when I have a collection of shapes inside a GeoCompositeMembershipShape.
The wrong behavior happens because of this call GeoBaseShape.isShapeInsidePolygon(final GeoShape geoShape).
When checking in a multishape you might get SOME_INSIDE and therefore overlaps.
The Polygon to be compared should be the composite polygon and not the subcomponent so the methods returns the correct answer ALL_INSIDE.
What it means is that either GeoConvexPolygon and GeoConcavePolygon should have a reference to the parent composite polygon. I have implemented it and it works but it means that the contructor for those objects need to change. Is that ok?
Hi Ignacio Vera, I think it is OK to include a reference to the containing GeoPolygon in the constructor – but then you'd also need a pointer to the enclosing GeoPolygon in the constructor for GeoCompositePolygon, because they can be nested (and the factory constructs them in a nested fashion).
I don't think you'll be able to have GeoCompositePolygon simply call the getRelationship() methods of its child GeoPolygon members. I think you'll need to compute the intersection from first principles in GeoCompositePolygon itself, by asking the child polygons if any of their external edges get intersected etc. That may require the addition of a new method to GeoPolygon, but that's what I think is needed.
Yes, adding a new interface method to the polygon interface does the trick. I have added the method GeoPolygon.intersects(Geshape geoshape) and it is working as expected. Patch attached
Ignacio Vera, I had a quick glance at the newer patch. So far, so good, but have a care for spelling and for code style. Have a look here:
+ private boolean instersectsEdge(GeoShape other,Edge currentEdge,Edge firstEdge){ + if (currentEdge == firstEdge){ + return false; + } + if (other.intersects(currentEdge.plane,currentEdge.notablePoints,currentEdge.startPlane,currentEdge.endPlane)) { + return true; + } + if (firstEdge == null){ + firstEdge = currentEdge; + } + return instersectsEdge(other,currentEdge.next,firstEdge); + }
First note: "instersectsEdge" is misspelled; let's fix that before proceeding to commit.
Second, the style guide for Lucene states that there's a space after commas in argument lists for methods.
Minor details, but important. I'll have a longer look this evening.
Yes, you are right.
I fixed the spelling mistake and improve coding style.
Move the getRelationship method down to the GeoBasePolygon.
Hi Ignacio Vera, I had a more detailed look a this patch.
I note that there is a symmetry difference between GeoConcavePolygon and GeoConvexPolygon that I don't understand. GeoConcavePolygon has the following lazyinit'd member variable:
+ /** Convex polygon counter part used for bounding intersections. Lazy initialized */ + protected GeoPolygon convexPolygon=null; +
GeoConvexPolygon has no similar member variable. Can you explain why one has the converse shape, and the other doesn't? What is the code trying to do here?
I also worry a bit when a direct shape inversion is used, because points that are on a shape edge will be members of both the shape and its inverse. That may not be what you want.
The tests look good so far, but you really want to consider adding a randomized test as well. Have a look at extending some of the randomized Geo3d testing classes under spatialextras to include testing intersections against polygons:
06/29/2017 01:39 PM 10,420 Geo3dRptTest.java 06/29/2017 01:39 PM 9,563 Geo3dShapeRectRelationTestCase.java 04/17/2016 03:38 PM 3,418 Geo3dShapeSphereModelRectRelationTest.java 04/05/2016 06:10 AM 6,144 Geo3dShapeWGS84ModelRectRelationTest.java 03/31/2016 08:08 PM 10,239 RandomizedShapeTestCase.java
Hi Karl Wright,
The problem with convex polygons is that the whole plane is within the shape and therefore if you try to bound the intersection with the convex polygon you get OVERLAP when the shape is actually WITHIN. What it holds true is that the bounds for an intersection for convex polygons are the ones defined by the convex counter part. Therefore I need to invert the shape to bound the intersection. The class variable is to cash the object so it is only created once. Does it make sense?
I will try to implement randomized tests as well but it will take a bit longer because I have never used the framework and I am actually having problems running those tests (environment issues).
Finally, I want to go back to the idea of moving GeoArea down to GeoShape. If the implementation for polygons is valid, it means that any shape that can implement the new interface method intersects(GeoShape geoShape) can implement GeoArea. You were concerned about circle intersection but I think it is a trivial implementation. We only need to add the interface GeoOutsideDistance to GeoShape which is free as all shapes already implement the interface. Then intersection is trivial by calculating the distance of the shape to the center of the circle. What do you think?
Cheers,
Ignacio
Ignacio Vera, requiring GeoArea implementation for all GeoShapes very much complicates the implementation of new GeoShapes, and I would be very much against it. You are welcome to try to implement GeoArea for GeoCircles but remember that your distance computation does not work in WGS84, only in SPHERE. Complex shapes like GeoPaths are not only messy to make work generally, but they also have even messier considerations when you use WGS84. Polygons in WGS84 aren't much harder than polygons in SPHERE which is why I thought that was doable, but after that point it gets much tougher. The "GeoCircle" is by definition the intersection of a specific plane with the unit ellipsoid, so it's in fact an ellipse and distance calculations are exorbitantly expensive.
One of the reasons I am absolutely certain we need to include GeoPolygons in the randomized testing is because, for the geo3d world, such testing is essential to be sure you've really covered all the corner cases and have no numeric precision problems. So this is something we need to tackle I'm afraid.
If your concern is that you want new shapes to be able to support your way of computing intersection, let me point out that any shape where the edge planes go through the ellipsoid center is likely to be represented as a polygon, so you've got that well covered. It's the shapes that don't have that characteristic that I don't think are straightforward to implement. So for that reason I'm OK with the way it's set up now.
Thanks!
The problem with convex polygons is that the whole plane is within the shape and therefore if you try to bound the intersection with the convex polygon you get OVERLAP when the shape is actually WITHIN. What it holds true is that the bounds for an intersection for convex polygons are the ones defined by the convex counter part. Therefore I need to invert the shape to bound the intersection. The class variable is to cash the object so it is only created once. Does it make sense?
Yes, I understand the limitations. I'm not, however, thrilled with the lazyinit part of this since it gives us some thread safety concerns, and the "inverse shape" way of doing things has problems as I described earlier. If all you are trying to do is model the bounds for each edge plane, you're probably better off, and safer too, computing and saving those bounds when the polygon is constructed. You'll especially need to worry about almostcoplanar adjacent polygon edges; it may be better to construct a pair of perpendicular planes for each edge if you need a good bound. Or, you can use the adjoining edges but just invert their sidedness; there's a SidedPlane constructor that does that. Let me look carefully at the code for both kinds of polygon and give you my recommendation.
The above concerns are exactly why randomized tests are so valuable, by the way, and why they really need to be there before we can have assurance that your implementation is not going to generate a slew of bug reports when it hits the real world.
The randomized tests I pointed you at earlier construct mainly GeoBBox shapes to intersect against. You'd want almost the same test but with random (but regular and not selfoverlapping) GeoPolygons. You'll need to put some thought into how to construct a random, nondegenerate GeoConvexPolygon or GeoConcavePolygon, especially with holes. There are IllegalArgumentException conditions thrown by the constructors when shapes are found to be illegal for some reason, but I believe we removed some of these in the polygon constructors because of their cost. Other randomized tests that construct GeoPolygons use a center point, and walk around the center point N times with a random angle each time and a random arc distance; that guarantees nonselfintersecting but doesn't prevent concavity/convexity. You could use the GeoPolygonFactory method, though, to create a composite polygon from this consisting of multiple child shapes and that is guaranteed to work and be legal. So I encourage you to look at how polygon construction is done in the existing tests.
Thanks!
Hi Ignacio Vera, for both GeoConcavePolygon and GeoConvexPolygon, there is a member variable already constructed as follows:
/** A bounds object for each sided plane */ protected Map<SidedPlane, Membership> eitherBounds = null;
This map can be used to look up the bounds, as a single Membership object, for every edge plane in the polygon. I suggest you use this rather than some other way of doing it.
Thanks!
Ok, I did not know that distance calculation is only support for unit sphere. That is my use case so I guess I am bias. It is totally fine to leave things then as they are.
Thanks for your suggestions, I will try to put everything together in the next week or so.
Cheers,
Ignacio
Ignacio Vera, arcDistance is defined well for ellipsoids but surfaceDistance requires an iterative convergent loop. Also, the GeoCircle is in fact a single plane which slices through the ellipsoid forming an ellipse. Since surfaceDistance is prohibitively expensive to calculate for all but a sphere, an approximation is required either way, and the GeoCircle is fitted specially to the ellipsoid in order to be a good approximation for WGS84.
Hi Ignacio Vera,
In Geo3D, there is currently only support for computing the intersection with shapes that implement GeoArea. These only include GeoBBox (2D) and XYZSolid (3D). Currently, GeoPolygon objects do not implement GeoArea. This is by design. There are many cases and corner cases that would need algorithmic development to properly implement polygon intersection.
If you need to support this case, feel free to supply a patch where GeoPolygon extends GeoArea. You will need to implement getRelationship() for GeoComplexPolygon, GeoConvexPolygon, GeoConcavePolygon, and GeoCompositePolygon. I would also urge you to include many test cases to be sure your code is working as designed.