Pnpoly algorithm on a cross/+ shape c++

Question

I am trying to check if a point is in a cross shape. That looks like this

Example of cross shape

Not sure how to modify the pnpoly to suit this type of shape

bool PointInPolygon(vector<pair<int,int>> points,int x, int y) {
    
    int i, j, nvert = points.size();
    bool c = false;

 for(i = 0, j = nvert- 1; i < nvert; j = i++) {
      
    if( ( (points[i].second >= y) != (points[j].second >= y) ) &&
        (x <= (points[j].first - points[i].first) * (y - points[i].second) / (points[j].second - points[i].second) + points[i].first)
      )
      
      c = !c;
}

Appreciate any help

I remember seeing almost exactly the same question earlier today. I think it became marked and closed as a duplicate and then deleted. So you might want to take some time to search for similarly named questions here already to avoid the same duplication fate. — Some programmer dude, Aug 09 '22 at 13:22
I will also recommend learning about the [mre], which your code is not. For example, what exactly is `points`? Is it a C-array, `std::array`, or `std::vector`? Is is holding a `std::pair`? If so, what are the types being held by the pair? What in the holy heck is `c`? Had you posted a proper snipped of code, these could all be answered by looking at the code. — sweenish, Aug 09 '22 at 13:23
@sweenish The type of `points` is plainly visible in the argument list of the function. — BitTickler, Aug 09 '22 at 13:39
@BitTickler So it is. That's what I get for being in a hurry. — sweenish, Aug 09 '22 at 15:26
Cosmetics: `std::pair` is a bit clumsier in handling than its alternatives, such as e.g. `std::array` or `std::tuple` The latter having nice destructuring capabilities and the former has simple array indexing. Both nicer than ".first" and ".second". — BitTickler, Aug 10 '22 at 02:58
see [How to compare two shapes?](https://stackoverflow.com/a/22166032/2521214) so convert it to polygon represented by relative polar coordinates (turtle graphics) and just check if it is `line, +90deg turn, line, -90deg turn,, line, -90deg turn ...` or the same with reversed turns — Spektre, Aug 10 '22 at 07:04
Are L, K, H, G or A, B, E, F, respectively, guaranteed to be on one line? Or in other words is g=n and k=m? — Sebastian, Aug 10 '22 at 07:06

score 1 · Answer 1 · answered Aug 09 '22 at 15:21

While googling reveals, that the term "scanline" has gotten a new meaning recently, it used to be the name for an algorithm to detect intersections of lines and other geometric shapes.

The algorithms basic idea is to move a vertical "scan line" across the vertices from left to right and to record the vertical boundaries of the shape at that very x-coordinate (where the scanline is currently positioned).

Given you only have horizontal and vertical lines, the implementation of that idea can simply jump from x-coordinate of a vertex to the next, if the vertices are sorted in ascending order on the x-coordinate.

Since multiple points can share the same x-coordinate, all we need to note is, at that very x-coordinate, which are the highest and lowest y coordinates of those vertices, respectively.

Given that 32degree Celsius summertime heat, I was too lazy to create a C++ version of it. Instead, some quick hacking in Common Lisp. But it should be easy enough to read and translate. Instead of defining some kind of point structure, I simply took complex numbers, where your C++ program uses a std::pair<int,int>. realpart/imagpart obtain the real or imaginary part of a complex number, which, here is simply the x and y component of the vertex.

(defparameter *shape* '(#C(3 3) #C(3 6) 
         #C(5 6) #C(5 9)
         #C(6 9) #C(6 6)
         #C(6 3) #C(6 0)
         #C(8 0) #C(8 3)
         #C(11 3) #C(11 6)))

(defun point-in-shape-p (shape point)
  (let ((x-sorted (sort
           shape
           #'(lambda (p1 p2) 
               (< (realpart p1)
              (realpart p2))))))
    (if (< (realpart point)
       (realpart (first x-sorted)))
    nil
    (loop
      with x-pivot = -1000000 ;; outside
      with y-high = -1000000 ;; outside
      with y-low = 100000 ;; outside
      for v in x-sorted
      when (> (realpart v) x-pivot)
        do (progn
         (setf x-pivot (realpart v))
         (setf y-high -1000000)
         (setf y-low 1000000))
      when (> (imagpart v) y-high)
        do (setf y-high (imagpart v))
      when (< (imagpart v) y-low)
        do (setf y-low (imagpart v))
      when (and (<= (realpart point) x-pivot)
            (<= (imagpart point) y-high)
            (>= (imagpart point) y-low))
        return t))))

Here a few test runs, I did for various points and the shape from your image:

CL-USER> (point-in-shape-p *shape* #C(7 8))
NIL
CL-USER> (point-in-shape-p *shape* #C(7 4))
T
CL-USER> (point-in-shape-p *shape* #C(9 2))
NIL
CL-USER> (point-in-shape-p *shape* #C(9 3))
T

No warranties, but I think it is looking good.

Pnpoly algorithm on a cross/+ shape c++

1 Answers1