7
\$\begingroup\$

Let us consider a regular n-sided polygon where all of the sides are equal in length with n being a natural number larger than or equal to three. All of the vertices lie on the unit circle (circle of radius one centered at the origin) and one of the vertices is always at the coordinate (x,y)=(1,0). Now let's draw all possible diagonals (including the edges) which connect all n vertices to one another. Here is an example for n=11.

enter image description here

This results in n-choose-2 (which is just n(n-1)/2) lines (diagonals and edges) which in this case is 55. The total number of line intersections, counting the interior intersection points as well as the n vertices, will be denoted I and I=341 in this case.

The Goal

Your goal is to write a full program or a function which takes in an integer n larger than or equal to three and outputs a list of (x,y) coordinates of all of the intersections of all of the diagonals and edges, that are contained within the regular n-sided polygon with one of its vertices being at (1,0). This includes the n vertices themselves which lie on the unit circle. The length of this list must be I. There is an OEIS sequence for I, which is A007569 and here is a paper which talks about it.

Rules and Specifications

  1. Standard loopholes are forbidden.

  2. Each coordinate has to be an ordered 2-tuple, giving the (x,y) coordinates in the Cartesian system.

  3. The list of coordinates can be in any order. It doesn't have to be sorted or in any particular order.

  4. All of the coordinates provided must be accurate to at least six significant figures. I am not specifying a rounding method. You are free to choose any rounding method or to simply chop off a number. Also for n large enough, it will be the case that two distinct intersections (in exact arithmetic) will be equal to each other to six significant figures in both coordinates (in floating point arithmetic). In this case you are free to treat them as the "same" and remove the "duplicates" from your list. The length of your list will be less than I, but oh well!

  5. The coordinates can be in decimal or scientific notation. For small enough n, decimal notation is fine and decimal notation will make it easier to check so it is preferred. But I am not mandating one over the other.

  6. Outputting I, which should be the length of your coordinate list, is not a requirement for this task. You don't have to output it.

You can assume whatever input/output form that is appropriate for your language. You can also assume that the input will always be a positive integer greater than or equal to three. In case of any other input, your program is free to do whatever it wants. You can also assume that the input and output will always be in the numerical range of your language/environment. Trailing newlines are okay in the output.

Some Test Cases

I am showing more significant digits here than I need to. You are only required to show six. Remember, you don't have to print I.

n => 3

I => 3
(1.000000000,0)
(-0.5000000000,0.8660254038)
(-0.5000000000,-0.8660254038)

n => 4

I => 5
(1.000000000,0)
(0,1.000000000)
(-1.000000000,0)
(0,0)
(0,-1.000000000)

n => 5

I => 10
(1.000000000,0)
(0.3090169944,0.9510565163)
(-0.8090169944,0.5877852523)
(-0.1180339887,0.3632712640)
(0.3090169944,0.2245139883)
(-0.8090169944,-0.5877852523)
(0.3090169944,-0.2245139883)
(-0.1180339887,-0.3632712640)
(0.3090169944,-0.9510565163)
(-0.3819660113,0)

n => 6

I => 19
(1.000000000,0)
(0.5000000000,0.8660254038)
(-0.5000000000,0.8660254038)
(0,0.5773502692)
(0.2500000000,0.4330127019)
(0.5000000000,0.2886751346)
(-1.000000000,0)
(0,0)
(0.5000000000,0)
(-0.5000000000,0)
(-0.5000000000,-0.8660254038)
(0.5000000000,-0.2886751346)
(0.2500000000,-0.4330127019)
(0,-0.5773502692)
(0.5000000000,-0.8660254038)
(-0.5000000000,0.2886751346)
(-0.2500000000,0.4330127019)
(-0.2500000000,-0.4330127019)
(-0.5000000000,-0.2886751346)

n => 7

I => 42
(1.000000000,0)
(0.6234898019,0.7818314825)
(-0.2225209340,0.9749279122)
(0.1539892642,0.6746710485)
(0.3215520661,0.5410441731)
(0.4559270000,0.4338837391)
(0.6234898019,0.3002568637)
(-0.9009688679,0.4338837391)
(-0.05495813209,0.2407873094)
(0.3215520661,0.1548513136)
(0.6234898019,0.08593599577)
(-0.5244586698,0.3479477434)
(-0.2225209340,0.2790324255)
(0.1539892642,0.1930964297)
(-0.9009688679,-0.4338837391)
(0.1539892642,-0.1930964297)
(0.6234898019,-0.08593599577)
(-0.2225209340,-0.2790324255)
(0.3215520661,-0.1548513136)
(-0.5244586698,-0.3479477434)
(-0.05495813209,-0.2407873094)
(-0.2225209340,-0.9749279122)
(0.6234898019,-0.3002568637)
(0.4559270000,-0.4338837391)
(0.3215520661,-0.5410441731)
(0.1539892642,-0.6746710485)
(0.6234898019,-0.7818314825)
(-0.4314683302,0.5410441731)
(-0.2225209340,0.5887350528)
(-0.05495813209,0.6269801688)
(-0.2225209340,0.1071604339)
(0.07941680185,0.3479477434)
(-0.5990311321,-0.1930964297)
(-0.3568958679,0)
(0.2469796037,0)
(0.07941680185,-0.3479477434)
(-0.05495813209,-0.6269801688)
(-0.6920214716,0)
(-0.5990311321,0.1930964297)
(-0.2225209340,-0.1071604339)
(-0.2225209340,-0.5887350528)
(-0.4314683302,-0.5410441731)

I can provide more test cases but they will take up a lot of space and I am not sure how to provide them here. Let me know if you guys need more cases and what is the best way for me to provide them.

Scoring

This is code-golf. The answer with the smallest byte-count will win. In case of a tie, I will pick the answer that was posted earlier as the winner.

Please post your answer in the standard format with all compiler/interpreter options/flags.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Are three-line intersections (such as the center of the hexagon) counted once or twice? \$\endgroup\$
    – Luis Mendo
    Sep 28, 2017 at 10:28
  • \$\begingroup\$ @LuisMendo No matter how many lines intersect at a point, the point is only counted once. \$\endgroup\$
    – Fixed Point
    Sep 28, 2017 at 15:46

2 Answers 2

Reset to default
2
\$\begingroup\$

Python 3, 211 204 bytes

from itertools import*
C=combinations
lambda n:{(round(z.real,6),round(z.imag,6))
          for z in[(a*b*c+a*b*d-a*c*d-b*c*d)/(a*b-c*d)
          for(a,b),(c,d)in C(C([23.140693**(2j*k/n)for k in range(n)],2),2)]
          if abs(z)<=1}

For readability I've added superfluous newlines in my answer that aren't included in the bytecount.

If we have a line crossing through points a and b, and another line crossing through points c and d, where a, b, c, d are complex numbers, then the intersection between those lines (not segments!) is

$$z=\frac{((\overline{b}-\overline{a})a-(b-a)\overline{a})(d-c)-((\overline{d}-\overline{c})c-(d-c)\overline{c})(b-a)}{(d-c)(\overline{b}-\overline{a})-(b-a)(\overline{d}-\overline{c})}$$

But for a point u on the unit circle, the conjugate of u is 1/u. Then the formula simplifies to:

$$z=\frac{abc+abd-acd-bcd}{ab-cd}$$

Now, if the intersection of the two lines also lies within the unit circle, that's a proper intersection of the diagonals.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Mathematica 165 143 112 bytes

53 bytes saved by Misha Lavrov! 22 thanks to his suggestion to use Cases instead of Select. 31 additional bytes saved thanks to his suggestion to use CirclePoints.

(s=Subsets;Union@Cases[RegionIntersection@@@s[Line/@s[N[{1,Pi/2}~CirclePoints~#,8]&@#,{2}],{2}],Point@{x_}:>x])&

Table[{Cos[Pi/2+(2k Pi)/# ],Sin[Pi/2+(2k Pi)/# ]},{k,0,#-1}] generates the coordinates of the vertices of a regular polygon (inscribed in the unit circle) with one vertex at (0,1).

Line segments are then defined for each subsets of possible pairs of those coordinates.

RegionIntersection finds a point of intersection for each pair of these line segments (iff such intersection exists).
Cases[... Point@{x_} :> x] returns the coordinates. Cases in which two segments do not intersect are ignored.

Union eliminates possible duplicates.

Example (n=7)

(s = Subsets; 
Union@Cases[
 RegionIntersection @@@s[Line /@s[N[{1, Pi/2}~CirclePoints~#&@#, {2}], {2}], 
Point@{x_} :> x]) &[7]

{{-0.974928, -0.222521}, {-0.781831, 0.62349}, {-0.674671, 0.153989}, {-0.62698, -0.0549581}, {-0.588735, -0.222521}, \ {-0.541044, -0.431468}, {-0.541044, 0.321552}, {-0.433884, -0.900969}, {-0.433884, 0.455927}, {-0.347948, -0.524459}, {-0.347948, 0.0794168}, {-0.300257, 0.62349}, {-0.279032, -0.222521}, {-0.240787, -0.0549581}, \ {-0.193096, -0.599031}, {-0.193096, 0.153989}, {-0.154851, 0.321552}, {-0.10716, -0.222521}, {-0.085936, 0.62349}, {0., -0.692021}, {0., -0.356896}, {0., 0.24698}, {0., 1.}, {0.085936, 0.62349}, {0.10716, -0.222521}, {0.154851, 0.321552}, {0.193096, -0.599031}, {0.193096, 0.153989}, {0.240787, -0.0549581}, {0.279032, -0.222521}, {0.300257, 0.62349}, {0.347948, -0.524459}, {0.347948, 0.0794168}, {0.433884, -0.900969}, {0.433884, 0.455927}, {0.541044, -0.431468}, {0.541044, 0.321552}, {0.588735, -0.222521}, {0.62698, -0.0549581}, {0.674671, 0.153989}, {0.781831, 0.62349}, {0.974928, -0.222521}}

Graphics[{PointSize[Large], Blue, Point@%}, Axes -> True]

out

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ We can simplify thing somewhat by using Cases instead of Select. Change Select[...,Head@#==Point&] to Cases[...,Point@_] and, as a bonus, we can do the wrapper-removal at the same time by making it Cases[...,Point@{x_}->x]. \$\endgroup\$
    – Misha Lavrov
    Sep 29, 2017 at 3:21
  • \$\begingroup\$ Also, there's a built-in CirclePoints: CirclePoints[#] or CirclePoints@# will get us n evenly spaced points around the unit circle, and CirclePoints[{1,Pi/2},#] or {1,Pi/2}~CirclePoints~# will get us n points rotated so that (1,0) is included. \$\endgroup\$
    – Misha Lavrov
    Sep 29, 2017 at 3:23
  • \$\begingroup\$ @MishaLavrov, First use I've seen of CirclePoints with rotation. You clearly examined the code carefully. Thanks \$\endgroup\$
    – DavidC
    Sep 29, 2017 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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