Evenly spaced polygon dilation [closed]

I would like to calculate a scaled polygon, such that its sides would be evenly distanced from the original polygon ones.

I’ve tried to use scaling, but it looks like I don’t get a perfect result: enter image description here

For rectangles, it works just fine, but with polygons, it seems that the sides are not spaced evenly. Furthermore, the angles don’t look equal.

  • Is this a normal situation with scaling?
  • Is there any better way to achieve my goal?
  • Maybe there’s something wrong with my calculations?

Here are the listings of code which I used:

    public static float[] getBypassPoints(Polygon polygon, float offsetX, float offsetY) {     Rectangle bbox = polygon.getBoundingRectangle();      float width = bbox.getWidth();     float height = bbox.getHeight();     float origScaleX = polygon.getScaleX();     float origScaleY = polygon.getScaleY();     float xScale = ((width + offsetX * 2) / width) * origScaleX;     float yScale = ((height + offsetY * 2) / height) * origScaleY;      setPolygonOrigin(polygon);     polygon.setScale(xScale, yScale);      float[] transformedVertices = polygon.getTransformedVertices();     float[] bypassPoints = transformedVertices.clone();      polygon.setScale(origScaleX, origScaleY);     return bypassPoints; }  public static void setPolygonOrigin(Polygon polygon) {     float[] vertices = polygon.getVertices();     int countOfCoords = vertices.length;      Vector2 centroid = polygonCentroid(             vertices, 0, countOfCoords, new Vector2(polygon.getX(), polygon.getY()));      polygon.setOrigin(centroid.x, centroid.y); } 

    public float[] getTransformedVertices () {     if (!dirty) return worldVertices;     dirty = false;      final float[] localVertices = this.localVertices;     if (worldVertices == null || worldVertices.length != localVertices.length) worldVertices = new float[localVertices.length];      final float[] worldVertices = this.worldVertices;     final float positionX = x;     final float positionY = y;     final float originX = this.originX;     final float originY = this.originY;     final float scaleX = this.scaleX;     final float scaleY = this.scaleY;     final boolean scale = scaleX != 1 || scaleY != 1;     final float rotation = this.rotation;     final float cos = MathUtils.cosDeg(rotation);     final float sin = MathUtils.sinDeg(rotation);      for (int i = 0, n = localVertices.length; i < n; i += 2) {         float x = localVertices[i] - originX;         float y = localVertices[i + 1] - originY;          // scale if needed         if (scale) {             x *= scaleX;             y *= scaleY;         }          // rotate if needed         if (rotation != 0) {             float oldX = x;             x = cos * x - sin * y;             y = sin * oldX + cos * y;         }          worldVertices[i] = positionX + x + originX;         worldVertices[i + 1] = positionY + y + originY;     }     return worldVertices; } 

What are the correct steps in solving polygon monotone triangulation?

I am working out enter image description here step by step and I am stuck on vertex 7. I got that it was a regular vertex and helper(e_i-1) is not a merge vertex so I look for the leftmost edge in the sweep line. My question is, would e6 be considered to the left of it, or is it none? Any already completed examples that I could see would help me understand this greatly.

When computing Monotone Polygon Triangulation, how do I store the formed diagonals in the DCEL?

It’s my understanding that a DCEL have the following structs

public class Vertex{   public Point Coordinate;   public Edge IncidentEdge; }  public class Edge{   public Vertex Origin;   public Edge Twin;   public Face IncidentFace;   public Edge Next;   public Edge Prev; }  public class Face{   public Edge IncidentEdge;   public List<Edge> edges; } 

If I go about determining the diagonals based on the type of vertex I’m at, how would I store the diagonal that was formed. Vertices can only store one incident edge. If I create a diagonal, any given vertex will have an additional incident edge. Do I just ignore this and just fix the half-edge pointers?

Joining points of polygon in correct order

I have a point’s array of some 2d shape(polygon). The polygon could be either crossed or convex, I don’t know it. And I want to join those points in the correct order.

My first thought was to take some point as an origin and start looking for the closest one and so on. But this approach doesn’t work for some crossed polygons, for example: on Image1, it would go from x3 to x5 because it is closer than to x4, but what I really want is to join x1-x2-x3-x4-x5-x6.

After some thinking, I’ve realized that my requirement correct order is very unclear because on Image2 red lines are in the correct order too. So let’s add the requirement that polygon lines shouldn’t at least cross.

I really confused, can someone point me in what direction I should move? Maybe it’s some famous algorithm but I just don’t know how to google it properly. Thanks.

Image1: enter image description here

Image2: enter image description here

Find closest points in a polygon

I have a 2D polygon defined by a list of $ n$ points: $ A$ , $ B$ , $ C$ … These points are sorted in clockwise order. Example:

enter image description here

I would like to find the most performant algorithm to detect all points which are close together (distance < $ x$ ).In the above example, it is $ (H, I)$ and $ (B, F)$ . I could compare each points with all others points and check their distance => complexity $ O(n^2)$ . Is it possible to have a better performance knowning that points are already sorted in clockwise order ?

Convert a polygon mesh into a b-spline surface

$ \textbf{Problem:}$

Getting a $ \textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $ \textit{b-spline}$ surface that exactly looks like the connected polygon mesh. It is obvious that my $ \textit{b-spline}$ surface has to have a degree of one in both directions $ \textit{u}$ and $ \textit{v}$ .

$ \textbf{Output:}$

As an output for my solution. I have to generate a matrix of $ \textit{control point}$ that represent that generated surface.

One property of this matrix is that each elements of each row and column are connected with each others. If our control points matrix is a $ n \times m$ matrix, then let $ C_i$ a column of this matrix with $ C_i = <e_{1i}, e_{2i}, \dots, e_{mi}>$ then there must exist path in the polygon from $ e_{1i}$ to $ e_{mi}$ .

One thing to consider if there is no edge between $ e_{ji}$ to $ e_{(j+1)i}$ , we can construct one as long as this edge lies inside the polygon.

$ \textbf{my trivial idea}$

Assuming that the polygon has $ n$ nodes. I create $ n$ other nodes inside the polygon near each original node. I create then a $ 2 \times n$ matrix. The first row contains all the points constructing the polygon. Second row contains the corresponding additional inserted node. In order to connect two additional inserted nodes, i have to make sure that the line between two nodes is kept inside the polygon.

This idea works only for simple structure and the complexer is the polygon the hard to find these additional points.

Any good solutions maybe ?.

How to create Polygon from Point datatype in MySQL?

I have a table like this:

CREATE TABLE `aois` (   `aois_id` int(11) NOT NULL DEFAULT '0',   `WS_A` point DEFAULT NULL,   `WS_B` point DEFAULT NULL,   `WS_C` point DEFAULT NULL,   `WS_D` point DEFAULT NULL,   `DB_A` point DEFAULT NULL,   `DB_B` point DEFAULT NULL,   `DB_C` point DEFAULT NULL,   `DB_D` point DEFAULT NULL ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci; 

Now i want to create a polygons from the points:

SELECT aois_id, polygon((WS_A, WS_B, WS_C, WS_D, WS_A)) as geom FROM aois; 

But i always get the error message:

Operand should contain 1 column(s) 

(I’m using MySQL Server Version 8.0.16 on Windows 10, if that is of any importance.)

Can anyone point me in the right direction?

Thanks a lot!

How can I determine if two vertices on a polygon are consecutive?

Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices on the polygon. Does anyone know of an algorithm that would do this, as in you would input the array of points and the two vertices as parameters and it would return a boolean?

It’s given that the polygon exists and is unique.

Selecting a polygon within an array of complex polygons

I have an array of polygons which are arrays of points. There are no gaps and none of them overlap like a Voronoi diagram.

Unlike a Voronoi diagram I cannot simply find the nearest centroid to select a polygon, this returns the correct polygon most of the time but sometimes the point lies within a neighboring polygon.

The developer tools in my chrome browser seem to be able to do it with the selection tool but I have no idea how it is doing it.