3
$\begingroup$

I have a list of coordinates that define the edges of a polygon and I would like to get a function defining the area Inside out if it (The polygon is convex and the points are in order)

So that for example: List[{0, 2}, {4, 2}, {.5, 0}]

Becomes: Boole[(y < 2 && 7y > 4x-3 && Y > 2-4x)]

I found the Polygon function to accept lists but I don't know how to turn it into a function. I guess there is some easy way to do that as it's a quite common thing but I fail to find it.

$\endgroup$
10
  • 1
    $\begingroup$ The type of example you give will work only for convex polygons. Is that a fair assumption to make in your application? If so, may we also assume the vertices have already been sorted in the order they appear around the polygon's boundary, and that the sorting follows a conventional orientation (such as keeping the interior of the polygon always to the left)? A solution for non-convex polygons can be obtained but would require more work (equivalent to triangulating them). Is it possible you only need some procedure to solve the point-in-polygon problem? $\endgroup$
    – whuber
    Jan 2 '13 at 21:33
  • $\begingroup$ Very related stackoverflow.com/questions/924171/… $\endgroup$ Jan 2 '13 at 21:35
  • 1
    $\begingroup$ @whuber Yes, the polygons are convex and the points are in order $\endgroup$
    – a3f
    Jan 2 '13 at 21:42
  • 1
    $\begingroup$ @whuber Sorry, yes, you are right. I had convinced myself otherwise in a momentary delusion of adequacy. $\endgroup$ Jan 2 '13 at 22:02
  • 2
    $\begingroup$ related mathematica.stackexchange.com/questions/9405/… $\endgroup$
    – george2079
    Jan 2 '13 at 22:13
3
$\begingroup$

When your points are in order then you could probably create a linear function for each point-pair. In this linear equation you replace the Equal by LessEqual to get not the points on the line but all points on the left side too.

The next creates exactly this closed half-plane by using the two-point form of a line

halfplane[{{x0_, y0_}, {x1_, y1_}}] := (y - y0) (x1 - x0) <= (y1 - y0) (x - x0)

What follows is, that you create pairs of your points and for each pair you calculate an in-equation. The region that fulfills all those in-equation should be your polygon. Note, that you have to Append the first point again at the end of your list to create the final, closing line.

createFunc[data_] := 
 And @@ Map[halfplane, Partition[Append[#, First[#]] &@data, 2, 1]]

data = {{0, 2}, {4, 2}, {.5, 0}};

RegionPlot[createFunc[data], {x, -1, 5}, {y, -1, 3}, 
 AspectRatio -> Automatic]

Mathematica graphics

Your function for this is

$$4 (y-2)\leq 0\land -3.5 (y-2)\leq -2 (x-4)\land -0.5 y\leq 2 (x-0.5)$$

which gives True for all points inside your polygon. Compare this to the display of the polygon created by your points

Graphics[Polygon[data], Frame -> True]

Mathematica graphics

$\endgroup$
3
  • $\begingroup$ Your answer is spot on, but strictly speaking, lineeq is an inequality describing a half-plane, rather than the equation of a line. $\endgroup$
    – m_goldberg
    Jan 3 '13 at 5:21
  • $\begingroup$ @m_goldberg Hmm, I wanted to make clear that the half-planes come directly from the two-point form of a line. Now that you say it, I see that my naming is misleading. $\endgroup$
    – halirutan
    Jan 3 '13 at 6:02
  • 1
    $\begingroup$ nice -- suggest you edit to point out the assumptions, polygon must be convex and points must be ordered counter clockwise. $\endgroup$
    – george2079
    Jan 3 '13 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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