473,889 Members | 1,656 Online

# Point in polygon

25 New Member
I am trying to find out whether a point is inside a polygon.I am using vector std c++.

My program till now:
Expand|Select|Wrap|Line Numbers
1. Polygon.h
2. class Polygon {
3. public:
4. Polygon();
5. virtual ~Polygon();
6. virtual bool Inside(Point p);
7. private:
8. std::vector<Point> pts;
9.
10. Polygon.cc
11. Polygon::Polygon()
12. {
13. }
14. Polygon::~Polygon()
15. {
16. }
17. bool Polygon Inside(Point p)
18. {
19. int nvert=pts.size;
20. }
--------
I liked the ray casting algorithm but I dont know how to do in C++. Could anyone help out?
Jul 17 '12
28 33771
gayathri81
25 New Member
Yes. It is also included. But I have found out where the mistake is. Thanks a lot.
Aug 14 '12 #21
gayathri81
25 New Member
I also found that I have to convert into degrees because of latitude and logitude. So I used this:
Expand|Select|Wrap|Line Numbers
1.  double Dataprocessor::calculateDistance(const Point& a, const Point& b)
2. {
3.     double lat = (a.latitude + b.latitude) / 2 * 0.01745;
4.     double dLat = 111.3 * cos(lat) * (a.longitude -b.longitude);
5.     double dLng = 111.3 * (a.latitude - b.latitude);
6.
7.     return sqrt(pow(dLat, 2) + pow(dLng, 2));
8. }
Now I want to find out whether a point is inside the polygon or not. So I used the above function and the polygon.cc and wrote:
Expand|Select|Wrap|Line Numbers
1. if(calculateDistance(position,.....))
2. {
3. // push back to geofence
4. }
In the above part, position is the position of test point and the other parameter would be the vertices of polygon. But it is not clear what should be written there? I want to compare the latitude and longitude of test point with each of the vertices of polygon using the ray casting algorithm.

I wrote points but showed me an error , failing to recognise it. What should be written?
Aug 14 '12 #22
Banfa
9,065 Recognized Expert Moderator Expert
points is a vector of Point, but calculateDistan ce is expecting a reference to a single Point.

You need to iterate through your vector of points and individually call the function for each one

Expand|Select|Wrap|Line Numbers
1. for(std::vector<Point>::iterator iter = points.begin(); iter != points.end(); iter++)
2. {
3.   double distance = calculateDistance(position, *iter);
4.
5.   // Do something with distance
6. }
7.
Aug 15 '12 #23
gayathri81
25 New Member
Hello
I perfectly agree with you. I have done what you have told. Now I want to call the polygon algorithm. I tried this out but did not work.
Expand|Select|Wrap|Line Numbers
1. if(isInside(curPosition.position))
2. {
3. //push geofences inside.
4. }
5. // Function to check whether the point is inside or outside the
6. //polygon : concept of ray casting algorithm
7. bool DataProcessor::isInside(Point& p)
8.  {
9.
10.     int i,j= this->points.size()-1;
11.     bool oddnodes=false;
12.     for(i=0;i<this->points.size();i++)
13.     {
14.         if((this->points[i].longitude < p.longitude && this->points[j].longitude >= p.longitude || this->points[j].longitude< p.longitude && this->points[i].longitude >= p.longitude)&&
15.                 (this->points[i].latitude <= p.latitude|| this->points[j].latitude <= p.latitude))
16.         {
17.             if(this->points[i].latitude + (p.longitude-this->points[i].longitude) / (this->points[j].longitude-this->points[i].longitude) * (this->points[j].latitude-this->points[i].latitude) < p.latitude)
18.             {
19.                 oddnodes!=oddnodes;
20.
21.             }
22.         }
23.         j=i;
24.     }
25.        return oddnodes;
26. }
//All the code is in DataProcessor.c c.
//curPosition.pos ition is the current position of GPS device.

Where am I going wrong? There are no syntax errors. But I am no getting sms.
Aug 16 '12 #24
Banfa
9,065 Recognized Expert Moderator Expert
As I already pointed out in post #20 you have some errors that are causing your code to go wrong, for example `oddnodes!=oddno des;` does nothing.
Aug 16 '12 #25
gayathri81
25 New Member
Hallo

Yes you are right. This statement always returns me 0 even if the point is outside or inside. Or how should I modify the code above to get even for outside and odd for inside ( ray casting method)? Please help me out.
Aug 16 '12 #26
Banfa
9,065 Recognized Expert Moderator Expert
As I already said I gave the solution to this in post #20
Aug 16 '12 #27
gayathri81
25 New Member
Hello

Thank you for the solution. But I could not understand this :
double distance = calculateDistan ce(position, *iter);

I am a starter with vector in C++ and I am trying to develop myself.
Aug 17 '12 #28
Banfa
9,065 Recognized Expert Moderator Expert
This is just a call to a function
Expand|Select|Wrap|Line Numbers
1. double distance = calculateDistance(position, *iter);
double distance = - we are declaring a variable to hold the result called distance and we will initialise it with something.

calculateDistan ce(position, *iter); the thing we are going to initialise it, the return value of the function calculateDistan ce, 2 parameters are being passed to this function, position (which came from your own post) and *iter. Sinceiter is an iterator into your vector by dereferencing iter (*iter) we get the value that the iterator is currently pointing at.

When using a standard container, such as std::vector iterators are used to address each entry in the container in turn, a little like using a pointer you access members of an array. Iterators can be incremented to access the next member and there are a variety of stand-library methods which can help, for example std::distance the distance between 2 iterators into the same container. All containers have methods begin and end to get the iterator to the first entry and the iterator just after the last entry and rbegin and rend which gets elements in reverse order.

Look at this example (run and compile and understand)

Expand|Select|Wrap|Line Numbers
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4.
5.
6. int main()
7. {
8.     // Declare my vector
9.     std::vector<int> numbers;
10.
11.     // Populate it
12.     for(int ix = 0; ix < 10; ix++)
13.     {
14.         numbers.push_back(ix);
15.     }
16.
17.     // Iterate through the vector and print out its values
18.     for(std::vector<int>::iterator iter = numbers.begin(); iter != numbers.end(); iter++)
19.     {
20.         std::cout << "Forward Iterate: " << *iter << std:: endl;
21.     }
22.
23.     // Iterate in reverse order through the vector and print out its values
24.     for(std::vector<int>::reverse_iterator riter = numbers.rbegin(); riter != numbers.rend(); riter++)
25.     {
26.         std::cout << "Reverse Iterate: " << *riter << std:: endl;
27.     }
28.
29.     // Check size
30.     std::cout << "Count: " << numbers.size() << " = " << std::distance(numbers.begin(), numbers.end()) << std::endl;
31.
32.     return 0;
33. }
34.
Aug 17 '12 #29