Mixing
How can I determine if a coordinates ordered pair (x,y) is within the bounds of n ordered pairs? [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Is there a math formula of some kind, where I have a set of ordered pair coordinates, and then pass in a single ordered pair coordinate to determine if that pair is within the bounds of the set?
I'm not the greatest at math, so I'm hoping someone who is can help me out here. I am not even sure if I'm explaining it correctly. Please correct my tags and terminology as needed.
Example data:
I have a coordinate where someone is located in lat-long. Let's say (28.3797770, -81.5431893).
I also have a set of coordinates that corresponds to an area. It could be 3-sided or higher. In this example with the screenshot, it's 7 coordinates.
latitude, longitude
(28.3795930, -81.5433286)
(28.3797771, -81.5431891)
(28.3797098, -81.5430725)
(28.3796355, -81.5431288)
(28.3794715, -81.5428780)
(28.3793546, -81.5429665)
(28.3795859, -81.5433219)
calculus algebra-precalculus geometry
asked Jul 18 at 21:46
Ethan Allen
1363
closed as off-topic by amWhy, max_zorn, Mostafa Ayaz, Adrian Keister, Strants Jul 19 at 14:59
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, max_zorn, Mostafa Ayaz
add a comment |Â
up vote
0
down vote
favorite
Is there a math formula of some kind, where I have a set of ordered pair coordinates, and then pass in a single ordered pair coordinate to determine if that pair is within the bounds of the set?
I'm not the greatest at math, so I'm hoping someone who is can help me out here. I am not even sure if I'm explaining it correctly. Please correct my tags and terminology as needed.
Example data:
I have a coordinate where someone is located in lat-long. Let's say (28.3797770, -81.5431893).
I also have a set of coordinates that corresponds to an area. It could be 3-sided or higher. In this example with the screenshot, it's 7 coordinates.
latitude, longitude
(28.3795930, -81.5433286)
(28.3797771, -81.5431891)
(28.3797098, -81.5430725)
(28.3796355, -81.5431288)
(28.3794715, -81.5428780)
(28.3793546, -81.5429665)
(28.3795859, -81.5433219)
calculus algebra-precalculus geometry
asked Jul 18 at 21:46
Ethan Allen
1363
closed as off-topic by amWhy, max_zorn, Mostafa Ayaz, Adrian Keister, Strants Jul 19 at 14:59
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, max_zorn, Mostafa Ayaz
This is the Point in Polygon problem. Ray casting is a typical solution algorithm.
– Adrian Keister
Jul 19 at 12:57
1
Possible duplicate of Point in Polygon algorithm - Why does it work?
– Adrian Keister
Jul 19 at 12:57
@amWhy et al. You are being too fussy by putting this question on hold. It was clear enough to me. He has a point and a polygon and wants to determine if the point is inside or outside.
– herb steinberg
Jul 19 at 16:11
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Is there a math formula of some kind, where I have a set of ordered pair coordinates, and then pass in a single ordered pair coordinate to determine if that pair is within the bounds of the set?
I'm not the greatest at math, so I'm hoping someone who is can help me out here. I am not even sure if I'm explaining it correctly. Please correct my tags and terminology as needed.
Example data:
I have a coordinate where someone is located in lat-long. Let's say (28.3797770, -81.5431893).
I also have a set of coordinates that corresponds to an area. It could be 3-sided or higher. In this example with the screenshot, it's 7 coordinates.
latitude, longitude
(28.3795930, -81.5433286)
(28.3797771, -81.5431891)
(28.3797098, -81.5430725)
(28.3796355, -81.5431288)
(28.3794715, -81.5428780)
(28.3793546, -81.5429665)
(28.3795859, -81.5433219)
calculus algebra-precalculus geometry
asked Jul 18 at 21:46
Ethan Allen
1363
Is there a math formula of some kind, where I have a set of ordered pair coordinates, and then pass in a single ordered pair coordinate to determine if that pair is within the bounds of the set?
I'm not the greatest at math, so I'm hoping someone who is can help me out here. I am not even sure if I'm explaining it correctly. Please correct my tags and terminology as needed.
Example data:
I have a coordinate where someone is located in lat-long. Let's say (28.3797770, -81.5431893).
I also have a set of coordinates that corresponds to an area. It could be 3-sided or higher. In this example with the screenshot, it's 7 coordinates.
latitude, longitude
(28.3795930, -81.5433286)
(28.3797771, -81.5431891)
(28.3797098, -81.5430725)
(28.3796355, -81.5431288)
(28.3794715, -81.5428780)
(28.3793546, -81.5429665)
(28.3795859, -81.5433219)
calculus algebra-precalculus geometry
asked Jul 18 at 21:46
Ethan Allen
1363
asked Jul 18 at 21:46
Ethan Allen
1363
asked Jul 18 at 21:46
Ethan Allen
1363
asked Jul 18 at 21:46
Ethan Allen
1363
1363
closed as off-topic by amWhy, max_zorn, Mostafa Ayaz, Adrian Keister, Strants Jul 19 at 14:59
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, max_zorn, Mostafa Ayaz
closed as off-topic by amWhy, max_zorn, Mostafa Ayaz, Adrian Keister, Strants Jul 19 at 14:59
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, max_zorn, Mostafa Ayaz
This is the Point in Polygon problem. Ray casting is a typical solution algorithm.
– Adrian Keister
Jul 19 at 12:57
1
Possible duplicate of Point in Polygon algorithm - Why does it work?
– Adrian Keister
Jul 19 at 12:57
@amWhy et al. You are being too fussy by putting this question on hold. It was clear enough to me. He has a point and a polygon and wants to determine if the point is inside or outside.
– herb steinberg
Jul 19 at 16:11
add a comment |Â
This is the Point in Polygon problem. Ray casting is a typical solution algorithm.
– Adrian Keister
Jul 19 at 12:57
1
Possible duplicate of Point in Polygon algorithm - Why does it work?
– Adrian Keister
Jul 19 at 12:57
@amWhy et al. You are being too fussy by putting this question on hold. It was clear enough to me. He has a point and a polygon and wants to determine if the point is inside or outside.
– herb steinberg
Jul 19 at 16:11
This is the Point in Polygon problem. Ray casting is a typical solution algorithm.
– Adrian Keister
Jul 19 at 12:57
This is the Point in Polygon problem. Ray casting is a typical solution algorithm.
– Adrian Keister
Jul 19 at 12:57
1
1
Possible duplicate of Point in Polygon algorithm - Why does it work?
– Adrian Keister
Jul 19 at 12:57
Possible duplicate of Point in Polygon algorithm - Why does it work?
– Adrian Keister
Jul 19 at 12:57
@amWhy et al. You are being too fussy by putting this question on hold. It was clear enough to me. He has a point and a polygon and wants to determine if the point is inside or outside.
– herb steinberg
Jul 19 at 16:11
@amWhy et al. You are being too fussy by putting this question on hold. It was clear enough to me. He has a point and a polygon and wants to determine if the point is inside or outside.
– herb steinberg
Jul 19 at 16:11
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
Construct a line at the given latitude with longitude along a line to the right of the point, past all the edges of the polygon.
Determine the intersections of this line with each of the edges of the polygon.
Count those to the right of the point of interest.
- If the number is even, the point is outside.
- If odd, the point is inside.
edited Jul 19 at 14:07
amWhy
189k25219431
answered Jul 18 at 22:03
herb steinberg
94429
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
add a comment |Â
up vote
0
down vote
Assume you have ordered all of your coordinates in the order you wish to construct your polygon (as the order matters). I will show an example. Let's assume that our polygon has 4 vertices:
$$ V = (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) = V_1,V_2,V_3,V_4$$
First we want to construct lines which pass through $V_1$ and $V_2$, then $V_2$ and $V_3$ and so on 'till we finally get the line which passes through $V_4$ and $V_1$ "closing" our polygon. I would suggest making a class which represents points and lines if you're using an OOP based language and keeping them in a vector, or array. Let's assume we now have the equations of all $n$ lines ($n$ is the number of vertices of your polygon).
$$E = f_1, f_2, f_3, f_4 $$
In order to obtain the equation of a line which passes through two points you can use the formula:
$$ y - y_1 = fracy_2 - y_1x_2 - x_1(x-x_1)$$
After that we want to find the equation of the line which passes through the point we are checking if it's inside the polgyon and is parallel to the $x$ axis. Lets assume our point has the coordinates $(1,2)$, in that case its equation would be:
$$y = 2 $$
Finally we want to check how many intersections we have between the lines in the set of $E$ and the line we previously defined. If the number of intersections is odd, then our point is located inside the polgyon, and if it is even, then it's located outside. The logic is simple If the line crosses the lines which belong to $E$ once, that means we were inside the polgyon as the line started inside, so in order for it to leave and go towards infinity it had to only cross the lines which construct the polygon once. Obviously, if it had two intersections or zero it was outside to begin with. I'll leave it to you to see how it would be possible that there are 5 intersections.
IMPORTANT NOTE: Only check for the intersections on the part of the line which actually constructs the polgyon. If you make a class this is easy to implement. With proper implementation it should have complexity $O(n)$ which is really nice. I'll add a picture to illustrate what I meant:
Obviously, point $A$ belongs to the polgyon, and we can see that there is only one intersection. Point $B$ and $C$ don't belong, because there are zero and two intersections, respectively. Try to answer the question what happens when the point is on the edge of the polgyon?
answered Jul 18 at 23:28
user1949350
977
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Construct a line at the given latitude with longitude along a line to the right of the point, past all the edges of the polygon.
Determine the intersections of this line with each of the edges of the polygon.
Count those to the right of the point of interest.
- If the number is even, the point is outside.
- If odd, the point is inside.
edited Jul 19 at 14:07
amWhy
189k25219431
answered Jul 18 at 22:03
herb steinberg
94429
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
add a comment |Â
up vote
2
down vote
Construct a line at the given latitude with longitude along a line to the right of the point, past all the edges of the polygon.
Determine the intersections of this line with each of the edges of the polygon.
Count those to the right of the point of interest.
- If the number is even, the point is outside.
- If odd, the point is inside.
edited Jul 19 at 14:07
amWhy
189k25219431
answered Jul 18 at 22:03
herb steinberg
94429
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Construct a line at the given latitude with longitude along a line to the right of the point, past all the edges of the polygon.
Determine the intersections of this line with each of the edges of the polygon.
Count those to the right of the point of interest.
- If the number is even, the point is outside.
- If odd, the point is inside.
edited Jul 19 at 14:07
amWhy
189k25219431
answered Jul 18 at 22:03
herb steinberg
94429
Construct a line at the given latitude with longitude along a line to the right of the point, past all the edges of the polygon.
Determine the intersections of this line with each of the edges of the polygon.
Count those to the right of the point of interest.
- If the number is even, the point is outside.
- If odd, the point is inside.
edited Jul 19 at 14:07
amWhy
189k25219431
answered Jul 18 at 22:03
herb steinberg
94429
edited Jul 19 at 14:07
amWhy
189k25219431
edited Jul 19 at 14:07
amWhy
189k25219431
edited Jul 19 at 14:07
amWhy
189k25219431
189k25219431
answered Jul 18 at 22:03
herb steinberg
94429
answered Jul 18 at 22:03
herb steinberg
94429
answered Jul 18 at 22:03
herb steinberg
94429
94429
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
add a comment |Â
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
Sorry for my possible ignorance here... Are you suggesting I graph this? I'm looking for a possible mathematical solution. I'm going to be writing a function purely in computer code to determine whether a coordinate is in/out (true/false) of the shape.
– Ethan Allen
Jul 18 at 22:15
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
@EthanAllen No, he’s suggesting that you apply the Jordan curve theorem: cast a ray to some faraway point that you know is outside of the area and count the number of times that ray crosses an edge of the polygon. You can find several algorithms for computing the intersection of a ray (line) and line segment by searching the Web.
– amd
Jul 18 at 23:28
add a comment |Â
up vote
0
down vote
Assume you have ordered all of your coordinates in the order you wish to construct your polygon (as the order matters). I will show an example. Let's assume that our polygon has 4 vertices:
$$ V = (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) = V_1,V_2,V_3,V_4$$
First we want to construct lines which pass through $V_1$ and $V_2$, then $V_2$ and $V_3$ and so on 'till we finally get the line which passes through $V_4$ and $V_1$ "closing" our polygon. I would suggest making a class which represents points and lines if you're using an OOP based language and keeping them in a vector, or array. Let's assume we now have the equations of all $n$ lines ($n$ is the number of vertices of your polygon).
$$E = f_1, f_2, f_3, f_4 $$
In order to obtain the equation of a line which passes through two points you can use the formula:
$$ y - y_1 = fracy_2 - y_1x_2 - x_1(x-x_1)$$
After that we want to find the equation of the line which passes through the point we are checking if it's inside the polgyon and is parallel to the $x$ axis. Lets assume our point has the coordinates $(1,2)$, in that case its equation would be:
$$y = 2 $$
Finally we want to check how many intersections we have between the lines in the set of $E$ and the line we previously defined. If the number of intersections is odd, then our point is located inside the polgyon, and if it is even, then it's located outside. The logic is simple If the line crosses the lines which belong to $E$ once, that means we were inside the polgyon as the line started inside, so in order for it to leave and go towards infinity it had to only cross the lines which construct the polygon once. Obviously, if it had two intersections or zero it was outside to begin with. I'll leave it to you to see how it would be possible that there are 5 intersections.
IMPORTANT NOTE: Only check for the intersections on the part of the line which actually constructs the polgyon. If you make a class this is easy to implement. With proper implementation it should have complexity $O(n)$ which is really nice. I'll add a picture to illustrate what I meant:
Obviously, point $A$ belongs to the polgyon, and we can see that there is only one intersection. Point $B$ and $C$ don't belong, because there are zero and two intersections, respectively. Try to answer the question what happens when the point is on the edge of the polgyon?
answered Jul 18 at 23:28
user1949350
977
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
add a comment |Â
up vote
0
down vote
Assume you have ordered all of your coordinates in the order you wish to construct your polygon (as the order matters). I will show an example. Let's assume that our polygon has 4 vertices:
$$ V = (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) = V_1,V_2,V_3,V_4$$
First we want to construct lines which pass through $V_1$ and $V_2$, then $V_2$ and $V_3$ and so on 'till we finally get the line which passes through $V_4$ and $V_1$ "closing" our polygon. I would suggest making a class which represents points and lines if you're using an OOP based language and keeping them in a vector, or array. Let's assume we now have the equations of all $n$ lines ($n$ is the number of vertices of your polygon).
$$E = f_1, f_2, f_3, f_4 $$
In order to obtain the equation of a line which passes through two points you can use the formula:
$$ y - y_1 = fracy_2 - y_1x_2 - x_1(x-x_1)$$
After that we want to find the equation of the line which passes through the point we are checking if it's inside the polgyon and is parallel to the $x$ axis. Lets assume our point has the coordinates $(1,2)$, in that case its equation would be:
$$y = 2 $$
Finally we want to check how many intersections we have between the lines in the set of $E$ and the line we previously defined. If the number of intersections is odd, then our point is located inside the polgyon, and if it is even, then it's located outside. The logic is simple If the line crosses the lines which belong to $E$ once, that means we were inside the polgyon as the line started inside, so in order for it to leave and go towards infinity it had to only cross the lines which construct the polygon once. Obviously, if it had two intersections or zero it was outside to begin with. I'll leave it to you to see how it would be possible that there are 5 intersections.
IMPORTANT NOTE: Only check for the intersections on the part of the line which actually constructs the polgyon. If you make a class this is easy to implement. With proper implementation it should have complexity $O(n)$ which is really nice. I'll add a picture to illustrate what I meant:
Obviously, point $A$ belongs to the polgyon, and we can see that there is only one intersection. Point $B$ and $C$ don't belong, because there are zero and two intersections, respectively. Try to answer the question what happens when the point is on the edge of the polgyon?
answered Jul 18 at 23:28
user1949350
977
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Assume you have ordered all of your coordinates in the order you wish to construct your polygon (as the order matters). I will show an example. Let's assume that our polygon has 4 vertices:
$$ V = (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) = V_1,V_2,V_3,V_4$$
First we want to construct lines which pass through $V_1$ and $V_2$, then $V_2$ and $V_3$ and so on 'till we finally get the line which passes through $V_4$ and $V_1$ "closing" our polygon. I would suggest making a class which represents points and lines if you're using an OOP based language and keeping them in a vector, or array. Let's assume we now have the equations of all $n$ lines ($n$ is the number of vertices of your polygon).
$$E = f_1, f_2, f_3, f_4 $$
In order to obtain the equation of a line which passes through two points you can use the formula:
$$ y - y_1 = fracy_2 - y_1x_2 - x_1(x-x_1)$$
After that we want to find the equation of the line which passes through the point we are checking if it's inside the polgyon and is parallel to the $x$ axis. Lets assume our point has the coordinates $(1,2)$, in that case its equation would be:
$$y = 2 $$
Finally we want to check how many intersections we have between the lines in the set of $E$ and the line we previously defined. If the number of intersections is odd, then our point is located inside the polgyon, and if it is even, then it's located outside. The logic is simple If the line crosses the lines which belong to $E$ once, that means we were inside the polgyon as the line started inside, so in order for it to leave and go towards infinity it had to only cross the lines which construct the polygon once. Obviously, if it had two intersections or zero it was outside to begin with. I'll leave it to you to see how it would be possible that there are 5 intersections.
IMPORTANT NOTE: Only check for the intersections on the part of the line which actually constructs the polgyon. If you make a class this is easy to implement. With proper implementation it should have complexity $O(n)$ which is really nice. I'll add a picture to illustrate what I meant:
Obviously, point $A$ belongs to the polgyon, and we can see that there is only one intersection. Point $B$ and $C$ don't belong, because there are zero and two intersections, respectively. Try to answer the question what happens when the point is on the edge of the polgyon?
answered Jul 18 at 23:28
user1949350
977
Assume you have ordered all of your coordinates in the order you wish to construct your polygon (as the order matters). I will show an example. Let's assume that our polygon has 4 vertices:
$$ V = (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) = V_1,V_2,V_3,V_4$$
First we want to construct lines which pass through $V_1$ and $V_2$, then $V_2$ and $V_3$ and so on 'till we finally get the line which passes through $V_4$ and $V_1$ "closing" our polygon. I would suggest making a class which represents points and lines if you're using an OOP based language and keeping them in a vector, or array. Let's assume we now have the equations of all $n$ lines ($n$ is the number of vertices of your polygon).
$$E = f_1, f_2, f_3, f_4 $$
In order to obtain the equation of a line which passes through two points you can use the formula:
$$ y - y_1 = fracy_2 - y_1x_2 - x_1(x-x_1)$$
After that we want to find the equation of the line which passes through the point we are checking if it's inside the polgyon and is parallel to the $x$ axis. Lets assume our point has the coordinates $(1,2)$, in that case its equation would be:
$$y = 2 $$
Finally we want to check how many intersections we have between the lines in the set of $E$ and the line we previously defined. If the number of intersections is odd, then our point is located inside the polgyon, and if it is even, then it's located outside. The logic is simple If the line crosses the lines which belong to $E$ once, that means we were inside the polgyon as the line started inside, so in order for it to leave and go towards infinity it had to only cross the lines which construct the polygon once. Obviously, if it had two intersections or zero it was outside to begin with. I'll leave it to you to see how it would be possible that there are 5 intersections.
IMPORTANT NOTE: Only check for the intersections on the part of the line which actually constructs the polgyon. If you make a class this is easy to implement. With proper implementation it should have complexity $O(n)$ which is really nice. I'll add a picture to illustrate what I meant:
Obviously, point $A$ belongs to the polgyon, and we can see that there is only one intersection. Point $B$ and $C$ don't belong, because there are zero and two intersections, respectively. Try to answer the question what happens when the point is on the edge of the polgyon?
answered Jul 18 at 23:28
user1949350
977
answered Jul 18 at 23:28
user1949350
977
answered Jul 18 at 23:28
user1949350
977
answered Jul 18 at 23:28
user1949350
977
977
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
add a comment |Â
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
@Ethan Allen There is one problem you need to address - what do you do if the test point is on an edge. Moreover the computer algorithms should have some mechanism to take care of these possibilities. For example if $x_1=x_2$ in the above answer.
– herb steinberg
Jul 19 at 16:16
add a comment |Â
This is the Point in Polygon problem. Ray casting is a typical solution algorithm.
– Adrian Keister
Jul 19 at 12:57
1
Possible duplicate of Point in Polygon algorithm - Why does it work?
– Adrian Keister
Jul 19 at 12:57
@amWhy et al. You are being too fussy by putting this question on hold. It was clear enough to me. He has a point and a polygon and wants to determine if the point is inside or outside.
– herb steinberg
Jul 19 at 16:11