# Convex Hull in R

I've to draw a polygon which will join the four vertexes on the plot in R. For this I need
minimum value of X which has minimum Y value.

X <- c(-62,  -40,   9,  13,  26,  27,  27)
Y <- c( 7, -14,  10,   9,  -8, -16,  12)
plot(x = X, y = Y)
abline(h = 0, v = 0, lty = 2.5, col = "green", lwd = 2)


I've tough time to find four vertexes

• minimum of X and minimum Y (which is (-40, -14))
• minimum of X and maximum Y (which is (-62, 7))
• maximum of X and minimum Y (which is ( 27, -16))
• maximum of X and maximum Y (which is ( 27, 12))

in R.

-
I think you have a typo related to the min value of X...it should be -62, right? And the max value of Y is 12? – Chase Jun 15 '11 at 4:06
@Chase: I guess I didn't use correct words to phrase my question. If you plot the data then you can see that I'm trying to find the four extreme points (-40, -14), (-62, 7), (27, -16) and (27, 12) in the plots. Sorry for inconvenience. – MYaseen208 Jun 15 '11 at 4:17
what you really want then is called the convex hull, see ?chull. You may also be interested in bounding.box in package spatstat – Chase Jun 15 '11 at 5:08
I might suggest updating the title of your question to include the terms "convex hull" or "border of irregular points" since it has now been clarified. This will help others in the future. – Chase Jun 15 '11 at 5:26

## 2 Answers

I think you want the convex hull of your data. Try this

library(grDevices) # load grDevices package
df <- data.frame(X = c(-62,  -40,   9,  13,  26,  27,  27),
Y = c( 7, -14,  10,   9,  -8, -16,  12)) # store X,Y together
con.hull.pos <- chull(df) # find positions of convex hull
con.hull <- rbind(df[con.hull.pos,],df[con.hull.pos[1],]) # get coordinates for convex hull
plot(Y ~ X, data = df) # plot data
lines(con.hull) # add lines for convex hull


EDIT

If you want to add a line from the origin to each side of the convex hull such that each line is perpendicular to the convex hull, then try this:

getPerpPoints <- function(mat) {
# mat: 2x2 matrix with first row corresponding to first point
#      on the line and second row corresponding to second
#      point on the line
#
# output: two points which define the line going from the side
#         to the origin

# store the inputs more conveniently
x <- mat[,1]
y <- mat[,2]

# define a new matrix to hold the output
out <- matrix(0, nrow = 2, ncol = 2)

#  handle special case of vertical line
if(diff(x) == 0) {
xnew <- x[1]
}
else {
# find point on original line
xnew <- (diff(y) / diff(x)) * x[1] - y[1]
xnew <- xnew / (diff(y) / diff(x) + diff(x) / diff(y))
}
ynew <- -(diff(x) / diff(y)) * xnew

# put new point in second row of matrix
out[2,] <- c(xnew, ynew)

return(out = out)
}


After you've plotted the initial points, as well as the convex hull of the data, run the above code and the following:

for(i in 1:4) {
lines(getPerpPoints(con.hull[i:(i+1),]))
}


Keep in mind that some of the lines going from the origin to each side will not terminate within the interior of the convex hull of the data. Here is what I got as output:

-
@Max: X[minXpos] and Y[minYpos] give (27, -16) which is far away from correct coordinate. – MYaseen208 Jun 15 '11 at 4:02
@MYaseen208: You are right. I answered this question before you edited your post to make it more clear. I thought you were asking for the minimum X value associated with the minimum Y value. I will edit my response soon. – Max Jun 15 '11 at 4:43
@Max: Thanks. Waiting for your reply. – MYaseen208 Jun 15 '11 at 4:45
@MYaseen208: Are you looking for the convex hull of your data? – Max Jun 15 '11 at 4:48
@Max: I guess yes if I understood correctly. But for only four extreme points (four vertexes). – MYaseen208 Jun 15 '11 at 4:51

I'm not 100% sure I'm following what you are trying to do with abline, but maybe this will move you in the right direction. You can use the function which.min() and which.max() to return the minimum or maximum values from a vector. You can combine that with the [ operator to index a second vector with that condition. For example:

X[which.min(Y)]
X[which.max(Y)]


EDIT to address additional details in the question

Instead of indexing the X vector with the min/max value of the Y vector, you can index the Y vector itself...and the X vector for the X vector:

c(X[which.min(X)], Y[which.min(Y)])
c(X[which.min(X)], Y[which.max(Y)])
c(X[which.max(X)], Y[which.min(Y)])
c(X[which.max(X)], Y[which.max(Y)])


EDIT # 2:

You want to find the convex hull of your data. Here's how you go about doing that:

#Make a data.frame out of your vectors
dat <- data.frame(X = X, Y = Y)
#Compute the convex hull. THis returns the index for the X and Y coordinates
c.hull <- chull(dat)
#You need five points to draw four line segments, so we add the fist set of points at the end
c.hull <- c(c.hull, c.hull[1])
#Here's how we get the points back
#Extract the points from the convex hull. Note we are using the row indices again.
dat[c.hull ,]
#Make a pretty plot
with(dat, plot(X,Y))
lines(dat[c.hull ,], col = "pink", lwd = 3)

###Note if you wanted the bounding box
library(spatstat)
box <- bounding.box.xy(dat)
plot(box, add = TRUE, lwd = 3)

#Retrieve bounding box points
with(box, expand.grid(xrange, yrange))


And as promised, your pretty plot:

-
@Chase: X[which.min(Y)] gives (27, 6) which is far away from the correct coordinate. – MYaseen208 Jun 15 '11 at 4:01
@Myaseen208 - now that you've updated your question, it is clear that what I supplied is now what you are after. What the previous answer supplies is the X value that corresponds to the minimum value of Y. For example, the minimum value of Y is -16, which corresponds to the 6th position of that vector. The code above returns the X value in the 6th position of the vector, and is equivalent to X[6]. I'll update my answer to address your real question now that it is clarified. The same basic concepts will be in play... – Chase Jun 15 '11 at 4:05
@Chase: Thanks, I'm looking forward for to your answer. – MYaseen208 Jun 15 '11 at 4:08
@Chase: Thanks for your reply. Is this possible to draw perpendiculars from origin to every side of the polygon? – MYaseen208 Jun 15 '11 at 6:19
@MYa i sure. where should they intersect the polygon, i assume midpoint? – Chase Jun 15 '11 at 11:05