Sign in to follow this  
robosara

How to know a point is contained by a not-crossed-polygon ?

Recommended Posts

robosara    100
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 ?

Share this post


Link to post
Share on other sites
Emergent    982
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?

Share this post


Link to post
Share on other sites
alvaro    21246
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.

#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[i]-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';
}


Share this post


Link to post
Share on other sites
robosara    100
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this