Skip to main content
P
ptc-62251211-Visitor
1-Visitor
June 24, 2014
Solved

finding ANY point inside a printed shape

  • June 24, 2014
  • 12 replies
  • 7983 views

Hi a friend's just asked how you find ANY point inside a printed shape without testing mountains of points.

I suggested the simplex method with a dummy objective function but all the trivial examples I've seen consist of (in themselves) unconstrained straight lines that interfere only at suitably appropriate points .e.g to form a nice convenient triangle.

I've attached a diagram of the "feasible" region and as you can see if you continued some of the implied lines forming the edges you'd slice the region to shreds.

My question is how would you represent the truncations of the lines in your system of inequalities.

BTW Assume you're talking to a layman...'cos you ARE! <smile>.

Thank you in anticipation for any forthcoming help.

Dean

Best answer by ptc-6225121

No algorithm in particular i.e. LP was the only one I was aware of that got you a point on the enclosed region. What we're after is ABSOLUTELY ANY x,y point INSIDE the arrow i.e. not on the boundary/lines. My friend said he doesn't want to try lot's of points out so I was looking for a calculated method to get on the boundary. From here it's a question of testing the movement of the point in 8 directions until you find one that moves the point inside the boundary/line. That's all really i.e. no real optimisation as such, just enough to get a feasible solution. I don't know if there's an easier algo to do this?

Again thanks for confirming that line segments/coordinates is our best bet.

12 replies

Werner_E
Werner_E25-Diamond I
25-Diamond I
June 24, 2014

I am not sure what kind of MATHCAD help you would need and in as much this would have to deal with "Statistics & Data Analysis". I would suggest to attach the Mathcad sheet with your problem to show what version you use, what you have done so far and show what you are after.

I've attached a diagram of the "feasible" region and as you can see if you continued some of the implied lines forming the edges you'd slice the region to shreds.

I am not sure what you mean by this and I have no idea what the starting point of your problem would be - a scanned picture, an area given as polygon, ... and also its unclear to me what the endresult should be - a function which decides if a point is in or out, a list of "all" points inside an area, a plot of all points inside the area colored in a distinct color,....

You would first have to state whether we are dealing with vector or pixel graphics (your attachment suggests the latter) and how the boundery of your are will be given.

Generally there are some quite proven and efficient algorithms available, maybe the wellknown, widespread and easy to implement "floodfill" algorithm is what you are looking for.

My question is how would you represent the truncations of the lines in your system of inequalities.

Huuh!??

P
ptc-62251211-VisitorAuthor
1-Visitor
June 24, 2014

Hi

Thank you for your response and for "floodfill".

I have no solution because I don't know how to specify the system of inequalities or even if they are specifiable.

That is my question.

LP finds the optimum solution on the boundary of a region constructed by intersecting lines.

The attached diagram shows two pictures.

One is the typical y=mx+c lines that are not constrained re their extents and typically form a nice convenient triangular region from which you find your solution.

Re the diagram in the first post...the 2nd picture underneath the triangle shows that if that pixel diagram converted to vectors of the same form i.e. y=mx+c.

You can see that in thelr unconstrained form these lines slice up the drawn arrow/region so I'm not sure if or how LP can cope with such a region.

An optimal solution is not required i.e. any point on the boundary of the arrow will do...it's just that LP is the only method I know that takes a system of lines and gives you a point somewhere on the boundary.

if we take the top of the arrow...it's a 4 pixel horizontal line and assuming it was drawn at the top of the screen we could represent it as y=0 but only for x>18 and x<23. Unfortunately, other lines require x to be limited to other values so I can't see how you could rope x into your system so as to limit the length of your lines.

Does that make things any clearer?

BTW I'm not seeing a link to add attachments like I did in the first post

Edit...Ahh you have to post and then Edit and then the Attachment facility is visible.

gary3.png is crude but shows what happens to the arrow region when you don't constrain the extent of the lines that form it's boundary.

This doesn't happen with problems in LP tutorials e.g. like the triangle (shown).

Can LP handle regions shaped like this arrow?

R
RichardJ19-Tanzanite
19-Tanzanite
June 24, 2014

What exactly do you mean by "find any point inside a printed shape"? It's not clear to me what it is you want to do.

Terms & ConditionsAccessibility statement