1
$\begingroup$

Given a convex polygon with $n$ edges sorted in cyclic order. How fast can we decide whether a line $\bar{pq}$ is fully inside the polygon?

My idea was to use a method for deciding whether a point is inside a polygon (e.g. ray casting algorithm) and do this twice. If both points are inside then the line between them is also inside the convex polygon.

Now my question is if there is any other faster method I didn't know of or if this is the usual way to go.

Any hint is appreciated!

$\endgroup$
  • $\begingroup$ I am no expert on this kind of algorithm, but can't you exploit the fact that the polygon is convex to do better than ray casting for the point-in-polygon test? Apart from that, I don't see how to do better than check that both ends of the line segment line in the polygon. $\endgroup$ – Rob Arthan Oct 29 '17 at 21:51
  • $\begingroup$ There is indeed an other way for the p-i-p test (think it's called winding number algorithm). But since there is some setting up required (done in O(n)) for that it's only efficient for a larger number of points to check (done in O(log n)). Ray casting method would result in 2*O(n) = O(n) AFAIK. $\endgroup$ – rndmusr Oct 29 '17 at 22:05
  • $\begingroup$ The winding number algorithm doesn't depend on convexity. I thought you would be able to do better than ray casting for convex polygons, but maybe there is no gain in the asymptotic complexity. $\endgroup$ – Rob Arthan Oct 29 '17 at 22:28
  • $\begingroup$ Then winding number is the wrong name. The algorithm I am talking about relies on convexity, kinda hard to explain and not of importance here anyways. Thanks for your thoughts anyways! $\endgroup$ – rndmusr Oct 29 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.