Member Avatar for Jeff-Bennett

I'm looking for a way to get the coordinates of a polygon offset x pixels within a known polygon. This seems to be a non-trivial problem, but I thought of a trick - What if I have the original polygon drawn by Windows with a thick line, the inside edges of that thick line will describe a new polygon. Does anyone know a way to get the coordinates of the inside edges of this thickly drawn polygon ? 

    - Jeff
  • 5 Contributors
  • 7 Replies
  • 529 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Stagnant

Dani AI

Generated

The operation you want is a geometric inset (polygon offset / erosion), not a uniform scale or midpoint trick. Scaling about a centroid (as suggested by and ) moves vertices radially and does not produce a constant perpendicular offset from every edge. The “thick-pen” idea in ’s picture can sometimes be used for visualization (GDI+/Direct2D can produce a widened path), but extracting a clean, ordered inner contour from a stroked render is fragile compared with computing the offset precisely.

Practical algorithm (robust enough to implement in VB.NET):

  • Compute polygon orientation (signed area) so the inward normal is chosen consistently.
  • For each edge compute the unit normal and shift (offset) the edge by distance d along that normal.
  • Intersect each pair of consecutive offset lines to produce the inset vertex.
  • Handle special cases: parallel adjacent edges, extremely sharp/flat angles, and concave vertices (offset lines can diverge or create spurs).

A compact VB.NET outline for the math (compute signed area, unit normal, and line intersection):

' Signed area -> orientation
Function SignedArea(pts As List(Of PointF)) As Single
  Dim a As Single = 0
  For i = 0 To pts.Count - 1
    Dim j = (i + 1) Mod pts.Count
    a += pts(i).X * pts(j).Y - pts(j).X * pts(i).Y
  Next
  Return a / 2.0F
End Function

' Line intersection of (x1,y1)-(x2,y2) with (x3,y3)-(x4,y4)
Function LineIntersection(...) As PointF?
  ' standard determinant formula; return Nothing if denom near zero
End Function

If reliability and edge cases matter, use a tested library instead of hand-rolling the whole cleanup. For .NET/VB the Clipper library (ClipperOffset) performs inset/outset with join options (miter/round/square) and handles self-intersections and small-feature collapse — supply paths as scaled integers, call Execute with a negative delta to inset, then unscale results.

Cautions and tips: ensure polygon orientation is correct before choosing the sign of the offset; choose a round or bevel join when miters would be excessively long; test with features smaller than the offset (those may disappear); visualize intermediate offset lines to debug problems. This approach directly answers the goal you showed in ’s image and avoids the inaccuracies of naive scaling or midpoint methods discussed earlier.

Recommended Answers

All 7 Replies

Member Avatar for Stagnant

I didn't know there's an inside and an outside edge. Assuming I comprehended your question correctly... This is a geometry related topic, whereas such imaginary laws (postulates and theorems) apply. Anyways enough rambling...

Suppose the polygon is a square. Given its borders are thick enough to produce a polygon-within-a-polygon illusion.

  • thickness of a line = th
  • length = x
  • width = x
  • Assuming this is a 2D square, and we're talking about enclosure of pixels, finding the Area of the square is necessary, as respresented as A.

Now the trick is to include from the outermost edges of the borders to retrieve the Area of the outside square. And the formula as follows A = (x + th)^2

What do you think the formula for the innermost polygon should be?

Edited by Stagnant because: Text formatting and neatness.
Member Avatar for ddanbe

Do you talk about regular-irregular polygons?
Do you have some origin and radius?
Please elaborate.

Member Avatar for AssertNull

Please elaborate.

Yes. More info is needed. I was thinking about this one and it's clear that Stagnant and I already interpreted this problem differently as far as how the "thick line" would be drawn. Regardless, I concur that this is a Geometry problem, not a problem of Windows drawing a line and doing the Geometry for you. I'm all for using someone else figuring out the Geometry for me and simply calling their function, but I'm wondering if the time you take investigating how that line is drawn and grabbing the points and making sure it matches your needs would take longer than simply working the Geometry yourself. I believe Stagnant was drawing the thick line so that the original square edges are in the MIDDLE of that thick line. I was going to draw that line so that no part of my thick pen ever strayed outside of the original square. One can also define "x pixels within a known polygon" is also vague and needs to be defined. That could refer to x pixels from the edge or x pixels from the vertex. Calculating it from the vertex might be easier, I think, but x would no longer be the thickness of the brush/pen and could be microscopically thin with very small interior angles. So the first thing to do is define exactly what you want.

It's times like these when I wish I knew how to use PowerPoint, Visio, Dia, etc., or actually knew how to draw. It's 2016 and I'm still paper/penciling things and scanning them in as a JPEG with a scanner, which is on the fritz, so I have no diagrams to post. Hopefully the words get the point across, but things are so much easier with drawings.

Member Avatar for rproffitt

You tagged this with THREE languages. I have to lead with you know how to use the 3 shells (Demolition Man.)

So while that's a little misleading not one of those languages directly treats a polygon as an object so you have to step back and think about how you would do this as a Human. Now that you can do that on your own, you "port" from Human (some call that Psuedocode) to code in the computer language of your choice.

Member Avatar for Jeff-Bennett

. PolygonOffsetProblem.jpg

I have tried to look into this from Geometry standpoint - the concept is called "Erosion of a polygon" and is not as simple as one would think. This is why I was trying to use the trick of having Windows draw the polygon with thick line and then trying to get the coordinates of vertices of the inner edges of the thickly drawn polygon.

As per "AssertNull 292" I am thinking no part of the thick line would be outside the boundry of the original polygon. So the original polygon defines outer boundry of the thickly drawn polygon, and inner boundry edges of this thickly drawn polygon defines the polygon I am looking for.

I am thinking of offset distance X being thickness of the drawn line - so perpandicular distance from the original polygon to the internal polygon.

Note - it is very easy for a rectangle, but gets complex if the polygon can have convex and concave areas.

I have added a picture here which I hope will help explain

Member Avatar for rproffitt

Per your picture it looks like you want to scale a polygon.

Member Avatar for Stagnant

So I got a little knowledge after watching this video. https://www.youtube.com/watch?v=ThrfCh_Y0YA

I figure you want the de-scalar of the polygon, so I applied the reference center point, the red dot. It didn't seem right to have the red dot outside of the polygon, but it looked a lot better placing within the polygon. The scaling part was tricky because connecting the first segment, point A to red dot was so wide... Scaling factor of 2 and -2 were nonsensical so then I realize it's the inverse of 2, 1/2, as depicted as midpoints of the all those segments. Connect the dots and there is the polygon "within". It looks like a prism!

Now to find the coordinates of your eroded polygon at each of its vertices, apply the midpoint formula. Welcome back to 8th grade Geometry.

calculating_descale_destination.png 38.68 KB half_scale_factor_complete.png 40.13 KB irregular_polygon.png 26.98 KB
Edited by Stagnant because: Changed link label
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.