Solved

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

Posted on 2011-02-22
5
349 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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
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…

734 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