Math Wizard needed: Attn: Prof

[kabira]

I need to find a simple solution. I have bunch of coordinates in 2D plane. the shape can be anything. I just need to find whether given point is inside the boundary or its outside. Just to give you more info. Points actually are latiutde and longitude positions. The positions are very close (less than 2 Kms) and we can asssume 2D plane here. Now how to find if given value of lat and longitude falls inside the boundary of a region. How would I do that?

[punjabi_khota]

If the point is inside, the sum of angles subtended by it to each pair of consecutive boundary points will equal 360. :nice:

[kabira]

^hmm can you explain it better?

[punjabi_khota]

^hmm can you explain it better?

Number the boundary points of the region in (clockwise or anticlockwise..doesn't matter) order..starting from P1 to PN, where N is the number of total points making the boundary. Lets say the point you are checking is Q. Now look at angle P1-Q-P2, then P2-Q-P3, ....till PN-1 - Q- PN and finally PN-Q-P1. Add all the angles, and they should sum upto 360 for the point Q to be inside a polygon with vertices P1,P2,...PN.

[Nova]

^ I think you made it more complicated for him. :phehehe:

[kabira]

^will that work for irregular shapes like C shape or U Shape, Circles etc..

[seedhi]

^will that work for irregular shapes like C shape or U Shape' date=' Circles etc..[/quote']Assuming that the body is a closed, bounded region the following will work. Shoot a ray from the given point in any direction - and count the number of times the ray intersects the boundary of the given body. If the number is odd then the point is within the body and if it is even then it is outside.

[b555]

what seedhi has given is the ray casting algorithm now u can alo use the winding number algorithm. If the winding number is non-zero, the point lies inside the polygon http://en.wikipedia.org/wiki/Winding_number

[b555]

and seedhi`s method and this winding number method both work for any closed figure

[seedhi]

what seedhi has given is the ray casting algorithm now u can alo use the winding number algorithm. If the winding number is non-zero, the point lies inside the polygon http://en.wikipedia.org/wiki/Winding_number

May I ask how do you define the winding number for a fat ring, i.e. the region between two concentric circles? I think this will work only for bodies bounded by a single curve. Moreover, this cannot be generalized to higher dimensions in any obvious manner, unlike the ray method which works in any dimension.

[kabira]

Assuming that the body is a closed' date=' bounded region the following will work. Shoot a ray from the given point in any direction - and count the number of times the ray intersects the boundary of the given body. If the number is odd then the point is within the body and if it is even then it is outside.[/quote'] Great. I knew about this, but not sure how to implement this as a algorithm. How would I find if Ray interacts with the boundary assuming boundary is irregular.

[Aaku]

nerds :headshake:

[flamy]

Take a point on a surface. How do you know you're contained inside a box?

[seedhi]

Great. I knew about this' date=' but not sure how to implement this as a algorithm. How would I find if Ray interacts with the boundary assuming boundary is irregular.[/quote']Depends on how the body in given. If the body is a polygon in 2-dimensions then it may be given as an ordered sequence of vertices of the polygon. The closed curve formed by joining successive points in the sequence by line segments (and joining the last with the first as well) will give the boundary of the polygon, assuming it is does not intersect itself. It is easy to check whether a ray intersects a line segment (just need to solve a simple linear system). For more complicated bodies also it depends on how it is represented as an input.

[b555]

May I ask how do you define the winding number for a fat ring, i.e. the region between two concentric circles? I think this will work only for bodies bounded by a single curve. Moreover, this cannot be generalized to higher dimensions in any obvious manner, unlike the ray method which works in any dimension.

i havent ever tried but he was asking for 2d in particular so i even gave it i dont think it gives any trouble in 2-d plane situtations . or does it ?

[seedhi]

i havent ever tried but he was asking for 2d in particular so i even gave it i dont think it gives any trouble in 2-d plane situtations . or does it ?

It does have a problem, even in 2-d: suppose the body is the region between two concentric circles, centered at origin of radii 1 and 0.5. This body looks like a fat ring and is bounded by two curves viz the the two circles. Winding number is defined for a single continuous curve with respect to a point. It will work as long as the boundary of the body is a single continuous curve. However, in the example of a fat ring - the body is bounded by two curves.

[b555]

It does have a problem, even in 2-d: suppose the body is the region between two concentric circles, centered at origin of radii 1 and 0.5. This body looks like a fat ring and is bounded by two curves viz the the two circles. Winding number is defined for a single continuous curve with respect to a point. It will work as long as the boundary of the body is a single continuous curve. However, in the example of a fat ring - the body is bounded by two curves.

yes u r right but does this dont work like we can subtract the winding numbers of the two cylinders? as in n(big)-n(small) where n is the winding number ??

[kabira]

seedhi how will you do the math on this type of shape

[b555]

seedhi how will you do the math on this type of shape

if u denote the point u r talking by `x` mark the winding number iwill be zero as u can see from here illustrated http://mathworld.wolfram.com/ContourWindingNumber.html

[b555]

from the link i have given , if u can do the integration thats given below which needs basic knowledge of complex analysis , u yourself also can arrive at the result