[
https://issues.apache.org/jira/browse/LUCENE-7212?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15239937#comment-15239937
]
Karl Wright commented on LUCENE-7212:
-------------------------------------
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.
{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]
