Items tagged with computational-geometry computational-geometry Tagged Items Feed

Not homework (from the telly): A gallery takes a concave polygon shape with a square pillar in the centre. security cameras can do a 360 degree sweep but they can't see around corners. The cameras have to be attached to the walls. What is the fewest number of cameras such that they can see everywhere in the gallery?

I got as far as drawing it in Maple.

there is an algorithm -which supposedly finds the optimal solutuion- breaking the object into triangular shapes. that gets an answer:  4 cameras.

EDIT 11/10

this is based on Fisk's short proof. See Markiyan's wiki ref below.

1.first stand on on a corner and scan clockwise around the room. Any two corners passed creates one triangle.

Repeat for every corner


2. Pick three colours and allocate each color to each corner of each triangle.

sometimes you will end up with a triangle which has 2 corners of the same colour. This one has two blue corners


This triangle must be broken in two and add a green dot

3.finally the algorithm places cameras on the colour which occurs least.

But by experimenting with more complex shapes (convex polygons) you can cover the gallery with 3.


In Maple anyone?


Let a planar polygon P without selfintersections be given through the plottools:-polygon command.
How to find its triangulation as a set of triangles (The indication of common sides is desired too.) in an optimal way with Maple? This is used in the finite element method.


Let a finite set of closed intervals in the plane be given.
How to find all the intersections of these, outputing the intersection points together with the intersecting intervals?
This is a problem of computational geometry
In other words, how to realize the sweep line algorithm in Maple?

PS. I'd like to note that computational geometry has serious applications, in particular, in robotics.

Let  us consider the general case of symbolic values C(xC,yC). I make use of the idea suggested by edgar in : no assumptions.

restart; with(geometry); point(A, 0, 0);
point(B, 1, 0);
point(C, xC, yC);
point(MA, (xC+1)*(1/2), (1/2)*yC);
point(MC, 1/2, 0);
point(MB, (1/2)*xC, (1/2)*yC);
point(E, (0+1+xC)*(1/3), (0+0+yC)*(1/3));# the center of mass
line(l1, x = 1/4, [x, y]);
The coordinates of the center of the first described circle are found as the solutions of the system of the equations of midperpendiculars.

midpoint(ae, A, E); coordinates(ae);

S1 := solve({x = 1/4, ((xC+1)*(1/3))*(x-(xC+1)*(1/6))+(1/3)*yC*(y-(1/6)*yC) = 0}, {x, y});

BTW, Maple can't create the midperpendiculars in this case.

point(O1, op(map(rhs, S1)));

Simple details are omitted in the above. The coordinates of the centers of the two next described circles are found similarly.
coordinates(midpoint(mce, MC, E));

S2 := solve({x = 3/4, ((-1/2+xC)*(1/3))*(x-5/12-(1/6)*xC)+(1/3)*yC*(y-(1/6)*yC) = 0}, {x, y});

point(O2, op(map(rhs, S2)));

coordinates(midpoint(bma, B, MA)); coordinates(midpoint(be, B, E));


S3 := solve({(xC-1)*(x-(xC+3)*(1/4))+yC*(y-(1/4)*yC) = 0, ((-2+xC)*(1/3))*(x-(4+xC)*(1/6))+(1/3)*yC*(y-(1/6)*yC) = 0}, {x, y});

point(O3, op(map(rhs, S3)));


Now we find the equation of the circumference which passes through O1, O2, and O3.

eq := a*x+b*y+x^2+y^2+c = 0:
sol := solve({eval(eq, S1), eval(eq, S2), eval(eq, S3)}, {a, b, c});

A long output can be seen in the attached .mw file.

eq1 := eval(eq, sol);

  Now we find (in suspense)  the coordinates of the next center and verify whether it belongs to the sircumference O1O2O3.

coordinates(midpoint(mac, C, MA)); coordinates(midpoint(ec, E, C)); S4 := solve({(xC-1)*(x-(3*xC+1)*(1/4))+yC*(y-3*yC*(1/4)) = 0, ((2*xC-1)*(1/3))*(x-(4*xC+1)*(1/6))+(2*yC*(1/3))*(y-4*yC*(1/6)) = 0}, {x, y});

 point(O4, op(map(rhs, S4)));

simplify(eval(eq1, S4));

                             0 = 0

Hope the reader will have a real pleasure to find the two residuary centers and to verify these on his/her own.





It is well known that the medians of a triangle divide it into 6 triangles.
It is less known that the centers of their circumscribed circles belong to one circumference as drawn below

This remarkable theorem  was proved in the 21st century! Unfortunately, I lost its source.
I can't prove this difficult  theorem by hand. However, I can prove it with Maple.
The aim of this post is to expose these proofs. Everybody knows that it is scarcely possible
to construct a general triangle with help of the geometry package of Maple.
Without loss of generality one may assume that the vertex A is placed at the origin,
the vertex B is placed at (1,0), and the vertex C(xC,yC). We firstly consider the theorem
in the case of concrete values of xC and yC.

restart; with(geometry):with(plots):
point(A, 0, 0);
point(B, 1, 0);
xC := 15*(1/10); yC := sqrt(3); point(C, xC, yC);
triangle(T, [A, B, C]);
median(mA, A, T, MA);
median(mB, B, T, MB);
median(mC, C, T, MC);
line(m1, [A, MA]);
line(m2, [B, MB]);
intersection(E, m1, m2);
triangle(AEMB, [A, E, MB]);
circumcircle(c1, AEMB, 'centername' = C1);
circumcircle(c2, triangle(CEMB, [C, E, MB]), 'centername' = C2);
circumcircle(c3, triangle(CEMA, [C, E, MA]), 'centername' = C3);
circumcircle(c4, triangle(BEMA, [B, E, MA]), 'centername' = C4);
circumcircle(c5, triangle(BEMC, [B, E, MC]), 'centername' = C5);
circumcircle(c6, triangle(AEMC, [A, E, MC]), 'centername' = C6);
circle(CC, [C1, C2, C3]);
IsOnCircle(C4, CC);

IsOnCircle(C5, CC);
IsOnCircle(C6, CC);
display([draw([T(color = black), mA(color = black), mB(color = black), mC(color = black), C1(color = blue), C2(color = blue), C3(color = blue), C4(color = blue), C5(color = blue), C6(color = blue), CC(color = red)], symbol = solidcircle, symbolsize = 15, thickness = 2, scaling = constrained), textplot({[-0.5e-1, 0.5e-1, "A"], [.95, 0.5e-1, "B"], [xC-0.5e-1, yC+0.5e-1, "C"]})], axes = frame, view = [-.1 .. max(1, xC)+.1, 0 .. yC+.1]);

This can be done as a procedure in such a way.

restart; SixPoints := proc (xC, yC) geometry:-point(A, 0, 0); geometry:-point(B, 1, 0); geometry:-point(C, xC, yC); geometry:-triangle(T, [A, B, C]); geometry:-median(mA, A, T, MA); geometry:-median(mB, B, T, MB); geometry:-median(mC, C, T, MC); geometry:-line(m1, [A, MA]); geometry:-line(m2, [B, MB]); geometry:-intersection(E, m1, m2); geometry:-triangle(AEMB, [A, E, MB]); geometry:-circumcircle(c1, AEMB, 'centername' = C1); geometry:-circumcircle(c2, geometry:-triangle(CEMB, [C, E, MB]), 'centername' = C2); geometry:-circumcircle(c3, geometry:-triangle(CEMA, [C, E, MA]), 'centername' = C3); geometry:-circumcircle(c4, geometry:-triangle(BEMA, [B, E, MA]), 'centername' = C4); geometry:-circumcircle(c5, geometry:-triangle(BEMC, [B, E, MC]), 'centername' = C5); geometry:-circumcircle(c6, geometry:-triangle(AEMC, [A, E, MC]), 'centername' = C6); geometry:-circle(CC, [C1, C2, C3]); return geometry:-IsOnCircle(C4, CC), geometry:-IsOnCircle(C5, CC), geometry:-IsOnCircle(C6, CC), geometry:-draw([CC(color = blue), C1(color = red), C2(color = red), C3(color = red), C4(color = red), C5(color = red), C6(color = red), T(color = black), mA(color = black), mB(color = black), mC(color = black), c1(color = green), c4(color = green), c2(color = green), c3(color = green), c5(color = green), c6(color = green)], symbol = solidcircle, symbolsize = 15, thickness = 2) end proc;
SixPoints(1.5, 1.2);

true, true, true, PLOT(...)
 SixPoints(1.5, 1.2)[4];


To be continued (The general case will be considered in  part 2 .).




I have a linear space spanned by the column vectors of:

I want to know its exact intersection of the first quadrant in 16 dimensional space (meaning Sum(a[i]*e[i]),i=1..16), how could I accomplish it? The output could possibly be the vectors defining the convex cone in higher dimensional space...



My question is: how to find the coordinates of the vertices of a dodecahedron?
I can find the  coordinates of the vertices of a tetrahedron as the solutions of a certain polynomial system in 8 variables (see for details).
However, that approach seems not to work for a dodecahedron. A new idea is required.

PS. Of course, I have in mind a regular dodecadron.

Here 'show triangle napoleon considering the sintaxis Maple, to be supplemented and explained with Math Apps.


Lenin Araujo Castillo

This is my question that I posted at "I want to find the numbers $a$, $b$, $c$, $d$ of the function $y = \dfrac{a x + b}{c x + d}$ so that the triangle $ABC$ with three points  $A$, $B$, $C$  have integer coordinates and lies on the graph of the given function, then the centroid of the triangle $ABC$ (have also integer coordinates) is also lies on the graph". The ansewr at that site...

A user community of Maple I leave one of my contributions to the advancement of science. Here you see the true use of Mathematics in its real dimension Geometric. Just need to improve it with Components someone can help?

A more serious formulation is the following. Let us consider the cartesian product
 {1, 2, 3, 4, 5, 6, 7, 8} x {1, 2, 3, 4, 5, 6, 7, 8} as a subset of the plane xOy. What is its maximal subset which does not include three points belonging to a straight line? How to find this with Maple? I don't know the answer. My hypothesis is the number of the elements of that set is about 10.

Page 1 of 1