enter image description here

How to judge whether a rectangle in the figure is inside the given point cloud? For example, in this figure, the red rectangle is outside the point cloud and the green rectangle is outside the point cloud.

  • 2
    $\begingroup$ could you include what you mean by point cloud. $\endgroup$ – sashas Aug 25 '16 at 16:05
  • 1
    $\begingroup$ It would be nice to define how do you store those points, why standard point-in-polygon is not good enough, how do you plan to use it (one cloud and multiple rectangles or low number of rectangles per cloud), are rectangles on integer grid while cloud is on floating-points? Are your clouds simply fonts / Bézier curves? I assume that the cloud is stored in such way that you can tell apart in and out of cloud, right? $\endgroup$ – Evil Aug 25 '16 at 17:00
  • 1
    $\begingroup$ Welcome to CS.SE! I'm having a hard time understanding what you're trying to ask. In addition to the other comments... How is your point cloud represented? How does that relate to the picture in the question? Do you mean you have a set of points that are along the outline of some shape? Are they in consecutive order along the path a stroke would take? What approaches have you considered and rejected? Where are you stuck? I encourage you to edit the question to address the feedback you've been given. $\endgroup$ – D.W. Aug 25 '16 at 20:40

The point cloud can define a polygon. After you define a polygon you can use the point inside polygon test on the four corners of the rectangle and see if all the points are inside the polygon.

The point in polygon test.

| cite | improve this answer | |
  • $\begingroup$ The generic PIP test takes edges not points to perform test, on simple polygon (which might not be the case), what then? $\endgroup$ – Evil Aug 26 '16 at 0:16
  • $\begingroup$ Go in a clock wise order around the points and convert each successive two points to an edge $\endgroup$ – Amitay Nachmani Aug 26 '16 at 3:49
  • $\begingroup$ If it was in the clockwise direction, if it was simple polygon. If it looks like this plot which edges are inside? $\endgroup$ – Evil Aug 26 '16 at 4:33
  • $\begingroup$ For this kind of cloud points i would find the convex hull of all the points and use the convex hull as the polygon. $\endgroup$ – Amitay Nachmani Aug 26 '16 at 4:48
  • $\begingroup$ The point is, that it is unknown from the picture what constitutes the polygon, and if convex hull was the answer why bother with so many points? And it is not clear yet ehat the question was about. So your answer to use PIP test is valid only under certain conditions. $\endgroup$ – Evil Aug 26 '16 at 5:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.