# TikZ Region bounded by points

I have a set of points. I would like to "enclose" the points by a region. Since a picture is worth a thousand words:

The dots are the points I want to enclose. I want the ability to control the enclosure "rate". A parameter that allows me to go from the convex hull of the points to the minimal area(but within a padding). The Yellow region is the convex hull while the red region is a sort of "minimal" region(with padding). I would like to be able to get any region "in between". e.g., 0 would be minimal, 1 would be "maximal"(convex hull) and 1/2 would sort of be an average

The point of this is to "highlight" a group of points(which you can see from the picture that regions do a good job) but I in some cases I'll need to prevent overlap by not using the convex hull(for example, if you combined the points from the blue and red then the convex hull of those points would overlap with the green while the minimal region would not).

This maybe more of a mathematics problem than tikz but maybe someone knows of an easy way to accomplish this. (I am using lualatex and would prefer lua code(or possibly C/C++) since it would surely run faster)

BTW, the point is to make it easy to use. I would like to simply specify the points, the parameter, and the color and that's it else it will become too tedious as there are a lot of regions to deal with.

-
Is this a duplicate of padded boundary of convex hull? –  Peter Grill Apr 16 '12 at 20:54
@PeterGrill It looks like it is. Not sure about the bumerang though. –  percusse Apr 16 '12 at 21:25
@PeterGrill's linked question seems to be appropriate for the convex hull, but the question about minimal paths might get very involving, especially for a lrger number of nodes. I think this is related to the travelling salesman problem where you would drop the longest edge. Even bigger sets might require an iterative approach like ruin and recreate, although I don't know how to implement either or how soon this would exceed TeX's capacity. –  Tom Bombadil Apr 16 '12 at 21:36
This will help: iis.sinica.edu.tw/page/jise/FILE/AcceptedList/100/… (The difference is I have few points and want to find a rather smooth and large concave hull around the line segments connecting adjacent points) –  Uiy Apr 16 '12 at 22:44
Alpha hull is the word you want to look for, see this question on the gis site, gis.stackexchange.com/q/1200/751. Couldn't find any tikz library with a quick google search, but some stat packages and many gis packages are capable of computing such polygons. –  Andy W Apr 16 '12 at 23:11

[en]I'm not sure it meets your problem completely but I think it is a constructive draft

[fr]je ne suis pas sur que cela reponde complètement à ton problème mais je pense que c'est une ébauche constructive

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{backgrounds}

\newdimen\qx
\newdimen\qy
\begin{document}

\begin{tikzpicture}

\foreach \nn/\cood in {1/{0,0},2/{1,2},3/{3,2},4/{4,1}}{
\node [circle,draw,fill=green,label=N\nn](N\nn) at (\cood) {};
}

\foreach \nn [remember=\nn as \lastx (initially 1)] in {2,3,4}{
\begin{scope}[shift={(N\lastx)}]
\pgfextractx\qx{\pgfpointanchor{N\nn}{center}}
\pgfextracty\qy{\pgfpointanchor{N\nn}{center}}
\pgfmathsetmacro{\angle}{atan2(\qx,\qy)}
\begin{scope}[rotate=\angle,on background layer]
\node[circle,minimum width=1cm,](N1a)at(N\lastx){};
\node[circle,minimum width=1cm,](N2a)at(N\nn){};
\coordinate(N1s) at (N1a.{\angle-90});
\coordinate(N1n) at (N1a.{\angle+90});
\coordinate(N2s) at (N2a.{\angle-90});
\coordinate(N2n) at (N2a.{\angle+90});
\draw[fill=pink,draw=pink] (N1s) (N1s) -- (N2s) arc (-90:90:0.5cm)--(N1n) arc (90:270:0.5cm)  ;
\end{scope}
\end{scope}
}

\end{tikzpicture}
\end{document}


-