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?

Improve this question
$\endgroup$
1
  • $\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, 2018 at 17:42

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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, 2018 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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