How to determine the longest edge in a graph?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
I have a list of 2D points such as in the image.
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0,
5;
I would like to determine the longest "edge" length in a way that if 2 segments are in same line, they would be considered as part of 1 edge. For example, segments 1-2, 2-3, 3-4 are continuous and in the same line, so we consider it as 1 edge connecting Vertex 1 and Vertex 4. In this example, the longest edge length would be the distance from vertex 1 to vertex 4. How can I determine the longest edge length in Mathematica?
list-manipulation graphics
$endgroup$
add a comment |
$begingroup$
I have a list of 2D points such as in the image.
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0,
5;
I would like to determine the longest "edge" length in a way that if 2 segments are in same line, they would be considered as part of 1 edge. For example, segments 1-2, 2-3, 3-4 are continuous and in the same line, so we consider it as 1 edge connecting Vertex 1 and Vertex 4. In this example, the longest edge length would be the distance from vertex 1 to vertex 4. How can I determine the longest edge length in Mathematica?
list-manipulation graphics
$endgroup$
add a comment |
$begingroup$
I have a list of 2D points such as in the image.
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0,
5;
I would like to determine the longest "edge" length in a way that if 2 segments are in same line, they would be considered as part of 1 edge. For example, segments 1-2, 2-3, 3-4 are continuous and in the same line, so we consider it as 1 edge connecting Vertex 1 and Vertex 4. In this example, the longest edge length would be the distance from vertex 1 to vertex 4. How can I determine the longest edge length in Mathematica?
list-manipulation graphics
$endgroup$
I have a list of 2D points such as in the image.
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0,
5;
I would like to determine the longest "edge" length in a way that if 2 segments are in same line, they would be considered as part of 1 edge. For example, segments 1-2, 2-3, 3-4 are continuous and in the same line, so we consider it as 1 edge connecting Vertex 1 and Vertex 4. In this example, the longest edge length would be the distance from vertex 1 to vertex 4. How can I determine the longest edge length in Mathematica?
list-manipulation graphics
list-manipulation graphics
asked Jan 3 at 10:53
N.T.CN.T.C
44128
44128
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Update: The function in the original answer does not work for arbitrary polygons. The following seems to work
ClearAll[nonCollinearHull]
nonCollinearHull = Module[coords = #,
angles = ArcTan @@@ (Subtract @@@ Partition[#, 2, 1 , 1, 1]),
rotation, lengths,
rotation = LengthWhile[Reverse[angles], # == angles[[1]] &];
lengths = Length /@ Split[RotateRight[angles, rotation]];
TakeList[RotateRight[coords, rotation], lengths][[All, 1]]] &;
Examples:
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0, 5;
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Using
SeedRandom[123]
coord2 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] & @
DeleteDuplicates@RandomInteger[10, 50, 2];
we get
And with
SeedRandom[123]
coord3 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] &@
DeleteDuplicates@RandomInteger[20, 200, 2]];
Alternatively, you can use MaximalBy
to define longest
:
SeedRandom[777777]
coord = MapIndexed[#2[[1]], # &, Accumulate[RandomInteger[-2, 2, 50]]];
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = MaximalBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Line@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Original answer:
Using the function noncollinearF
from this answer:
ClearAll[noncollinearF]
noncollinearF[verts_] := Function[k, Nor @@ (RegionMember[ConvexHullMesh[#], k] & /@
Subsets[Complement[verts, k], 2])]
lines = Line /@ Partition[Pick[#, noncollinearF[#] /@ #], 2, 1, 1, 1]& @ coord;
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord,
Blue, PointSize[Large], Point@coord,
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
$endgroup$
$begingroup$
WhyConvexHullMesh
and not justLine
?
$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. TryRotateLeft[coord, 2]
for the original example.
$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f188760%2fhow-to-determine-the-longest-edge-in-a-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Update: The function in the original answer does not work for arbitrary polygons. The following seems to work
ClearAll[nonCollinearHull]
nonCollinearHull = Module[coords = #,
angles = ArcTan @@@ (Subtract @@@ Partition[#, 2, 1 , 1, 1]),
rotation, lengths,
rotation = LengthWhile[Reverse[angles], # == angles[[1]] &];
lengths = Length /@ Split[RotateRight[angles, rotation]];
TakeList[RotateRight[coords, rotation], lengths][[All, 1]]] &;
Examples:
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0, 5;
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Using
SeedRandom[123]
coord2 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] & @
DeleteDuplicates@RandomInteger[10, 50, 2];
we get
And with
SeedRandom[123]
coord3 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] &@
DeleteDuplicates@RandomInteger[20, 200, 2]];
Alternatively, you can use MaximalBy
to define longest
:
SeedRandom[777777]
coord = MapIndexed[#2[[1]], # &, Accumulate[RandomInteger[-2, 2, 50]]];
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = MaximalBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Line@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Original answer:
Using the function noncollinearF
from this answer:
ClearAll[noncollinearF]
noncollinearF[verts_] := Function[k, Nor @@ (RegionMember[ConvexHullMesh[#], k] & /@
Subsets[Complement[verts, k], 2])]
lines = Line /@ Partition[Pick[#, noncollinearF[#] /@ #], 2, 1, 1, 1]& @ coord;
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord,
Blue, PointSize[Large], Point@coord,
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
$endgroup$
$begingroup$
WhyConvexHullMesh
and not justLine
?
$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. TryRotateLeft[coord, 2]
for the original example.
$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
add a comment |
$begingroup$
Update: The function in the original answer does not work for arbitrary polygons. The following seems to work
ClearAll[nonCollinearHull]
nonCollinearHull = Module[coords = #,
angles = ArcTan @@@ (Subtract @@@ Partition[#, 2, 1 , 1, 1]),
rotation, lengths,
rotation = LengthWhile[Reverse[angles], # == angles[[1]] &];
lengths = Length /@ Split[RotateRight[angles, rotation]];
TakeList[RotateRight[coords, rotation], lengths][[All, 1]]] &;
Examples:
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0, 5;
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Using
SeedRandom[123]
coord2 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] & @
DeleteDuplicates@RandomInteger[10, 50, 2];
we get
And with
SeedRandom[123]
coord3 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] &@
DeleteDuplicates@RandomInteger[20, 200, 2]];
Alternatively, you can use MaximalBy
to define longest
:
SeedRandom[777777]
coord = MapIndexed[#2[[1]], # &, Accumulate[RandomInteger[-2, 2, 50]]];
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = MaximalBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Line@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Original answer:
Using the function noncollinearF
from this answer:
ClearAll[noncollinearF]
noncollinearF[verts_] := Function[k, Nor @@ (RegionMember[ConvexHullMesh[#], k] & /@
Subsets[Complement[verts, k], 2])]
lines = Line /@ Partition[Pick[#, noncollinearF[#] /@ #], 2, 1, 1, 1]& @ coord;
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord,
Blue, PointSize[Large], Point@coord,
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
$endgroup$
$begingroup$
WhyConvexHullMesh
and not justLine
?
$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. TryRotateLeft[coord, 2]
for the original example.
$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
add a comment |
$begingroup$
Update: The function in the original answer does not work for arbitrary polygons. The following seems to work
ClearAll[nonCollinearHull]
nonCollinearHull = Module[coords = #,
angles = ArcTan @@@ (Subtract @@@ Partition[#, 2, 1 , 1, 1]),
rotation, lengths,
rotation = LengthWhile[Reverse[angles], # == angles[[1]] &];
lengths = Length /@ Split[RotateRight[angles, rotation]];
TakeList[RotateRight[coords, rotation], lengths][[All, 1]]] &;
Examples:
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0, 5;
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Using
SeedRandom[123]
coord2 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] & @
DeleteDuplicates@RandomInteger[10, 50, 2];
we get
And with
SeedRandom[123]
coord3 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] &@
DeleteDuplicates@RandomInteger[20, 200, 2]];
Alternatively, you can use MaximalBy
to define longest
:
SeedRandom[777777]
coord = MapIndexed[#2[[1]], # &, Accumulate[RandomInteger[-2, 2, 50]]];
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = MaximalBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Line@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Original answer:
Using the function noncollinearF
from this answer:
ClearAll[noncollinearF]
noncollinearF[verts_] := Function[k, Nor @@ (RegionMember[ConvexHullMesh[#], k] & /@
Subsets[Complement[verts, k], 2])]
lines = Line /@ Partition[Pick[#, noncollinearF[#] /@ #], 2, 1, 1, 1]& @ coord;
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord,
Blue, PointSize[Large], Point@coord,
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
$endgroup$
Update: The function in the original answer does not work for arbitrary polygons. The following seems to work
ClearAll[nonCollinearHull]
nonCollinearHull = Module[coords = #,
angles = ArcTan @@@ (Subtract @@@ Partition[#, 2, 1 , 1, 1]),
rotation, lengths,
rotation = LengthWhile[Reverse[angles], # == angles[[1]] &];
lengths = Length /@ Split[RotateRight[angles, rotation]];
TakeList[RotateRight[coords, rotation], lengths][[All, 1]]] &;
Examples:
coord = 0, 0, 10, 0, 20, 0, 30, 0, 25, 10, 0, 10, 0, 5;
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Using
SeedRandom[123]
coord2 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] & @
DeleteDuplicates@RandomInteger[10, 50, 2];
we get
And with
SeedRandom[123]
coord3 = DeleteDuplicates[#[[FindShortestTour[#][[2]]]] &@
DeleteDuplicates@RandomInteger[20, 200, 2]];
Alternatively, you can use MaximalBy
to define longest
:
SeedRandom[777777]
coord = MapIndexed[#2[[1]], # &, Accumulate[RandomInteger[-2, 2, 50]]];
lines = Line /@ Partition[nonCollinearHull[coord], 2, 1];
longest = MaximalBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Line@coord, Blue,
PointSize[Large], Point@coord, Opacity[.5, Green],
AbsolutePointSize[15], Point[nonCollinearHull[coord]],
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
Original answer:
Using the function noncollinearF
from this answer:
ClearAll[noncollinearF]
noncollinearF[verts_] := Function[k, Nor @@ (RegionMember[ConvexHullMesh[#], k] & /@
Subsets[Complement[verts, k], 2])]
lines = Line /@ Partition[Pick[#, noncollinearF[#] /@ #], 2, 1, 1, 1]& @ coord;
longest = Last@SortBy[lines, N@ArcLength[#] &];
Graphics[EdgeForm[Gray], FaceForm, Polygon@coord,
Blue, PointSize[Large], Point@coord,
Thickness[.03], CapForm["Round"], Opacity[.5], Red, longest]
edited Jan 5 at 11:04
answered Jan 3 at 11:54
kglrkglr
179k9198410
179k9198410
$begingroup$
WhyConvexHullMesh
and not justLine
?
$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. TryRotateLeft[coord, 2]
for the original example.
$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
add a comment |
$begingroup$
WhyConvexHullMesh
and not justLine
?
$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. TryRotateLeft[coord, 2]
for the original example.
$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
$begingroup$
Why
ConvexHullMesh
and not just Line
?$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
Why
ConvexHullMesh
and not just Line
?$endgroup$
– swish
Jan 4 at 7:18
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. Try
RotateLeft[coord, 2]
for the original example.$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
It breaks if a coordinate list starts in the middle of the longest edge. Try
RotateLeft[coord, 2]
for the original example.$endgroup$
– swish
Jan 4 at 7:45
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
$begingroup$
@swish, thank you. Updated with an alternative that does not have the issue.
$endgroup$
– kglr
Jan 4 at 19:47
add a comment |
Thanks for contributing an answer to Mathematica Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f188760%2fhow-to-determine-the-longest-edge-in-a-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown