Did Boyko answer this sufficiently? You don't have to examine each point. One way to think of a convex polygon is that the vertices are sorted (in angular order), so the parallel is close.
Henry Rich Roger Hui wrote: > I don't think it's possible to "do a convex polygon" > (or to do most anything) in O(log n) time. Simply to > examine each point requires O(n) time. > > You can do binary search in O(log n) time, but > that assumes that the points are sorted. > > > > ----- Original Message ----- > From: "R.E. Boss" <[email protected]> > Date: Wednesday, April 21, 2010 9:36 > Subject: Re: [Jprogramming] Polygon containment > To: 'Programming forum' <[email protected]> > >>> Van: [email protected] [mailto:programming- >>> [email protected]] Namens Henry Rich >>> Onderwerp: Re: [Jprogramming] Polygon containment >>> >>> If you have a gazillion points in a single polygon, you should pay >>> attention to Boyko's comment that you can do a convex polygon >> in O(log >>> n) time. >>> >>> I think the approach would be to recursively cut the polygon into >>> sections (perhaps just 2 sections), and then test each section by >>> testing a chord between the first and last vertices; if you're >> on the >>> good side of that chord, you need no further testing of that >> section.> >>> Henry Rich >>> >> >> For statements like that ("you can do a convex polygon in O(log >> n) time") I >> would like a proof or (at least) a reference. >> >> Apart from that, I rather see some actual performance figures, since >> probably it will be not too hard to come up with a process that >> is O(n), but >> in all real cases (much) faster than an O(log n) process. > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
