perpendicular line

Careful with the cross posting - this community is a great bunch of people, but the cross-posting thing is a faux-pas!

If you can, I would delete your other threads (edit -> delete checkbox)

Here and Here

Instead of using slope, use the fact that the distance between each foci and the endpoints of the minor axis are going to be equal (refer to this image). Instead of using the foci you can use the endpoints of the major axis which you already found, and instaed of checking for exactly equality - which as you mentioned won't work well - you want to find the point that minimizes the difference in distances. So instead of checking for d₁ - d₂ = 0, you check for min(abs(d₁ - d₂)). The pseudo-code might like look this, assuming you already found the major axis endpoints -

minorIdx := 0diff[0] := MAX_INTdiff[1] := MAX_INTfor each point x,y on the ellipse starting at a major axis endpoint   d1 := (Major[0].x - x)^2 + (Major[0].y - y)^2   d2 := (Major[1].x - x)^2 + (Major[1].y - y)^2   if((diff[1] - diff[0]) < 0 && (abs(d1 - d2) - diff[1]) > 0)      Minor[minorIdx].x := lastX      Minor[minorIdx].y := lastY      minorIdx := minorIdx + 1   diff[0] := diff[1]   diff[1] := abs(d1 - d2)   lastX := x   lastY := yend for

This logic takes advantage of the fact the the difference in distances reaches a local minimum (ideally 0) at the minor axis endpoints. So if we detect a decrease between diff[0] and diff[1], and then an increase between diff[1] and the current distance difference, we know the last point was at the minimum. We can use squared distance instead of regular distance, and there's no need to check if we've already found both endpoints because after a single iteration of all the ellipse points you're going to find exactly two local minimum. That code is off the top of my head so someone else might have a cleaner solution, especially for finding local minimums.

Hi Zipster,

Thanks for your reply, and sorry about the crosspost. I thought I had deleted two of them but I guess it didn't go through, I will check that. I am going to code this up in a moment to give it a shot, but is this logic specifically based on the characteristics of an ellipse? I ask because I may get a shape in the future that's not quite an ellipse, but some kind of closed circuit blob. I can definitely still find the maximum diameter, but will what you posted still be able to find the max perpendicular diameter?

Thanks,
Mark

I'm sorry, I was able to delete one of the other posts, but the one says the post is locked?

Quote:

Original post by mark-w I'm sorry, I was able to delete one of the other posts, but the one says the post is locked?

Probably cos someone already replied to it. Don't worry about it, some Mod will clear it up. [smile]

The logic I posted is based on the properties of an ellipse. For arbitrary blobs I think you'll have to iterate all possible perpendicular lines. But you don't have to go through all the edge points again. If you already have the maximum diameter, you can walk that line, and for each point raster a perpendicular line in both directions, and search for the longest line (using Bresenham for rasterization). Out of curiosity, how are you dealing with concavity? Do you check to make sure that the diameter doesn't intersect the blob more than twice, or are you just ignoring it?

No for my application it doesn't matter if the blob is concave, the longest diameter can cross over any concave regions.

I think I'll do what you just mentioned, walk the max diameter line and draw perpendicular lines from each point and see the max that gets intersected.

Alright, at last I have something I can start programming!

Thanks for your help,
Mark