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

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

## 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 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 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 on other sites
Quote:
 Original post by EmergentYou 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 simpleor2 - No two polygons intersector both?

I mean 1 : Simple polygons. But that's right the polygons that I am dealing with cannot intersect.

Thank you.

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631787
• Total Posts
3002354
×