5
$\begingroup$

I want to insert $n$ points into arbitrary polygon $P$ described by ordered list of its vertexes $v_1, v_2, ..., v_m$. Each inserted point must distanced from the others on distance at least $d$. In case when $n$ it to large to do it, we should be able to detect such situation.

Here is example solution for $n=8$ (green circle diameter is equal to some $d$).

enter image description here

I try to find something about this problem on internet but no luck. So also I try myself to figure out how to do it - my idea was to split polygon into convex parts and put points on each part but there is problem to set proper distance between points in two parts (and putting points into convex part is also not trivial for me). Any idea?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Instead of the polygon $P$, consider the set $P+B$ which is the set of points $p + b$ where $p \in P$ and $b$ is in the disk $B$ radius $R$. This set looks like a fatter version of $P$, but with rounded corners. Your problem then is to pack circles into this set, so search for "circle packing". Except for some special shapes, general solutions are hard to find, but there are numerical approaches possible. $\endgroup$
    – J.J. Green
    Commented Dec 9, 2021 at 13:36
  • 2
    $\begingroup$ @J.J.Green But there can be balls contained in P+B with center outside P $\endgroup$
    – Saúl RM
    Commented Dec 9, 2021 at 20:44
  • $\begingroup$ @SaúlRodríguezMartín : I think you're quite right, a simple example is $P$ the unit square (not its interior) and the ball $B$ radius $R = \sqrt 2 / 2$, then the centre of the square is in $P+B$, the ball radius $R$ centred there is in $P+B$ ... so please ignore the above. $\endgroup$
    – J.J. Green
    Commented Dec 10, 2021 at 10:13
  • 1
    $\begingroup$ Please state the problem more precisely. Your example shows that you probably do not wish to obtain the same number $n$ of interior points as the number of vertices. So you should define $P$ by a tuple $(v_1,v_2,\ldots,v_m)$, where $m,n\in \mathbb{N}$ . Also it is not clear if the problem is to find any arrangement, or if you try to find the maximal number $n$ of interior points separated by distances $\geq d$. One approach is to find a maximal intersection of the hexagonal lattice spanned by $(d, d\,e^{i\,\pi/3})$ in the complex plane with a rotated and translated copy of $P$. $\endgroup$
    – Karl Fabian
    Commented Dec 11, 2021 at 17:09
  • 2
    $\begingroup$ I suggest the centers of the disks should lie on the medial axis of 𝑃, a.k.a. the cut locus. E.g., see this MO question. This could reduce the search to locating those centers on a tree inside 𝑃. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 12, 2021 at 0:13

1 Answer 1

Reset to default
2
$\begingroup$

I don't think there is an easy greedy algorithm for this, circle packing is a hard problem and most results are about simple instances e.g. circle packing in a circle, square, equilateral triangle and it is one of the problems in the book "Unsolved problems in geometry

there is an upperbound on $n$ of $\lfloor{\frac{A + Pd}{\pi d^2}}\rfloor ​+ 1$ where $A, P$ are the area and perimetar of the polygon, which can be proved easily for the case of convex polygons, but that upperbound is not always possible

I suggest to try to use randomized algorithms, I also do think that genetic algorithms can get great results for this problem

Improve this answer
$\endgroup$
2
  • $\begingroup$ Good point - however I'm not sure that this is circle packing problem - because circles can cross Poly borders $\endgroup$
    – Kamil Kiełczewski
    Commented Dec 11, 2021 at 21:34
  • 1
    $\begingroup$ it's, at least for convex polygon because if we extend the walls of the polygon outwards distance d then the answer of the circle backing for this new polygon works for the original problem as well $\endgroup$
    – Noureldin Yosri
    Commented Dec 11, 2021 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .