CODEWITHSUNDEEP
javaalgorithm
Akeshwar Jha
Akeshwar Jha

Reputation: 4576

All points inside a convex/concave polygon - better approach?

I need to list down all the coordinates that lie inside of a particular polygon with a given precision of coordinates, say 1. It means, all the coordinates of the polygon-boundary will be integral. The polygon can be convex or concave.

I have all the coordinates of the boundary, coords[n][2]

Here's how I'm approaching the problem:

For simplicity, let's say the first coordinate of the polygon, is [0,0]

for (i = 1;; i++)

    for all points that lie on the lines: y = ±i, x = ±i, 

        check if the point lies inside the polygon.

    if no point lies on the polygon

        break;

My method is pretty much a brute-force one. Is there an efficient algorithm to figure out the same?

Upvotes: 1

Views: 803

Answers (1)

rici
rici

Reputation: 241931

The best approach is probably to use the common strategy of sweeping a scan line over the polygon. Move the scan line vertically from smallest y value to largest y value; at each y value, you can compute a list of intervals of x by computing the intersection of the scan line with the boundary lines which cross that y value. (Since the scan line is horizontal, the intersections are easy to compute.)

Basically, the idea is:

  1. Create an array of active boundary lines. This array is initially empty.

  2. Create an array of boundary line endpoints sorted by y co-ordinate. If there are two endpoints with the same y co-ordinate, sort them by x co-ordinate. Each endpoint appears twice (once for each end of the boundary line); sort the two occurrences according to the other endpoint of the line.

  3. Now sweep the scan line from minimum y to maximum y. At each y value which appears the in the sorted array of endpoints, adjust the list of active boundary lines, either adding or deleting the boundary line from the list. Newly-added lines are inserted in order by x coordinate into the list so that the list is always left to right. That way, each intersection is a transition between inside and outside, so that the list of intersections taken as pairs will be the start and end of a segment of points inside the polygon.

Horizontal boundary lines are a bit annoying, and how they are handled depends on whether you want points precisely on a boundary line to be considered inside or outside the polygon. If the boundary is considered inside, you should be able to just ignore horizontal line segments altogether. But see below.

Although you've said that the polygon boundary is not self-intersecting, you may need to worry about self-intersections resulting from quantisation. If a boundary vertex is very near a boundary line, rounding the all the endpoints to integral values (quantisation) might eliminate the tiny gap, resulting in what looks like a self-intersection. Particularly irritating are nearly-parallel near-horizontal lines:

                   A        B                         C
                   |___________________________________
                            ___________________________
                            |

If these two lines are quantised onto the same y coordinate, you will end up with

                   A        B                         C
                   |  
                   .________._________________________.
                            |

And then, if you ignore the horizontal boundary lines, the segment BC will not be reported as being part of the polygon.

The above algorithm will work equally with convex and concave boundaries, and even with multiple boundaries, but it fails if the boundary self-intersects. To handle self-intersection, you need to use something similar to the Bentley-Ottmann algorithm, which adds line intersections to the list of "events" in the scan line sweep. (At an intersection point, you must reverse the order of the line segments so that the horizontal scan is correct, and you must also compute new intersection points for the reordered segments.) Also, you will want to change the simple even-odd crossing algorithm with a winding number computation, which requires knowing for each segment whether it is clockwise or counter-clockwise. While the Bentley-Ottmann algorithm looks simple in theory, practical implementations need to deal with edge cases, such as multiple lines intersecting at the same point, or even collapsing on top of each other (possibly as a result of quantisation, as above).

Upvotes: 1

Related Questions