lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Karl Wright (JIRA)" <>
Subject [jira] [Resolved] (LUCENE-7216) Find an O(N) way to tile arbitrary geo3d polygons
Date Mon, 16 May 2016 10:47:12 GMT


Karl Wright resolved LUCENE-7216.
    Resolution: Won't Fix

This has been superceded by GeoComplexPolygon, which does not require tiling.

> Find an O(N) way to tile arbitrary geo3d polygons
> -------------------------------------------------
>                 Key: LUCENE-7216
>                 URL:
>             Project: Lucene - Core
>          Issue Type: Improvement
>          Components: modules/spatial3d
>    Affects Versions: 6.0
>            Reporter: Karl Wright
>            Assignee: Karl Wright
> Construction of GeoPolygons through GeoPolygonFactory.makeGeoPolygon() takes O(N^2) time,
where N is the number of points.  This is due to the non-transitive nature of edge/point comparisons
in Geo3D; just knowing that the next point is on the right side of an edge doesn't tell you
anything about previous edges.  Still, maybe there is a 2D algorithm somewhere that can be
adapted to run in O(N) time.

This message was sent by Atlassian JIRA

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message