[Jprogramming] Polygon containment

[R.E. Boss]

> Van: programming-bounces at jsoftware.com [mailto:programming-
> bounces at jsoftware.com] 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