Recent

Author Topic: Scaling a "skewed polygon"  (Read 2756 times)

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Scaling a "skewed polygon"
« on: July 16, 2024, 03:20:26 pm »
I appreciate that some might raise their eyebrows at the idea of a polygon being skewed, but I ask for their indulgence while I explain the problem.

The attached image shows the circuit pattern associated with a small airfield, with the runway on the lower of the two long legs (marked with a grey track). The Northeastern approach is offset due to a requirement to avoid overflying certain properties ("avoid" areas marked in red).

I have been attempting to expand the circuit track using software to give me an overlay such as the one I've drawn in manually (yellow), with the intention of being able to identify a "circuit perimeter" within which aircraft should exercise particular caution. Nominally, the perimeter is 500m outside the circuit.

Unfortunately, I seem to have presented myself with a rather thorny problem :-)

The main issue is that due to the (approximate) rectangle being rotated, even if I translate it so that the geographical origin is at its centre two of the corners (marked with a through-line) lie in the "wrong quadrant" with the result that standard graphics operations don't work properly: they move at least one corner in the wrong direction, and/or by a significantly wrong distance.

It might be possible to compensate for that by rotating the circuit pattern before trying to scale it, but as soon as that approach was applied to an airfield with two active runways I'm pretty sure it would go wrong.

There are two approaches I feel might work:

a) Move each line (leg of the circuit) out by 500m along the normal, then (iteratively?) work out a new point of intersection. I feel the latter stage could get hairy, particularly since it would have to accommodate situations where the lines already crossed due to a rentrant point.

b) For each pair of lines, compute the angle between them and move the intersection an appropriate distance. If they met at a right angle this would presumably be Sqrt(2) * 500m, for a rentrant point this would be proportionately smaller... wouldn't have to be exact.

I'm not for the moment attaching what I've been struggling with so far, since I think the "quadrant problem" makes it unusable by definition.

Any thoughts would be appreciated.

MarkMLl
« Last Edit: July 16, 2024, 06:49:39 pm by MarkMLl »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

loaded

  • Hero Member
  • *****
  • Posts: 853
Re: Rotating a "skewed polygon"
« Reply #1 on: July 16, 2024, 05:48:28 pm »
https://forum.lazarus.freepascal.org/index.php/topic,67542.msg520124.html#msg520124
In the sample application I sent in the relevant message called "Interactive_ Transparent_ Polygon" (which I wrote with the experience I gained from cartography knowledge), there is a function of rotating clockwise or counterclockwise from any point of the polygon (Ctrl + Mouse Middle Wheel).
There is also a method for enlarging or reducing (Shift + Mouse Middle wheel).
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Re: Scaling a "skewed polygon"
« Reply #2 on: July 16, 2024, 06:51:03 pm »
I've corrected the misleading initial subject line.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Re: Scaling a "skewed polygon"
« Reply #3 on: July 16, 2024, 07:28:05 pm »
Program illustrating my problem attached. My code is pretty sloppy: I'm doing maths on degrees when I should be scaling them to metres first but there's some fairly serious sign errors in there I've not managed to track down yet.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

alpine

  • Hero Member
  • *****
  • Posts: 1298
Re: Scaling a "skewed polygon"
« Reply #4 on: July 16, 2024, 07:31:46 pm »
As I understand, you mean a "polygon buffering" -  offsetting with all points in the perimeter of the new shape are equidistant with their closest points in the perimeter of the original shape. Am I right?
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Re: Scaling a "skewed polygon"
« Reply #5 on: July 16, 2024, 08:47:56 pm »
Yes. Draw airspace perimeter outside (500m by default) the circuit.

The magnitude handling in my code is crappy, but there's a far more serious problem- which I can't see- in the sign handling.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

alpine

  • Hero Member
  • *****
  • Posts: 1298
Re: Scaling a "skewed polygon"
« Reply #6 on: July 17, 2024, 01:31:52 pm »
Yes. Draw airspace perimeter outside (500m by default) the circuit.

The magnitude handling in my code is crappy, but there's a far more serious problem- which I can't see- in the sign handling.

MarkMLl
IMO the scaling won't work.

I wrote makePerimeter2 function. The approach is to offset each segment outwards, then to connect them with a (Bezier) curve. Segments intersection point was taken twice for the control points, which isn't optimal.

The reentrant case is not considered, but it must be trivial since the intersection point must replace both segment ends and no need for a curve.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Re: Scaling a "skewed polygon"
« Reply #7 on: July 17, 2024, 01:45:58 pm »
IMO the scaling won't work.

I wrote makePerimeter2 function. The approach is to offset each segment outwards, then to connect them with a (Bezier) curve. Segments intersection point was taken twice for the control points, which isn't optimal.

The reentrant case is not considered, but it must be trivial since the intersection point must replace both segment ends and no need for a curve.

Thanks very much, I'll take a look. Obviously this is very much subsidiary to the Barkway example which was intended to be entirely to illustrate adding areas and lines to LMV, but I thought it was a useful example in which to raise it.

I can see one of the problems in my original code: the signs are transposed between lat and long when working out the distance the points should be offset.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

alpine

  • Hero Member
  • *****
  • Posts: 1298
Re: Scaling a "skewed polygon"
« Reply #8 on: July 17, 2024, 07:19:06 pm »
For smoother curves you can add (see the highlighted lines below):
Code: Pascal  [Select][+][-]
  1.  // Calculate points of a 4-point bezier
  2.   procedure CalcBezier(APoints: array of TPoint; out APoly: TPointArray);
  3.   var
  4.     NPoints: Integer;
  5.     PtArray: PPoint;
  6.     PtCount: LongInt = 0;
  7.   begin
  8.     NPoints := Length(APoints);
  9.     if NPoints < 4 then
  10.       Exit; // Curve must have at least 4 points
  11.     PtArray := Nil;
  12.     APoly := Nil;
  13.     try
  14.       // Assuming APoints[1]=APoints[2]=crossing point, replace APoints[1]
  15.       // with a 2/3-rd of <APoints[0],APoints[1]> and APoints[2] with a 2/3-rd
  16.       // of <APoints[3],APoints[2]> to make the curve smoother
  17.       APoints[1].X := Round((2 * APoints[1].X + APoints[0].X) / 3);
  18.       APoints[1].Y := Round((2 * APoints[1].Y + APoints[0].Y) / 3);
  19.       APoints[2].X := Round((2 * APoints[3].X + APoints[2].X) / 3);
  20.       APoints[2].Y := Round((2 * APoints[3].Y + APoints[2].Y) / 3);
  21.  
  22.       PolyBezier2Polyline(APoints, PtArray, PtCount, True);      
  23.       ...

EDIT: It occurs to me now that instead of calculating the curve you can just add the two control points [1,2] and thus create a miter joint, which IMHO is preferable no matter it's less accurate
« Last Edit: July 17, 2024, 07:40:17 pm by alpine »
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

cdbc

  • Hero Member
  • *****
  • Posts: 1655
    • http://www.cdbc.dk
Re: Scaling a "skewed polygon"
« Reply #9 on: July 17, 2024, 11:24:28 pm »
Hi
@alpine: How do you highlight lines like that, in your forum-post?!?
I can't seem to figure it out...
Regards Benny
If it ain't broke, don't fix it ;)
PCLinuxOS(rolling release) 64bit -> KDE5 -> FPC 3.2.2 -> Lazarus 2.2.6 up until Jan 2024 from then on it's: KDE5/QT5 -> FPC 3.3.1 -> Lazarus 3.0

alpine

  • Hero Member
  • *****
  • Posts: 1298
Re: Scaling a "skewed polygon"
« Reply #10 on: July 18, 2024, 01:26:10 am »
See the attached picture.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

cdbc

  • Hero Member
  • *****
  • Posts: 1655
    • http://www.cdbc.dk
Re: Scaling a "skewed polygon"
« Reply #11 on: July 18, 2024, 06:54:46 am »
Hi
Cool, thanks mate  8-)
Regards Benny
If it ain't broke, don't fix it ;)
PCLinuxOS(rolling release) 64bit -> KDE5 -> FPC 3.2.2 -> Lazarus 2.2.6 up until Jan 2024 from then on it's: KDE5/QT5 -> FPC 3.3.1 -> Lazarus 3.0

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Re: Scaling a "skewed polygon"
« Reply #12 on: July 18, 2024, 11:18:14 am »
Rather to my surprise, it appears that my original approach does work... not perfectly since it doesn't take the angle of intersecting lines into account, and it operates along lines from the center so the perimeter is somewhat distorted on a typical airfield circuit pattern.

Unfortunately, I can't get your better way to work, even with LMV r9394... there's +infs in the output values and LMV (possibly wisely) refuses to plot the resulting area. See bottom of new geometry unit.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

alpine

  • Hero Member
  • *****
  • Posts: 1298
Re: Scaling a "skewed polygon"
« Reply #13 on: July 18, 2024, 01:00:32 pm »
Unfortunately, I can't get your better way to work, even with LMV r9394... there's +infs in the output values and LMV (possibly wisely) refuses to plot the resulting area. See bottom of new geometry unit.
That's because when moved to the separate geometry.pas unit, you forgot to initialize CosLat0 global (used for Lat,Lon to/from X,Y)
Code: Pascal  [Select][+][-]
  1. var
  2.   CosLat0: Double = 0.615661475; // = Cos(DegToRad(52));

Must be the cosine of the map center longitude, but assuming we have fixed that on 52.
« Last Edit: July 18, 2024, 01:03:35 pm by alpine »
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

MarkMLl

  • Hero Member
  • *****
  • Posts: 8027
Re: Scaling a "skewed polygon"
« Reply #14 on: July 18, 2024, 01:16:06 pm »
Unfortunately, I can't get your better way to work, even with LMV r9394... there's +infs in the output values and LMV (possibly wisely) refuses to plot the resulting area. See bottom of new geometry unit.
That's because when moved to the separate geometry.pas unit, you forgot to initialize CosLat0 global (used for Lat,Lon to/from X,Y)
Code: Pascal  [Select][+][-]
  1. var
  2.   CosLat0: Double = 0.615661475; // = Cos(DegToRad(52));

Got it: in form creation (mea culpa). Result looks a bit small visually but nicely aligned.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

 

TinyPortal © 2005-2018