• Advertisement
Sign in to follow this  

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

This topic is 2903 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
Advertisement
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-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
Sign in to follow this  

  • Advertisement