Hello! Can you help me with this?

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 Thompson]

What do you have so far? If you don't have anything, how would you like to go about solving the problem conceptually?

[Stany Stone]

I already have the loop and the code for the square, but i have a problem with it finding a square with all its four corners on the loop. I thought i could ask and find a different solution to it. I would like a random loop on which squares can be defined through a program that simply looks for them. Do you want to see what i have so far? Would that help?

[Bob Thompson]

Yes, please paste the code you have already. Feel free to expand on the specific issues you're having with reference to the code as well. What kind of results are you seeing, and how are the wrong? Or, if you're getting an error message, copy the entire message as well.

[Stany Stone]

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

I have a problem with making the square have all 4 points on it. I thought i could use the area in green and say that if the other two points are inside it then it means that they could be on the loop, i don't know, it made sense at the time.

[Stany Stone]

I thought it could work, using the area in green, because i saw a 90 degree angle made by it on the south-west side of it and it connects 4 points that could actually make the right square. Do you think it could work?

[darova]

Your code looks strange. Have you seen how codes look usually?

[Stany Stone]

Yes, i've seen. Why are you saying that?

[darova]

Because i'm simple guy without high education. Can afford it. That is why

[Image Analyst]

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]

Done! Sorry about that!

Answer 1

[Bob Thompson]

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]

Well yes, it is complicated :) 1. My problem says that it does not have to be a circle. So yes, i think a circle could work. 2. Those were added so i could move on the loop and kind of know them. 3. 4. And 5. Yes. 6. The other stuff.. I tried to use only one side and not use the negative reciprocal because i couldn't handle going with two squares that weren't okay anyway.

[Bob Thompson]

1) The method I propose would work whether you have a circle or not.

I don't understand how you are getting two squares from the negative reciprocal. By definition, a square is a four sided shape, where each adjacent side is perpendicular, and all four sides have the same length. If you have the slope of one side, then the negative reciprocal of that side is the slope of the adjacent side. How does that result in two squares?

[Stany Stone]

I thought you were talking about something else that would result in this:

[Bob Thompson]

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]

oki, thank you for your answear!

Answer 2

[Image Analyst]

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

[Stany Stone]

Thank you for your answear!