How to find a polygon from a set of nodes?

Question

I have a problem to find a polygon from a set of points that represent the boundary of a figure.

The points are not sorted and I want to make this polygon in order to verify if a generic point is inside or not in this polygon e.g. the point (0,0). Following the points, listed in:

coordinates=np.array(coordinates)

Points

then I did:

polygon = Polygon(coordinates)

and plotting the polygon with:

x,y = polygon.exterior.xy
plt.plot(x,y)

and the figure is this:

Polygon

But I want a polygon which has the outline coinciding with a line connecting all the nodes.

Here I post the array coordinates:

coordinates=[(2.328125, -5.525),
 (2.5, -5.5),
 (1.984375, -5.574999999999999),
 (2.15625, -5.55),
 (1.46875, -5.65),
 (1.640625, -5.625),
 (3.015625, -5.574999999999999),
 (3.1875, -5.6),
 (2.671875, -5.525),
 (2.84375, -5.55),
 (2.5, -5.5),
 (2.671875, -5.525),
 (1.8125, -5.6),
 (1.984375, -5.574999999999999),
 (2.15625, -5.55),
 (2.328125, -5.525),
 (1.640625, -5.625),
 (1.8125, -5.6),
 (1.296875, -5.675000000000001),
 (1.46875, -5.65),
 (2.84375, -5.55),
 (3.015625, -5.574999999999999),
 (3.359375, -5.625),
 (3.53125, -5.65),
 (3.703125, -5.675000000000001),
 (3.875, -5.7),
 (3.1875, -5.6),
 (3.359375, -5.625),
 (4.390625, -5.775),
 (4.5625, -5.800000000000001),
 (3.53125, -5.65),
 (3.703125, -5.675000000000001),
 (3.875, -5.7),
 (4.21875, -5.75),
 (4.21875, -5.75),
 (4.390625, -5.775),
 (4.734375, -5.825000000000001),
 (4.90625, -5.8500000000000005),
 (4.5625, -5.800000000000001),
 (4.734375, -5.825000000000001),
 (4.90625, -5.8500000000000005),
 (5.078125, -5.875),
 (5.078125, -5.875),
 (5.25, -5.9),
 (5.59375, -5.95),
 (5.9375, -6.0),
 (6.453125, -6.074999999999999),
 (6.625, -6.1),
 (5.9375, -6.0),
 (6.109375, -6.025),
 (5.25, -5.9),
 (5.59375, -5.95),
 (6.109375, -6.025),
 (6.28125, -6.05),
 (0.609375, -5.775),
 (0.7812500000000002, -5.75),
 (8.0, -3.825),
 (8.0, -3.61875),
 (8.0, -3.20625),
 (8.0, -3.0),
 (8.0, -3.4125),
 (8.0, -3.20625),
 (7.53125, -2.0625),
 (7.4375, -1.875),
 (7.625, -2.25),
 (7.53125, -2.0625),
 (7.34375, -1.6875),
 (7.25, -1.5),
 (7.4375, -1.875),
 (7.34375, -1.6875),
 (7.25, -1.5),
 (7.15625, -1.3125),
 (6.875, -0.75),
 (6.78125, -0.5625),
 (7.15625, -1.3125),
 (7.0625, -1.125),
 (6.28125, -6.05),
 (6.453125, -6.074999999999999),
 (-0.2500000000000001, -5.9),
 (0.09374999999999993, -5.8500000000000005),
 (8.0, -4.03125),
 (8.0, -3.825),
 (8.0, -3.61875),
 (8.0, -3.4125),
 (8.0, -5.26875),
 (8.0, -5.0625),
 (7.8125, -2.625),
 (7.71875, -2.4375),
 (7.90625, -2.8125),
 (7.8125, -2.625),
 (8.0, -3.0),
 (7.90625, -2.8125),
 (7.71875, -2.4375),
 (7.625, -2.25),
 (6.59375, -0.1875),
 (6.5, 0.0),
 (6.6875, -0.375),
 (6.59375, -0.1875),
 (6.78125, -0.5625),
 (6.6875, -0.375),
 (7.140625, -6.174999999999999),
 (7.3125, -6.199999999999999),
 (6.625, -6.1),
 (6.796875, -6.125),
 (6.796875, -6.125),
 (6.96875, -6.15),
 (0.4375, -5.800000000000001),
 (0.609375, -5.775),
 (0.09374999999999993, -5.8500000000000005),
 (0.4375, -5.800000000000001),
 (0.953125, -5.725),
 (1.125, -5.7),
 (0.7812500000000002, -5.75),
 (0.953125, -5.725),
 (8.0, -5.0625),
 (8.0, -4.85625),
 (8.0, -4.85625),
 (8.0, -4.65),
 (8.0, -4.65),
 (8.0, -4.4437500000000005),
 (8.0, -4.237500000000001),
 (8.0, -4.03125),
 (6.78125, 0.5625),
 (6.875, 0.75),
 (6.5, 0.0),
 (6.59375, 0.1875),
 (6.875, 0.75),
 (6.96875, 0.9375),
 (6.96875, 0.9375),
 (7.0625, 1.125),
 (6.59375, 0.1875),
 (6.6875, 0.375),
 (7.15625, 1.3125),
 (7.25, 1.5),
 (7.0625, 1.125),
 (7.15625, 1.3125),
 (7.0625, -1.125),
 (6.96875, -0.9375),
 (6.96875, -0.9375),
 (6.875, -0.75),
 (-2.3125, -6.199999999999999),
 (-1.96875, -6.15),
 (1.125, -5.7),
 (1.296875, -5.675000000000001),
 (8.0, -4.4437500000000005),
 (8.0, -4.237500000000001),
 (7.25, 1.5),
 (7.34375, 1.6875),
 (6.96875, -6.15),
 (7.140625, -6.174999999999999),
 (-3.0, -5.68125),
 (-3.0, -5.887499999999999),
 (-1.453125, -6.074999999999999),
 (-1.28125, -6.05),
 (-1.796875, -6.125),
 (-1.625, -6.1),
 (-2.484375, -6.225),
 (-2.3125, -6.199999999999999),
 (-3.0, -4.65),
 (-3.0, -4.85625),
 (-1.625, -6.1),
 (-1.453125, -6.074999999999999),
 (-1.109375, -6.025),
 (-0.9375, -6.0),
 (-0.9375, -6.0),
 (-0.765625, -5.975),
 (-0.4218750000000001, -5.925000000000001),
 (-0.2500000000000001, -5.9),
 (-0.765625, -5.975),
 (-0.59375, -5.95),
 (-1.96875, -6.15),
 (-1.796875, -6.125),
 (-3.0, -5.887499999999999),
 (-3.0, -6.09375),
 (-3.0, -5.26875),
 (-3.0, -5.475),
 (-2.65625, -6.25),
 (-2.484375, -6.225),
 (-3.0, -5.0625),
 (-3.0, -5.26875),
 (-3.0, -4.85625),
 (-3.0, -5.0625),
 (-0.59375, -5.95),
 (-0.4218750000000001, -5.925000000000001),
 (-2.876301695089436, -6.282007519285736),
 (-2.65625, -6.25),
 (-3.0, -5.475),
 (-3.0, -5.68125),
 (-3.0, -4.237500000000001),
 (-3.0, -4.4437500000000005),
 (-3.0, -4.4437500000000005),
 (-3.0, -4.65),
 (-3.0, -4.03125),
 (-3.0, -4.237500000000001),
 (7.484375, -6.225),
 (7.65625, -6.25),
 (7.3125, -6.199999999999999),
 (7.484375, -6.225),
 (7.65625, -6.25),
 (7.828125, -6.275),
 (8.0, -5.68125),
 (8.0, -5.475),
 (8.0, -5.475),
 (8.0, -5.26875),
 (7.53125, 2.0625),
 (7.625, 2.25),
 (7.34375, 1.6875),
 (7.4375, 1.875),
 (4.046875, 5.725),
 (3.875, 5.7),
 (4.390625, 5.775),
 (4.21875, 5.75),
 (3.875, 5.7),
 (3.53125, 5.65),
 (3.359375, 5.625),
 (3.1875, 5.6),
 (3.53125, 5.65),
 (3.359375, 5.625),
 (3.015625, 5.574999999999999),
 (2.84375, 5.55),
 (4.21875, 5.75),
 (4.046875, 5.725),
 (4.5625, 5.800000000000001),
 (4.390625, 5.775),
 (-2.4375, -1.875),
 (-2.53125, -2.0625),
 (-2.71875, -2.4375),
 (-2.8125, -2.625),
 (-3.0, -3.4125),
 (-3.0, -3.61875),
 (-2.8125, -2.625),
 (-2.90625, -2.8125),
 (-2.625, -2.25),
 (-2.71875, -2.4375),
 (-3.0, -3.20625),
 (-3.0, -3.4125),
 (-3.0, -3.61875),
 (-3.0, -3.825),
 (-2.90625, -2.8125),
 (-3.0, -3.0),
 (-3.0, -3.0),
 (-3.0, -3.20625),
 (-1.28125, -6.05),
 (-1.109375, -6.025),
 (-3.0, -6.09375),
 (-3.0, -6.3),
 (-3.0, -6.3),
 (-2.876301695089436, -6.282007519285736),
 (-3.0, -3.825),
 (-3.0, -4.03125),
 (8.0, -6.09375),
 (8.0, -5.887499999999999),
 (7.828125, -6.275),
 (8.0, -6.3),
 (8.0, -6.3),
 (8.0, -6.09375),
 (7.4375, 1.875),
 (7.53125, 2.0625),
 (7.71875, 2.4375),
 (7.8125, 2.625),
 (7.625, 2.25),
 (7.71875, 2.4375),
 (8.0, 3.0),
 (8.0, 3.20625),
 (2.84375, 5.55),
 (2.5, 5.5),
 (1.984375, 5.574999999999999),
 (1.8125, 5.6),
 (3.1875, 5.6),
 (3.015625, 5.574999999999999),
 (4.90625, 5.8500000000000005),
 (4.5625, 5.800000000000001),
 (5.25, 5.9),
 (4.90625, 5.8500000000000005),
 (-1.78125, -0.5625),
 (-1.875, -0.75),
 (-1.96875, -0.9375),
 (-2.0625, -1.125),
 (-2.0625, -1.125),
 (-2.25, -1.5),
 (-1.875, -0.75),
 (-1.96875, -0.9375),
 (8.0, -5.887499999999999),
 (8.0, -5.68125),
 (-2.53125, -2.0625),
 (-2.625, -2.25),
 (-2.34375, -1.6875),
 (-2.4375, -1.875),
 (7.90625, 2.8125),
 (8.0, 3.0),
 (7.8125, 2.625),
 (7.90625, 2.8125),
 (8.0, 3.20625),
 (8.0, 3.4125),
 (8.0, 3.4125),
 (8.0, 3.825),
 (2.5, 5.5),
 (2.15625, 5.55),
 (2.15625, 5.55),
 (1.984375, 5.574999999999999),
 (-1.6875, 0.375),
 (-1.59375, 0.1875),
 (-2.25, -1.5),
 (-2.34375, -1.6875),
 (8.0, 4.4437500000000005),
 (8.0, 4.65),
 (8.0, 4.85625),
 (8.0, 5.0625),
 (8.0, 4.65),
 (8.0, 4.85625),
 (8.0, 4.237500000000001),
 (8.0, 4.4437500000000005),
 (8.0, 5.26875),
 (8.0, 5.475),
 (6.453125, 6.074999999999999),
 (6.28125, 6.05),
 (1.8125, 5.6),
 (1.46875, 5.65),
 (1.46875, 5.65),
 (1.125, 5.7),
 (1.125, 5.7),
 (0.7812500000000002, 5.75),
 (-1.59375, 0.1875),
 (-1.5, 0.0),
 (-2.15625, 1.3125),
 (-2.0625, 1.125),
 (-1.96875, 0.9375),
 (-1.875, 0.75),
 (-2.0625, 1.125),
 (-1.96875, 0.9375),
 (-1.875, 0.75),
 (-1.78125, 0.5625),
 (-1.5, 0.0),
 (-1.59375, -0.1875),
 (8.0, 3.825),
 (8.0, 4.03125),
 (8.0, 4.03125),
 (8.0, 4.237500000000001),
 (8.0, 5.0625),
 (8.0, 5.26875),
 (6.625, 6.1),
 (6.453125, 6.074999999999999),
 (6.109375, 6.025),
 (5.9375, 6.0),
 (6.796875, 6.125),
 (6.625, 6.1),
 (5.9375, 6.0),
 (5.59375, 5.95),
 (6.28125, 6.05),
 (6.109375, 6.025),
 (5.421875, 5.925000000000001),
 (5.25, 5.9),
 (5.59375, 5.95),
 (5.421875, 5.925000000000001),
 (6.96875, 6.15),
 (6.796875, 6.125),
 (8.0, 5.68125),
 (8.0, 5.887499999999999),
 (7.140625, 6.174999999999999),
 (6.96875, 6.15),
 (8.0, 5.475),
 (8.0, 5.68125),
 (7.3125, 6.199999999999999),
 (7.140625, 6.174999999999999),
 (7.484375, 6.225),
 (7.3125, 6.199999999999999),
 (7.65625, 6.25),
 (7.484375, 6.225),
 (-1.78125, 0.5625),
 (-1.6875, 0.375),
 (-1.6875, -0.375),
 (-1.78125, -0.5625),
 (-2.25, 1.5),
 (-2.15625, 1.3125),
 (-1.59375, -0.1875),
 (-1.6875, -0.375),
 (0.4374999999999999, 5.800000000000001),
 (0.09374999999999993, 5.8500000000000005),
 (0.7812500000000002, 5.75),
 (0.4374999999999999, 5.800000000000001),
 (-0.07812499999999999, 5.875),
 (-0.2500000000000001, 5.9),
 (0.09374999999999993, 5.8500000000000005),
 (-0.07812499999999999, 5.875),
 (7.828125, 6.275),
 (7.65625, 6.25),
 (8.0, 5.887499999999999),
 (8.0, 6.09375),
 (8.0, 6.09375),
 (8.0, 6.3),
 (8.0, 6.3),
 (7.828125, 6.275),
 (-2.34375, 1.6875),
 (-2.25, 1.5),
 (-2.4375, 1.875),
 (-2.34375, 1.6875),
 (-2.53125, 2.0625),
 (-2.4375, 1.875),
 (-2.625, 2.25),
 (-2.53125, 2.0625),
 (-2.8125, 2.625),
 (-2.71875, 2.4375),
 (-0.2500000000000001, 5.9),
 (-0.59375, 5.95),
 (-0.765625, 5.975),
 (-0.9375, 6.0),
 (-0.59375, 5.95),
 (-0.765625, 5.975),
 (-0.9375, 6.0),
 (-1.28125, 6.05),
 (-1.453125, 6.074999999999999),
 (-1.625, 6.1),
 (-2.71875, 2.4375),
 (-2.625, 2.25),
 (-1.28125, 6.05),
 (-1.453125, 6.074999999999999),
 (-1.796875, 6.125),
 (-1.96875, 6.15),
 (-3.0, 3.825),
 (-3.0, 3.61875),
 (-3.0, 3.20625),
 (-3.0, 3.0),
 (-3.0, 4.03125),
 (-3.0, 3.825),
 (-3.0, 3.61875),
 (-3.0, 3.4125),
 (-3.0, 3.4125),
 (-3.0, 3.20625),
 (-2.90625, 2.8125),
 (-2.8125, 2.625),
 (-3.0, 3.0),
 (-2.90625, 2.8125),
 (-1.625, 6.1),
 (-1.796875, 6.125),
 (-2.140625, 6.174999999999999),
 (-2.3125, 6.199999999999999),
 (-2.484375, 6.225),
 (-2.65625, 6.25),
 (-1.96875, 6.15),
 (-2.140625, 6.174999999999999),
 (-3.0, 6.09375),
 (-3.0, 5.887499999999999),
 (-2.828125, 6.275),
 (-3.0, 6.3),
 (-3.0, 6.3),
 (-3.0, 6.09375),
 (-2.65625, 6.25),
 (-2.828125, 6.275),
 (-3.0, 4.237500000000001),
 (-3.0, 4.03125),
 (-2.3125, 6.199999999999999),
 (-2.484375, 6.225),
 (-3.0, 5.475),
 (-3.0, 5.26875),
 (-3.0, 4.85625),
 (-3.0, 4.65),
 (-3.0, 5.26875),
 (-3.0, 5.0625),
 (-3.0, 5.0625),
 (-3.0, 4.85625),
 (-3.0, 4.65),
 (-3.0, 4.4437500000000005),
 (-3.0, 4.4437500000000005),
 (-3.0, 4.237500000000001),
 (-3.0, 5.887499999999999),
 (-3.0, 5.68125),
 (-3.0, 5.68125),
 (-3.0, 5.475)]

What should be the result if `coordinates = [(0, 0), (1, 0), (0, 1), (-1, 0), (0, -1)]`? — mkrieger1, Dec 13 '20 at 16:04
Looking at the pictures, I would find for each point the two closest points and that would sort them in order of outline. Then for each two consecutive points I would calculate how X and Y changes and the points where it changes drastically is probably a vertex of your polygon — Alexey S. Larionov, Dec 13 '20 at 16:07
Does this answer your question? https://stackoverflow.com/questions/57260352/python-concave-hull-polygon-of-a-set-of-lines — mkrieger1, Dec 13 '20 at 16:09
It seems the terms you need to search for are [*concave hull* or *alpha shape*](https://en.wikipedia.org/wiki/Alpha_shape). — mkrieger1, Dec 13 '20 at 16:09
QHull is the de facto standard for this sort of application: http://www.qhull.org/html/index.htm Here is a python interface: https://pypi.org/project/pyhull/ — Throwback1986, Dec 13 '20 at 16:29
Please, check the following posts. Do they answer your question? [Fitting a closed curve to a set of points](https://stackoverflow.com/q/31464345/7851470). [Boundary enclosing a given set of points](https://stackoverflow.com/q/50549128/7851470). — Georgy, Dec 13 '20 at 17:19

How to find a polygon from a set of nodes?

0 Answers0