Solved

Points form a line. How can I find the most distant points?

Posted on 2011-02-22
5
356 Views
Last Modified: 2012-05-11
Hello experts!

I have set of points.
I know that they form a line.

I need to find two most distant points (start and end of line).

How can I do it?

Thank you

panJames
0
Comment
Question by:panJames
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 32

Expert Comment

by:phoffric
ID: 34952669
How about sorting the set of points, { (xi, yi) } by the key x.
The first point (x_min, y1) and the last point (x_max, y2) should be the two most distant points.

If the slope of the line is positive, then y1 should be y_min; otherwise y1 should be y_max.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 500 total points
ID: 34952683
If the line is vertical, the all x's are the same. So, if x_min = x_max, then start over and sort all the points by the key y.
0
 
LVL 12

Expert Comment

by:Amick
ID: 34952686
What do you know about the points?  Do you have their coordinates?  
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34952851
The ends of the line segment must include the maximum and minimum values of
x and y.

If the line is vertical, the max and min values of x will be the same.

If the line is horizontal, the max and min values of y will be the same.

If the slope of the line is positive, the max and min values of x will be paired
with the max and min values of y respectively.

If the slope is negative, the max and min values of x will be paired
with the min and max values of y respectively.
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34952865
You don't have to sort, all you have to do is find the max and min.
0

Featured Post

Get MySQL database support online, now!

At Percona’s web store you can order your MySQL database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

630 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question