Algorithm for finding if a line segment connecting two vertices in a polygon is contained in the polygon

algorithmsgeometrypolygons

My question is as follows. Consider a polygon $P$. Here I am assuming $P$ is a simple polygon, that is, no self intersections, though I am allowing double edges as can be seen in the image below.
Picture depicting acceptable and unacceptable polygons

Suppose I pick two vertices $u$ and $v$ of $P$. I want to know if there is an algorithm which tells me if the line segment connecting $u$ and $v$ is contained in $P$. Here, "contained" means the line is contained in the polygon and does not cross any internal "double" edges. I know there exists an algorithm for simple polygons with no double edges but have not been able to find an algorithm that deals with this case.

Any answers are greatly appreciated.

Best Answer

[[ In the Question, you mentioned that you are aware of Algorithms to Check whether a Line is within a Polygon or not (CONTAINED or not) , but those known Algorithms only work on Polygon Cases where there are no Double Edges. I am giving a tweak to those "Standard Algorithms" to handle the Polygon Cases where there may be Double Edges. ]]

Given a Polygon $P$ with your Criteria, we can always convert that to a new Polygon $X$ with no Double Edges & a set of Double Edges $Y$, which may or may not be empty.

We can now use the "Standard Algorithms" to check whether $X$ contains the Edge $uv$ :

  • If NO , $P$ also does not contain $uv$.
  • If YES , we have to check , using "Standard Algorithms" , whether $uv$ intersects some Edge in $Y$.
    -- If YES , $P$ does not contain $uv$.
    -- If NO , $P$ contains $uv$.

Example In Action :
Polygon with Double Edges

We are given this Polygon $P$ having Single Edges in Black & Double Edges in Blue. The interior is the Shaded Area.
We make the new Polygon $X$ with only the Black Edges. We also make the set $Y$ of Double Edges in Blue.

We can check that the left Gray Edge is outside the Polygon $X$, hence we return NOT CONTAINED in this Algorithm.
We can check that the middle Gray Edge is contained by the Polygon $X$, thus we move to Edge-Checking. It intersects Exactly one Blue Double Edge in $Y$, hence we return NOT CONTAINED in this Algorithm
The Purple Edge is contained by the Polygon $X$, thus we move to Edge-Checking. No Blue Edge in $Y$ intersects the Purple Edge, hence we return CONTAINED in this Algorithm.

[[ I assume you know about Polygon Checking & Line Segment Intersections , from the wording in your Question ]]

Related Question