# Segment Inside a Polygon

10 messages
Open this post in threaded view
|

## Segment Inside a Polygon

 Hello I am new to CGAl and I need to check whether there is a way to check if a line segment lies completely inside a polygon or not. The file intersection.h in CGAL offers intersection of line vs live, triangle vs line and many more options but not a polygon. Can anyone help me?
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 Hi Prateek, The function CGAL::bounded_side_2 computes if a point lies inside a polygon. Please check the reference manual for its usage.  #include An example of how to use this function is also given in the Polygon chapter of the CGAL Manual.  Hope this helps. Best regards, Sandeep. On Thu, Feb 2, 2012 at 8:06 PM, pgiitu wrote: Hello I am new to CGAl and I need to check whether there is a way to check if a line segment lies completely inside a polygon or not. The file intersection.h in CGAL offers intersection of line vs live, triangle vs line and many more options but not a polygon. Can anyone help me? -- View this message in context: http://cgal-discuss.949826.n4.nabble.com/Segment-Inside-a-Polygon-tp4352456p4352456.html Sent from the cgal-discuss mailing list archive at Nabble.com. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 Hi Prateek,It is written in the manual: The function bounded_side_2 computes if a point lies inside a polygon. The polygon is defined by the sequence of points first. . . last. Being inside is defined by the odd-even rule. If we take a ray starting at the point and extending to infinity (in any direction), we count the number of intersections. If this number is odd, the point is inside, otherwise it is outside. So if we write a similar function in which the ray is in the direction of other end point, then depending on the number of intersection up to the other end point we can decide if the line segment is inside or not.  May be there are other existing possible solutions. Best regards, Sandeep. On Thu, Feb 2, 2012 at 11:27 PM, Sandeep Dey wrote: Hi Prateek, The function CGAL::bounded_side_2 computes if a point lies inside a polygon. Please check the reference manual for its usage.  #include An example of how to use this function is also given in the Polygon chapter of the CGAL Manual.  Hope this helps. Best regards, Sandeep. On Thu, Feb 2, 2012 at 8:06 PM, pgiitu wrote: Hello I am new to CGAl and I need to check whether there is a way to check if a line segment lies completely inside a polygon or not. The file intersection.h in CGAL offers intersection of line vs live, triangle vs line and many more options but not a polygon. Can anyone help me? -- View this message in context: http://cgal-discuss.949826.n4.nabble.com/Segment-Inside-a-Polygon-tp4352456p4352456.html Sent from the cgal-discuss mailing list archive at Nabble.com. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 Hello Sandeep, Thanks for the help but I would like to emphasize that point inside a polygon and line segment inside a polygon are two very different problems. Even after counting the no. of intersections it is not possible to tell whether the whole line segment is inside the polygon or not. For Ex consider the following image in the file imagepdf.pdfFor the two red line segments the no of intersections are the same in every case. so The no of intersections thing will not work.
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 Hi,If we consider that segment lies completely inside polygon means: that end point of segment is also inside polygon and not on the boundary then the query can be answered by writing a similar function bounded_side_2. Actually if the 1st end point of the segment is inside the polygon then shooting the ray directing towards other end point of the segment can answer the query, In case there is any intersection before reaching the other end point, then for sure the segment is not inside the polygon. And if there is no intersection then the segment is inside the polygon.Now if we want to consider a point on the boundary of polygon to be inside the polygon, we need one extra check for the special case as shown in your figure:  We can do the following:The case when both the end points are on the boundary of polygon , and no other intersection taken place between two end points, we need to do one more check, take any point in the line segment say mean of the two end points, then if this point lies outside polygon then the segment also lies outside polygon,  else the whole segment is inside the polygon.Regards,Sandeep.On Fri, Feb 3, 2012 at 11:03 AM, pgiitu wrote: Hello Sandeep, Thanks for the help but I would like to emphasize that point inside a polygon and line segment inside a polygon are two very different problems. Even after counting the no. of intersections it is not possible to tell whether the whole line segment is inside the polygon or not. For Ex consider the following image in the file http://cgal-discuss.949826.n4.nabble.com/file/n4354159/imagepdf.pdf imagepdf.pdf For the two red line segments the no of intersections are the same in every case. so The no of intersections thing will not work. -- View this message in context: http://cgal-discuss.949826.n4.nabble.com/Segment-Inside-a-Polygon-tp4352456p4354159.html Sent from the cgal-discuss mailing list archive at Nabble.com. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 On 02/03/2012 02:04 PM, Sandeep Dey wrote: > Hi, > > If we consider that segment lies completely inside polygon means: that > end point of segment is also inside polygon and not on the boundary then > the query can be answered by writing a similar function bounded_side_2. > Actually if the 1st end point of the segment is inside the polygon then > shooting the ray directing towards other end point of the segment can > answer the query, >   In case there is any intersection before reaching the other end point, > then for sure the segment is not inside the polygon. > And if there is no intersection then the segment is inside the polygon. > > Now if we want to consider a point on the boundary of polygon to be > inside the polygon, we need one extra check for the special case as > shown in your figure: > We can do the following: > The case when both the end points are on the boundary of polygon , and > no other intersection taken place between two end points, > we need to do one more check, take any point in the line segment say > mean of the two end points, then if this point lies outside polygon then > the segment also lies outside polygon, > else the whole segment is inside the polygon. In that case it is not sufficient, (the midpoint can be inside the polygon but not the segment itself). In that case, I think you need to check if each polygon segments is intersected in its interior by the query segment. Sebastien. > > Regards, > > Sandeep. > > > > > > On Fri, Feb 3, 2012 at 11:03 AM, pgiitu <[hidden email] > > wrote: > >     Hello Sandeep, > >     Thanks for the help but I would like to emphasize that point inside a >     polygon and line segment inside a polygon are two very different >     problems. >     Even after counting the no. of intersections it is not possible to tell >     whether the whole line segment is inside the polygon or not. > >     For Ex consider the following image in the file > >     http://cgal-discuss.949826.n4.nabble.com/file/n4354159/imagepdf.pdf>     imagepdf.pdf > > >     For the two red line segments the no of intersections are the same >     in every >     case. so The no of intersections thing will not work. > >     -- >     View this message in context: >     http://cgal-discuss.949826.n4.nabble.com/Segment-Inside-a-Polygon-tp4352456p4354159.html>     Sent from the cgal-discuss mailing list archive at Nabble.com. > >     -- >     You are currently subscribed to cgal-discuss. >     To unsubscribe or access the archives, go to >     https://lists-sop.inria.fr/wws/info/cgal-discuss> > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 Hii First of all I am sorry for the confusion. The line segment with points on the boundary of the polygon are also allowed(There should not be any point on the line segment which lies outside the polygon). I think the the algorithm is like this:- 1. Calculate the intersections of the line segment with all the edges of the polygon. 2. If there is is/are intersection/intersections other than the vertices of the polygon then the segment is not in the polygon. 3. If there is no intersection then we need to check for some point on the line segment if it lies inside the polygon or outside. I have implemented it in the above mentioned way and I hope that it works. If there is any problem in the above algorithm please let me know. Anyways Thank you very much  for the help......
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 In reply to this post by Sebastien Loriot (GeometryFactory) Hii First of all I am sorry for the confusion. The line segment with points on the boundary of the polygon are also allowed(There should not be any point on the line segment which lies outside the polygon). I think the the algorithm is like this:- 1. Calculate the intersections of the line segment with all the edges of the polygon. 2. If there is is/are intersection/intersections other than the vertices of the polygon then the segment is not in the polygon. 3. If there is no intersection then we need to check for some point on the line segment if it lies inside the polygon or outside. I have implemented it in the above mentioned way and I hope that it works. If there is any problem in the above algorithm please let me know. Anyways Thank you very much  for the help......
Open this post in threaded view
|

## Re: Segment Inside a Polygon

 In reply to this post by Sebastien Loriot (GeometryFactory) Hii First of all I am sorry for the confusion. The line segment with points on the boundary of the polygon are also allowed(There should not be any point on the line segment which lies outside the polygon). I think the the algorithm is like this:- 1. Calculate the intersections of the line segment with all the edges of the polygon. 2. If there is is/are intersection/intersections other than the vertices of the polygon then the segment is not in the polygon. 3. If there is no intersection then we need to check for some point on the line segment if it lies inside the polygon or outside. I have implemented it in the above mentioned way and I hope that it works. If there is any problem in the above algorithm please let me know. Anyways Thank you very much  for the help......
Open this post in threaded view
|

## Re: Segment Inside a Polygon

I am afraid your algorithm is basically correct, except for the second step.
We made a trivial modification to it.

1. Iterate the intersection of the line segment with all the edges of the polygon.

2. If there is intersection that is neither endpoints of the segment in checking nor the polygon vertex,then the segment is not in the polygon and exit. (we prefer singulative expression, because in each time of iteration, there is no more than one intersection of two segments).

3. Check the middle point of line segment if it lies inside the polygon or outside.
-------------