> 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.
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
