lucene-dev mailing list archives

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

     [ https://issues.apache.org/jira/browse/LUCENE-7216?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

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: https://issues.apache.org/jira/browse/LUCENE-7216
>             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
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message