I think we were (at least I was) not so much interested in the number of points of the polygon (vertices), as well as the number of points to be examined, which was huge: "there are very few polygons but a gazillion points" http://jsoftware.com/pipermail/programming/2010-April/019248.html
R.E. Boss > -----Oorspronkelijk bericht----- > Van: [email protected] [mailto:programming- > [email protected]] Namens Henry Rich > Verzonden: donderdag 22 april 2010 3:55 > Aan: Programming forum > Onderwerp: Re: [Jprogramming] Polygon containment > > 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. > > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
