Archive for the ‘Geometry’ Category
Distance Between A Point And A Line.
As seen in the diagram we define a line segment to be between P1 and P2 and want to know the Point on the line segment that is closest to our point P3. We call this closest point on the line point P. An assumption is made that P1 and P2 are not co-incident (exactly the same).
We can write the Point P as
where u is a simple scaler. If we can work out u then it is easy to find P. For a line segment u must be between 0 an 1 as this keeps P between P1 and P2. If we are considering an infinite line defined by P1 and P2 then u can be any value.
The shortest distance is given when the line between P3 to P and the line p1 to p2 is perpendicular to each other. That is they have an angle of 90 degrees. The 90 degrees should give you a hint that we will need to use the dot product (inner product) to solve this problem. When the angle between two lines is 90 degree the dot product is zero. Therefor
Substitute in the value for P we obtain
Then is you site down and solve this you get
Now you know u find P is trivial.
Remember to clamp u between 0 and 1 if you are solving for the line segment rather than the infinite line case.
Douglas Peuker Line Simplification Explained.
Douglas Peuker Line simplification algorithm was first published in 1973 and has been a firm favourite ever since. Well I can’t be sure about the early years but google sure likes throwing up the algorithm when you search for line simplification. In this article I give an overview of how the algorithm works. It may be a bit wordy for those who prefer math equations but the idea it to present this in an accessible way. Part of the beauty of the Douglas Peuker algorithm is its simplicity and I hope to convey that here.
Selecting a Random Point in a Triangle
Given a triangle defined by the 3 points a, b, c and given the vectors AB,AC going from point a to points b and c respectively as shown in the diagram below. Read the rest of this entry »
Bounding Circles – Algorithm Comparision
Repost from old site.
Introduction
In this article I am going to discuss how given a set of points you can generate a circle that encompasses them. Calculation of the best possible fit for n points has an O(n^3) dependence making it unsuitable for large data sets or real time applications. We have to use our brains to generate a good approximation to the optimum solution; I should say use other peoples brains as this is a well researched topic. To keep this article a reasonable length I will focus on a few algorithms that have guaranteed O(n) behaviour. These tend to be the simplest to implement but it does mean we exclude some good algorithms like the one discussed in Eberly[1]. Read the rest of this entry »