-1

here's a geometric problem that I've been unsuccessful to solve:

  • we have four points A, B, C, D defining an area
  • and two points E, F
  • E is within the boundaries of the polygon ABCD
  • F is outside the borders

We know the (x, y) coordinates of each point.

(see the figure below)

illustration

Determine for any point G (x, y) if G is inside or outside ABCD

Any ideas out there?

Thanks Adrien

adrienlucca.net
  • 677
  • 2
  • 10
  • 26
  • This sounds like math. – nhgrif Nov 06 '13 at 19:33
  • Also, as a hint, the fact that this is not a "concave" shape will be a key to solving this puzzle. – BlackVegetable Nov 06 '13 at 19:33
  • Step one: find a point that's guaranteed to be outside of the poligon –  Nov 06 '13 at 19:34
  • 1
    This question appears to be off-topic because it is about math. – Mihai Maruseac Nov 06 '13 at 19:34
  • 3
    Well, the generalized question is [one of the most popular on this site](http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test). I wouldn't say it's off-topic, it's just computational geometry. – Zong Nov 06 '13 at 19:34
  • @JerryCoffin well no, inside of a rectangle is very easy... – adrienlucca.net Nov 06 '13 at 19:39
  • @adrienlucca.wordpress.com: Axis aligned rectangles, yes. The other question asks about rotated rectangles, and Jerry's answer also provides information for general polygons. – Zeta Nov 06 '13 at 19:40
  • @adrienlucca.wordpress.com: The fact that the points might not form a rectangle doesn't change the validity of (at least some of) the answers given to those. – Jerry Coffin Nov 06 '13 at 19:40
  • @BlackVegetable Okay I think I got a part, I can first trace a rectange with min/max x,y coordinates, then check if G_x is inferior to the min_x value or superior to the max_x, same with G_y and min_y, max_y, then there's only triangles left, so it becomes a problem of "is it inside triangles... Is that it? – adrienlucca.net Nov 06 '13 at 19:55
  • Topic should be changed, "Area" => "Quadrilateral", then it would not be a duplicate since the others are for "polygon" (whatever point number is) and "rectangle". An optimized version for quadrilateral would be interresting and I couldn't find it here. My idea at the moment: it is inside if area of ABCD == area of ABG + area of BCG + area of CDG + area of DAG. Another solution It is inside if G is either in triangle ABC or in triangle ACD. – matthieu Jun 21 '19 at 08:18

1 Answers1

2

For your specific problem (quadrilateral - convex), you can do the following:
1) calculate the equations for the 4 sides
2) calculate the intersection of a vertical line which has G on it with each line
3) if you find an even number of intersections, then it is outside
4) if you find an odd number of intersections, then it is inside
5) be careful at the endpoint intersections
6) be careful if G is on one of the sides

No One in Particular
  • 2,846
  • 4
  • 27
  • 32