1

I am given a set of grid points (defined by their x and y coordinates) that make up an arbitrary quadrilateral. I want to be able to find which of these points are the corner points. I have been looking at minimum bounding problems, however in my case, 4 of the points already in this set of grid points are the corner points. An example of the points I would have are shown in blue below, however there are cases where it's not as simple as just picking the point most to the left, right, top or bottom, and this is where I get stuck. For example, if I decreased the y-coordinate of the point farthest on the right to be less than the y-coordinate of the point currently on the bottom, you would not be able to classify the current bottom point. I am not sure how to approach this and any help would be greatly appreciated.

EDIT: There is no restriction on the quadrilateral to be a parallelogram, concave, convex and can contain diagonals of angles other than 45º.

The matrix is ​​filled and in case there is any possibility of more than one solution, it should return any one of them.

enter image description here

UXK
  • 405
  • 3
  • 12
Jehan Dastoor
  • 647
  • 1
  • 8
  • 15
  • are points only on the grid? Are rectangle corners guaranteed to be in the points? – Marat Mar 23 '22 at 04:09
  • the corners are guaranteed to be in the array of points, and points are only on the grid yes – Jehan Dastoor Mar 23 '22 at 04:19
  • if you allow concave polygons, the solution is not unique (that these are "the real problem" is new to me). –  Mar 23 '22 at 21:49

1 Answers1

0

If I well understand want you want to do, it is unfeasible. In the following example, you have the set of grid points [(0,0), (2,1), (2,2), (3,1), (4,1)] but you have at least 2 quadrilaterals that could be generated from this set: ABCD and ABCE.

enter image description here

Jonathan Dauwe
  • 317
  • 2
  • 6