19 views (last 30 days)

I have to write a program that will solve the Inscribed Square Problem. The loop doesn't have to be a circle but it must contain at least a square with its four corners on it.

[Image Analyst edit -- added code from a now hidden comment]

fontSize = 15;

x = [5.5, 6, 4.5, 3.5, 5, 5, 3, 2, 2.5, 3, 2, 2.5, 4, 5, 4.5]

y = [3, 2, 2.5, 1.5, 1.5, 1, 0.5, 1, 2, 3, 4, 4.5, 5, 4, 3.5]

% Append first point to last to close the curve

x = [x, x(1)];

y = [y, y(1)];

plot(x, y, 'r*');

grid on;

knots = [x; y];

areaOfPolygon = polyarea(x,y);

numberOfPoints = length(x);

% Interpolate with a spline curve and finer spacing.

originalSpacing = 1 : numberOfPoints;

% Make 9 points in between our original points that the user clicked on.

finerSpacing = 1 : 0.1 : numberOfPoints;

% Do the spline interpolation.

splineXY = spline(originalSpacing, knots, finerSpacing);

% Plot the interpolated curve.

hold off;

plot(knots(1, :), knots(2, :), 'ro', 'LineWidth', 2, 'MarkerSize', 16);

hold on;

plot(splineXY(1, :), splineXY(2, :), 'b+-', 'LineWidth', 2, 'MarkerSize', 8);

title('Blue Spline Between Red Knots', 'FontSize', fontSize);

legend('Knots', 'Spline');

xlabel('X', 'FontSize', fontSize);

ylabel('Y', 'FontSize', fontSize);

grid on;

hold on;

% Get a known index. "known" because it's one of the training points.

knownIndex = randperm(length(x), 1)

% Get a unknown index. "unknown" because it's one of the interpolated points.

unknownIndex = randperm(length(finerSpacing), 1)

% Get the x,y coordinates for these indexes.

xKnown = knots(1, knownIndex)

yKnown = knots(2, knownIndex)

xUnknown = splineXY(1, unknownIndex)

yUnknown = splineXY(2, unknownIndex)

%define the distance between the two points

A=[xKnown, yKnown]

B=[xUnknown, yUnknown]

AB=sqrt((xKnown-splineXY(1, unknownIndex))^2+(yKnown-splineXY(2, unknownIndex))^2)

% Now draw a line between them in dark green.

darkGreen = [0, 0.5, 0];

plot([xKnown, xUnknown], [yKnown, yUnknown], 'o-', ...

'Color', darkGreen, 'MarkerSize', 24, 'LineWidth', 3);

legend('Knots', 'Spline', 'Line between random knot and random point')

unkownIndex1= randperm(length(finerSpacing), 1)

hold on

% slope of oldL

slope = (yKnown - yUnknown)./(xKnown - xUnknown);

% slope and tilt angle of newL

perSlope = -1/slope;

perTheta = atan(perSlope);

% set the lenght of line segment you want to add to the figure

lineLength = 2*AB;

halfLineLength = lineLength/2;

% calculate the end points of a newL based on the Known points of oldL

xPerKnown = [xKnown + halfLineLength*cos(perTheta), ...

xKnown - halfLineLength*cos(perTheta)];

yPerKnown = [yKnown + halfLineLength*sin(perTheta), ...

yKnown - halfLineLength*sin(perTheta)];

% calculate the ends points of another newL based on the Unknown points of oldL

xPerUnknown = [xUnknown + halfLineLength*cos(perTheta), ...

xUnknown - halfLineLength*cos(perTheta)];

yPerUnknown = [yUnknown + halfLineLength*sin(perTheta), ...

yUnknown - halfLineLength*sin(perTheta)];

xPerKnown(1) = [xKnown + halfLineLength*cos(perTheta)]

xPerKnown(2)=[xKnown - halfLineLength*cos(perTheta)];

yPerKnown(1)= [yKnown + halfLineLength*sin(perTheta)]

yPerKnown(2)=[yKnown - halfLineLength*sin(perTheta)];

% calculate the ends points of another newL based on the Unknown points of oldL

xPerUnknown(1) = [xUnknown + halfLineLength*cos(perTheta)]

xPerUnkown(2)=[xUnknown - halfLineLength*cos(perTheta)];

yPerUnknown(1) = [yUnknown + halfLineLength*sin(perTheta)]

yPerUnknown(2)=[yUnknown - halfLineLength*sin(perTheta)];

% draw these two newL

plot([xPerKnown(1), xKnown], [yPerKnown(1), yKnown], 'o-', ...

'Color', darkGreen, 'MarkerSize', 24, 'LineWidth', 3);

plot([xPerUnknown(1), xUnknown], [yPerUnknown(1), yUnknown], 'o-', ...

'Color', darkGreen, 'MarkerSize', 24, 'LineWidth', 3);

% set the unit length of two axis to be equal, to get a clear visualization of 90 degree

axis equal

plot([xPerKnown(1),xUnknown + halfLineLength*cos(perTheta)],[yPerKnown(1),yUnknown + halfLineLength*sin(perTheta)],'o-','Color', darkGreen, 'MarkerSize', 24, 'LineWidth', 3)

patch(x,y, 'black', 'FaceColor', 'green', 'FaceAlpha', 0.1);

xv=[xPerKnown(1),xPerUnknown(1)]

yv=[yPerKnown(1),yPerUnknown(1)]

[in,on] = inpolygon(x,y, xv,yv); % Logical Matrix

inon = in | on; % Combine ‘in’ And ‘on’

idx = find(inon(:)); % Linear Indices Of ‘inon’ Points

xcoord = x(idx); % X-Coordinates Of ‘inon’ Points

ycoord = y(idx); % Y-Coordinates Of ‘inon’ Points

figure(1)

plot(x, y, 'bp') % Plot All Points

hold on

plot(xv, yv, '-r') % Plot Polygon

plot(xcoord, ycoord, 'gp')

coefficients = polyfit(x, y, 1);

yFit = polyval(coefficients, x);

residualsSum = sum(abs(yFit - y))

if (residualsSum ==0)

% They're considered to be on a line

else

f=msgbox('no line','continue') % They are not considered to be on a line.

end

Bob Nbob
on 13 Jan 2020

Edited: Bob Nbob
on 13 Jan 2020

It seems to me like you're totally overcomplicating this. Let me know if I'm interpretting the steps of your code correctly.

Things you do:

1) Make a circle with some points

2) Interpolate extra points to make it more circular

3) Randomly pick an original and interpolated point

4) Make a line between the two chosen points

5) Get the slope between the two points

6) Some other stuff...

Because you have calculated the slope of the first side, you can get the slop of the two perpendicular sides by taking the negative reciprocal. With that, and the two endpoints of your first side, you can define the opposite endpoints of the sides relatively easily. With those four points you now have your box.

Bob Nbob
on 13 Jan 2020

No, I meant only going one direction or the other at a time. In the particular answer you show the right side will never connect with the shape again, and the left doesn't form a square, so this isn't a viable option, but the idea remains the same.

From incorporating the slope of your new sides it would be relatively easy to check if the appropriate length (distance between first two points) is also on the random curve. If it is then you're in business, if not then that particular random iteration doesn't work.

Sign in to comment.

Image Analyst
on 13 Jan 2020

Edited: Image Analyst
on 13 Jan 2020

Here's a start. Snippet to draw points and fit a spline curve through them with a lot more points:

numPoints = 7;

hFig = figure;

axis on;

grid on;

promptMessage = sprintf('Please specify the %d points,\nor Quit processing?', numPoints);

titleBarCaption = 'Continue?';

buttonText = questdlg(promptMessage, titleBarCaption, 'Continue', 'Quit', 'Continue');

if contains(buttonText, 'Quit')

% Close the figure window.

close(hFig);

return;

end

xy = zeros(numPoints, 2);

for k = 1 : numPoints

caption = sprintf('Click point #%d of %d', k, numPoints);

title(caption, 'FontSize', fontSize, 'Interpreter', 'none');

roi = drawpoint('Color', 'y');

xy(k, :) = roi.Position;

end

x = xy(:, 1)

y = xy(:, 2)

% Use splines to interpolate a smoother curve,

% with 10 times as many points,

% that goes exactly through the same data points.

samplingRateIncrease = 10;

newXSamplePoints = linspace(1, length(x), length(x) * samplingRateIncrease);

newYSamplePoints = linspace(1, length(y), length(y) * samplingRateIncrease);

smoothedX = spline(1:length(x), x, newXSamplePoints);

smoothedY = spline(1:length(y), y, newYSamplePoints);

% Close the curve

smoothedX(end+1) = smoothedX(1);

smoothedY(end+1) = smoothedY(1);

% Plot smoothed curve and show how the line is

% smooth, and has no sharp bends.

plot(x, y, 'r.', 'MarkerSize', 25);

grid on;

hold on; % Don't destroy the first curve we plotted.

plot(smoothedX, smoothedY, '-ob');

title('Spline Interpolation Demo', 'FontSize', 20);

legend('Original Points', 'Spline Points');

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 10 Comments

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785600

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785600

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785626

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785626

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785630

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785630

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785639

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785639

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785664

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785664

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785674

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785674

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785697

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785697

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785704

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785704

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785754

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785754

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785759

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/500063-hello-can-you-help-me-with-this#comment_785759

Sign in to comment.