For a personal project involving a coordinate system for navigating the galaxy using 36/38 equidistant points around a circle, I need to find all intersections between 3+ lines using 3 pairs of points (6 unique points) so that it makes a valid "Address", I have looked up many articles on this website and all that I could find involved intersections between two lines only.

I started off doing this to visualize the lines themselves:

lines = CirclePoints[36];
Graphics[{Black, Line@Subsets[lines, {2}]}]

Then I managed to adapt the code to show two line intersections:


The code above works for less than 21 points but any higher and it displays nothing, I suspect its because of an old function, aside from that issue I am lost on how to check specifically for 3+ line intersections while ignoring just 2 line ones, is such a thing possible?


1 Answer 1



Here we fixed one point say pts[[1]] and let the other 5 points are the subset of remain points,but it still take a long times. We only test n=18 or n=20.

k = 9;
n = 2 k;
pts = CirclePoints[n];
lines = Line /@ Subsets[pts, {2}];
sixsubsets = Prepend[1] /@ Subsets[Range[2, n], {5}];
intersectionpts = 
  RegionIntersection[Line[{pts[[#1]], pts[[#4]]}], 
     Line[{pts[[#2]], pts[[#5]]}], Line[{pts[[#3]], pts[[#6]]}]] & @@@
Cases[intersectionpts, Except[EmptyRegion[2]]];
      RotationTransform[j*2 π/n]] & /@ %, {j, 1, n}]];
Graphics[{lines, {Red, %}}]

enter image description here

enter image description here

Not so effective,only provide a possible way.

pts = CirclePoints[12];
lines = Line /@ Subsets[pts, {2}];
sixsubsets = {Line[{#1, #4}], Line[{#2, #5}], Line[{#3, #6}]} & @@@ 
   Subsets[pts, {6}];
intersections = RegionIntersection @@@ sixsubsets;
Graphics[{lines, {Red, intersections}}]

enter image description here

enter image description here

enter image description here

  • $\begingroup$ Is it possible to reduce the # of comparisons by checking intersections on 1/nth of the circle? intersections are symmetrical on 2pi/n, so perhaps checking all intersections between one set of adjacent points aka(point 1 to n other) and (point 2 to n other) with the third line being created between any two points where atleast one is on the same hemisphere as the initial 2 adjacent points. e.g. 12 points, pick point 1&2, make subsets where lines are (1, [3 -11]) and (2, [4-12]) with the last list ([3,4,11,12], [3-12] ). Compare for intersects, then duplicate and rotate by pi/6. $\endgroup$ Jun 30, 2021 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.