1
$\begingroup$

I want to implement algorithms from this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf

In particular, I am currently dealing with the one in section 2.2.1. In page 4 (first paragraph), one algorithm step is as follows:

Find an edge $(v_k, v_{k+1})$ of $P_i$ ($P_i$ is a convex hull) that is completely visible from $s_i$ ($s_i$ is a point outside the convex hull).

My question is, how can I find a completely visible edge of a convex hull, that is completely visible from a point outside the convex hull?

$\endgroup$
  • $\begingroup$ If the two ends of an edge is visible, the the whole edge is visible. To check if $v_k$ is visible from $s_i$, you need to check if line segment $s_iv_k$ intersects with any of the edges (other than $v_kv_{k+1}$. $\endgroup$ – Helium Jul 15 '18 at 17:42
1
$\begingroup$

It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a convex polygon).

To find the intersection, you can use a binary search and find that is there any intersection or not.

$\endgroup$
  • 1
    $\begingroup$ Or just search linearly (rather than a binary search). The code is simpler and unless your polygon has millions of vertices, it may be faster. $\endgroup$ – Joseph O'Rourke Jul 15 '18 at 20:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.