🚀 go-pugleaf

pa@verano.sba.ca.us (Pierre Asselin) writes:
>In <Jmv-D2=@engin.umich.edu> takriti@engin.umich.edu (samer Takriti) writes:
>
>>Linear programming does that very simply.
>[Linear program deleted]
>
>Only for convex polygons.  Your LP determins whether the point is
>interior to the convex hull of the polygon, not the polygon itself.

Right, and if you do have the convex polygon with vertices in sorted order,
you can use binary search (assuming constant access time, i.e. not a linked
list) to determine point inclusion in O(log N) time...That has to beat solving
for the convex combination of the vertices with a simple application of linear
programming...

-- 
 -- Erick, the perfect square  :-)