EzDevInfo.com

Shortest distance between a point and a line segment

I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript).

EDIT: My line segment is defined by two endpoints. So my line segment AB is defined by the two points A (x1,y1) and B (x2,y2). I'm trying to find the distance between this line segment and a point C (x3,y3). My geometry skills are rusty, so the examples I've seen are confusing, I'm sorry to admit.

Equation for testing if a point is inside a circle

If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?

How do CSS triangles work?

There're plenty of different CSS shapes over at http://css-tricks.com/examples/ShapesOfCSS/ and I'm particularly puzzled with a triangle:

#triangle-up {
    width: 0;
    height: 0;
    border-left: 50px solid transparent;
    border-right: 50px solid transparent;
    border-bottom: 100px solid red;
}

So, how and why does it work?

How do you detect where two line segments intersect?

How do I determine whether or not two lines intersect, and if they do, at what x,y point?

Determine if two rectangles overlap each other?

I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges will have slopes of 0 or infinity.

I've tried to implement what is mentioned in this question but I am not having very much luck.

My current implementation does the following:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;

However I'm not quite sure if (a) I've implemented the algorithm I linked to correctly, or if I did exactly how to interpret this?

Any suggestions?

How to calculate an angle from three points?

Lets say you have this:

P1 = (x=2, y=50)
P2 = (x=9, y=40)
P3 = (x=5, y=20)

Assume that P1 is the center point of a circle. It is always the same. I want the angle that is made up by P2 and P3, or in other words the angle that is next to P1. The inner angle to be precise. It will always be an acute angle, so less than -90 degrees.

I thought: Man, that's simple geometry math. But I have looked for a formula for around 6 hours now, and only find people talking about complicated NASA stuff like arccos and vector scalar product stuff. My head feels like it's in a fridge.

Some math gurus here that think this is a simple problem? I don't think the programming language matters here, but for those who think it does: java and objective-c. I need it for both, but haven't tagged it for these.

Circle drawing with SVG's arc path

The following SVG path can draw 99.99% of a circle: (try it on http://jsfiddle.net/DFhUF/46/ and see if you see 4 arcs or only 2, but note that if it is IE, it is rendered in VML, not SVG, but have the similar issue)

M 100 100 a 50 50 0 1 0 0.00001 0

But when it is 99.99999999% of a circle, then nothing will show at all?

M 100 800 a 50 50 0 1 0 0.00000001 0    

And that's the same with 100% of a circle (it is still an arc, isn't it, just a very complete arc)

M 100 800 a 50 50 0 1 0 0 0 

How can that be fixed? The reason is I use a function to draw a percentage of an arc, and if I need to "special case" a 99.9999% or 100% arc to use the circle function, that'd be kind of silly.

Again, a test case on jsfiddle using RaphaelJS is at http://jsfiddle.net/DFhUF/46/
(and if it is VML on IE 8, even the second circle won't show... you have to change it to 0.01)

Update:

This is because I am rendering an arc for a score in our system, so 3.3 points get 1/3 of a circle. 0.5 gets half a circle, and 9.9 points get 99% of a circle. But what if there are scores that are 9.99 in our system? Do I have to check whether it is close to 99.999% of a circle, and use an arc function or a circle function accordingly? Then what about a score of 9.9987? Which one to use? It is ridiculous to need to know what kind of scores will map to a "too complete circle" and switch to a circle function, and when it is "a certain 99.9%" of a circle or a 9.9987 score, then use the arc function.

The smallest difference between 2 Angles

Given 2 angles in the range -PI -> PI around a coordinate, what is the value of the smallest of the 2 angles between them?

Taking into account that the difference between PI and -PI is not 2 PI but zero.

Example:

Imagine a circle, with 2 lines coming out from the center, there are 2 angles between those lines, the angle they make on the inside aka the smaller angle, and the angle they make on the outside, aka the bigger angle. Both angles when added up make a full circle. Given that each angle can fit within a certain range, what is the smaller angles value, taking into account the rollover

Position of the sun given time of day, latitude and longitude

This question has been asked before a little over three years ago. There was an answer given, however I've found a glitch in the solution.

Code below is in R. I've ported it to another language, however have tested the original code directly in R to ensure the issue wasn't with my porting.

sunPosition <- function(year, month, day, hour=12, min=0, sec=0,
                    lat=46.5, long=6.5) {


  twopi <- 2 * pi
  deg2rad <- pi / 180

  # Get day of the year, e.g. Feb 1 = 32, Mar 1 = 61 on leap years
  month.days <- c(0,31,28,31,30,31,30,31,31,30,31,30)
  day <- day + cumsum(month.days)[month]
  leapdays <- year %% 4 == 0 & (year %% 400 == 0 | year %% 100 != 0) & day >= 60
  day[leapdays] <- day[leapdays] + 1

  # Get Julian date - 2400000
  hour <- hour + min / 60 + sec / 3600 # hour plus fraction
  delta <- year - 1949
  leap <- trunc(delta / 4) # former leapyears
  jd <- 32916.5 + delta * 365 + leap + day + hour / 24

  # The input to the Atronomer's almanach is the difference between
  # the Julian date and JD 2451545.0 (noon, 1 January 2000)
  time <- jd - 51545.

  # Ecliptic coordinates

  # Mean longitude
  mnlong <- 280.460 + .9856474 * time
  mnlong <- mnlong %% 360
  mnlong[mnlong < 0] <- mnlong[mnlong < 0] + 360

  # Mean anomaly
  mnanom <- 357.528 + .9856003 * time
  mnanom <- mnanom %% 360
  mnanom[mnanom < 0] <- mnanom[mnanom < 0] + 360
  mnanom <- mnanom * deg2rad

  # Ecliptic longitude and obliquity of ecliptic
  eclong <- mnlong + 1.915 * sin(mnanom) + 0.020 * sin(2 * mnanom)
  eclong <- eclong %% 360
  eclong[eclong < 0] <- eclong[eclong < 0] + 360
  oblqec <- 23.429 - 0.0000004 * time
  eclong <- eclong * deg2rad
  oblqec <- oblqec * deg2rad

  # Celestial coordinates
  # Right ascension and declination
  num <- cos(oblqec) * sin(eclong)
  den <- cos(eclong)
  ra <- atan(num / den)
  ra[den < 0] <- ra[den < 0] + pi
  ra[den >= 0 & num < 0] <- ra[den >= 0 & num < 0] + twopi
  dec <- asin(sin(oblqec) * sin(eclong))

  # Local coordinates
  # Greenwich mean sidereal time
  gmst <- 6.697375 + .0657098242 * time + hour
  gmst <- gmst %% 24
  gmst[gmst < 0] <- gmst[gmst < 0] + 24.

  # Local mean sidereal time
  lmst <- gmst + long / 15.
  lmst <- lmst %% 24.
  lmst[lmst < 0] <- lmst[lmst < 0] + 24.
  lmst <- lmst * 15. * deg2rad

  # Hour angle
  ha <- lmst - ra
  ha[ha < -pi] <- ha[ha < -pi] + twopi
  ha[ha > pi] <- ha[ha > pi] - twopi

  # Latitude to radians
  lat <- lat * deg2rad

  # Azimuth and elevation
  el <- asin(sin(dec) * sin(lat) + cos(dec) * cos(lat) * cos(ha))
  az <- asin(-cos(dec) * sin(ha) / cos(el))
  elc <- asin(sin(dec) / sin(lat))
  az[el >= elc] <- pi - az[el >= elc]
  az[el <= elc & ha > 0] <- az[el <= elc & ha > 0] + twopi

  el <- el / deg2rad
  az <- az / deg2rad
  lat <- lat / deg2rad

  return(list(elevation=el, azimuth=az))
}

The problem I'm hitting is that the azimuth it returns seems wrong. For example, if I run the function on the (southern) summer solstice at 12:00 for locations 0ºE and 41ºS, 3ºS, 3ºN and 41ºN:

> sunPosition(2012,12,22,12,0,0,-41,0)
$elevation
[1] 72.42113

$azimuth
[1] 180.9211

> sunPosition(2012,12,22,12,0,0,-3,0)
$elevation
[1] 69.57493

$azimuth
[1] -0.79713

Warning message:
In asin(sin(dec)/sin(lat)) : NaNs produced
> sunPosition(2012,12,22,12,0,0,3,0)
$elevation
[1] 63.57538

$azimuth
[1] -0.6250971

Warning message:
In asin(sin(dec)/sin(lat)) : NaNs produced
> sunPosition(2012,12,22,12,0,0,41,0)
$elevation
[1] 25.57642

$azimuth
[1] 180.3084

These numbers just don't seem right. The elevation I'm happy with - the first two should be roughly the same, the third a touch lower, and the fourth much lower. However the first azimuth should be roughly due North, whereas the number it gives is the complete opposite. The remaining three should point roughly due South, however only the last one does. The two in the middle point just off North, again 180º out.

As you can see there are also a couple of errors triggered with the low latitudes (close the equator)

I believe the fault is in this section, with the error being triggered at the third line (starting with elc).

  # Azimuth and elevation
  el <- asin(sin(dec) * sin(lat) + cos(dec) * cos(lat) * cos(ha))
  az <- asin(-cos(dec) * sin(ha) / cos(el))
  elc <- asin(sin(dec) / sin(lat))
  az[el >= elc] <- pi - az[el >= elc]
  az[el <= elc & ha > 0] <- az[el <= elc & ha > 0] + twopi

I googled around and found a similar chunk of code in C, converted to R the line it uses to calculate the azimuth would be something like

az <- atan(sin(ha) / (cos(ha) * sin(lat) - tan(dec) * cos(lat)))

The output here seems to be heading in the right direction, but I just can't get it to give me the right answer all the time when it's converted back to degrees.

A correction of the code (suspect it's just the few lines above) to make it calculate the correct azimuth would be fantastic.

How do you calculate the average of a set of angles?

I want to calculate the average of a set of angles. For example, I might have several samples from the reading of a compass. The problem of course is how to deal with the wraparound. The same algorithm might be useful for a clockface.

The actual question is more complicated - what do statistics mean on a sphere or in an algebraic space which "wraps round", eg the additive group mod n. The answer may not be unique, eg the average of 359 degrees and 1 degree could be 0 degrees or 180, but statistically 0 looks better.

This is a real programming problem for me and I'm trying to make it not look like just a Math problem.

[Edit: to resolve all the confusion, when I refer to angles you can assume I mean bearings]

Sort points in clockwise order?

Given an array of x,y points, how do I sort the points of this array in clockwise order (around their overall average center point)? My goal is to pass the points to a line-creation function to end up with something looking rather "solid", as convex as possible with no lines intersecting.

For what it's worth, I'm using Lua, but any pseudocode would be appreciated. Thanks so much for any help!

Update: For reference, this is the Lua code based on Ciamej's excellent answer (ignore my "app" prefix):

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then return false
    end

    local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
    local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
    return d1 > d2
end

function appGetCenterPointOfPoints(points)
    local pointsSum = {x = 0, y = 0}
    for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
    return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end

Generate a random point within a circle (uniformly)

I need to generate a uniformly random point within a circle of radius R.

I realize that by just picking a uniformly random angle in the interval [0 ... 2π), and uniformly random radius in the interval (0 ... R) I would end up with more points towards the center, since for two given radii, the points in the smaller radius will be closer to each other than for the points in the larger radius.

I found a blog entry on this over here but I don't understand his reasoning. I suppose it is correct, but I would really like to understand from where he gets (2/R²)×r and how he derives the final solution.

Regarding rejection sampling: I could generate a random point within the R×R square over and over again until I get one within the circle. This approach has the obvious draw-back that it doesn't provide a guarantee for termination (even though it is highly unlikely that it goes on for long).

An algorithm for inflating/deflating (offsetting, buffering) polygons

UPDATE: the math term for what I'm looking for is actually inward/outward polygon offseting. +1 to balint for pointing this out. The alternative naming is polygon buffering.

UPDATE 2 (02.11.2011): check out the newly accepted answer - Clipper library by Angus Johnson.

Before I start developing my own solution from scratch, does anyone know of any good source for an algorithm that can inflate a polygon, something similar to this:

The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the example pic. they are not, since then it would have to use arcs for inflated vertices, but let's forget about that for now ;) ).

Results of my search:

Here are some links:

• A Survey of Polygon Offseting Strategies
• Polygon offset, PROBLEM
• Buffering Polygon Data

Circle-Rectangle collision detection (intersection)

How can I tell whether a circle and a rectangle intersect in 2D Euclidean space? (i.e. classic 2D geometry)

How to determine if a list of polygon points are in clockwise order?

Having a list of points, how do I find if they are in clockwise order?

For example:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

would say that it is anti-clockwise (counter-clockwise for some people).