Segment Inside a Polygon

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Segment Inside a Polygon

pgiitu
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?
Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

Sandeep Dey-2

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 <CGAL/Polygon_2_algorithms.h>

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 <[hidden email]> 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


Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

Sandeep Dey-2
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 <[hidden email]> 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 <CGAL/Polygon_2_algorithms.h>

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 <[hidden email]> 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



Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

pgiitu
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.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.
Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

Sandeep Dey-2
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 <[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


Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

Sebastien Loriot (GeometryFactory)
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]
> <mailto:[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

Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

pgiitu
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......
Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

pgiitu
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......
Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

pgiitu
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......
Reply | Threaded
Open this post in threaded view
|

Re: Segment Inside a Polygon

ayongwust_sjtu
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.
-------------

Regards,

Xianyong Liu