[
https://issues.apache.org/jira/browse/LUCENE-7212?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15239937#comment-15239937
]
Karl Wright edited comment on LUCENE-7212 at 4/13/16 8:06 PM:
--------------------------------------------------------------
bq. detecting these things can be done in linear or n log n time.
Ok, this code snippet from GeoConvexPolygon does nothing more than confirm that
a polygon is in fact convex in the 3D world. Can you point me at a resource
that would describe how to do this in O(n log n) time? The actual checks that
are done in GeoPolygonFactory are a good deal more complex than this but one
algorithm would likely solve both problems.
In a nutshell, the problem in the 3D planar world is that relationships are not
transitive. If you show that a point is within an edge, and you construct a
new edge with it, and then you find a subsequent point, there's no guarantee
that the newest point will be within the oldest edge.
As a practical matter, this needs to be done only once (in GeoPolygonFactory),
and this check can go away from GeoConvexPolygon since it's now package
private. But that does not stop the need to perform a check of this kind and
break up the original polygon accordingly.
{code}
// In order to naively confirm that the polygon is convex, I would need to
// check every edge, and verify that every point (other than the edge
endpoints)
// is within the edge's sided plane. This is an order n^2 operation.
That's still
// not wrong, though, because everything else about polygons has a similar
cost.
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
final SidedPlane edge = edges[edgeIndex];
for (int pointIndex = 0; pointIndex < points.size(); pointIndex++) {
if (pointIndex != edgeIndex && pointIndex != legalIndex(edgeIndex + 1))
{
if (!edge.isWithin(points.get(pointIndex)))
throw new IllegalArgumentException("Polygon is not convex: Point "
+ points.get(pointIndex) + " Edge " + edge);
}
}
}
{code}
was (Author: [email protected]):
bq. detecting these things can be done in linear or n log n time.
Ok, this code snippet from GeoConvexPolygon does nothing more than confirm that
a polygon is in fact convex in the 3D world. Can you point me at a resource
that would describe how to do this in O(n log n) time? The actual checks that
are done in GeoPolygonFactory are a good deal more complex than this but one
algorithm would likely solve both problems.
In a nutshell, the problem in the 3D planar world is that relationships are not
transitive. If you show that a point is within an edge, and you construct a
new edge with it, and then you find a subsequent point, there's no guarantee
that the newest point will be within the oldest edge.
{code}
// In order to naively confirm that the polygon is convex, I would need to
// check every edge, and verify that every point (other than the edge
endpoints)
// is within the edge's sided plane. This is an order n^2 operation.
That's still
// not wrong, though, because everything else about polygons has a similar
cost.
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
final SidedPlane edge = edges[edgeIndex];
for (int pointIndex = 0; pointIndex < points.size(); pointIndex++) {
if (pointIndex != edgeIndex && pointIndex != legalIndex(edgeIndex + 1))
{
if (!edge.isWithin(points.get(pointIndex)))
throw new IllegalArgumentException("Polygon is not convex: Point "
+ points.get(pointIndex) + " Edge " + edge);
}
}
}
{code}
> Add Geo3DPoint equivalents of LatLonPointDistanceComparator and
> LatLonPointSortField
> ------------------------------------------------------------------------------------
>
> Key: LUCENE-7212
> URL: https://issues.apache.org/jira/browse/LUCENE-7212
> Project: Lucene - Core
> Issue Type: Improvement
> Affects Versions: master
> Reporter: Karl Wright
> Assignee: Karl Wright
>
> Geo3D has a number of distance measurements and a generic way of computing
> interior distance. It would be great to take advantage of that for queries
> that return results ordered by interior distance.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
