CODEWITHSUNDEEP
algorithm
OneNeptune
OneNeptune

Reputation: 903

Find enclosed points of 2D polygon

I am building a game where the player moves 1 point a time, and leaves a path behind them. They can not cross their own path, and when the path is completed, I need to capture all enclosed points. I don't have a ton of math experience to identify what algorithms I need to look at, but I imagine I need to break the shape in to sub-rectangles, and then find the contained points in each sub-rectangle.

I was pointed towards the convex hull algorithm, and after looking at it for some time, it seems it just finds the convex perimeter of a given group of points. So that won't work.

I haven't found any algorithms for solving any problem, so if I'm looking for direction on algorithms to explore or perhaps one that could solve the problem directly.

As the player can only move up / down / left / right and no diagonals, all vertices of the polygon(?) will always be right angles.

Example Plane:

   0   1   2   3   4
0 [x] [x] [x] [ ] [ ]

1 [x] [o] [x] [ ] [ ]

2 [x] [o] [x] [x] [x]

3 [x] [o] [o] [o] [x]

4 [x] [x] [x] [x] [x]

Stored Points: (marked as 'x' on example plane)

[
  [0,0],
  [0,1],
  [0,2],
  [1,2],
  [2,2],
  [2,3],
  [2,4],
  [3,4],
  [4,4],
  [4,3],
  [4,2],
  [4,1],
  [4,0],
  [3,0],
  [2,0],
  [1,0]
]

Objective Points: (marked as 'o' on example plane)

[
  [1,1],
  [2,1],
  [3,1],
  [3,2],
  [3,3],
]

Other example planes:

   0   1   2   3   4
0 [ ] [x] [x] [x] [ ]

1 [ ] [x] [o] [x] [ ]

2 [x] [x] [o] [x] [x]

3 [x] [o] [o] [o] [x]

4 [x] [x] [x] [x] [x]


   0   1   2   3   4
0 [x] [x] [x] [ ] [ ]

1 [x] [o] [x] [ ] [ ]

2 [x] [x] [x] [x] [x]

3 [ ] [x] [o] [o] [x]

4 [ ] [x] [x] [x] [x]

Upvotes: 0

Views: 385

Answers (1)

user949300
user949300

Reputation: 15729

I suggest the Even-Odd ray casting algorithm.

  1. First determine the highest and lowest X & Y in the user's points.
  2. For each Y, start scanning from minimumX-1 to maximumX+1.
  3. Count how many times you encounter a user point.

Note: this has some issues if the user draws horizontal lines, read the lit for more info.

Upvotes: 1

Related Questions