Sign in to follow this  

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

This topic is 2835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
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
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
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

This topic is 2835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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