Algorithm to find the inner side of a polygon [closed]
Within my CAD-like application I have different kinds of 2D polygons. They can be concave or convex, and they can be drawn clockwise or counter-clockwise.
Now I want to find out where the inner side of such a polygon is, means at its beginning I want to add a a vector which has a 90 degree angle to the following one but which points to the inner side of the polygon.
So: any idea how I can calculate this and find the inner side for this additional vector?
Thanks!
c math vector vector-graphics cad
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
asked Nov 23 '18 at 7:18
Elmi
2,12664087
closed as too broad by chux, Spektre, Brett Hale, Owen Pauling, greg-449 Nov 23 '18 at 10:31
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
Within my CAD-like application I have different kinds of 2D polygons. They can be concave or convex, and they can be drawn clockwise or counter-clockwise.
Now I want to find out where the inner side of such a polygon is, means at its beginning I want to add a a vector which has a 90 degree angle to the following one but which points to the inner side of the polygon.
So: any idea how I can calculate this and find the inner side for this additional vector?
Thanks!
c math vector vector-graphics cad
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
asked Nov 23 '18 at 7:18
Elmi
2,12664087
closed as too broad by chux, Spektre, Brett Hale, Owen Pauling, greg-449 Nov 23 '18 at 10:31
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
3
You can tell if a point is in a polygon or not by shooting a ray from the point in any direction and computing the number of edges the ray intersects. If that's odd, the point is in the polygon.
– Fei Xiang
Nov 23 '18 at 7:21
@FeiXiang this is unfortunately too slow - too much rays are required for this and too much calculations to check for the intersections
– Elmi
Nov 23 '18 at 8:15
@Elmi only one ray is needed for the hit test ... btw do you have an image of what you need to achieve I am still a bit fuzzy on what you consider inner part of polygon? That is whole area so how can you add a vector pointing inside to it??? Did you perhaps want to find which vertex is the first of the concave part of polygon instead?
– Spektre
Nov 23 '18 at 8:41
Compute the polygon area by the shoelace formula. The sign tells you the orientation and the inside will be on the same side of the oriented edges.
– Yves Daoust
Nov 23 '18 at 13:35
add a comment |
Within my CAD-like application I have different kinds of 2D polygons. They can be concave or convex, and they can be drawn clockwise or counter-clockwise.
Now I want to find out where the inner side of such a polygon is, means at its beginning I want to add a a vector which has a 90 degree angle to the following one but which points to the inner side of the polygon.
So: any idea how I can calculate this and find the inner side for this additional vector?
Thanks!
c math vector vector-graphics cad
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
asked Nov 23 '18 at 7:18
Elmi
2,12664087
Within my CAD-like application I have different kinds of 2D polygons. They can be concave or convex, and they can be drawn clockwise or counter-clockwise.
Now I want to find out where the inner side of such a polygon is, means at its beginning I want to add a a vector which has a 90 degree angle to the following one but which points to the inner side of the polygon.
So: any idea how I can calculate this and find the inner side for this additional vector?
Thanks!
c math vector vector-graphics cad
c math vector vector-graphics cad
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
asked Nov 23 '18 at 7:18
Elmi
2,12664087
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
asked Nov 23 '18 at 7:18
Elmi
2,12664087
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
edited Nov 23 '18 at 9:33
Andreas Rejbrand
72.4k6208302
72.4k6208302
asked Nov 23 '18 at 7:18
Elmi
2,12664087
asked Nov 23 '18 at 7:18
Elmi
2,12664087
asked Nov 23 '18 at 7:18
Elmi
2,12664087
2,12664087
closed as too broad by chux, Spektre, Brett Hale, Owen Pauling, greg-449 Nov 23 '18 at 10:31
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as too broad by chux, Spektre, Brett Hale, Owen Pauling, greg-449 Nov 23 '18 at 10:31
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
3
You can tell if a point is in a polygon or not by shooting a ray from the point in any direction and computing the number of edges the ray intersects. If that's odd, the point is in the polygon.
– Fei Xiang
Nov 23 '18 at 7:21
@FeiXiang this is unfortunately too slow - too much rays are required for this and too much calculations to check for the intersections
– Elmi
Nov 23 '18 at 8:15
@Elmi only one ray is needed for the hit test ... btw do you have an image of what you need to achieve I am still a bit fuzzy on what you consider inner part of polygon? That is whole area so how can you add a vector pointing inside to it??? Did you perhaps want to find which vertex is the first of the concave part of polygon instead?
– Spektre
Nov 23 '18 at 8:41
Compute the polygon area by the shoelace formula. The sign tells you the orientation and the inside will be on the same side of the oriented edges.
– Yves Daoust
Nov 23 '18 at 13:35
add a comment |
3
You can tell if a point is in a polygon or not by shooting a ray from the point in any direction and computing the number of edges the ray intersects. If that's odd, the point is in the polygon.
– Fei Xiang
Nov 23 '18 at 7:21
@FeiXiang this is unfortunately too slow - too much rays are required for this and too much calculations to check for the intersections
– Elmi
Nov 23 '18 at 8:15
@Elmi only one ray is needed for the hit test ... btw do you have an image of what you need to achieve I am still a bit fuzzy on what you consider inner part of polygon? That is whole area so how can you add a vector pointing inside to it??? Did you perhaps want to find which vertex is the first of the concave part of polygon instead?
– Spektre
Nov 23 '18 at 8:41
Compute the polygon area by the shoelace formula. The sign tells you the orientation and the inside will be on the same side of the oriented edges.
– Yves Daoust
Nov 23 '18 at 13:35
3
3
You can tell if a point is in a polygon or not by shooting a ray from the point in any direction and computing the number of edges the ray intersects. If that's odd, the point is in the polygon.
– Fei Xiang
Nov 23 '18 at 7:21
You can tell if a point is in a polygon or not by shooting a ray from the point in any direction and computing the number of edges the ray intersects. If that's odd, the point is in the polygon.
– Fei Xiang
Nov 23 '18 at 7:21
@FeiXiang this is unfortunately too slow - too much rays are required for this and too much calculations to check for the intersections
– Elmi
Nov 23 '18 at 8:15
@FeiXiang this is unfortunately too slow - too much rays are required for this and too much calculations to check for the intersections
– Elmi
Nov 23 '18 at 8:15
@Elmi only one ray is needed for the hit test ... btw do you have an image of what you need to achieve I am still a bit fuzzy on what you consider inner part of polygon? That is whole area so how can you add a vector pointing inside to it??? Did you perhaps want to find which vertex is the first of the concave part of polygon instead?
– Spektre
Nov 23 '18 at 8:41
@Elmi only one ray is needed for the hit test ... btw do you have an image of what you need to achieve I am still a bit fuzzy on what you consider inner part of polygon? That is whole area so how can you add a vector pointing inside to it??? Did you perhaps want to find which vertex is the first of the concave part of polygon instead?
– Spektre
Nov 23 '18 at 8:41
Compute the polygon area by the shoelace formula. The sign tells you the orientation and the inside will be on the same side of the oriented edges.
– Yves Daoust
Nov 23 '18 at 13:35
Compute the polygon area by the shoelace formula. The sign tells you the orientation and the inside will be on the same side of the oriented edges.
– Yves Daoust
Nov 23 '18 at 13:35
add a comment |
2 Answers
2
active
oldest
votes
Given the n edge vectors v_1, ..., v_n of the polygon you can find the inner side as follows:
- for i from 1 to n calculate the angle between v_i, v_(i+1) (for i=n use v_n and v_1 instead)
- sum up these angles
If the sum is 2pi/-2pi (or 360/-360 degrees) the inner side lies "to the right/left"
answered Nov 23 '18 at 9:37
randomwalker
2627
1
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
add a comment |
Take a point anywhere, create list of new vectors, each going from that point to your edge vectors, sum the angle each vector of this list makes with the next one (including last with first). Result is 0 if point is outside, 360 (clockwise) or -360 (counterclockwise) if inside.
answered Nov 23 '18 at 8:25
Bastien
4281515
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Given the n edge vectors v_1, ..., v_n of the polygon you can find the inner side as follows:
- for i from 1 to n calculate the angle between v_i, v_(i+1) (for i=n use v_n and v_1 instead)
- sum up these angles
If the sum is 2pi/-2pi (or 360/-360 degrees) the inner side lies "to the right/left"
answered Nov 23 '18 at 9:37
randomwalker
2627
1
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
add a comment |
Given the n edge vectors v_1, ..., v_n of the polygon you can find the inner side as follows:
- for i from 1 to n calculate the angle between v_i, v_(i+1) (for i=n use v_n and v_1 instead)
- sum up these angles
If the sum is 2pi/-2pi (or 360/-360 degrees) the inner side lies "to the right/left"
answered Nov 23 '18 at 9:37
randomwalker
2627
1
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
add a comment |
Given the n edge vectors v_1, ..., v_n of the polygon you can find the inner side as follows:
- for i from 1 to n calculate the angle between v_i, v_(i+1) (for i=n use v_n and v_1 instead)
- sum up these angles
If the sum is 2pi/-2pi (or 360/-360 degrees) the inner side lies "to the right/left"
answered Nov 23 '18 at 9:37
randomwalker
2627
Given the n edge vectors v_1, ..., v_n of the polygon you can find the inner side as follows:
- for i from 1 to n calculate the angle between v_i, v_(i+1) (for i=n use v_n and v_1 instead)
- sum up these angles
If the sum is 2pi/-2pi (or 360/-360 degrees) the inner side lies "to the right/left"
answered Nov 23 '18 at 9:37
randomwalker
2627
edited Nov 23 '18 at 12:09
answered Nov 23 '18 at 9:37
randomwalker
2627
answered Nov 23 '18 at 9:37
randomwalker
2627
answered Nov 23 '18 at 9:37
randomwalker
2627
2627
1
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
add a comment |
1
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
1
1
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
You must also add the angle between v_n and v_1 so you complete the polygon loop.
– Bastien
Nov 23 '18 at 10:28
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
Correct! Thanks for your comment.
– randomwalker
Nov 23 '18 at 12:07
add a comment |
Take a point anywhere, create list of new vectors, each going from that point to your edge vectors, sum the angle each vector of this list makes with the next one (including last with first). Result is 0 if point is outside, 360 (clockwise) or -360 (counterclockwise) if inside.
answered Nov 23 '18 at 8:25
Bastien
4281515
add a comment |
Take a point anywhere, create list of new vectors, each going from that point to your edge vectors, sum the angle each vector of this list makes with the next one (including last with first). Result is 0 if point is outside, 360 (clockwise) or -360 (counterclockwise) if inside.
answered Nov 23 '18 at 8:25
Bastien
4281515
add a comment |
Take a point anywhere, create list of new vectors, each going from that point to your edge vectors, sum the angle each vector of this list makes with the next one (including last with first). Result is 0 if point is outside, 360 (clockwise) or -360 (counterclockwise) if inside.
answered Nov 23 '18 at 8:25
Bastien
4281515
Take a point anywhere, create list of new vectors, each going from that point to your edge vectors, sum the angle each vector of this list makes with the next one (including last with first). Result is 0 if point is outside, 360 (clockwise) or -360 (counterclockwise) if inside.
answered Nov 23 '18 at 8:25
Bastien
4281515
edited Nov 23 '18 at 8:51
answered Nov 23 '18 at 8:25
Bastien
4281515
answered Nov 23 '18 at 8:25
Bastien
4281515
answered Nov 23 '18 at 8:25
Bastien
4281515
4281515
add a comment |
add a comment |
3
You can tell if a point is in a polygon or not by shooting a ray from the point in any direction and computing the number of edges the ray intersects. If that's odd, the point is in the polygon.
– Fei Xiang
Nov 23 '18 at 7:21
@FeiXiang this is unfortunately too slow - too much rays are required for this and too much calculations to check for the intersections
– Elmi
Nov 23 '18 at 8:15
@Elmi only one ray is needed for the hit test ... btw do you have an image of what you need to achieve I am still a bit fuzzy on what you consider inner part of polygon? That is whole area so how can you add a vector pointing inside to it??? Did you perhaps want to find which vertex is the first of the concave part of polygon instead?
– Spektre
Nov 23 '18 at 8:41
Compute the polygon area by the shoelace formula. The sign tells you the orientation and the inside will be on the same side of the oriented edges.
– Yves Daoust
Nov 23 '18 at 13:35