How to know a point is contained by a not-crossed-polygon ?
Author
Hi all,
I have a list of 2D polygons (not crossed ones).
How to know a 2D point belongs to one of them ?
I have 2 fast ideas :
- Drawing my polygons in a buffer using different colors, and check the color of the coord of the point.
- Test if the point belongs to one triangle of each polygon, but then I am not sure how to get the triangles of a polygon.
Is there a smart way to do this ?
You can quickly determine if a point is inside a polygon in O(V) time, where V is the number of vertices of the polygon; see here for how (Solution 1 is good). Now the obvious thing to do if you have N points and P polygons is to just do a point-in-polygon test for each point and each polygon; this has O(NPV) time complexity.
(I have a suspicion that this can be done more efficiently in a sweepline fashion though...)
And, by "not crossed ones," do you mean that,
1 - The polygons are simple
or
2 - No two polygons intersect
or both?
(I have a suspicion that this can be done more efficiently in a sweepline fashion though...)
And, by "not crossed ones," do you mean that,
1 - The polygons are simple
or
2 - No two polygons intersect
or both?
For the mathematically inclined, I thought of a way to reformulate solution 2 (in the link provided by Emergent above) in terms of complex numbers, using the fact that lifting a path through the logarithm multi-valued function measures the winding number of the path around the origin.
I'm not recommending using this code, but I like how clean it comes out.
I'm not recommending using this code, but I like how clean it comes out.
#include <iostream>#include <complex>#include <vector>typedef std::complex<double> Point;typedef std::vector<Point> Polygon;// I'm not dealing with the case where the point is on the border of // the polygon. If you have a clear idea of what you want the result // to be in that case, add checks. bool is_point_in_polygon(Point const &point, Polygon const &polygon) { unsigned n=polygon.size(); std::complex<double> sum_of_log_ratios = std::log((polygon[0]-point)/(polygon[n-1]-point)); for (unsigned i=1; i<n; ++i) sum_of_log_ratios += std::log((polygon-point)/(polygon[i-1]-point)); // At this point sum_of_log_ratios is 2*PI*w*sqrt(-1), where w is the // winding number of the polygon around the point. return std::abs(sum_of_log_ratios.imag()) > 3.14;}int main() { Polygon polygon; polygon.push_back(Point(1.0,1.0)); polygon.push_back(Point(-1.0,1.0)); polygon.push_back(Point(-1.0,-1.0)); polygon.push_back(Point(1.0,-1.0)); std::cout << is_point_in_polygon(Point(-0.7,0.3), polygon) << '\n';}
Author
Quote:Original post by Emergent
You can quickly determine if a point is inside a polygon in O(V) time, where V is the number of vertices of the polygon; see here for how (Solution 1 is good). Now the obvious thing to do if you have N points and P polygons is to just do a point-in-polygon test for each point and each polygon; this has O(NPV) time complexity.
(I have a suspicion that this can be done more efficiently in a sweepline fashion though...)
And, by "not crossed ones," do you mean that,
1 - The polygons are simple
or
2 - No two polygons intersect
or both?
I mean 1 : Simple polygons. But that's right the polygons that I am dealing with cannot intersect.
Your link seems to be very helpfull.
Thank you.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
