473,836 Members | 2,136 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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;
  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 33767
25 New Member
Hello Sir

I am still not able to get sms frm polygonal geofence. As I told you, I tried to make Shape as a base class and Polygon as derived class. I have created a class called DataProcessor.c c

DataProcessor.c c
Expand|Select|Wrap|Line Numbers
  1. void DataProcessor::run()
  2. {
  3. std::vector<Geofence> geofences= DBCon->getGeofences(deviceID);
  4. /*Geofence is a struct in another file by the name DataObjects.h and geofences is a object of Geofence.I am writing the query in DBCon to get geofences which is also working fine and no errors are there.
  5. */
  6. }
  7. void DataProcessor::checkGeofence()
  8. {
  9. if(geofences.empty())
  10. {
  11. return null;
  12. }
  13. else
  14. {
  15. std::vector<Geofence>::iterator it_GF;
  16. std::vector<Geofence> curGeofences;
  17. std::vector<Shape> shapes;
  18. std::vector<Shape>::iterator shapeIt=shapes.begin();
  19. for (; shapeIt != shapes.end(); shapeIt++) 
  20. {
  21. if (shapeIt->isInside(curPosition.position))
  22. {
  23. curGeofences.push_back(*it_GF);
  24. }
  25. }
  26. }
  27. }
/*Shape is a base class and has the formula to calculate distance between two points. I want to assign the value of "geofences" into "shapes". I think that shapes.begin is always empty.
How should I do it? Please help me out.
Aug 8 '12 #11
9,208 Recognized Expert Moderator Expert
You are not implementing polymorphism correctly.

If your Shapes class is a base class then your ocde using Shapes objects can only use a Shapes* or a Shapes&.

The Shapes class will define the interface and the derived classes will define the implementation.

Your best course here is to write a small test program so see how this all works. Polymorphism in C++ will require that you study up so I woulds look for articles on the web or perhaps get a textbook and actually implement the polymorphism examples to see them working.

Understanding how a virtual function works will be key in your being able to progress with your geofences project.

AS I see it you have a Shape with a derived class called Polygon which itself may have a derived class Pentagon.

Only the Pentagon class knows how to work with Pentagons.

You create a Pentagon and use it indirectly as a Shape:

Expand|Select|Wrap|Line Numbers
  1. Shape* s = new Pentagon;
  2. Myfunction(s);
Inside MyFunction, which has a Shape* argument you code:

Expand|Select|Wrap|Line Numbers
  1. void MyFunction(Shape* arg)
  2. {
  3.    bool result = arg->isInside();
  4. etc....
When you call MyFunction with a Pentagon, arg->isInside() is a call to Pentagon::isIns ide.

This works because Shape::isInside is a virtual function. The Pentago class overrides Shape::isInside with Pentagon::isIns ide. Then when you access a Pentagon object using as Shaoe* you gt the call to Pentagon::isIns ide.

If you use a Pentagon object as a Shape object, this does not work because a Pentagon object only partly a Shape object. Pentagon has more stuff than Shape. You lose the extra stuff in Pentagon when tu treat it as a Shape. You must treat it as a Shape* or Shape&.
Aug 8 '12 #12
25 New Member
Thanks a lot for your comments. I found out the mistake. I have edited my program and now in the process of compilation.
Aug 9 '12 #13
25 New Member
I think I am making mistake in designing the polygon algorithm. This is the algorithm which I have written. Is it correct?
Expand|Select|Wrap|Line Numbers
  1. class Polygon : public Shape {
  2. public:
  4.     Polygon(points_polygon p);
  5.     Polygon();
  6.     Polygon(const Polygon& orig);
  7.     virtual ~Polygon();
  9.     virtual bool isInside(const Point& p);
  11.     std::vector<Point> points;
  12.     int _ID;
  13.     int _userID;
  14.     std::string _deviceID;
  15.     std::string _name;
  16.     Point _polygon;
  17.     int _side;
  19. };

Expand|Select|Wrap|Line Numbers
  1. Polygon::Polygon(points_polygon p)
  2. {
  3.    _name = p.name;
  4.    _ID = p.ID;
  5.    _side = p.side;
  6.    _userID = p.userID;
  7.    _deviceID = p.deviceID;
  8.    _polygon = p.polygon;
  10. }
  12. Polygon::Polygon() {
  13. }
  15. Polygon::Polygon(const Polygon& orig) {
  16. }
  18. Polygon::~Polygon() {
  19. }
  20. // Function to check whether the point is inside or outside the polygon : concept of ray casting algorithm
  21.  bool Polygon::isInside(const Point& p) {
  22.     int i,j,c=0;
  24.     for(i=0,j=this->points.size()-1;i<this->points.size();j=i++)
  25.     {
  26.         if(((this->points[i].longitude > p.longitude) != (this->points[j].longitude > p.longitude))
  27.        &&(p.latitude < (this->points[j].latitude - points[i].latitude) * 
  28.           (p.longitude - this->points[i].longitude) / 
  29.           (this->points[j].longitude - this->points[i].longitude) + this->points[i].latitude))
  30.             c!=c;
  31.     }
  32.     return c;
  33. }
Aug 9 '12 #14
9,208 Recognized Expert Moderator Expert
This code:
Expand|Select|Wrap|Line Numbers
  1. (((this->points[i].longitude > p.longitude) != (this->points[j].longitude > p.longitude))
  2.  &&(p.latitude < (this->points[j].latitude - points[i].latitude) * 
  3. (p.longitude - this->points[i].longitude) / 
  4. (this->points[j].longitude - this->points[i].longitude) + this->points[i].latitude))
  5.  c!=c;
  6. etc...
Is non-readable. Generally, compact code like this means smaller executable programs that run faster. Unfortunuately, the program has to work first.

Break this into sections:

Expand|Select|Wrap|Line Numbers
  1. int A;
  2. int B;
  3. int C;
  4. int D;
  5. int E;
  6.      A = this->points[i].longitude > p.longitude;
  7.      B = this->points[j].longitude > p.longitude;
  8.      C = p.latitude < (this->points[j].latitude - points[i].latitude;
  9.      D = p.longitude - this->points[i].longitude;
  10.      E = this->points[j].longitude - this->points[i].longitude) + this->points[i].latitude;
Using your debugger, verify each of these variables have the correct value.

Change the if statement to use A,B,C,D and E.

I was not able to understand this:

Expand|Select|Wrap|Line Numbers
  1. c!=c;
since that will always be false.

I have no idea if the algorithm is correct. But remember with int calculations there are no fractional parts. 6/100 is zero. So code like X/Y where X is smaller than Y wil always be zero. Just be aware of this.

Also, you have public data members. These should be private. The reason is that should these get screwed up, the functions that did ir are the class member functions whose main job is to guarantee these values are never screwed up. That's a better deal as opposed to having screwed up values and not have anu idea where in the program that happened.
Aug 9 '12 #15
25 New Member
Hello Sir

I did as you told. First made as executable statements and wrote as
((A!=B)&&(C*D/E)); However I found that it does not enter the function at all in the main program DataProcessor.c c(I checked this by giving some statements like hello1, hello2 etc...). Does this mean my algorithm is wrong or there is some problem in calling function in main program? Please help me out.
Aug 13 '12 #16
9,208 Recognized Expert Moderator Expert
Have you set a breakpoint in your function to verify that it is not called? Your algorithm can't be wrong unless it is actually used to produce a result.

Sometimes a comiler omits code that can never be reached:

if (A is true) do this and return.
if (A is not true) do this and return.
Do some other processsing and return.

The Do some other processing will never be reached so wile it may be in your code, the compile will generally drop it from the compiled code.
Aug 14 '12 #17
25 New Member
I just modified the algorithm in Polygon.cc
Expand|Select|Wrap|Line Numbers
  1. bool Polygon::isInside(const Point& p)
  2.  {
  3.     int i,j= this->points.size()-1;
  4.     bool oddnodes=false;
  5.     for(i=0;i<this->points.size();i++)
  6.     {
  7.         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)&&
  8.                 (this->points[i].latitude<=p.latitude|| this->points[j].latitude<=p.latitude))
  9.         {
  10.             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)
  11.             {
  12.                 oddnodes!=oddnodes;
  14.             }
  15.         }
  16.         j=i;
  17.     }
  18.     return oddnodes;
  19. }
However now I get an error "unable to resolve identifier points", though I have declared
std::vector<Poi nt>points;

Why is this hapening now? I never got this error before.
Aug 14 '12 #18
9,208 Recognized Expert Moderator Expert
Does polygon.cc #include polygon.h?
Aug 14 '12 #19
9,065 Recognized Expert Moderator Expert
weaknessforcats is away for a bit and has asked me to look after this thread.

I have tried compiling your code (as given in this thread) and it compiles without the error you are getting which suggests that you may have failed to properly include the header for Polygon or some other file structural issue.

Is this the only error you are getting? If not lets see them all please.

What compiler are you using? Have you set it to produce all possible warnings.

When I compile the above code I get these warnings

Line 7 that it would be best to use parentheses () to make sure the logic of the if statement happens correctly.

Line 12 the statement has no effect

In oddnodes!=oddno des; != is the comparison operator that produces a boolean result, it does not change the value of its parameters. I believe that you where trying to toggle the value of oddnotes that would be oddnodes = !oddnodes;
Aug 14 '12 #20

Sign in to post your reply or Sign up for a free account.

Similar topics

by: paul | last post by:
library for querying virtual polygon over raster spatial data in my c++ application, after calculating my polygon i wish to define it (simple 4 sided polygon with floats or line parameters) and use this to query a b/w image in memory, i want to get the pixel counts, full, hopefully partial, perhaps specific to a side, data to calculate area ect, can someone help point me to a library paul
by: Jaime | last post by:
When I send a graph (polygon) to printer, I receive the next message: Object referente not set to an instante of an object.--- at System.Drawing.SafeNativeMethods.GdipFillPolygonI(HandleRef graphics, HandleRef brush, HandleRef points, Int32 count, Int32 brushMode) at System.Drawing.Graphics.FillPolygon(Brush brush, Point points, FillMode fillMode) at WinAppSeguimiento.frmImpresion.PaintRadar(Graphics& graphToRender, Double paramRadio,...
by: BSOB | last post by:
im gone for a long weekend so plenty of time for anyone to answer. if i have 4 points representing a polygon and each point is represented by an x and a y coordinate, is there an easy (or slightly less painfull) way to decide whether or not a point (a,b) lays within that polygon? please note that this polygon DOES NOT take the shape of a square and has NO right angles and all side lengths are somewhat random. the application: say i...
by: renu | last post by:
Hello, I have drawn polygon on window. And I want to check wheather given point is in that polygon region or not? How shold I find that? I have created object of class region GraphicsPath path = new GraphicsPath(); path.AddPolygon(pts); //////// Some points I have passed Region rgn = new Region(path); RegionData rgnDta = rgn.GetRegionData();
by: jojo41300000 | last post by:
Hi, Is anyone know that how to get the x and y points inside the polygon using C++ program? I have the given polygon data to draw the polygon, but i don't know how to get all the points inside the polygon. Eg. Let's say we have 5 points to draw a polygon. Polygon ---------------------
by: friendkitty | last post by:
Hi All, I m a new member here.I am now writing a program that render Vertex Normals.I m now trying to implement a data structure that will best suit computing vertex normals.For that computation , my data structure should have accessed to the faces adjacent to each vertices. first i read all vertices ,and faces from .m file into a structure.And stored in vectors. vector<Vertex> vertices; vector<Face> faces; Then i render that model.No...
by: AccessIdiot | last post by:
I have a puzzle for all you sql fans. Imagine a polygon with 12 sides (SideA, SideB, SideC, etc) Within this polygon are 96 points (Pt1, Pt2, Pt3, etc). Now let's say I have a table that has the distances from each point to each side Point Side Distance Pt1 SideA 25.6683 Pt1 SideB 37.6778
by: moondaddy | last post by:
I need to be able to make polygons with rounded corners. This will be to draw group outlines around shapes in a diagramming tool in wpf. all angles in the polygon will be 90 degrees, but somehow I wanted to make the corners a bit rounded (otherwise it will look like an old legacy app). Is this possible in wpf? The reason I wanted to use a polygon was because I will bind an adorner to each point so the user can drag the corners around to...
by: Dave Bootsma | last post by:
I have an application where I want to redraw a polygon from points I retrieve from a file. The file is read with streamreader line by line each line contains the points for each polygon. Below is a typical line from my file. 500,748 500,678 552,678 552,696 584,696 584,714 612,714 612,748 Each set of x,y coordinates is separated by a space. How can I read this into my points collection. If I currently try I get
by: JennySmith | last post by:
Hello friend. I want to write a program whether a given point in the plane lies inside, outside, or on the boundary of a polygon. I have found this interesting website which shows 2 ways of doing that. i.e InsidePolygon() and pnpoly() http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/ But these Algo/code don't detect if the input pt is on the boundary of a polygon? Can you guys help me in that part of code/algo? Your help is...
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.