I'm looking for method for determining if location given by longitude and latitude (on WGS84 reference spheroid) is inside or outside of an arbitrary polygon. My polygons will have the span of a few hundreds of kilometres, and the number of vertices of the polygon should be < 100. The acceptable error is around 10-20 meters, but could be larger, if that might reduce the complexity of the algorithm or improve computational power requirements.
So far I found a method described here: https://gis.stackexchange.com/questions/147629/testing-if-a-geodesic-polygon-contains-a-point-c
I'm afraid that having to recompute the gnomonic projection of the polygon with the point in question being the centre might be too time consuming for my application (there will be many polygons to consider). As I understand, another limitation is that the point and polygon must be on the same hemisphere for this to work, and this is something that does not fit into my application.
I have another idea how the task could be solved, but I'm not sure if it is correct.
Instead of using the gnomonic projection I'm thinking about converting the polygon onto the UTM or MGRS coordinates (only once, so that would not be repeated), and then, when I need to verify if a point is inside, I will convert its location UTM/MGRS coordinates and work on that cooridnate system. The insidness then will be solved using raycasting algorithm. Will that method work accurately (or at all)?
Thanks and regards,
BG
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Don't give in to your fear (that the method you refer to will be too time consuming). Try it! Maybe it's not as slow as you think.
If you have a few polygons and for each polygon you need to test many points, then you can speed things up by changing the method to use some suitable "central" point for each polygon as the center of the gnomonic project (instead of the test point). Then you can transform each polygon just once and the test for each point is merely (a) transform the test point (b) apply the 2d "inside polygon" test.
If your polygons span a few hundred km, they will comfortably fit in a hemisphere. If your test point lies outside the hemisphere, then the gnomonic projection returns NANs and you will then know that the point is outside the polygon.
Attempting to use UTM or MGRS will be very inflexible since you'll have to deal with the UTM zones all over the place.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I'm looking for method for determining if location given by longitude and latitude (on WGS84 reference spheroid) is inside or outside of an arbitrary polygon. My polygons will have the span of a few hundreds of kilometres, and the number of vertices of the polygon should be < 100. The acceptable error is around 10-20 meters, but could be larger, if that might reduce the complexity of the algorithm or improve computational power requirements.
So far I found a method described here: https://gis.stackexchange.com/questions/147629/testing-if-a-geodesic-polygon-contains-a-point-c
I'm afraid that having to recompute the gnomonic projection of the polygon with the point in question being the centre might be too time consuming for my application (there will be many polygons to consider). As I understand, another limitation is that the point and polygon must be on the same hemisphere for this to work, and this is something that does not fit into my application.
I have another idea how the task could be solved, but I'm not sure if it is correct.
Instead of using the gnomonic projection I'm thinking about converting the polygon onto the UTM or MGRS coordinates (only once, so that would not be repeated), and then, when I need to verify if a point is inside, I will convert its location UTM/MGRS coordinates and work on that cooridnate system. The insidness then will be solved using raycasting algorithm. Will that method work accurately (or at all)?
Thanks and regards,
BG
Don't give in to your fear (that the method you refer to will be too time consuming). Try it! Maybe it's not as slow as you think.
If you have a few polygons and for each polygon you need to test many points, then you can speed things up by changing the method to use some suitable "central" point for each polygon as the center of the gnomonic project (instead of the test point). Then you can transform each polygon just once and the test for each point is merely (a) transform the test point (b) apply the 2d "inside polygon" test.
If your polygons span a few hundred km, they will comfortably fit in a hemisphere. If your test point lies outside the hemisphere, then the gnomonic projection returns NANs and you will then know that the point is outside the polygon.
Attempting to use UTM or MGRS will be very inflexible since you'll have to deal with the UTM zones all over the place.