vendredi 24 avril 2020

Random x,y coordinate within an irregular polygon given a list of x,y-points, without being on such a corner-point nor edge

I'm trying to tackle the following use-case:

Input: A list of x,y-coordinates that will form an irregular polygon (they are guaranteed valid and lines will not intersect; it can however be concaved). Input-format is irrelevant, so I'm currently using two loose int-arrays for x and y respectively.

Output: A x,y-coordinate within this polygon, which is NOT directly on top of a corner nor edge.

Using the following code, I have been able to tackle the random x,y-coordinate within the polygon:

// Currying Function with two int-arrays as parameters and double-pair return-type
X->Y->{
  // Create a Path2D object
  java.awt.geom.Path2D path = new java.awt.geom.Path2D.Double();
  // Start at the first coordinate given
  path.moveTo(X[0], Y[0]);
  // Loop over the remaining coordinates:
  for(int i=1; i<X.length; i++)
    // And draw lines from corner to corner
    path.lineTo(X[i], Y[i]);
  // After the loop, close the path to finish the polygon
  path.closePath();
  // Create a Rectangle that encapsulates the entire Path2D-polygon
  java.awt.Rectangle rect = s.getBounds();
  // The resulting x,y-coordinate, starting uninitialized
  double x,y;
  // Do-while the Path2D polygon does not contain the random x,y-coordinate:
  do{
    // Select a random x,y-coordinate within the Rectangle
    x = rect.getX() + Math.random()*rect.getWidht();
    y = rect.getY() + Math.random()*rect.getHeight();
  }while(!path.contains(x,y));
  // After which we return this random x,y-coordinate as result:
  return new double[]{x,y};
}

This all works as intended. Now I want to make sure that the random x,y-coordinate is not one of the input x,y-coordinates (this is pretty easily) AND is not on an edge/line of the Path2D. This second part I'm not sure how to tackle, and a quick google search wasn't given any useful information, hence this question.

NOTE: I know the chances that the random point is exactly on top of an edge/corner are astronomical small and could probably be ignored, but this is for a challenge, hence the need to implement it regardless.




Aucun commentaire:

Enregistrer un commentaire