point.go

Documentation: oss.terrastruct.com/d2/lib/geo

     1  package geo
     2  
     3  import (
     4  	"fmt"
     5  	"math"
     6  	"sort"
     7  	"strings"
     8  )
     9  
    10  //nolint:forbidigo
    11  
    12  type RelativePoint struct {
    13  	XPercentage float64
    14  	YPercentage float64
    15  }
    16  
    17  func NewRelativePoint(xPercentage, yPercentage float64) *RelativePoint {
    18  	// 3 decimal points of precision is enough. Floating points on Bezier curves can reach the level of precision where different machines round differently.
    19  	return &RelativePoint{
    20  		XPercentage: TruncateDecimals(xPercentage),
    21  		YPercentage: TruncateDecimals(yPercentage),
    22  	}
    23  }
    24  
    25  type Point struct {
    26  	X float64 `json:"x"`
    27  	Y float64 `json:"y"`
    28  }
    29  
    30  func NewPoint(x, y float64) *Point {
    31  	return &Point{X: x, Y: y}
    32  }
    33  
    34  func (p1 *Point) Equals(p2 *Point) bool {
    35  	if p1 == nil {
    36  		return p2 == nil
    37  	} else if p2 == nil {
    38  		return false
    39  	}
    40  	return (p1.X == p2.X) && (p1.Y == p2.Y)
    41  }
    42  
    43  func (p1 *Point) Compare(p2 *Point) int {
    44  	xCompare := Sign(p1.X - p2.X)
    45  	if xCompare == 0 {
    46  		return Sign(p1.Y - p2.Y)
    47  	}
    48  	return xCompare
    49  }
    50  
    51  func (p *Point) Copy() *Point {
    52  	return &Point{X: p.X, Y: p.Y}
    53  }
    54  
    55  type Points []*Point
    56  
    57  func (ps Points) Equals(other Points) bool {
    58  	if ps == nil {
    59  		return other == nil
    60  	} else if other == nil {
    61  		return false
    62  	}
    63  	pointsSet := make(map[Point]struct{})
    64  	for _, p := range ps {
    65  		pointsSet[*p] = struct{}{}
    66  	}
    67  
    68  	for _, otherPoint := range other {
    69  		if _, exists := pointsSet[*otherPoint]; !exists {
    70  			return false
    71  		}
    72  	}
    73  	return true
    74  }
    75  
    76  func (ps Points) GetMedian() *Point {
    77  	xs := make([]float64, 0)
    78  	ys := make([]float64, 0)
    79  
    80  	for _, p := range ps {
    81  		xs = append(xs, p.X)
    82  		ys = append(ys, p.Y)
    83  	}
    84  
    85  	sort.Float64s(xs)
    86  	sort.Float64s(ys)
    87  
    88  	middleIndex := len(xs) / 2
    89  
    90  	medianX := xs[middleIndex]
    91  	medianY := ys[middleIndex]
    92  
    93  	if len(xs)%2 == 0 {
    94  		medianX += xs[middleIndex-1]
    95  		medianX /= 2
    96  		medianY += ys[middleIndex-1]
    97  		medianY /= 2
    98  	}
    99  
   100  	return &Point{X: medianX, Y: medianY}
   101  }
   102  
   103  // GetOrientation gets orientation of pFrom to pTo
   104  // E.g. pFrom ---> pTo, here, pFrom is to the left of pTo, so Left would be returned
   105  func (pFrom *Point) GetOrientation(pTo *Point) Orientation {
   106  	if pFrom.Y < pTo.Y {
   107  		if pFrom.X < pTo.X {
   108  			return TopLeft
   109  		}
   110  		if pFrom.X > pTo.X {
   111  			return TopRight
   112  		}
   113  		return Top
   114  	}
   115  
   116  	if pFrom.Y > pTo.Y {
   117  		if pFrom.X < pTo.X {
   118  			return BottomLeft
   119  		}
   120  		if pFrom.X > pTo.X {
   121  			return BottomRight
   122  		}
   123  		return Bottom
   124  	}
   125  
   126  	if pFrom.X < pTo.X {
   127  		return Left
   128  	}
   129  
   130  	if pFrom.X > pTo.X {
   131  		return Right
   132  	}
   133  
   134  	return NONE
   135  }
   136  
   137  func (p *Point) ToString() string {
   138  	if p == nil {
   139  		return ""
   140  	}
   141  	return fmt.Sprintf("(%v, %v)", p.X, p.Y)
   142  }
   143  
   144  func (points Points) ToString() string {
   145  	strs := make([]string, 0, len(points))
   146  	for _, p := range points {
   147  		strs = append(strs, p.ToString())
   148  	}
   149  	return strings.Join(strs, ", ")
   150  }
   151  
   152  // https://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
   153  func (p *Point) DistanceToLine(p1, p2 *Point) float64 {
   154  	a := p.X - p1.X
   155  	b := p.Y - p1.Y
   156  	c := p2.X - p1.X
   157  	d := p2.Y - p1.Y
   158  
   159  	dot := (a * c) + (b * d)
   160  	len_sq := (c * c) + (d * d)
   161  
   162  	param := -1.0
   163  
   164  	if len_sq != 0 {
   165  		param = dot / len_sq
   166  	}
   167  
   168  	var xx float64
   169  	var yy float64
   170  
   171  	if param < 0.0 {
   172  		xx = p1.X
   173  		yy = p1.Y
   174  	} else if param > 1.0 {
   175  		xx = p2.X
   176  		yy = p2.Y
   177  	} else {
   178  		xx = p1.X + (param * c)
   179  		yy = p1.Y + (param * d)
   180  	}
   181  
   182  	dx := p.X - xx
   183  	dy := p.Y - yy
   184  
   185  	return math.Sqrt((dx * dx) + (dy * dy))
   186  }
   187  
   188  // Moves the given point by Vector
   189  func (start *Point) AddVector(v Vector) *Point {
   190  	return start.ToVector().Add(v).ToPoint()
   191  }
   192  
   193  // Creates a Vector of the size between start and endpoint, pointing to endpoint
   194  func (start *Point) VectorTo(endpoint *Point) Vector {
   195  	return endpoint.ToVector().Minus(start.ToVector())
   196  }
   197  
   198  func (p *Point) FormattedCoordinates() string {
   199  	return fmt.Sprintf("%d,%d", int(p.X), int(p.Y))
   200  }
   201  
   202  // returns true if point p is on orthogonal segment between points a and b
   203  func (p *Point) OnOrthogonalSegment(a, b *Point) bool {
   204  	if a.X < b.X {
   205  		if p.X < a.X || b.X < p.X {
   206  			return false
   207  		}
   208  	} else if p.X < b.X || a.X < p.X {
   209  		return false
   210  	}
   211  	if a.Y < b.Y {
   212  		if p.Y < a.Y || b.Y < p.Y {
   213  			return false
   214  		}
   215  	} else if p.Y < b.Y || a.Y < p.Y {
   216  		return false
   217  	}
   218  	return true
   219  }
   220  
   221  // Creates a Vector pointing to point
   222  func (endpoint *Point) ToVector() Vector {
   223  	return []float64{endpoint.X, endpoint.Y}
   224  }
   225  
   226  // get the point of intersection between line segments u and v (or nil if they do not intersect)
   227  func IntersectionPoint(u0, u1, v0, v1 *Point) *Point {
   228  	// https://en.wikipedia.org/wiki/Intersection_(Euclidean_geometry)
   229  	//
   230  	// Example ('-' = 1, '|' = 1):
   231  	//    v0
   232  	//    |
   233  	//u0 -+--- u1
   234  	//    |
   235  	//    |
   236  	//    v1
   237  	//
   238  	// s = 0.2 (1/5 along u)
   239  	// t = 0.25 (1/4 along v)
   240  	// we compute s and t and if they are both in range [0,1], then
   241  	// they intersect and we compute the point of intersection to return
   242  
   243  	// when s = 0, x = u.Start.X; when s = 1, x = u.End.X
   244  	// x = s * u1.X + (1 - s) * u0.X
   245  	//   = u0.X + s * (u1.X - u0.X)
   246  
   247  	// x = u0.X + s * (u1.X - u0.X)
   248  	//   = v0.X + t * (v1.X - v0.X)
   249  	// y = u0.Y + s * (u1.Y - u0.Y)
   250  	//   = v0.Y + t * (v1.Y - v0.Y)
   251  
   252  	// s * (u1.X - u0.X) - t * (v1.X - v0.X) = v0.X - u0.X
   253  	// s*udx - t*vdx = uvdx
   254  	// s*udy - t*vdy = uvdy
   255  	udx := u1.X - u0.X
   256  	vdx := v1.X - v0.X
   257  	uvdx := v0.X - u0.X
   258  	udy := u1.Y - u0.Y
   259  	vdy := v1.Y - v0.Y
   260  	uvdy := v0.Y - u0.Y
   261  
   262  	denom := (udy*vdx - udx*vdy)
   263  	if denom == 0 {
   264  		// lines are parallel
   265  		return nil
   266  	}
   267  	// Cramer's rule
   268  	s := (vdx*uvdy - vdy*uvdx) / denom
   269  	t := (udx*uvdy - udy*uvdx) / denom
   270  
   271  	// lines don't intersect within segments
   272  	if s < 0 || s > 1 || t < 0 || t > 1 {
   273  		// if s or t is outside [0, 1], the intersection of the lines are not on the segments
   274  		return nil
   275  	}
   276  
   277  	// use s parameter to get point along u
   278  	intersection := new(Point)
   279  	intersection.X = u0.X + math.Round(s*udx)
   280  	intersection.Y = u0.Y + math.Round(s*udy)
   281  	return intersection
   282  }
   283  
   284  func (p *Point) Transpose() {
   285  	if p == nil {
   286  		return
   287  	}
   288  	p.X, p.Y = p.Y, p.X
   289  }
   290  
   291  // point t% of the way between a and b
   292  func (a *Point) Interpolate(b *Point, t float64) *Point {
   293  	return NewPoint(
   294  		a.X*(1.0-t)+b.X*t,
   295  		a.Y*(1.0-t)+b.Y*t,
   296  	)
   297  }
   298  
   299  func (p *Point) TruncateFloat32() {
   300  	p.X = float64(float32(p.X))
   301  	p.Y = float64(float32(p.Y))
   302  }
   303  
   304  func (p *Point) TruncateDecimals() {
   305  	p.X = TruncateDecimals(p.X)
   306  	p.Y = TruncateDecimals(p.Y)
   307  }
   308  
   309  // RemovePoints returns a new Points slice without the points in toRemove
   310  func RemovePoints(points Points, toRemove []bool) Points {
   311  	newLen := len(points)
   312  	for _, should := range toRemove {
   313  		if should {
   314  			newLen--
   315  		}
   316  	}
   317  
   318  	without := make([]*Point, 0, newLen)
   319  	for i := 0; i < len(points); i++ {
   320  		if toRemove[i] {
   321  			continue
   322  		}
   323  		without = append(without, points[i])
   324  	}
   325  	return without
   326  }
   327
View as plain text