CODEWITHSUNDEEP
javajavafxtilediscrete-mathematicsgame-development
65Roadster
65Roadster

Reputation: 260

How to determine if a grid cell is within an enclosed perimeter of cells

I've been working on a game (in JavaFX) where a player draws a path on a playing board and when he closes the path the interior tiles become his controlled area.

I've seen an approach to this for polygons that almost works. I iterate through the tiles to the right of the point in question and count how many times I enter a series of tiles that are part of the perimeter. if it's odd, it's inside (with a count of 1 being a special case).

The problem is points P1 vs P2 in the drawing below. Counting to the right both will have identical counts but one is inside, one is outside the enclosed area. I can't figure out how to define this special case.

Any pointers or thoughts are more than welcome.

enter image description here

Edited in response to the first comment: This example shows how looking above/below and/or left/right for points on both sides to make a determination may not work.

enter image description here

Upvotes: 1

Views: 1654

Answers (1)

Harmlezz
Harmlezz

Reputation: 8068

I do not consider points sitting on a border cell. You have to define if such a point is considered to be inside or outside of the area.

Algorithm:

  1. Determine the smallest rectangle R enclosing the area but sharing no cells with the area.
  2. Mark the point P, for which to determine if it is inside or outside the area, as unvisited.
  3. If there are no cells marked as unvisited, P is inside the area.
  4. Pick an arbitrary cell C marked as unvisited and mark it as visited.
  5. If the cell C is a border cell of R, P is outside the area.
  6. Pick all nighbor cells of C (top, bottom, left, right) which are not marked as unvisited or visited or are a border cell of the area, and mark them as unvisited.
  7. Continue with 3.

Example 1:

Point outside area

In this example the point P is outside the area. This gets detected by step 5. of the algorithm for the cell rendered in green.

Example 2:

Point inside area

In this example the point P is inside the area. This gets detected by step 3. of the algorithm if you would continue with the remaining two unvisited cells.

Example 3:

Point outside area

In this example the point P is outside the area. This gets detected by step 5. of the algorithm for the cells rendered in green.

Upvotes: 1

Related Questions