CODEWITHSUNDEEP
algorithmcomputational-geometry
galdikas
galdikas

Reputation: 1669

How could I calculate if XY coordinate is within certain area?

So lets imagine that I have a grid of 10x10 (can be any size, but just for the sake of example say 10), and with that grid there is 3 points marking vertexes of a triangle (again can be any amount of points delimiting any arbitrary shape).

So my question is.. Is there a way given just this information to determine programatically if any given coordinate is within that shape?

Lest say the coordinates are 3,2-7,3-5,5. Can I while iterating over the given grid pick out the cells that fall within these points?

Upvotes: 3

Views: 1376

Answers (1)

tlehman
tlehman

Reputation: 5167

Call P the point that you are checking, and S1,S2,...,Sn the n vertices of the shape.

Assume that P ≠ Si for all i.

  1. Is P on the boundary?
  2. If 1 is no, then randomly choose a line L that passes through P
  3. Pick a point F that you know is outside the polygon
  4. Follow the sequence of intersections of L with the shape from F until you hit P (Call the Sequence F, ..., P)
  5. Count the sequence F, ..., P, store the value in M
  6. If M is even, then P is in the polygon, Otherwise P is not in the polygon

NOTE: By introducing the starting point F, we change the parity mentioned in the point in polygon algorithm description on wikipedia

Upvotes: 2

Related Questions