# Hello! Can you help me with this?

3 views (last 30 days)
Stany Stone on 13 Jan 2020
Commented: Stany Stone on 15 Jan 2020
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

darova on 13 Jan 2020
Because i'm simple guy without high education. Can afford it. That is why
Image Analyst on 13 Jan 2020
Can you format your code properly, with the "code" button (so we can click to copy it into the clipboard so that we can paste it into MATLAB), and have just one statement per line?
Stany Stone on 13 Jan 2020

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.

Stany Stone on 13 Jan 2020
I thought you were talking about something else that would result in this:
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.
Stany Stone on 15 Jan 2020
oki, thank you for your answear!

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');

#### 1 Comment

Stany Stone on 15 Jan 2020