How to check if a given point lies inside a rectilinear figure? Given a point (x, y) and a rectilinear polygon (a polygon whose each side is either parallel or perpendicular to coordinate axes) represented by coordinates (x1, y1), (x2, y2) ..... (xn, yn).
We need to write a function which returns true if (x, y) lies inside this rectilinear polygon.

struct Point {
  int x, y;
};

bool IsPointInsideRectilinearPolygon(Point p, const std::vector<Point>& polygon) {
/**  Code  **/
}

I was able to solve this problem if the polygon was a rectangle. But not able to extend it for a general case.
Dividing the given polygon into rectangles and then checking that the point doesn't fall in any of these rectangles is a solution, but I was not able to work out how do we divide this polygon programmatically and get coordinates of the generated rectangles.
Please refer to the image attached.

 A: Pick a point $p_0$ that you know to be outside the polygon.  You could use $p_0=(x_{max}, 2y_{max})$, where $x_{max}$ and $y_{max}$ are the largest $x$ and $y$ coordinates of any vertex.  Draw the line segment between $p_0$ and $(x, y)$ and find the intersections of that line segment with the boundary of your polygon.  If any of those intersections occur exactly at a vertex, choose a new $p_0$.
Once you've found a $p_0$ such that none of the intersections occur at a vertex, count intersections between the line segment from $(x, y)$ to $p_0$ and the boundaries of your polygon.  If that number is odd, $(x, y)$ is inside the polygon.  It it's even, $(x, y)$ is outside the polygon.
This technique also works even if the polygon is not rectilinear.
A: Whether it's a valid polygon could be checked even if not told. [Then program outputs "invalid polygon"] Idea is to check for "invalid crossings", where a vertical and horizontal side from the given points cross each other at a point on or interior to both sides.
Anyway, one can (against what I said in comment) determine which points are linked horizontally and vertically. For each $x_k,$ sort the list of the even number of $y_k$ paired with it from low to high, and pair these off. There must be an even number of such $y_k,$ easily shown. This determines the vertical edges, and in a similr way one can determine the horizontal edges.
If $P=(x,y)$ is the point to be classed as inside or outside, it's easy to check if it's actually on the boundary, then program answers "yes" as you said in comment.
Now imagine the actual sides are black, and that there are grey lines vertical and horizontal through each coordinate of the given points. Pick some convenient $\delta>0$ less than the smallest absolute difference between given coordinates and, if $P$ lies on a grey line, (and not on a black segment) add $\delta$ to one or both coordinates so the new $P$ is not on an edge or a grey line. This new $P$ is inside iff the old $P$ was. Now one needs to count the parity of the number of horizontal sides which lie strictly above $P$ and also for which $x$ lies between the endpoints of said horizontal side. Finally output "inside" if get odd parity, "outside" if even.
Note this method is similar to Robert's answer but addresses some issues OP mentioned in comments. [that in turn is like the way the Jordan curve theorem is proved, in one version.] It doesn't work for non-rectilinear polygons.
