25
\$\begingroup\$

Introduction

The \$n\$-ellipse is a generalization of the ellipse with possibly more than two foci. Specifically, given \$n\$ points on the plane, called foci, the \$n\$-ellipse is the set of points of the plane whose sum of distances to the \$n\$ foci is equal to a constant \$t\$.

This challenge is about plotting the \$n\$-ellipse together with its interior; that is, the set of points whose sum of distances to the \$n\$ foci is less than or equal to equal to \$t\$. Note that the resulting set is always convex.

To simplify, only points with integer coordinates need to be considered.

The challenge

Input:

  • Number of points \$n\$: positive integer;
  • List of \$n\$ foci (possibly repeated) with integer coordinates, \$(x_1, y_1)\$, ..., \$(x_n, y_n)\$;
  • Threshold \$t\$: positive integer.

Output:

An image representing all points \$P\$ with integer coordinates such the sum of Euclidean distances from \$P\$ to the \$n\$ foci is less than or equal to \$t\$.

Each pixel in the image should correspond to a point with integer coordinates; that is, pixel size is \$1 \times 1\$. Alternatively, you can use a finer resolution (smaller pixels), or vector graphics.

The image should consistently use two different colours for points satisfying the condition ("active" pixels) or not satisfying it ("inactive").

Additional rules

  • Graphical output is required, in any format. (ASCII art is not allowed because of size limitations and aspect ratio).

  • Both axes should have the same scale. The \$x\$ axis should be horizontal, and can consistently increase left to right or right to left. Similarly, the \$y\$ axis should be vertical and can consistently increase upwards or downwards.

  • Axis labels, auxiliary grid lines and similar elements are allowed.

  • The output image can have an arbitrarily large "frame" of inactive pixels around the set of active pixels.

  • The set of active points is guaranteed to be non-empty.

  • Input format is flexible as usual. A program or a function can be provided. Standard loopholes are forbidden.

  • The code should work in theory for inputs containing arbitrarily large numbers. In practice, it is acceptable if the program is limited by time, memory or data-type restrictions.

  • Shortest code in bytes wins.

Test cases

Input is shown as a list of \$n\$ foci defined as coordinate pairs, followed by \$t\$, and an optional comment.

In the output images, \$x\$ axis increases left to right, \$y\$ axis increases upwards.

(5,8), 100  % A circle

enter image description here

(0,0), (70, 150), 220  % An ellipse

enter image description here

(-100, 0), (100, 0), (100, 0), 480  % Repeated point

enter image description here

(-90, -90), (-90, 90), (90, -90), (90, 90), (90, -90), 670  % Repeated; arbitrary order

enter image description here

(200, 600), (320, -60), (-350, 220), (-410, 130), (40, -140), 2100

enter image description here

(-250, -250), (-250, 250), (250, -250), 1000

enter image description here

(-250, -250), (-250, 250), (250, -250), 1200

enter image description here

(-390, 0), (-130, 120), (130, -120), (390, 0), 1180  % Finally, a pair of lips?

enter image description here

\$\endgroup\$
  • 3
    \$\begingroup\$ Sorry for a week title \$\endgroup\$ – Luis Mendo Mar 4 at 11:11
  • \$\begingroup\$ I read through the link on acceptable input/output methods. Can we output a gray-scale image in the format of a matrix of floats between 0 and 1? \$\endgroup\$ – RGS Mar 4 at 14:31
  • 2
    \$\begingroup\$ Now I know where guitar picks come from! \$\endgroup\$ – Kaddath Mar 4 at 16:07
  • 1
    \$\begingroup\$ @Kaddath Those were my thoughts too (guitar player here) \$\endgroup\$ – Luis Mendo Mar 4 at 16:30
  • 1
    \$\begingroup\$ @LuisMendo What about this? By the way, I like the title. \$\endgroup\$ – David Conrad Mar 7 at 0:16

11 Answers 11

6
\$\begingroup\$

Jelly, 36 35 bytes

«/_⁹r»/+¥,þ/_Ɱ⁸²§½S>⁹µ;L;ZL$;1ṚK”P;

Try it online!

A full program that takes a list of lists of integers as the first argument, representing the foci, and the threshold as an integer as its second argument. Prints a PBM file to STDOUT.

Example

  • First argument: (0,0), (7, 15)
  • Second argument: 220

  • Output (converted to PNG): enter image description here

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

Python 3 + numpy + pylab, 168 163 156 bytes

import numpy,pylab
f,t=eval(input())
s=max(map(abs,sum(f,())))+t
k=numpy.r_[-s:s+1]
pylab.imsave('a.png',sum(((k-x)**2+(k[:,None]-y)**2)**.5for x,y in f)>t)

Outputs to a file called a.png, the y-axis increases downwards.

Sample outputs (click for full-res versions)

[(5, 8)], 100:

enter image description here

[(0, 0), (70, 150)], 220:

enter image description here

[(-90, -90), (-90, 90), (90, -90), (90, 90), (90, -90)], 670:

enter image description here

[(-390, 0), (-130, 120), (130, -120), (390, 0)], 1180:

enter image description here

Python 2, 152 bytes

f,t=input()
s=max(map(abs,sum(f,())))+t
w=s*2+1
k=range(-s,s+1)
print'P1',w,w
for y in k:
 for x in k:print+(sum(((a-x)**2+(b-y)**2)**.5for a,b in f)>t)

Try it online!

Outputs a PBM file to STDOUT. Sample output:

enter image description here

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Any reason not to output to a file called a to save 4 bytes? \$\endgroup\$ – Noodle9 Mar 4 at 15:48
  • 3
    \$\begingroup\$ @Noodle9 the imsave function needs the file extension to determine the desired file format. \$\endgroup\$ – ovs Mar 5 at 12:34
6
\$\begingroup\$

Haskell + Gloss, 165 bytes

import Graphics.Gloss
i=fromIntegral
h t=[i(-t)*3..i t*3]
d f t=display(InWindow""(t*3,t*3)(0,0))red$Line[(x,y)|x<-h t,y<-h t,i t>sum[sqrt$(x-u)^2+(y-v)^2|(u,v)<-f]]

Draws the shapes to the screen. It sometimes draws the images REALLY BIG, so I have cropped accordingly.

main = d [(5,8)] 100

enter image description here

main = d [(0,0), (70, 150)] 220

enter image description here

main = d [(-100, 0), (100, 0), (100, 0)] 480

enter image description here

main = d [(-250, -250), (-250, 250), (250, -250)] 1000

enter image description here

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES7), 212 196 bytes

with(Math)f=(c,l,...p)=>{m=l-max(...p)
c.height=c.width=s=min(...p)+l+m
for(i=0;i<s;i++)for(j=0;j<s;j++){for(d=k=0;1/p[k];)d+=hypot(p[k++]+m-i,p[k++]+m-j)
d>l||c.getContext`2d`.fillRect(i,j,1,1)}}

eval(`f(c,${e.value})`)
input{position:fixed}
<input id=e oninput=eval(`f(c,${e.value})`) value="100,-25,-25,-25,25,25,-25"><canvas id=c>

Outputs via first parameter which is a canvas element to draw on, second parameter is the threshold, then the remaining parameters are the loci. Edit: Saved 16 bytes thanks to @Arnauld, however the code is now dead slow and will trigger slow script warnings for large thresholds.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Running the snippet itself doesn't actually trigger the input event that calls the function, so the suggested input doesn't run unless you edit the value e.g. by appending a space. \$\endgroup\$ – Neil Mar 4 at 20:53
  • \$\begingroup\$ 196 bytes, I think (not really tested). \$\endgroup\$ – Arnauld Mar 4 at 23:53
  • \$\begingroup\$ @LuisMendo I've added an extra line to calculate the suggestion automatically. \$\endgroup\$ – Neil Mar 5 at 0:39
  • \$\begingroup\$ @Arnauld Boy that's slow :-( \$\endgroup\$ – Neil Mar 5 at 0:39
5
\$\begingroup\$

APL (Dyalog Unicode), 67 bytes (SBCS)

⎕IO←0

+{(⎕NEW'Bitmap'(⊂'Cbits'(⍵≥+⌿⍺∘.(.5*⍨-+.×-)(⊢,-)⍳2×⍵ ⍵))).MakePNG}⊢

NB

  • This image is very low contrast (made from a boolean matrix) - the output can be white interior shape on black background by multiplying the boolean matrix:

    +{(⎕NEW'Bitmap'(⊂'Cbits'(16777215×~⍵≥+⌿⍺∘.(.5*⍨-+.×-)(⊢,-)⍳2×⍵ ⍵))).MakePNG}⊢

  • Images are transposed compared to many other solutions, but you can flip the indices of each focus

  • Only works on Dyalog for Windows

Explanation

This function is a 3-train (fork), the arguments to the inner function are the results of the outer functions:

+

+ (plus): Translate the image by adding distance to the foci (please comment if this is a misinterpretation of the challenge)

(right): given two arguments (left and right), return the right argument

APL is parsed (glossing over some binding rules) as Brackets, long Right scope, short Left scope. We break it down as follows:

⍳2×⍵ ⍵

Indices from 0 to 2×⍵ in 2 dimensions (our integer pixels)

(⊢,-)⍳2×⍵

(⊢,-) (Same catenate negate) to cover positive and negative coordinates

(.5*⍨-+.×-)

Euclidean distance from focus to pixel...

⍺∘.(.5*⍨-+.×-)

... applied between each focus and every pixel

+⌿⍺∘.(.5*⍨-+.×-)

Sum the distances between all foci and each pixel (n-ellipse)

⍵≥+⌿⍺∘.(.5*⍨-+.×-)

Boolean matrix where 1 indicates interior (active) pixels (i.e. sum of distances between foci and pixel is less than t)

(⎕NEW'Bitmap'(⊂'Cbits'(*boolean matrix*))).MakePNG

Output signed integer PNG. This can be written to file using

∇  WritePNG png;tn
   tn←'img.png'⎕NCREATE 0
   png ⎕NAPPEND tn 83
   ⎕NUNTIE tn
∇

Output Images

First is to demonstrate, the written PNG has very low contrast

f ← +{(⎕NEW'Bitmap'(⊂'Cbits'(⍵≥+⌿⍺∘.(.5*⍨-+.×-)(⊢,-)⍳2×⍵ ⍵))).MakePNG}⊢
WritePNG 5 8 f 100

enter image description here Below I'm using the black and white version.

WritePNG (0 0)(70 150) f 220

enter image description here

WritePNG (¯100 0)(100 0)(100 0) f 480

enter image description here

Very resource hungry algorithm so I did a low res version of this

WritePNG (20 60)(32 ¯6)(¯35 22)(¯41 13)(4 ¯14) f 210

enter image description here

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you perhaps include a couple of screenshots of your results? \$\endgroup\$ – RGS Mar 4 at 23:20
4
\$\begingroup\$

Red, 300 bytes

Red[]f: func[p t][a: :absolute 
m: last sort collect[foreach n p[keep a n/x keep a n/y]]s: t + m * 2
u: as-pair s s i: make image! reduce[u]k: 0 repeat y s[repeat x s[d: 0
foreach a p[d: d +(sqrt x - t - m - a/x ** 2 +(y - t - m - a/y ** 2))]k: k + 1
if d <= t[i/:k: 0.0.255]]]save/as %1.jpg i 'jpeg]

f [5x8] 100

enter image description here

f [0x0 70x150] 220

enter image description here

f [-100x0 100x0 100x0] 480

enter image description here

f [200x600 320x-60 -350x220 -410x130 40x-140] 2100

enter image description here

f [-390x0 -130x120 130x-120 390x0] 1180

enter image description here

Note: I scaled all the images to 256x256 pixels and croped the last two images so that they don't take too much space - they had a large "frame"

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Applescript + grapher, 601

This will almost certainly be the longest answer, but I thought this would be a fun challenge in Applescript.

on f(l, t)
set y to 0
tell application "Grapher" to activate
tell application "System Events"
keystroke "n" using command down
keystroke return
keystroke "a" using command down
repeat with d in l
keystroke "sqrt((x-"&d's item 1&")^2)+(y-"&d's item 2&")^2))+"
set y to y+d's item 2
end repeat
click application process "Grapher"'s menu bar 1's menu bar item 8's menu 1's menu item 3
set c to l's items count
keystroke "             "&(y-t)/c as text&" "&(y+t)/c as text&"     "
keystroke "c" using command down
keystroke "             "
keystroke "v" using command down
keystroke return&"0<"&t as text&return
end tell
end f

This is an applescript function. It may be called as follows for the testcases:

my f({{5, 8}}, 100)
my f({{0, 0}, {70, 150}}, 220)
my f({{-100, 0}, {100, 0}, {100, 0}}, 480)
my f({{-90, -90}, {-90, 90}, {90, -90}, {90, 90}, {90, -90}}, 670)
my f({{200, 600}, {320, -60}, {-350, 220}, {-410, 130}, {40, -140}}, 2100)
my f({{-250, -250}, {-250, 250}, {250, -250}}, 1000)
my f({{-250, -250}, {-250, 250}, {250, -250}}, 1200)
my f({{-390, 0}, {-130, 120}, {130, -120}, {390, 0}}, 1180)

Output looks like this, e.g. for the 5th testcase:

enter image description here

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

MATLAB + DIPimage toolbox, 133 121 117 111 bytes

(shaved off 12 16 bytes thanks to flawr and LuisMendo)

function s(c,r),c=c-min(c)+r;a=zeros(max(c)+r);l='corner';for x=c',a=a+hypot(xx(a,l)-x(1),yy(a,l)-x(2));end,a>r

Use:

c = [-390, 0; -130, 120; 130, -120; 390, 0];
r = 1180;
s(c,r)

In a more readable fashion:

function s(c,r)
c=c-min(c)+r;           % offset coordinates so all points within shape have non-negative coordinates
a=zeros(max(c)+r);      % compute image size and create empty output image
l='corner';             % long argument used twice below
for x=c'
   a=a+hypot(xx(a,l)-x(1),yy(a,l)-x(2)); % add distance to each point
end
a>r                     % threshold and display (leaving semi-colon off causes graphical display of image)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Bash + Standard utilities (but no graphics library), 194 190 186 bytes

t=$1
shift
L=H=$1
for n do
L=$[n<L?n:L]
H=$[n>H?n:H]
done
echo P2 $[L-=t,H+=t+1,H-L] $[H-L] 1
for((x=y=L;y<H;++x>=H?x=L,y++:0)){ bc -l<<<`printf "sqrt(($x- %d)^2+($y- %d)^2)+" $@`0\>$t;}

Try it online! (If you do, though, try a tiny example: even the circle test times out on TIO.)


Input is passed in the arguments: first \$t\$, then \$x_1\$, \$y_1\$, \$x_2\$, \$y_2\$, ..., \$x_n\$, \$y_n\$.

Output is a PGM image on stdout. Save it in a file named something.pgm and view it in your favorite graphics program.

The x-axis goes from left to right, and the y-axis goes from top to bottom. White is the background, and black is the n-ellipse being drawn.

For example, to view the first example (the circle), you could execute:

lips 100 5 8 > lips-circle.pgm

(where the program is named lips). Then open the imagelips-circle.pgm. Here's the result: enter image description here

Here's the second test, the output of lips 220 0 0 70 150 > lips-ellipse.pgm:enter image description here

Next is lips 480 -100 0 100 0 100 0 > lips-repeatedpoint.pgm:

enter image description here

Here is lips 670 -90 -90 -90 90 90 -90 90 90 90 -90 > lips-repeated-arbitaryOrder.pgm:

enter image description here

The next test is lips 2100 200 600 320 -60 -350 220 -410 130 40 -140 > lips-shape1.pgm:

enter image description here


This script is very slow (but runnable). I will post more sample images as my computer gets around to finishing them :) ....

Well, after waiting overnight again, the other tests are finally done!


Here's the guitar pick: lips 1000 -250 -250 -250 250 250 -250 > lips-guitarpick.pgm enter image description here

The next test is lips 1200 -250 -250 -250 250 250 -250 > lips-shape2.pgm: enter image description here

And finally the pair of lips! lips 1180 -390 0 -130 120 130 -120 390 0 > lips-pairOfLips.pgm: enter image description here

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Shadertoy (GLSL, non-competing) 125 bytes + input data

vec2 a[]=vec2[](vec2(-390, 0),vec2(-130,120),vec2(130,-120),vec2(390,0));
float d=1180.;

void mainImage(out vec4 o,vec2 c){c-=iResolution.xy/2.;o-=o;for(int i=0;i<a.length();o.a+=length(c-a[i++]));o.b=step(o.a,d);}

Shadertoy link for the last testcase.

As the input array's size is known, this could be further reduced by replacing the a.length() by n.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why is this non-competing? \$\endgroup\$ – pppery Mar 29 at 21:26
  • \$\begingroup\$ Also, why don't you do the further reduction you suggest in your answer? \$\endgroup\$ – pppery Mar 29 at 21:27
  • \$\begingroup\$ it doesn't receive input, I could change it to a uniform value but that's still not like in other languages. \$\endgroup\$ – Gábor Fekete Mar 29 at 21:57
2
\$\begingroup\$

Desmos, 50 49 bytes

\sum_{n=1}^c \sqrt{(x-a[n].x)^2+(y-a[n].y)^2}<=t

-1 byte from finding a new quirk in Desmos' syntax while working on another problem.

View it online

It just kinda... works. Input n in the variable c, t in the variable t, and the points as an array a of coordinates.

Lips example:

"lips" n-ellipse in Desmos

Guitar pick example:

"guitar pick" n-ellipse in Desmos

Note: If you try to copy the equation from the editor, you'll find a bunch of \lefts and \rights and such. These have been golfed out of this answer, as you can paste this text in and it works. The editor automatically re-adds those when parsing input from the clipboard, but it accepts the code without them.

Note two: I'm not 100% sure if this counts due to the infill being transparent, but hopefully it's ok. If not, there's a couple options:

  1. Stack a bunch of whole bunch of these equations on top of each other. I tried this and it turns out that a quirk of their rendering engine is that the fill color can never drop below #010101, while the outline is at #000000. Additionally, the area is a little larger than would be ideal because the outline looks like part of the fill.

  2. Rewrite the n-ellipse equation in parametric form. I don't know if this is possible or not, but if it is, Desmos's enhanced visual options for parametric equations allows us to remove the outline.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Right tool for the job :-) Fill being half-transparent is ok \$\endgroup\$ – Luis Mendo Aug 23 at 1:01

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.